HashMap 是无论在工作还是面试中都非常常见常考的数据结构。比如 Leetcode 第一题 Two Sum 的某种变种的最优解就是需要用到 HashMap 的，高频考题 LRU Cache 是需要用到 LinkedHashMap 的。 随着JDK（Java Developmet Kit）版本的更新，JDK1.8对HashMap底层的实现进行了优化，例如引入红黑树的数据结构和扩容的优化等。

# LinkedHashMap 继承于 HashMap ``` public class LinkedHashMap extends HashMap implements Map ```

# 树形结构修剪 split() HashMap 中， 当扩容时，如果当前桶中元素结构是红黑树，并且元素个数小于链表还原阈值 UNTREEIFY_THRESHOLD （默认为 6），就会把桶中的树形结构缩小或者直接还原（切分）为链表结构，调用的就是 split()。 ```java /** * Splits nodes in a tree bin into lower and upper

# 准备 首先创建了类 TreeNodeHashMap， 提供内部类MapKey。 ``` MapKey:重写了hashCode使得hashCode碰撞极高. 在hashCode() 中，所有数字，hashCode全部给1，为了复现碰撞极高， 且更容易树化(超过8)。 非数字的均为2. 由于在TreeNodeHashMap测试的key都为数字，所以每次key的hashCode都相同， 都为1.实现

toc + JDK1.8 HashMap源码解析 目录 - [JDK1.8 HashMap源码解析(一) 数据结构&初始化](https://muzinuo.com/article/byuan-ma-jie-xi.html) - [JDK1.8 HashMap源码解析(二) 数据赋值 put](https://muzinuo.com/article/b45cuf36os38.html)

+ JDK1.8 HashMap源码解析 目录 - [JDK1.8 HashMap源码解析(一) 数据结构&初始化](https://muzinuo.com/article/byuan-ma-jie-xi.html) - [JDK1.8 HashMap源码解析(二) 数据赋值 put](https://muzinuo.com/article/b45cuf36os38.html)

+ JDK1.8 HashMap源码解析 目录 - [JDK1.8 HashMap源码解析(一) 数据结构&初始化](https://muzinuo.com/article/byuan-ma-jie-xi.html) - [JDK1.8 HashMap源码解析(二) 数据赋值 put](https://muzinuo.com/article/b45cuf36os38.html)

/** * HashMap中键值对的存储形式为链表节点，hashCode相同的节点（位于同一个桶）用链表组织 * hash方法分为三步: * 1.取key的hashCode * 2.key的hashCode高16位异或低16位 * 3.将第一步和第二步得到的结果进行取模运算。 */

+ JDK1.8 HashMap源码解析 目录 - [JDK1.8 HashMap源码解析(一) 数据结构&初始化](https://muzinuo.com/article/byuan-ma-jie-xi.html) - [JDK1.8 HashMap源码解析(二) 数据赋值 put](https://muzinuo.com/article/b45cuf36os38.html)