Java 集合深入理解HashMap 主要特点和关键方法源码解读.docx

《Java 集合深入理解HashMap 主要特点和关键方法源码解读.docx》由会员分享，可在线阅读，更多相关《Java 集合深入理解HashMap 主要特点和关键方法源码解读.docx（20页珍藏版）》请在三一办公上搜索。

1、Java 集合深入理解HashMap 主要特点和关键方法源码解读Java 集合深入理解：HashMap 主要特点和关键方法源码解读 什么是 HashMap HashMap 是一个采用哈希表实现的键值对集合，继承自 AbstractMap，实现了 Map 接口 。 HashMap 的特殊存储结构使得在获取指定元素前需要经过哈希运算，得到目标元素在哈希表中的位置，然后再进行少量比较即可得到元素，这使得 HashMap 的查找效率贼高。 当发生 哈希冲突的时候，HashMap 采用 拉链法 进行解决，因此 HashMap 的底层实现是 数组+链表，如下图 所示： HashMap 的特点 结合平时使用

2、，可以了解到 HashMap 大概具有以下特点： 底层实现是 链表数组，JDK 8 后又加了 红黑树 实现了 Map 全部的方法 key 用 Set 存放，所以想做到 key 不允许重复，key 对应的类需要重写 hashCode 和 equals 方法 允许空键和空值 元素是无序的，而且顺序会不定时改变 插入、获取的时间复杂度基本是 O(1) 遍历整个 Map 需要的时间与 桶(数组) 的长度成正比 两个关键因子：初始容量、加载因子 除了不允许 null 并且同步，Hashtable 几乎和他一样。 下面结合源码进行验证这些特点。 HashMap 的 13 个成员变量 1.默认初始容量：16

3、，必须是 2 的整数次方 static final int DEFAULT_INITIAL_CAPACITY = 1 4; 2.默认加载因子的大小：0.75，可不是随便的，结合时间和空间效率考虑得到的 static final float DEFAULT_LOAD_FACTOR = 0.75f; 3.最大容量： 2 30 次方 static final int MAXIMUM_CAPACITY = 1 30; 4.当前 HashMap 修改的次数，这个变量用来保证 fail-fast 机制 transient int modCount; 5.阈值，下次需要扩容时的值，等于 容量*加载因子 in

4、t threshold; 6.树形阈值：JDK 1.8 新增的，当使用 树 而不是列表来作为桶时使用。必须必 2 大 static final int TREEIFY_THRESHOLD = 8; 7.非树形阈值：也是 1.8 新增的，扩容时分裂一个树形桶的阈值，要比 TREEIFY_THRESHOLD 小 static final int UNTREEIFY_THRESHOLD = 6; 8.树形最小容量：桶可能是树的哈希表的最小容量。至少是 TREEIFY_THRESHOLD 的 4 倍，这样能避免扩容时的冲突 static final int MIN_TREEIFY_CAPACITY =

5、 64; 9.缓存的 键值对集合 transient SetMap.Entry entrySet; 10.哈希表中的链表数组 transient Node table; 11.键值对的数量 transient int size; 12.哈希表的加载因子 final float loadFactor; HashMap 的初始容量和加载因子 由于 HashMap 扩容开销很大，因此与扩容相关的两个因素： 容量：数组的数量 加载因子：决定了 HashMap 中的元素占有多少比例时扩容 成为了 HashMap 最重要的部分之一，它们决定了 HashMap 什么时候扩容。 HashMap 的默认加载因子

6、为 0.75，这是在时间、空间两方面均衡考虑下的结果： 加载因子太大的话桶太多，遍历时效率变低 太小的话频繁 rehash，导致性能降低 当设置初始容量时，需要提前考虑 Map 中可能有多少对键值对，设计合理的加载因子，尽可能避免进行扩容。 如果存储的键值对很多，干脆设置个大点的容量，这样可以少扩容几次。 HashMap 的关键方法 1. HashMap 的 4 个构造方法 /创建一个空的哈希表，初始容量为 16，加载因子为 0.75 public HashMap this.loadFactor = DEFAULT_LOAD_FACTOR; / all other fields default

7、ed /创建一个空的哈希表，指定容量，使用默认的加载因子 public HashMap(int initialCapacity) this(initialCapacity, DEFAULT_LOAD_FACTOR); /创建一个空的哈希表，指定容量和加载因子 public HashMap(int initialCapacity, float loadFactor) if (initialCapacity MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor = 0 | Float.isNaN(loadFacto

8、r) throw new IllegalArgumentException(Illegal load factor: + loadFactor); this.loadFactor = loadFactor; /根据指定容量设置阈值 this.threshold = tableSizeFor(initialCapacity); /创建一个内容为参数 m 的内容的哈希表 public HashMap(Map m) this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); 其中第三种构造方法调用了 tableSizeFor(int

9、) 来根据指定的容量设置阈值，这个方法经过若干次无符号右移、求异运算，得出最接近指定参数 cap 的 2 的 N 次方容量。假如你传入的是 5，返回的初始容量为 8 。 static final int tableSizeFor(int cap) int n = cap - 1; n |= n 1; n |= n 2; n |= n 4; n |= n 8; n |= n 16; return (n = MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 第四种构造方法调用了 putMapEntries，这个方法用于向哈希表中添加整个集合： final

10、void putMapEntries(Map m, boolean evict) int s = m.size; if (s 0) /数组还是空，初始化参数 if (table = null) float ft = (float)s / loadFactor) + 1.0F; int t = (ft threshold) threshold = tableSizeFor(t); /数组不为空，超过阈值就扩容 else if (s threshold) resize; for (Map.Entry e : m.entrySet) K key = e.getKey; V value = e.get

11、Value; /先经过 hash 计算位置，然后复制指定 map 的内容 putVal(hash(key), key, value, false, evict); 2.HashMap 中的链表节点 前面提到，HashMap 的底层数据结构之一就是链表数组： transient Node table; 每一个链表节点如下： /实现了 Map.Entry 接口 static class Node implements Map.Entry /哈希值，就是位置 final int hash; /键 final K key; /值 V value; /指向下一个几点的指针 Node next; Node

12、(int hash, K key, V value, Node 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.ha

13、shCode(value); public final V setValue(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 相等的条件：键相等、值相等、个数相等、顺序相等 Map.Entry e = (Map.Entry)o; if (Objects.equals(key, e.getKey) & Ob

14、jects.equals(value, e.getValue) return true; return false; 3.HashMap 中的添加操作 * 下文用“桶”来指代要数组，每个桶都对应着一条链表： /添加指定的键值对到 Map 中，如果已经存在，就替换 public V put(K key, V value) /先调用 hash 方法计算位置 return putVal(hash(key), key, value, false, true); final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean

15、evict) Node tab; Node p; int n, i; /如果当前 哈希表内容为空，新建，n 指向最后一个桶的位置，tab 为哈希表另一个引用 /resize 后续介绍 if (tab = table) = null | (n = tab.length) = 0) n = (tab = resize).length; /如果要插入的位置没有元素，新建个节点并放进去 if (p = tabi = (n - 1) & hash) = null) tabi = newNode(hash, key, value, null); else /如果要插入的桶已经有元素，替换 / e 指向被替

16、换的元素 Node e; K k; if (p.hash = hash & (k = p.key) = key | (key != null & key.equals(k) /p 指向要插入的桶第一个 元素的位置，如果 p 的哈希值、键、值和要添加的一样，就停止找，e 指向 p e = p; else if (p instanceof TreeNode) /如果不一样，而且当前采用的还是 JDK 8 以后的树形节点，调用 putTreeVal 插入 e = (TreeNode)p).putTreeVal(this, tab, hash, key, value); else /否则还是从传统的链

17、表数组查找、替换 /遍历这个桶所有的元素 for (int binCount = 0; ; +binCount) /没有更多了，就把要添加的元素插到后面得了 if (e = p.next) = null) p.next = newNode(hash, key, value, null); /当这个桶内链表个数大于等于 8，就要树形化 if (binCount = TREEIFY_THRESHOLD - 1) / -1 for 1st treeifyBin(tab, hash); break; /如果找到要替换的节点，就停止，此时 e 已经指向要被替换的节点 if (e.hash = hash

18、& (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; /如果超出阈值，就得扩容 if (+size threshold) resize; afterNodeInsertion(evict); return nul

19、l; 根据代码可以总结插入逻辑如下: 1. 先调用 hash 方法计算哈希值 2. 然后调用 putVal 方法中根据哈希值进行相关操作 3. 如果当前 哈希表内容为空，新建一个哈希表 4. 如果要插入的桶中没有元素，新建个节点并放进去 5. 否则从桶中第一个元素开始查找哈希值对应位置 1. 如果桶中第一个元素的哈希值和要添加的一样，替换，结束查找 2. 如果第一个元素不一样，而且当前采用的还是 JDK 8 以后的树形节点，调用 putTreeVal 进行插入 3. 否则还是从传统的链表数组中查找、替换，结束查找 4. 当这个桶内链表个数大于等于 8，就要调用 treeifyBin 方法进行树

20、形化 6. 最后检查是否需要扩容 插入过程中涉及到几个其他关键的方法 ： hash:计算对应的位置 resize:扩容 putTreeVal:树形节点的插入 treeifyBin:树形化容器 HashMap 在 JDK1.8 新增树形化相关的内容比较多，下一篇介绍，接下来先介绍传统的 HashMap 相关内容。 4.HashMap 中的哈希函数 hash * HashMap 中通过将传入键的 hashCode 进行无符号右移 16 位，然后进行按位异或，得到这个键的哈希值。 static final int hash(Object key) int h; return (key = null)

21、 ? 0 : (h = key.hashCode) (h 16); 看看源码里的注释怎么说的： Computes key.hashCode and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding c

22、onsecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits wnward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so dont benefit from spreading), and beca

23、use we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds. 大概意思就是： 由于哈希表的容

24、量都是 2 的 N 次方，在当前，元素的 hashCode 在很多时候下低位是相同的，这将导致冲突，因此 1.8 以后做了个移位操作：将元素的 hashCode 和自己右移 16 位后的结果求异或。 由于 int 只有 32 位，无符号右移 16 位相当于把高位的一半移到低位： 举个栗子： 这样可以避免只靠低位数据来计算哈希时导致的冲突，计算结果由高低位结合决定，可以避免哈希值分布不均匀。 而且，采用位运算效率更高。 5.HashMap 中的初始化/扩容方法 resize * 每次添加时会比较当前元素个数和阈值： /如果超出阈值，就得扩容 if (+size threshold) resize

25、; 扩容： final Node resize /复制一份当前的数据 Node 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) = D

26、EFAULT_INITIAL_CAPACITY) /如果旧容量小于等于 16，新的阈值就是旧阈值的两倍 newThr = oldThr 0，说明之前创建了哈希表但没有添加元素，初始化容量等于阈值 else if (oldThr 0) / initial capacity was placed in threshold newCap = oldThr; else / zero initial threshold signifies using defaults /旧容量、旧阈值都是0，说明还没创建哈希表，容量为默认容量，阈值为 容量*加载因子 newCap = DEFAULT_INITIAL_C

27、APACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); /如果新的阈值为 0 ，就得用 新容量*加载因子 重计算一次 if (newThr = 0) float ft = (float)newCap * loadFactor; newThr = (newCap MAXIMUM_CAPACITY & ft (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); /更新阈值 threshold = newThr; /创建新链表数组，容量是原来的两倍 Su

28、ppressWarnings(rawtypes,unchecked) Node newTab = (Node)new NodenewCap; table = Tab; /接下来就得遍历复制了 if (oldTab != null) for (int j = 0; j oldCap; +j) Node e; if (e = oldTabj) != null) /旧的桶置为空 oldTabj = null; /当前 桶只有一个元素，直接赋值给对应位置 if (e.next = null) newTabe.hash & (newCap - 1) = e; else if (e instanceof

29、TreeNode) /如果旧哈希表中这个位置的桶是树形结构，就要把新哈希表里当前桶也变成树形结构 (TreeNode)e).split(this, newTab, j, oldCap); else /保留旧哈希表桶中链表的顺序 Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node next; /do-while 循环赋值给新哈希表 do next = e.next; if (e.hash & oldCap) = 0) if (loTail = null) loHead = e; else loTai

30、l.next = e; loTail = e; else if (hiTail = null) hiHead = e; else hiTail.next = e; hiTail = e; while (e = next) != null); if (loTail != null) loTail.next = null; newTabj = loHead; if (hiTail != null) hiTail.next = null; newTabj + oldCap = hiHead; return newTab; 扩容过程中几个关键的点： 新初始化哈希表时，容量为默认容量，阈值为 容量*加载

31、因子 已有哈希表扩容时，容量、阈值均翻倍 如果之前这个桶的节点类型是树，需要把新哈希表里当前桶也变成树形结构 复制给新哈希表中需要重新索引，这里采用的计算方法是 o e.hash & (newCap - 1)，等价于 e.hash % newCap 结合扩容源码可以发现扩容的确开销很大，需要迭代所有的元素，rehash、赋值，还得保留原来的数据结构。 所以在使用的时候，最好在初始化的时候就指定好 HashMap 的长度，尽量避免频繁 resize。 6.HashMap 的获取方法 get * HashMap 另外一个经常使用的方法就是 get(key)，返回键对应的值: 如果 HashMap

32、中包含一个键值对 k-v 满足： (key = null ? k = null : key.equals(k) 就返回值 v，否则返回 null; public V get(Object key) Node e; /还是先计算 哈希值 return (e = getNode(hash(key), key) = null ? null : e.value; final Node getNode(int hash, Object key) Node tab; Node first, e; int n; K k; /tab 指向哈希表，n 为哈希表的长度，first 为 (n - 1) & hash

33、 位置处的桶中的头一个节点 if (tab = table) != null & (n = tab.length) 0 & (first = tab(n - 1) & hash) != null) /如果桶里第一个元素就相等，直接返回 if (first.hash = hash & (k = first.key) = key | (key != null & key.equals(k) return first; /否则就得慢慢遍历找 if (e = first.next) != null) if (first instanceof TreeNode) /如果是树形节点，就调用树形节点的 ge

34、t 方法 return (TreeNode)first).getTreeNode(hash, key); do /do-while 遍历链表的所有节点 if (e.hash = hash & (k = e.key) = key | (key != null & key.equals(k) return e; while (e = e.next) != null); return null; 查找 方法比较简单: 先计算哈希值; 然后再用 (n - 1) & hash 计算出桶的位置; 在桶里的链表进行遍历查找。 时间复杂度一般跟链表长度有关，因此哈希算法越好，元素分布越均匀，get 方法就越快

35、，不然遍历一条长链表，太慢了。 不过在 JDK 1.8 以后 HashMap 新增了红黑树节点，优化这种极端情况下的性能问题。 总结 1.HashMap 有那么多优点，也有个缺点：不是同步的。 当多线程并发访问一个 哈希表时，需要在外部进行同步操作，否则会引发数据不同步问题。 你可以选择加锁，也可以考虑用 Collections.synchronizedMap 包一层，变成个线程安全的 Map： Map m = Collections.synchronizedMap(new HashMap(.); 最好在初始化时就这么做。 2.HashMap 三个视图返回的迭代器都是 fail-fast 的：

36、如果在迭代时使用非迭代器方法修改了 map 的内容、结构，迭代器就会报ConcurrentModificationException 的错。 3.当 HashMap 中有大量的元素都存放到同一个桶中时，这时候哈希表里只有一个桶，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。 针对这种情况，JDK 1.8 中引用了 红黑树 优化这个问题。 4.为什么哈希表的容量一定要是 2的整数次幂? 首先，capacity 为 2的整数次幂的话，计算桶的位置 h&(length-1) 就相当于对 length 取模，提升了计算效率； 其次，c