- Java 1.7 HashMap 是由 数组+链表 数据结构。
- 数组的长度是固定的，因此会存在哈希碰撞，也就是下标位置冲突，
- 那么就会形成链表。若链表长度过长就会造成查询效率过慢，时间复杂度为O(n)。
- Java 1.8 数据结构就变成了 数组+链表+红黑树。
- 每个数据单元都是一个Node结构，结构中有Key ,value next ,hash 这几个属性。
- next 字段是在Hash冲突后形成链表需要的。
- 当链表长度超过阈值8，则调用转红黑树的方法，此时还判断若数组长度小于64的情况下，只会扩容， >=64转换为红黑树。主要为了提高查询效率。
- Java 1.7 采用的是 头插法，就是说新插入的值的时候，原来的值就会往后推一位，让新值放在头部位置，这样做的原因是因为后插入的值查找的可能性会更大一点，提高查找的效率。但是这样就会造成一个问题，在同一个位置上新元素总会被放在链表的头部位置，如果多线程put的情况下，就会改变数据的引用结构，那么就会造成环形链表，发生死循环！
- Java 1.8 之后采用的是 尾插法，这样扩容转移后前后链表顺序不变，保持之前节点的引用关系，就不会出现死循环的情况。
注：Java1.8HashMap
- 首先对 Key求Hash值，通过 key 的 hashCode 高低16位异 + 按位与运算 & ( table.length-1 )，计算所在数组下标。
- Hahs计算： key 为 null 返回 0，否则就将 key 的 hashCode 高低16位异或为了降低哈希冲突概率。
- 判断数组table是否为空。为空则进行初始化(这里是一个懒加载机制)。
以下分好几种情况
- 第一种 ，该位置为null,
- 将传入的内容封装成Node对象占用这个位置
- 第二种 该位置不为空，并且 node 还未链表
- 对比Node的key 与当前put的 key是否相同，若相同则执行更新操作。
- 若Key不同，则表示发生Hash冲突了 。会在Node节点后边追加一个新的Node，使用尾插法。
- 第三种情况, node 节点已经链表化
- 遍历链表
- 对比一下Node的key 与当前put的 key是否相同，若相同则执行更新操作，这里直接break跳出循环了。
- 若遍历到尾节点，也未匹配到Key不同，会在链表后边追加一个新的Node。
- 判断当链表的长度达到树化的阈值8，若超过则调用转红黑树的方法
- 转红黑树方法中判断，若数组长度<64的情况下，只会扩容 。数组>=64 并且链表长度超过8，才转红黑树
- 第四种情况, Node 节点已经转换成红黑树，TreeNode 类型
- 调用 putTreeval 方法增加树节点，
- 比较插入节点和当前节点的大小，若节点hash值小就往左子树查找，否则往右子树查找，
- 找到空位后执行调整平衡 balanceInsert 方法，插入节点并调整平衡;
- 执行重置根节点 moveRootToFront 方法，由于调整平衡后根节点可能变化，所以需要重置根节点 ;
- 添加完元素，后将 modCount 加 1
- 最后判断时候需要扩容，若超过百分之75的占用则进行扩容。
ps: 使用class对象作为Key需要重写该对象的hashCode()方法与equals()方法。
3.Get方法执行过程- 根据key 求Hash 并且与运算求出数组位置
- 若数组位置是非树，非链表则返回当前值，
- 若是链表或者红黑树则遍历，直到取到key与查找的key相同的数据，或查到没有数据。
- 默认初始化容量是 16
- 懒加载机制，第一次Put数据的时候创建。
- 默认的负载因子大小为0.75，限制最大不超过Integer的最大值。
- 当一个map占用达到容量75%的时候
- 将会创建原来HashMap大小的两倍的新Map，
- 遍历旧Map按照每个桶位迁移
- 第一种情况：当前位置，存储的是null （ 无需处理 ）
- 第二种情况：当前位置，存储的是Node 没有下级Next
- 没有发生过hash冲突，使用[ hash值 & (新容量-1) ] 计算下标后放入新Map
- 第三种情况：当前桶位存储的是链化的Node
- 遍历链表，拆分成两个链表，高位链，与低位链
- 通过hash值 & （与运算）旧容量 只可能是 0或1 ，一个是原下标的位置，另一种是在下标为<原下标+原容量>的位置
- 第四种情况：当前桶位存储的是红黑树根节点TreeNode对象
- 红黑树结构保留了Next字段，其实红黑树内部还维护者一个链表。虽然查询不用但是增删改的时候还维护了这个字段
- 主要用于方便 split 拆分 这个红黑树，根据高低位分成高位链，与低位链。低位链是原位置， 高位链存放在新表的下标老表的位置+老表的容量。
- 不管是高位链还是低位链表，拆分的链表，需要判断一下长度
- 若长度<=6 直接将treeNode 转换成普通的链表，放到扩容后的新表中
- 若扔> 6 还会升级成红黑树。
旧位置或 原下标+原容量
原先链表已经链化，推理出所有Node的hash字段转化成二进制后低位都是相同的，低位值就是老表的 size -1 ,转化出来的二进制数的有效位
比如 table 16 ；16-1=15 ,15转化成二进制1111 。 说明低位是低四位，高位是第5位 （ps:0 1111）
当链表低位是相同的，但是高位可能不一样，有的node 可能是0 ,有的 node 高位可能是 1
对应迁移到新表
低位链，因为高位是0 ，所以迁移到node 新表的时候，这个 slot下标和老的一样。
高位链，因为高位是1 ， 所以存储到新表之后。是老表的位置+老表的容量。
-
HashMap通过哈希算法得出哈希值之后，决定将键值放入对应的索引位 ;
-
HashMap的容量为16转化成二进制为10000，length-1得出的二进制为01111;
总结：因为2的幂-1，转化成二进制都是11111结尾的，所以碰撞几率小。
- 链表长度计数达到 8（put第9个的时候）
- 并且数组长大于64转换为红黑树。
- 若数组长度<64的情况下，只会扩容
- TreeNode 继承与 linkedHashMap.Entry 而linkedHashMap.Entry 继承与HashMap.Node
- 父节点(parent) 、 左指向（left）、右指向（right）、前一个节点（prev）、颜色标记（red）
- 首先找到一个合适的插入点，找到插入节点的父节点
- 红黑树由于满足二叉树的所有特性（左边的小，右边的大，每次向下查找一层就可以排除掉一半数据 todo 待看源码验证）
- 第一种情况；一直向下查找，直到查到左子树或右子树为null,说明整个树，没发现 node key 与当前put key一致的TreeNode
- 此时将当前插入的节点，就是父节点的左子树或者是右子树
- 根据插入节点的hash值和父节点的hash值大小决定左右。
- 插入会打破平衡，还需调用红黑树的平衡算法
- 第二种情况 ：根节点向下探测过程中，若发现treeNode的key与put的key完全一致，说明是更新操作。直接更新就好。
- 替换完成后还需要看一下是否满足二叉查找树的特性.
- 数组+链表改成了数组+链表或红黑树；
- JDK1.8中，HashMap采用位桶+链表+红黑树实现，当链表长度超过阈值（8）并且数组长度大于64，将链表转换为红黑树，大大减少了查找时间。
- 链表的插入方式从头插法改成了尾插法，简单说就是插入时，如果数组位置上已经有元素，1.7将新元素放到数组中，原始节点作为新节点的后继节点，1.8遍历链表，将元素放置到链表的最后；
- 扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置，1.8采用更简单的判断逻辑，位置不变或索引+旧容量大小；
- 在插入时，1.7先判断是否需要扩容，再插入，1.8先进行插入，插入完成再判断是否需要扩容；
头插法 (java 1.7 使用此法)：
- 不用遍历链表，速度快;
- 但是再扩容操作时，多线程操作下会出现 Entry 的 next 指针 并发修改导致数据丢失或死循环
尾插法 (java 1.8 使用此法)：：
- 需要遍历全链表。
- 不会出现闭环引用问，但是在多线程下也可能数据丢失。
为什么使用红黑树：
- 为了解决Hash 链化问题
- 链化问题会影响get 效率，本身散列查询复杂度 O(1)
- 链化后会导致退化为O(n)
- 红黑树其实就是一颗特殊的二叉排序树。
为什么一开始不直接用红黑树？
- 红黑树的插入慢（鱼和熊掌不可兼得）
为什么阈值>=8 ？：(其实这里不严谨，阈值>=8 && 数组长度 >= 64 才进行转红黑树，若数组< 64 则会进行扩容 )
- 在随机哈希代码下，桶中的节点频率遵循泊松分布，桶的长度超过8的概率非常非常小。
- 所以作者应该是根据概率统计而选择了8作为阀值。
- 中间有个差值7可以防止链表和树之间频繁的转换
假设一下：如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低
15.HashMap 为什么线程不安全？JDK7 存在死循环和数据丢失问题。
①数据丢失：
- 并发赋值被覆盖： 在 createEntry新增节点 方法中，新节点头插法，若两个线程同时执行到此处，可导致其中一个线程的赋值被覆盖。
- 已遍历区间新增元素丢失： 当某个线程在 transfer 方法迁移时，其他线程新增的元素可能落在已遍历过的哈希槽上。遍历完成后，table 数组引用指向了 newTable，新增元素丢失。
- 新表被覆盖： 如果 resize 完成，执行了 table = newTable，则后续元素就可以在新表上进行插入。但如果多线程同时 resize ，每个线程都会 new 一个数组，这是线程内的局部对象，线程之间不可见。迁移完成后resize 的线程会赋值给 table 线程共享变量，可能会覆盖其他线程的操作，在新表中插入的对象都会被丢弃。
② 死循环：
扩容时 resize 调用 transfer 使用头插法迁移元素，虽然 newTable 是局部变量，但原先 table 中的 Entry 链表是共享的，
问题根源是 Entry 的 next 指针 并发修改，某线程还没有将 table 设为 newTable 时用完了 CPU 时间片，导致数据丢失或死循环。
JDK8 在 resize 方法中完成扩容，并改用尾插法，不会产生死循环，但并发下仍可能丢失数据
16.HashMap存在线程安全问题，那是怎么处理这种情况的？- ConcurrentHashMap
- HashTable
- 使用 Collections.synchronizedMap(new HashMap<>())
- 在java1.7 头插时，PUT操作的时候，假如A线程和B线程同时对同一个数组位置，调用添加节点方法
在hashmap做put操作的时候, 假如A线程和B线程同时对同一个数组位置调用addEntry，两个线程会同时得到现在的头结点，然后A写入新的头结点之后，B也写入新的头结点，那B的写入操作就会覆盖A的写入操作造成A的写入操作丢失
18.何为快速失败(fail-fast)- fail-fast 是一种错误检测机制，并发情况下多个线程对集合的结构进行修改是就会触发 fail-fast机制，抛出ConcurrentModificationException异常。
- 原理： 迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量，遍历期间集合如果发生变化就会改变modCount的值，等下一个hasNext()/next()的时候就会比对modCount != expectedModCount 这个判断条件，如果为true则会抛出异常，终止遍历，否则就返回遍历。
- 左旋：右节点为当前节点，代替父节点，左孩子分支给父节点作为右孩子分支
- 不是
- 是 key 的 hashCode 高低16位异或
- 为了了降低哈希冲突概率。
| HashMap | Hashtable | ConcurrentHashMap | |
|---|---|---|---|
| 继承的父类 | AbstractMap | Dictiionary | AbstractMap |
| 线程安全性 | 不安全 | 安全 | 安全 |
| 锁 | 无 | synchronized锁方法 | jdk 1.6 采用分段的数组+链表实现 jdk 1.8 采用一种乐观锁，Cas机制实现 |
| 是否同步 | 否 | 是 | 是 |
| k，v可否null | 是 | 否 | 否(空指针异常) |
| 初始容量 | 16 | 11 | 16 |
| 扩容方式 | 2倍（2的整数次幂） | 2倍+1 | 2倍（2的整数次幂） |
| 哈希值的使用不同 | HashMap重新计算hash值 | 直接使用对象的hashCode | |
- 都是无序的，底层数据结构都是 数组+链表+红黑树
- HashMap 线程不安全，ConcurrentHashMap线程安全
- jdk1.8的实现：采用CAS + Synchronized，synchronized在put的时候锁是节点的第一个元素，但其底层还是“数组+链表+红黑树”的实现。当链表长度大于8并且数组长度大于64的时候转红黑树。
- k，v可否null HashMap 可以为 null , ConcurrentHashMap 不可以
- 初始容量 ，都是16
- 扩容方式 ， 2倍
HashMap
- 线程非安全
- 数组加链表方式存储key/value, java1.8之后新加了红黑树
- 允许null作为key和value
- key不可以重复，value允许重复
- 不保证元素迭代顺序是按照插入时的顺序；
TreeMap
- 基于红黑树
- 线程非安全
- 不允许null作为key
- key不可以重复，value允许重复
- 默认按照key的字典顺序来排序（升序），自定义排序规则需要实现Comparable接口
- 将任意长度的输入通过hash算法映射成固定长度
- 理论上无法避免。可以减少碰撞机率。
- 效率高
- 长文本也可以高效计算
- 通过hash值不能逆推出原文
- 值不同，Hash值不同。
- 尽可能分散。
