Java中的各种集合的实现原理
引言：java中的所有的集合是我们开发中常常会使用到的工具，今天自己翻阅一些资料查看了开发中常常使用的集合一些底层的知识，下面是自己学习的一些笔记：
1：ArrayList:
a:ArrayList熟称动态数组；是一个不允许被序列化的对象数组
private transient Object[] elementData;
b:存储数据时是按照你插入的顺序进行存储的；用于存储一系列的对象引用(references)
c:由于实现了List接口，底层是通过数组实现的；
d:实现了RandomAccess接口支持随机访问访问该集合中的元素；
但是向集合中插入元素和删除集合中的元素耗时比较长，因为需要按照顺查找到目标元素进行相关操作；
e:初始容量：10
private static final int DEFAULT_CAPACITY = 10;
f:关于扩容：
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//关键看这一步；通过位运算将其容量扩大了二倍；
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
2：LinkedList:
a：基于链表实现，不支持随机访问，随机查询某个元素不如ArrayList；但是向集合中插入和删除元素缺比ArrayList性能好；不需要移动元素；
b:存储数据是通过静态内部类Node；
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
c:链表不存在容量问题；
3:HashMap:
作为程序员使用最多的一种键值式的存储集合；它的底层是通过数组+链表+红黑树（JDK8优化之后）；它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
ashMap 的实例有两个参数影响其性能：初始容量 和加载因子
a:存储数据的格式:通过一个静态内部类Entry存储数据；
hashMap的存储形式.jpg
当链表长度大于8时会自动转换成红黑书
static class Entry<K,V> implements Map.Entry<K,V>{
}
b:初始容量：16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
```
c:加载因子：默认为0.75；
主要在扩容时起作用；
一般也是扩展为2倍
```
void resize(int newCapacity) {
Entry[] oldTable = table;
//获取扩容之前的容量
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
//将原来数组的元素拷贝到新的元素中；
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
```
e关于hash函数：
hashMap在存储数据时会先根据它的key值调用一次hash函数；将得到的值作为真实的存储数据的键；当然不排除两个不同的key值产生相同的键值情况；我们称之为hash冲突；关于hash冲突详见另一篇文章；这里解决hash冲突采用的拉链法；
```
int hash = hash(key);
```
e:插入元素：
①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；
④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
f： HashMap最多只允许一条记录的键为null，允许多条记录的值为null。
**4:hashSet**
hashSet也是一个键值对集合;该容器中只能存储不重复的对象；它是基于 HashMap 实现的，HashSet 底层采用 HashMap 来保存所有元素，
HashSet 的实现/：封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。
```
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
//插入元素
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
```
参考文献：
链接：https://zhuanlan.zhihu.com/p/21673805
http://alex09.iteye.com/blog/539549
