集合 - 常用集合 - 《Java 复习》

ArrayList

概述：ArrayList是实现List接口的动态数组，所谓动态就是它的大小是可变的，底层是一个object数组，并且由trasient修饰
数组序列化：ArrayList底层数组不会参与序列化，而是使用另外的序列化方式（使用writeobject方法进行序列化），就是只复制数组中有值的位置，其他未赋值的位置不进行序列化，可以节省空间
初始容量和扩容方式
- 初始容量是10（在第一次add的时候创建，默认是空数组）
- 每次扩容1.5倍（不会造成很大的内存消耗），通过grow（）方法实现
Fail-Fast 机制
- Fail-Fast 机制通过modCount属性实现，modCount 顾名思义就是修改次数，对ArrayList 内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的 expectedModCount。在迭代过程中，判断 modCount 跟 expectedModCount 是否相等，如果不相等就表示已经有其他线程修改了 ArrayList
数组Copy优化
- 底层用了本地方法System.arraycopy对数组copy进行了优化
线程安全
- ArrayList不是线程安全的集合
- 实现线程安全的方式
  - 使用Vector（ArrayList所有方法加synchronized，太重）。
  - 使用Collections.synchronizedList()转换成线程安全类。
  - 使用java.concurrent.CopyOnWriteArrayList（推荐）。
- CopyOnWriteArrayList原理

通过写时复制来实现读写分离。比如其add()方法，就是先复制一个新数组，长度为原数组长度+1，然后将新数组最后一个元素设为添加的元素

LinkedList

概述
- LinkedList是List接口链表的实现，使得LinkedList在插入和删除时更优于ArrayList，而随机访问则比ArrayList逊色些
- 实现 Deque 接口，为 add、poll 提供先进先出队列操作，以及其他堆栈和双端队列操作；
实质
- LinkedList底层的数据结构是基于双向循环链表的，且头结点中不存放数据

HashMap

概述
- 基于哈希表的Map接口实现，是以key-value存储形式存在，即主要用来存放键值对
- 线程不安全
- 它的key、value都可以为null，但key只能存在一个null值
- JDK1.8 之前 HashMap 由数组+链表组成的
- JDK1.8 以后当链表长度大于阈值（或者红黑树的边界值，默认为 8）并且当前数组的长度大于64时，此时此索引位置上的所有数据改为使用红黑树存储
扩容：超出临界值（Size>=threshold）时发生扩容，扩容为原来容量的2倍，并将原有的数据复制过来
- 如果创建HashMap对象时，输入的数组长度是10，不是2的幂，HashMap通过一通位移运算和或运算得到的肯定是2的幂次数，并且是离那个数最近的数字

int n = cap - 1; 这是为了防止，cap已经是2的幂
扩容后原来的节点移位问题
- 为了避免重新计算哈希：看原来的hash值新增的那个bit是1还是0就可以了，是0的话索引没变，是1的话索引变成“原索引+oldCap(原位置+旧容量)

临界值：threshold( 临界值) =capacity(容量) * loadFactor( 加载因子 )
将链表转换为红黑树的treeifyBin方法
- 根据哈希表中元素个数确定是扩容还是树形化
- 如果是树形化遍历桶中的元素，创建相同个数的树形节点，复制内容，建立起联系
- 然后让桶中的第一个元素指向新创建的树根节点，替换桶的链表内容为树形化内容
相关问题
- HashMap中hash函数是怎么实现的？
  - 对于key的hashCode做hash操作，无符号右移16位然后做异或运算。

当两个对象的hashCode相等时会怎么样？
- 会产生哈希碰撞，若key值内容相同则替换旧的value.不然连接到链表后面，链表长度超过阈值8就转换为红黑树存储。
初始化容量( 必须是二的n次幂 )，为什么必须是2的n次幂？
- 因为只有是2的n次幂，hash%length才等于hash&(length-1)
为什么Map桶中节点个数超过8才转为红黑树？
- 选择8因为符合泊松分布，超过8的时候，概率已经非常小了
当链表的值小于6则会从红黑树转回链表
- 当链表节点过少就不适宜维护红黑树了，所以转回链表提升效率

LinkedHashMap

概述：有序的HashMap，与HashMap相比，LinkedHashMap增加了两个属性用于保证迭代顺序
本质：HashMap + 双向链表
linkedhashmap在hashmap的数组加链表结构的基础上，将所有节点连成了一个双向链表
当主动传入的accessOrder参数为false时, 使用put方法时，新加入元素不会被加入双向链表，get方法使用时也不会把元素放到双向链表尾部
当主动传入的accessOrder参数为true时，使用put方法新加入的元素，如果遇到了哈希冲突，并且对key值相同的元素进行了替换，就会被放在双向链表的尾部，当元素超过上限且removeEldestEntry方法返回true时，直接删除最早元素以便新元素插入。如果没有冲突直接放入，同样加入到链表尾部。使用get方法时会把get到的元素放入双向链表尾部

HashSet