# HashMap 源码分析
# 1 属性
初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;红黑树阈值
static final int TREEIFY_THRESHOLD = 8;链表阈值
static final int UNTREEIFY_THRESHOLD = 6;红黑树桶阈值
static final int MIN_TREEIFY_CAPACITY = 64;table 数组，用来初始化
transient Node<K,V>[] table;entrySet 存放缓存
transient Set<Map.Entry<K,V>> entrySet;桶的数量
transient int size修改次数
transient int modCount;阈值
int threshold负载因子
float loadFactor
# 2 构造方法
HashMap()
public HashMap(){ this.loadFactor = DEFAULT_LOAD_FACTOR; }HashMap(int initialCapacity)
public HashMap(int initialCapacity){ this(int initialCapacity, DEFAULT_LOAD_FACTOR); }HashMap(int initialCapacity, float loadFactor )
public HashMap(int initialCapacity, float loadFactor){ if (initialCapacity < 0){ //抛出数值异常 } if (initialCapacity > MAXIMUM_CAPACITY){ initialCapacity = MAXIMUM_CAPACITY; } if (loadFactor <= 0 || Float.isNaN(loadFactor)){ //抛出数值异常 } this.loadFactor = loadFactor; //tableSizeFor，大于等于当前值的下一个 2 的幂，比如输入 17，返回 32 this.threshold = tableSizeFor(initialCapacity); }
# 3 增加元素
put 方法分析
public V put(K key, V value){ return putVal(hash(key), key, value, false, true); }hash 方法分析
static int hash(Object key){ int h; //key 为空返回 0，先计算 key 的 hashcode，然后与 h 无符号右移 16 位后的二进制进行异或 return key == null ? 0 : (h = key.hashCode() ^ (h >>> 16)); }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; /* * 如果 table 是否等于空或者等于 0，如果是则进行初始化 */ if ((tab = table) == null || (n = tab.length) == 0){ n = (tab = resize()).length(); } /* * 哈希取模，i = (n - 1) & hash，对值的位置进行确定 * 也是 capacity 为 2 的幂的原因，与运算效率高于% * capacity 为 2 的幂次时，(n - 1) & hash = hash % n * 如果 tab[i] = null，新增一个元素 */ if ((p = tab[i = (n - 1) & hash]) == null){ tab[i] = newNode(hash, key, value, null); } else { //说明该位置有值了 Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.eqauls(k)))){ //key 值存在，无论链表还是红黑树都需要替换 e = 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); //大于红黑树阈值，转换红黑树 if (binCount >= TREEIFY_THRESHOLD - 1){ treeifyBin(tab, hash); } break; } if (e.hash && hahs && ((k = e.key) == key || (key != null && key.equals(k)))){ break; } p = e; } } /* * 如果链表中重复就直接替换 */ if (e != null){ V oldValue = e.value; if (!onlyIfAbsent || oldValue == null){ e.value = value; } afterNodeAccess(e); return oldValue; } } //记录修改次数 modCount++; //如果超过 threshold，调用 resize if (++size > threshold){ resize(); } afterNodeInsertion(evict); return null; }- 如果定位到的数组位置没有元素，直接插入。
- 如果定位到的数组位置有元素，就要和插入的 key 比较，key 相同则直接覆盖，如果不相同，则判断 p 是否是 TreeNode，如果是则调用 e=((TreeNode<K,V)p).putTreeVal(this, tab, hash, key, value)将元素添加进入。如果不是则遍历链表插入到链表尾部。
resize 方法分析
final Node<k,V>[] resize(){ Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0){ if (oldCap >= MAXIMUM_CAPACITY){ threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY){ //threshold 加倍 newThr = oldThr << 1; } } else if (oldThr > 0){ newCap = oldThr; } else { //默认 Capacity 和 threshold，分别为 16 和 12 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0){ float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUN_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE); } threshold = newThr; Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null){ /* * 省略，拷贝旧的 hash 桶到 newTab */ } }
# 4 读取元素
get 方法分析
public V get(Object key){ Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; }getNode 方法分析
final Node<K,V> getNode(int hash, Object key){ Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //table 有元素 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null){ //从第一个 node 开始 if (first.hash = hash && ((k = first.key) == key || (key != null && key.equals(k)))){ return first; } //first 的下一个 node if ((e = first.next) != null){ //若是红黑树，调用红黑树查找方法 if (first instanceof TreeNode){ return ((TreeNode<K,V>)first).getTreeNode(hash, key); } //否则遍历链表查找 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){ return e; } } while ((e = e.next) != null); } } //table 没元素了，直接返回 null return null; }
# 5 删除元素
remove 方法分析
public V remove(Object key){ Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; }removeNode 方法分析
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable){ Node<K,V>[] tab; Node<K,V> p; int n, index; if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null){ Node<K,V> node = null; Node<K,V> e; K k; V v; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))){ node = p; } else if ((e = p.next) != null){ //如果是红黑树，调用红黑树查找方法 if (p instanceof TreeNode){ node = ((TreeNode<K,V>)p).getTreeNode(hash,key); } else { //否则，迭代链表 do{ if (e.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))){ node = e; break; } p = e; } while ((e = e.next) != null); } } //找到节点了 if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))){ //调用红黑树删除节点的方法 if (node instanceof TreeNode){ ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); } else if (node == p){ //是链表头部 tab[index] = node.next; } else { p.next = node.next; } //修改次数 modCount++; size--; afterNodeRemoval(node); return node; } } return null; }
# 6 底层数据结构分析
# 6.1 JDK1.8 之前
底层：数组加链表
基本原理：通过 key 的 hashcode 经过扰动处理得到 hash 值，然后通过(n - 1) & hash 判断当前元素存放的位置，如果当前位置存在元素的话，就判断该元素与要存放的元素的 hash 值以及 key 是否相同，如果相同则直接覆盖，不相同就用拉链法解决冲突。
扰动函数：hash 方法，目的是防止一些实现比较差的 hashcode 方法，减少碰撞。
hash 方法：
static int hash(int h){ h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }性能较于 1.8 差，扰动次数为 4
拉链法：将链表和数组结合，也就是创建一个链表数组 Node<K,V>[]，如果遇到哈希冲突，则将冲突的值加到链表中即可。
# 6.2 JDK1.8 之后
- 底层：数组加链表加红黑树
- 基本原理：当链表长度大于阈值 8 时，会调用 treeifyBin 方法，根据 HashMap 数组决定是否转化成红黑树，只有当数组长度大于或者等于 64时，才会执行转换红黑树的操作，减减少搜索时间。否则只会进行 resize()方法对数组进行扩容。