Java数据结构很多，常用的并不多，本篇主要就其中常接触到的原理与细节做一点总结(不含并发容器)

1.数组

1.1.ArrayList 1.8

数组列表，底层实现主要是object数组，基本特点是查询效率高，增删效率低，内存连续，不是线程安全的数据结构。

ArrayList刚开始不会初始化数组大小，初始大小为0，开始add时才会默认分配10的初始大小，即使我们在初始化时赋值给它，初始大小依然为0，因为它的size()方法是用size变量单独表示的，只代表列表中拥有的元素个数，不是真正的数组大小。

扩容：
扩容的大小为原先大小的1.5倍(扩容因子 = 1.5)，位运算右移一位加上原数组的大小，扩容完成后将数组原有元素拷贝至新数组中，再加上新元素。加载因子为1，意味着当元素填满数组时才会进行扩容。

增删改查：

• 增：中间增加需要后移后面的元素，可能还需要扩容

• 删：需要前移删除元素后的元素

• 改：找到索引位置直接修改

• 查：找到索引位置直接返回

注：增删正常为o(n)复杂度，但是对最后的元素操作则为O(1)复杂度，改查均为o(1)复杂度

1.2.LinkedList

链表实现的列表，与前者相比主要是增删均为O(1)，改查O(n)，每次添加元素都是在列表后新加一个新的节点，且内存不是连续的。

1.3.Vector

同步容器，线程安全的数据结构，所有的公有方法全部都有synchronized修饰，可以在多线程场景中 单独 使用它的方法，遇到复合操作(非原子操作)就会翻车，需要在外部主动加锁解决该问题。

此外，它的加锁粒度很大，每次都会锁住整个数据结构，且不区分读写，即使get与add两个方法也要顺序执行，大大降低了容器的并发能力。

2.Map

2.1.HashMap(1.7/1.8)

线程不安全的K-V数据结构，主要由数组和链表实现的，对于冲突的解决采用拉链法，初始容量为16，K与V均可以为null。

1.7版本:(仅包含部分与1.8相比较的点)

主要由Entry来实现的，没有链表转红黑树的优化操作

扩容：
插入由头插法实现，并发情况下会产生死循环或数据丢失的问题，两个线程同时检测到容量不足，对HashMap进行扩容操作，A线程先完成了扩容，此时B线程开始扩容，头插法会导致B线程将A已经分配好的节点再次进行遍历与转移，此时会形成一个环形结构。节点转移的位置与1.8相同，都是将原先位置的半数元素转移到当前的位置*2的位置，扩容大小也相同都为当前数组大小的2倍。

1.8版本:

主要由Node来实现的，当某一数组节点下的链表长度到达8时会将链表进行树化为红黑树便于查找，减少到6时又会退化回链表。

扩容：
扩容因子为2，每次扩容都为当前数组大小的2倍，会将数组元素的一半链表节点以尾插法的方式转移到原先2倍位置的数组元素下。不支持缩容。

此外扩容2倍的原因主要是因为整数与2的整数幂次减一做&运算可以当做取模来看，加速了hash函数的运算，也会减少很多冲突，尽量实现均匀分布，在初始化时也会遵循这一特点，开始如果设置的大小不是2的整数幂次，则会自动将初始大小设置为大于用户设置的大小的最小2的整数次幂。

加载因子：
0.75，即每次到达现在大小的四分之三即可开始扩容。取值0.75是一个时间与空间上的折中方案，过低的话虽然冲突会变少，但是会导致频繁扩容，且空间利用率很低的情况，过高的话虽然提高了空间利用率，也降低了扩容频率，但是会导致查询冲突概率很高。

哈希计算：
取模，位运算

2.2.HashTable

线程安全的K-V结构，由Dictionary实现的。利用synchronized对数据结构整体进行加锁，并发效率低。

与HashMap相比，它的K与V都不可以为null，HashTable没有对null值进行特殊处理，加入null时会报空。

K与V不可以为null的原因是：
HashTable的实现一部分采用了Fail-safe机制(Enumerator是，Iterator不是)，这种机制读取出的数据不一定是最新的数据，如果使用null值会使得其无法判断对应的key是不存在还是为空。

此外HashTable扩容为当前容量翻倍+1，初始容量为11，负载因子默认都是0.75

2.3.TreeMap

利用红黑树实现的K-V结构，可以对节点进行排序，线程不安全。

3.其他

3.1.HashSet

由HashMap实现

3.2.Queue、Deque、Stack

Queue：队列，尾进头出

Deque：双向队列，头尾都可以进出

Stack：先进后出，由Vector实现，大量操作需要加锁，效率较低，通常使用LinkedList实现的Deque代替

3.3.PriorityQueue

带有优先级的队列，由堆实现，可以自定义优先级。

注：一时想不起那么多的要点，后续可能还会更新