HashMap(一)——HashMap put方法原理 - 好文

1.HashMap重要成员
部分成员变量如下： //初始值，为16，必须为2的次幂 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//当容量被占满0.75时就需要reSize扩容 static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表长度到8，就转为红黑树 static final int TREEIFY_THRESHOLD = 8; // 树大小为6，就转回链表 static
final int UNTREEIFY_THRESHOLD = 6;
HashMap类中有一个非常重要的字段，就是Node[] table，即哈希桶数组
transient Node<K,V>[] table;
Node是HashMap的一个内部类，实现了Map.Entry接口，本质就是一个映射(键值对) ，起源代码如下：
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final
K key; Vvalue; Node<K,V> next; Node(int hash, K key, V value, Node<K,V>
next) {this.hash = hash; this.key = key; this.value = value; this.next = next; }
public final K getKey() { return key; } public final V getValue() { return value
; }public final String toString() { return key + "=" + value; } public final int
hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public
final VsetValue(V newValue) { V oldValue = value; value = newValue; return
oldValue; }public final boolean equals(Object o) { if (o == this) return true;
if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if
(Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return
true; } return false; } }
2.HashMap的put方法

JDK7中HashMap采用的是位桶+链表的方式，即我们常说的散列链表的方式，而JDK8中采用的是位桶+链表/红黑树，本文研究的是 JDK8中的put方法。

JDK1.8 put方法源码：
public V put(K key, V value) { return putVal(hash(key), key, value, false, true
); }
这里我们先关注下hash函数，在HashMap中其实现如下：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h =
key.hashCode()) ^ (h >>>16); }
这里用到的方法很简单，就是把key与其高16位异或。文档中有如下说明：
There is a tradeoff between speed, utility, and quality of bit-spreading.
因为没有完美的哈希算法可以彻底避免碰撞，所以只能尽可能减少碰撞，在各方面权衡之后得到一个折中方案，这里我们就不再追究了。
put方法的具体实现在putVal中，我们看下其实现：
// 参数onlyIfAbsent表示是否替换原值 // 参数evict我们可以忽略它，它主要用来区别通过put添加还是创建时初始化数据的 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 =
resize()).length;// (n - 1) & hash这种方式也熟悉了吧？都在分析ArrayDeque中有体现
//这里就是看下在hash位置有没有元素，实际位置是hash % (length-1) if ((p = tab[i = (n - 1) & hash]) ==
null) // 将元素直接插进去 tab[i] = newNode(hash, key, value, null); else {
//这时就需要链表或红黑树了 // e是用来查看是不是待插入的元素已经有了，有就替换 Node<K,V> e; K k; // p是存储在当前位置的元素 if
(p.hash == hash && ((k = p.key) == key || (key !=null && key.equals(k)))) e = p;
//要插入的元素就是p，这说明目的是修改值 // p是一个树节点 else if (p instanceof TreeNode) // 把节点添加到树中 e
= ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { //
这时候就是链表结构了，要把待插入元素挂在链尾 for (int binCount = 0; ; ++binCount) { //向后循环 if ((e =
p.next) ==null) { p.next = newNode(hash, key, value, null); // 链表比较长，需要树化， //
由于初始即为p.next，所以当插入第9个元素才会树化 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
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; //
size太大，达到了capacity的0.75，需要扩容 if (++size > threshold) resize(); //
默认也是空实现，允许我们插入完成后做一些操作 afterNodeInsertion(evict); return null; }
总结：

HashMap在put方法中，它使用hashCode()和equals()方法。当我们通过传递key-value对调用put方法的时候，HashMap使用Key
hashCode()和哈希算法来找出存储key-value对的索引。如果索引处为空，则直接插入到对应的数组中，否则，判断是否是红黑树，若是，则红黑树插入，否则遍历链表，若长度超过8，则将链表转为红黑树，转成功之后
再插入。

热门工具换一换