注：这里集合都是JDK1.8的
Arraylist:
ArraayList的结构和源码相对简单，是一个由数组组成的类，其查询快，增删慢,数据可重复，能保证数据的顺序性，线程不安全，不多BB直接看源码
几种构造方法
有参构造方法参数为0时构造一个空集合，参数不为0则构造一个 initialCapacity大小的集合，默认容量大小是10
public ArrayList(int initialCapacity) {//有参构造方法
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];//参数不为0则构造一个 initialCapacity大小的集合
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;//参数为0时构造一个空集合
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}//默认构造成空集合
```
add方法，当数组容量超过数组的容量时，一般情况下是进行扩容至原来的1.5倍
//调用了ensureCapacityInternal方法
public boolean add(E e) {
ensureCapacityInternal(size +1);
elementData[size++] = e;//向数组的已有数据的末尾添加一个元素
return true;
}
点到ensureCapacityInternal方法，发现里面调用了ensureExplicitCapacity，
private void ensureCapacityInternal(int minCapacity) {
if (elementData ==DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//如果数组为空
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);//比较并取出最大值
}
ensureExplicitCapacity(minCapacity);
}
里面调用的grow是ArrayList最核心的方法之一，如果当前容量大小大于ArrayList数组的容量时将进行扩容，调用grow方法
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity -elementData.length >0)
grow(minCapacity);
}
ArraList的扩容机制，grow方法现实，基本我们可以认为是当添加元素后数组的容量大于当前数组的容量时就需要进行扩容操作，基本上都是扩大到原来容量的1.5倍
private void grow(int minCapacity) {
int oldCapacity =elementData.length;
int newCapacity = oldCapacity + (oldCapacity >>1);//原来数组的容量扩大到1.5倍为newCapacity
//如果newCapacity 小于原来的数组容量+1为minCapacity 则扩容至minCapacity
if (newCapacity - minCapacity <0)
newCapacity = minCapacity;
if (newCapacity -MAX_ARRAY_SIZE >0)//如果newCapacity 如果小于（Integer.MAX_VALUE -8）=2147483639则扩容至2147483639
newCapacity =hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);扩容至newCapacity
}
Arraylist的操作其实是对数组的操作，包括取元素，删元素基本是和数组一个特点，但是扩容操作，在添加的元素没有超过其容量时，增加元素不影响其性能，如果超过了其容量，则会对集合的数组进行扩容，性能因此受到影响，查询性能和数组一样非常高效
HashSet：
底层是基于HashMap的，由于HashSet存储数据的方法调用的是HashMap的put方法，其存储的数据是存到HashMap的Key值中,key通过哈希函数可以算出HashMap的数组下标，加上value值是全部都是固定的object，所以相同key在HashMap对应的元素只有一个，所以hashSet的值是不重复的，hashSet无序性也是因为key通过哈希函数计算出HashMap的数组下标，由于是通过哈希计算，所以hashSet无法决定加入元素时的顺序性，但是却能保证这些元素是按照内部的顺序存储的，所以hashSet是一个无序的有序集合。。。
构造方法：
我们惊奇的发现HashSet中操作的其实是HashMap，我们知道HashMap是一个基于数组+链表+红黑树的集合工具，是一个线程不安全的集合
public HashSet() {
map =new HashMap<>();
}
add方法，我们可以看到其实就调用了HashMap的put方法，HashMap的put方法当传入的Key值相等时，就会将相同的旧值覆盖，这就达到了HashSet数据不能重复的效果（如果没有看HashMap的同学可以先去看HashMap，一举两得），这里我就不继续往下分析了，因为昨天我已经分析完了HashMap，懂了HashMap就自然懂了HashSet的源码了
LinkedList：
LinkedList是一个双向链表结构，其源码和结构都相对简单，特点就是查询慢，增删快，线程不安全,LinkList查找元素使用了二分查找法，但是只是用了一次，不想平衡二叉查找树，到达每个节点都会使用二分查找，所以其查找效率不高，但是增删只有改变节点的前指向和后指向就可以了，增删效率高
我们看看的一个重要的内部类，这个内部类就是LinkedList存储数据和双向连接的单元
private static class Node {
E item;//存储元素的成员变量
Node next;//存储下一个元素的成员变量
Node prev;//存储上一个元素的成员变量
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
add方法,方法调用了linkedLast对节点进行追加操作，如果追加的是首节点，则next prev的指向都为空，如果不是第一个节点，将next 节点指向插入节点，prev指向链表中最后的节点
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node l =last;//记录链表中最后的节点
final Node newNode =new Node<>(l, e, null);//将上一个节点 l 赋值给prev，表明追加节点 prev 指向链表中最后的节点
last = newNode; //将追加节点记录为链表最后节点
if (l ==null) //链表为空则将追加节点设置为首节点
first = newNode;
else //否则将追加节点设置为下一节点
l.next = newNode;
size++;
modCount++;
}
插入节点add(int index, E element) ，如果插入的索引值刚好等于链表的长度，则需要调用linkLast往链表末尾追加元素，否则调用linkBefore
public void add(int index, E element) {
checkPositionIndex(index);
if (index ==size)
linkLast(element);
else
linkBefore(element, node(index));
}
void linkBefore(E e, Node succ) {
final Node pred = succ.prev;//获得链表的index索引下的节点succ的前一个节点pred
final Node newNode =new Node<>(pred, e, succ);//将前一个节点pred 赋值个新的节点 newNode的前节点，succ赋值为后节点，将数据e存储进新创建的节点中
succ.prev = newNode;/ /succ 节点的前节点设置为新的节点 newNode
if (pred ==null)//如果pred 节点为空，证明succ是首节点
first = newNode;//将首节点设置为新的节点newNode
else//否则就将pred的下一个节点设置为新的节点 newNode
pred.next = newNode;
size++;
modCount++;
}
linkedList的结构
get方法
这里我们方法get方法调用的是node方法，进入node方法，我们可以看到这个node方法的搜索使用的是二分查找，先将index与长度size的一半比较，如果index<size/2，就只从位置0往后遍历到位置index处，而如果index>size/2，就只从位置size往前遍历到位置index处。这样可以减少一部分不必要的遍历
Node<E> node(int index) {
if (index < (size >>1)) {//先将index与长度size的一半比较，如果index<size/2,进入if逻辑中
Node x =first;//链表的第一个节点赋值给x
for (int i =0; i < index; i++)//x往下一个一个的遍历
x = x.next;
return x;
}else { //而如果index>size/2
Node x =last;//链表的最后一个节点赋值给x
for (int i =size -1; i > index; i--) //x往下一个一个的遍历
x = x.prev;
return x;
}
}
HashTable:
也是基于哈希的链地址法，由于同步锁存在，所以HashTable线程安全，性能较差、由于是通过哈希值计算是索引下标所在位置的数组去存储数据，不能保证数据的先后存储顺序
我们先看看HashTable的构造方法：
我们看到HashTable的无参构造函数是调用了HashTable其中的一个有参构造函数，其加载因子是0.75f，数组的容量大小是11，与HashMap的数组长度是16稍微不同
public Hashtable() {
this(11, 0.75f);//调用了无参构造函数
}
public Hashtable(int initialCapacity, float loadFactor) {
if (initialCapacity <0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
if (loadFactor <=0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor);
if (initialCapacity==0)
initialCapacity =1;
this.loadFactor = loadFactor;//加载因子
table =new Entry[initialCapacity];//数组默认最大长度
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE +1);
}
put方法
public synchronized V put(K key, V value) {//使用了synchronized 同步锁
if (value == null) {
throw new NullPointerException();
}
Entry tab[] = table;
int hash = hash(key);//根据键生成hash值
int index = (hash & 0x7FFFFFFF) % tab.length;//通过hash值找到数组的存储位置
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {//遍历数组的链表
if ((e.hash == hash) && e.key.equals(key)) {//若Key相同，则新值覆盖旧值
V old = e.value;
e.value = value;
return old;
}
}
modCount++;
if (count >= threshold) {//当前容量超过阈值。需要扩容
rehash();//重新构建桶数组，并对数组中所有键值对重哈希，这个过程是很耗时的
tab = table;
hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;//这里是取到数组的下标的运算
}
Entry<K,V> e = tab[index];
//将新结点插到链表首部
tab[index] = new Entry<>(hash, key, value, e);//生成一个新结点
count++;
return null;
}
public synchronized V put(K key, V value) {//使用了 synchronized 同步锁
if (value ==null) {
throw new NullPointerException();
}
Entry tab[] =table;
int hash = key.hashCode();//根据键生成hash值
int index = (hash &0x7FFFFFFF) % tab.length;//通过hash值计算出数组的存储的索引
@SuppressWarnings("unchecked")
Entry entry = (Entry)tab[index];//找到数组索引值所在位置的链表
for(; entry !=null ; entry = entry.next) {//遍历链表
if ((entry.hash == hash) && entry.key.equals(key)) {//若Key相同，则新值覆盖旧值
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);//扩容方法
return null;
}
点开addEntry方法分析代码，当集合内的数据大于阈值
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry tab[] =table;
if (count >=threshold) {//count 大于threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1)
rehash();//扩容并重新构建桶数组，并对数组中所有键值对重哈希，这个过程是很耗时的
tab =table;
hash = key.hashCode();
index = (hash &0x7FFFFFFF) % tab.length;
}
@SuppressWarnings("unchecked")
Entry e = (Entry) tab[index];
tab[index] =new Entry<>(hash, key, value, e);
count++;
}
rehash方法是HashTable主要的扩容并且重新哈希的方法
protected void rehash() {
int oldCapacity =table.length;
Entry[] oldMap =table;
int newCapacity = (oldCapacity <<1) +1;//扩容我原来两倍加1
if (newCapacity -MAX_ARRAY_SIZE >0) {
if (oldCapacity ==MAX_ARRAY_SIZE)
return;
newCapacity =MAX_ARRAY_SIZE;
}
Entry[] newMap =new Entry[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity *loadFactor, MAX_ARRAY_SIZE +1);//计算下一次rehash的阈值
table = newMap;
//把旧哈希表的键值对重新哈希到新哈希表中去
for (int i = oldCapacity; i-- >0 ;) {
for (Entry old = (Entry)oldMap[i]; old !=null ; ) {
Entry e = old;
old = old.next;
int index = (e.hash &0x7FFFFFFF) % newCapacity;
e.next = (Entry)newMap[index];
newMap[index] = e;
}
}
}
网友评论