hashmap 是一个 key-value 形式的键值对集合。（本文内容基于 JDK1.8）下面是一个简单的 hashmap 的结构。 本文主要是通过源码的方式分析 HashMap 的实现和优化。主要是围绕源码本身展开，以添加注释的方式进行记录和分析
初始化
在创建 HashMap 对象示例的时候不会初始化存储数组，会在首次调用 put 方法的时候初始化数组。构造方法如下：
public HashMap(int initialCapacity, float loadFactor) { // initialCapacity 初始容量 < 0 报错; 默认 16 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); // initialCapacity 初始容量是否大于最大容量 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; // loadFactor 负载因子 <= 0 || isNaN ; 默认0.75 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }
put 方法
添加数据通常我们采用 put 方法，该方法也是我们开发中比较常用的方法之一。最终会调用 putVal 方法进行初始化和添加数据。在这个方法中我们需要注意的有几个地方：
- 如果没有初始化会调用 resize() 方法进行 hashmap 存储数组的初始化。
- 默认通过 & 运算计算节点存储位置，这里也证明了为什么初始化数组的长度要是 2 的 n 次方。
- 如果不存在 hash 冲突的情况下，通过然后调用 newNode 方法创建节点，存放到对应的数组下标。
- 如果存在 hsah 冲突的情况下。这里就会有三种情况：
- 首次 hash 冲突的情况下，当前节点是一个普通的节点，如果 key 相同得话，将采取数据覆盖的方式；
- 如果当前节点类型是 treeNode 类型，是一棵红黑树。将调用 putTreeVal 方法来进行添加子节点；
- 最后，将当作链表处理，首先查找链表的尾节点，找到尾节点后，将当前节点添加到尾节点，这里有一个判断如果当前链表的节点数 > 8 并且 hashmap 的总长度 > 64 就会将当前的链表进行变换为红黑树。还有一种特殊情况，如果在链表的查找过程中查找到了一个当前新增key 相同的节点，那么就会覆盖当前节点数据并且退出循环；
- 前面所有的步骤都是为了找到当前的节点指针，然后再通过当前对象修改 value 值， 这里有一个需要注意的地方，在修改的时候会做一个判断如果
**_onlyIfAbsent_**等于 false 才可以修改，就是说可能当前 hashmap 存在不可以被修改的情况，比如：map.putIfAbsent 方法的时候调用就会修改失败，最后才能修改 value 值，并且返回旧值。
- 最后对修改次数累加，然后判断一次是否需要拓展 hashmap 的容量，然后返回 null , 方法结束。
// put 方法 public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } // putVal 方法 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 如果没有初始化 if ((tab = table) == null || (n = tab.length) == 0) // 调用 resize 初始化 // n = tab.length 容量 n = (tab = resize()).length; // 默认通过 & 运算计算节点存储位置，这里也证明了为什么初始化数组的长度要是2的n 次方 // 并且把当前节点的数据给 p if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { // 如果节点数据已经存在，即存在 hash 冲突的情况 Node<K,V> e; K k; // 1. 当前节点存在，并且插入k，和存在的 k 的value 值相同，那么直接刷新当前节点数据即可 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 新的节点数据 = p, 其实这里也只是获取 p 的指针 e = p; // 2. 如果是 TreeNode 结构， 即红黑树结构 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { // 3. 其他情况，即链表结构 for (int binCount = 0; ; ++binCount) { // 父节点子节点为 null if ((e = p.next) == null) { // 将 p.next = newNode p.next = newNode(hash, key, value, null); // 节点数是否大于变形的阈值 (TREEIFY_THRESHOLD = 8) if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st // 如果 tab.length < 64 默认拓容 // 否则进行红黑树转换 treeifyBin(tab, hash); break; } // 如果存在值相同的情况 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 如果 e 不为空，就是说当前节点指针不为空，【这种情况是覆盖】，返回旧值 if (e != null) { // existing mapping for key V oldValue = e.value; // 当前节点可以被修改或者是新增节点 if (!onlyIfAbsent || oldValue == null) e.value = value; // 预留模板方法 afterNodeAccess(e); return oldValue; } } // 修改次数 ++ ++modCount; // 大于拓容阈值 if (++size > threshold) // 拓容 resize(); // 预留模板方法 afterNodeInsertion(evict); return null; }
总结：其实通过上面的分析和代码的，我们分析出有一下几个核心方法：
newNode创建 Node 节点
((TreeNode<K,V>)p).putTreeVal(**this**, tab, hash, key, value);添加节点信息；
treeifyBin节点冲突情况下，链表转换为红黑树；
resize()HashMap 拓容；
newNode 创建节点
创建 HashMap 的节点信息，其实这个方法看上去比较普通，但是本质上也是比较普通。但是对于 hash 这个参数我们可以思考一下。
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) { return new Node<>(hash, key, value, next); }
hash 计算 hash 码
hash 方法如下，
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
理论上 hash 散列是一个 int 值，如果直接拿出来作为下标访问 hashmap 的话，考虑到二进制 32 位，取值范围在**-2147483648 ~ 2147483647** 范围。 大概有 40 亿个 key ， 只要哈希函数映射比较均匀松散，一般很难出现碰撞。 存在一个问题是 40 亿长度的数组，内存是不能放下的。因为咱们 HashMap 的默认长度为 16 。所以这个 hashCode , (key.hashCode ) 是不能直接来使用的。使用之前先做对数组长度的与运算，得到的值才能用来访问数组下标。 代码如下：
// n = hashmap 的长度 p = tab[i = (n - 1) & hash])
这里为什么要使用 n -1 ，来进行与运算，这里详单与是一个”低位掩码”, 以默认长度 16 为例子。 和某个数进行与预算，结果的大小是 < 16 的。如下所示：
10000000 00100000 00001001 & 00000000 00000000 00001111 ------------------------------ 00000000 00000000 00001001 // 高位全部归 0, 只保留后四位
这个时候会有一个问题，如果本身的散列值分布松散，只要是取后面几位的话，碰撞也会非常严重。还有如果散列本省做得不好的话，分布上成等差数列的漏洞，可能出现最后几位出现规律性的重复。 这个时候“扰动函数”的价值制就体现出来了。如下所示：
在 hash 函数中有这样的一段代码： (h = key.hashCode()) ^ (h >>> 16) 右位移 16 位， 正好是32bit 的一半，与自己的高半区做成异或，就是为了**混合原始的哈希码的高位和低位，以此来加大低位的随机性。**并且混合后的低位掺杂了高位的部分特征，这样高位的信息变相保存下来。其实按照开发经验来说绝大多数情况使用的时候 hashmap 的长度不会超过 1000，所以提升低位的随机性可以提升可以减少hash 冲突，提升程序性能。
如果感兴趣的小伙伴可以浏览下一下 Peter Lawlay 的专栏《An introduction to optimising a hashing strategy》
