集合框架
Last updated
Was this helpful?
Last updated
Was this helpful?
什么是集合？
集合是Java提供的数据结构和算法的api。不需要像C一样另造轮子，就能使用数据结构和算法了。
Collection接口
List
ArrayList:
package jihe.list;
/**
* 手写ArrayList
* 底层维护了数组，增删效率低，查询效率高
* @author xiasj
*
*/
public class TestArrayList<E> {
//List维护此数组
private Object[] elementData;
private int size;
//如果New一个新的ArrayList但是没指定默认大小，则设为10
private static final int DEFALT_CAPACITY=10;
/**
* 构造
*/
public TestArrayList() {
elementData=new Object[DEFALT_CAPACITY];
}
public TestArrayList(int capacity) {
if(capacity<0) {
throw new RuntimeException("容量不合法"+capacity);
}else if(capacity==0){
elementData=new Object[DEFALT_CAPACITY];
}
elementData=new Object[capacity];
}
/**
* get
*/
public E get(int index) {
return (E)elementData[index];
}
/**
* set
*/
public void set(E element,int index) {
//对索引index判断
if(size<0 || index>size-1) {
throw new RuntimeException("索引不合法"+index);
}
elementData[index]=element;
}
/**
* 扩容
* @param element
*/
public void add(E element) {
//什么时候扩容
if(size==elementData.length) {
//扩容
Object[] newArray=new Object[elementData.length+(elementData.length>>1)];//x>>n=x/(2^n)
System.arraycopy(elementData, 0, newArray, 0, elementData.length);
elementData=newArray;
}
elementData[size++]=element;
}
/**
* remove
* 会完成自己给自己拷贝，把index后面的元素都拷贝一遍，所以效率低
*/
public void remove(E element) {
//将element和所有元素比较，第一个为true的，返回
for (int i = 0; i < size; i++) {
if(element.equals(get(i))) {
//将该元素从此处移除
remove(i);
}
}
}
public void remove(int index) {
//A B C D 删除1位置的B
//A C D 会完成自己给自己拷贝，把index后面的元素都拷贝一遍，所以效率低
if(elementData.length-index-1>0) {
System.arraycopy(elementData, index+1, elementData, index, elementData.length-index-1);
}
elementData[--size]=null;
}
@Override
public String toString() {
StringBuilder sb=new StringBuilder();
sb.append("[");
for(int i=0;i<size;i++) {
sb.append(elementData[i]+",");
}
sb.setCharAt(sb.length()-1,']');
return sb.toString();
}
public static void main(String[] args) {
TestArrayList<String> tl=new TestArrayList<String>();
for (int i = 0; i <100; i++) {
tl.add("text"+i);
}
tl.set("xxx", 1);
System.out.println(tl);
tl.remove(1);
System.out.println(tl);
}
}LinkedList:
```java package jihe.list;
import javax.management.RuntimeErrorException;
/**
为双向链表：查询效率低，增删效率高线程不安全
每个节点有
class Node {
Node previous; //前一个节点
Object element; //本节点保存的数据
Node next; //后一个节点}
删除ax就把ax-1的next指向ax+1，ax+1的previous指向ax-1
*
@author xiasj / public class TestLinkedList {
private Node first; private Node last;
private int size;
public TestLinkedList() {
}
/**
* get
* @param index
* @return
*/
public E get(int index) {
checkIndex(index);
return getNode(index)!=null?(E)getNode(index).element:null;
}
/**
*
* @param index
*/
private void checkIndex(int index) {
if(index<0 || index>size-1) {
throw new RuntimeException("index不合法");
}
}
/**
* getNode得到制定节点
*/
public Node getNode(int index) {
checkIndex(index);
Node temp=first;
//遍历节点直到index位置的节点然后返回，二分法
if(index<size>>1) {
for (int i = 0; i < index; i++) {
temp=temp.next;
}
}else{
temp=last;
for (int i = size-1; i > index; i--) {
temp=temp.previous;
}
}
return temp;
}
/**
* add
*
*/
public void add(int index,E element) {
checkIndex(index);
Node newNode =new Node(element);
Node temp= getNode(index);
if(temp!=null && index!=0 && index!=size-1) {
Node pre=temp.previous;
Node nex=temp.next;
pre.next=newNode;
newNode.previous=pre;
newNode.next=temp;
temp.previous=newNode;
}
if(index==0){
newNode.next=temp;
first=newNode;
temp.previous=newNode;
System.out.println(temp.previous);
}else if (index==size-1) {
newNode.previous=temp;
last=newNode;
temp.next=newNode;
}
size++;
}
// ["a","b"]加入["c"]或[]加入["c"]
public void add(E element) {
Node node =new Node(element);
//如果没有节点，那么first和last都是我node
if(first==null) {
first =node;
last=node;
}else {
//如果新加节点内容为node("c")，那么这个新节点的previous=最后一个last("b")
node.previous=last;
//新节点的下一个为null
node.next=null;
//原来的last指向新节点node("c")，新节点再换成last节点
last.next=node;
last=node;
}
size++;
}
/**
* remove
*/
public void remove(int index) {
checkIndex(index);
Node temp=getNode(index);
if(temp!=null) {
Node pre=temp.previous;
Node nex=temp.next;
if(pre!=null) {
pre.next=nex;
}
if(nex!=null) {
nex.previous=pre;
}
if(index==0){
first=nex;
}else if (index==size-1) {
last=pre;
}
size--;
}
}
/**
* 重写toString
* @param args
* @return
*/
public String toString() {
StringBuilder sb=new StringBuilder("[");
Node temp=first;
while(temp!=null) {
sb.append(temp.element+",");
temp=temp.next;
}
sb.setCharAt(sb.length()-1, ']');
return sb.toString();
}
public static void main(String[] args) {
TestLinkedList<String> ll=new TestLinkedList<String>();
ll.add("a");
ll.add("b");
ll.add("c");
ll.add("d");
ll.add("e");
System.out.println(ll.toString()+" "+ll.size);
ll.remove(3);
System.out.println(ll.toString()+" "+ll.size);
ll.remove(3);
System.out.println(ll.toString()+" "+ll.size);
ll.add(0,"a1");
ll.add(3,"a1");
System.out.println(ll.toString()+" "+ll.size);
}
}
```Vector:
Vector底层是用数组实现的List，相关的方法都加了同步检查，因此“线程安全,效率低”。
Map
HashMap: 线程不安全，效率高。允许key或value为null；
JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）
.JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间。
HashTable: 线程安全，效率低。不允许key或value为null。
HashMap源码分析： 1. 数据存储可以由数组和链表进行存储，它们有各自的特点：
数组：占用的是连续的空间，随机访问快，但是增加删除效率低；
链表：占用的是不连续的空间，访问慢，增加和删除快 那么，结合了数组和链表的哈希表就非常重要了,好接下来分析源码： 2. 源码：(Jdk1.7) 数组+链表， 1.HashMap通过key的hashcode通过“扰动函数”处理后得到hash值， 2.然后通过hash&(n-1)得到存放到数组的位置， 3.生成Entry对象，一个Entry对象包括 hash,key,value,指向下一个Entry对象的引用； 4.如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同， 如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。
扰动函数：就是hash方法，目的是： 把hashcode这个整数，转化到[0,length-1]的范围内，但是要求尽量均匀的分布在其中，以减少hash冲突。 jdk1.8在这进行了修改： 由
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);变成了
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);扰动了1次提升了效率。
加载因子：loadFactor加载因子是控制数组存放数据的疏密程度，loadFactor越趋近于1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，load Factor越小，也就是趋近于0， loadFactor太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor的默认值为0.75f是官方给出的一个比较好的临界值。
HashMap的部分源码：
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
// 序列号
private static final long serialVersionUID = 362498820763181265L;
// 默认的初始容量是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的填充因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当桶(bucket)上的结点数大于这个值时会转成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 当桶(bucket)上的结点数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中结构转化为红黑树对应的table的最小大小
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组，总是2的幂次倍
transient Node<k,v>[] table;
...
}Node节点：
// 继承自 Map.Entry<K,V>
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;// 哈希值，存放元素到hashmap中时用来与其他元素hash值比较
final K key;//键
V value;//值
// 指向下一个节点
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
// 重写hashCode()方法
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// 重写 equals() 方法
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}put方法：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果table==0/null，则进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//确定位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 比较有没有值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 是否为树节点
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 链表
else {
// 找到链表最后
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 长度大8 转为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}ConcurrentHashMap
