键值之道：深入学习Java中强大的HashMap（一）https://developer.aliyun.com/article/1480891
接下来我们再来看看核心的方法 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) // 第一次新增元素的时候进行扩容到默认 16 n = (tab = resize()).length; // 计算索引下标查询对应下标下的数据 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.equals(k)))) // 存在相同的 key：内存地址相等或者 equals 方法为true 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) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key // hash值一样，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; }
大概逻辑如下：
- 先通过 hash 值计算出 key 映射到哪个桶
- 如果桶上没有碰撞冲突，则直接插入
- 如果出现碰撞冲突了，则需要处理冲突
- 如果该桶使用红黑树处理冲突，则调用红黑树的方法插入数据
- 否则采用传统的链式方法插入。如果链的长度达到临界值，则把链转变为红黑树
- 如果桶中存在重复的键，则为该键替换新值 value
- 如果 size 大于阈值 threshold，则进行扩容
扩容 resize
- capacity 即容量，默认16。
- loadFactor 加载因子，默认是0.75
- threshold 阈值。阈值=容量*加载因子。默认12。当元素数量超过阈值时便会触发扩容。
一般情况下，当元素数量超过阈值时便会触发扩容。每次扩容的容量都是之前容量的2倍。HashMap的容量是有上限的，必须小于 1<<30。
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) // 新容量等于旧容量的两倍 newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; // 计算新的临界值 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) // 创建新数组 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { // ...复制老数组中的元素到新数组，遍历所有的元素进行 rehash，非常耗时间，所以尽量少的出现扩容操作 } return newTab; }
JDK8 因为巧妙的设计，性能有了大大的提升，由于数组的容量是以 2 的幂次方扩容的，那么在扩容时，新的位置要么在原位置，要么在原长度+原位置的位置。
数组长度变为原来的 2 倍，表现在二进制上就是多了一个高位参与数组下标确定。此时，一个元素通过 hash 转换坐标的方法计算后，恰好出现一个现象：最高位是 0 则坐标不变，最高位是 1 则坐标变为“10000+原坐标”，即“原长度+原坐标”。因此，在扩容时，不需要重新计算元素的 hash 了，只需要判断最高位是 1 还是 0 就好了。
如果我们确切的知道我们有多少键值对需要存储，那么我们在初始化 HashMap 的时候就应该指定它的容量，以防止 HashMap 自动扩容，影响使用效率。
当我们明确知道 HashMap 中元素的个数的时候，把默认容量设置成 initialCapacity/ 0.75F + 1.0F 是一个在性能上相对好的选择，但是，同时也会牺牲些内存。
比如如果我们要存入100个数据，那么将容量可以设置成 100/0.75+1 约等 135。
删除 remove
public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; }
remove 方式实际将删除逻辑转交 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, e; K k; V v; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 直接根据 key 匹配到目标节点 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 = e.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 的时候要转回链表。
查找 get
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; }
调用 get 查找方法，通过元素的 key 找到 value，get 方法实际上将查找逻辑转交 getNode 方法处理。
final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; // 如果哈希表不为空并且 key 对应的桶上不为空 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // 根据索引的位置检查第一个元素 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; // 索引位置的第一个元素不是目标 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); } } return null; }
调用红黑树的查找使用的是 getTreeNode 的 find 方法。
final TreeNode<K,V> find(int h, Object k, Class<?> kc) { TreeNode<K,V> p = this; do { int ph, dir; K pk; TreeNode<K,V> pl = p.left, pr = p.right, q; if ((ph = p.hash) > h) p = pl; else if (ph < h) p = pr; else if ((pk = p.key) == k || (k != null && k.equals(pk))) return p; else if (pl == null) p = pr; else if (pr == null) p = pl; else if ((kc != null || (kc = comparableClassFor(k)) != null) && (dir = compareComparables(kc, k, pk)) != 0) p = (dir < 0) ? pl : pr; else if ((q = pr.find(h, k, kc)) != null) return q; else p = pl; } while (p != null); return null; }
- 查找红黑树，由于之前添加时已经保证这个树是有序的了，因此查找时基本就是折半查找，效率更高
- 这里和插入时一样，如果对比结点的哈希值和要查找的哈希值相等，就会判断key是否相等，相等就直接返回。不相等就从子树中递归查找
遍历 HashMap
分别遍历 Key 和 Value
for (String key : map.keySet()) { System.out.println(key); } for (Object vlaue : map.values() { System.out.println(value); }
使用 Iterator 迭代器迭代（推荐）
Iterator<Map.Entry<String, Object>> iterator = map.entrySet().iterator(); while (iterator.hasNext()) { Map.Entry<String, Object> entry = iterator.next(); System.out.println(entry.getKey()); System.out.println(entry.getValue()); }
通过 get 方式
Set<String> keySet = map.keySet(); for (String str : keySet) { System.out.println(str); System.out.println(map.get(str)); }
笔记大部分摘录自《Java核心技术卷I》，含有少数本人修改补充痕迹。
参考文章：http://985.so/b7m3v、http://985.so/b023n、http://985.so/b0xnv
