集合

HasMap

数据结构

JDK1.7

• 数组+链表
• 使用头插法

JDK1.8

• 数组 + 链表 + 红黑树
• 使用尾插法

put方法流程

• hash/扰动函数，(key == null) ? 0 : (h = key. hashCode()) ^ (h >>> 16)，高16不动，高16位异或低16位，增加结果随机性
  • 扰动函数解析：用于计算一个改进后的哈希码，主要用于提高哈希码的分布质量
  • 获取哈希吗：key.hashCode()，int取值[-2147483648,2147483647]，获取对象key的哈希码，并赋值给h
  • 无符号右移：(h >>> 16) 表示将h的二进制表示无符号右移16位。这意味着h的最高有效16位被移除，最低有效位补入16个0。此操作让原来在高位的信息移到了低位
  • 异或操作：^是按位异或操作符。当你对两个数进行异或操作时，如果两位相同结果为0，如果两位不同结果为1。通过h和右移后的h进行异或，可以将原来本高位信息与低位信息混合。
• 将扰动后的值与length - 1做与运算，得到数组下标，hash % (2^4)；本质就是和长度取余，等价计算方式：hash & (2^4 - 1)
• 把put进来的key，value封装成entry对象
• 判断数组下标对应的位置
  • 若为空，则把entry存在该数组位置
  • 若不为空，则把entry插入到链表中，并判断该链表中是否存在相同的key，如果存在，更新value
  • 如果超过8个且数组长度大于64，则进行树化，变成红黑树。红黑树主要为了解决链表过长导致查询和插入效率低的问题，解决这个问题，也可以通过数组扩容，把链表缩短。所以在数组长度还不太长的时候，可以先通过数组扩容来解决。
  • 入托红黑树节点个数<6转为链表

扩容流程

• HashMap的扩容指的是数组的扩容，因为数组占用的是连续的内存空间，所以数组的扩容其实只能新开一个新的数组，然后把老数组上的元素转移到新的数组上来，这样才是数组的扩容
• 当HashMap中的元素数量超过阈值（阈值threshold = 当前容量capacity * 负载因子loadfactor）
• 先创建一个2倍数大小的数组
• 然后遍历老数组上的每一个位置，如果这个位置上是一个链表，就把这个链表上的元素转移到新数组上去
• 在这个过程中就需要遍历链表，JDK7和JDK8的扩容方式是不一样的，JDK7简单的遍历链表上的每一个元素，然后按每个元素的hashcode结合新数组的长度重新计算得出一个下标，而重新得到的这个数组下标很可能和之前的下标是不一样的，这样子就达到扩容之后某个链表会变短，达到扩容目的，缩短链表长度，提高查询效率。在JDK8中，因为设计红黑树，其会用到一个双向链表来维护红黑树的元素，会遍历该位置的双向链表，统计哪些元素在扩容之后还在原位置，哪些元素在扩容之后在新位置，这样遍历完双向链表后，就会得到两个子链表，一个放在原下标位置，一个放在新下标位置，如果原下标位置或新下标位置没有元素，则红黑树不用拆分，否则判断这两个子链表长度，如果超过8个，则进行树化，否则直接将原位置的子链表转移到新位置。
• 元素转移完之后，把新数组对象赋值给HashMap的table属性，老数组会被回收。

ConcurrentHashMap

数据结构

JDK1.7

• 数组+链表
• segment分段锁
  • 继承ReentrantLock
  • 尝试获取锁存在竞争就自旋，阻塞
• get方法使用volatile修饰，不加锁，保证高效
• HashEntry

JDK1.8

• 数组+链表+红黑树
• CAS+synchronized
  • CAS失败自旋保证成功
  • 再失败就sync保证
• Node

HashTable

在每个public方法上加synchronized，保证线程安全，所有操作都是串行的，效率低下

ArrayList(List)

特点

• 元素有放入顺序，元素可重复。

储存结构

• 底层采用数组(连续的存储单元)来实现

CopyOnWriteArrayList

• 线程安全的类
• 采用一种读写分离的并发策略，读操作是无锁的，性能较高。写操作，将当前数组复制一份，在新的数组上进行修改，然后替换原数组。

LinkedList

• 双向链表
• 适合插入删除频繁的情况，内部维护了链表的长度

LinkedListMap

• 怎么实现有序
  • 内部维护了一个双向链表，有头尾节点，同时LinkedHashMap节点内部Entry内部除了继承HashMap的Node属性，还有before和after用于标识前置节点和后置节点

TreeMap

• 通过key的比较器决定元素的顺序
• 底层是红黑树