Java源码之HashMap

最后更新于:2022-04-01 09:37:51

**Java源码之HashMap** 转载请注意出处:[http://blog.csdn.net/itismelzp/article/details/50525647](http://blog.csdn.net/itismelzp/article/details/50525647) # 一、HashMap概述 HashMap基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了不同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)此类不保证映射的顺序,特别是它不保证该顺序恒久不变。 值得注意的是HashMap不是线程安全的,如果想要线程安全的HashMap,可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。 ~~~ Map map = Collections.synchronizedMap(new HashMap()); ~~~ # 二、HashMap中的数据结构 ### 1.jdk1.8之前 在jdk1.8之前的HashMap是基于**数组+链表**来实现,即严蔚敏版《数据结构》中**哈希表(散列表)**链地址法,哈希表的优点是查询速度快。 HashMap中主要是通过key的hashCode来计算hash值,只要hashCode相同,计算出来的hash值就一样。如果存储的对象多了,就有可能不同的对象映射到相同的hash值,这就是所谓的hash冲突。HashMap中所用解决hash冲突的方法是链地址法。 可参考严蔚敏版《数据结构》哈希表解决hash冲突的**链地址法**。 ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-02-24_56cd26a207584.jpg) 图中,黄色部分即代表哈希表,也称为哈希数组,数组的每个元素都是一个单链表的头节点,链表是用来解决冲突的,如果不同的key映射到了数组的同一位置处,就将其放入单链表中。 ### 2.jdk1.8中HashMap的实现方式 jdk1.8中对HashMap做的很大的改进,采用**数组+链表+红黑树**实现,当链表长度超过阈值(8)时,将链表转换为红黑树,大大减少了hash冲突时查找时间(从原来的O(n)->O(logn))。由于红黑树的结点空间是链表空间的2倍,为了节省空间,当链表长度减少(如删除操作)到阈值(6)时,又会转换为链表形式。 链表中的结点对应HashMap中的Node类(jdk1.8之前用的是Entry类,原理差不多),具体如下: ~~~ // Node是单向链表,实现了Map.Entry接口 static class Node<K,V> implements Map.Entry<K,V> { final int hash; // hash值 final K key; // 键 V value; // 值 Node<K,V> next; // 指向下一个结点 /* * 构造函数 * 利用(hash值、键、值、下一个结点)来构造结点 */ 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 V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final String toString() { return key + "=" + value; } // 实现hashCode() public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } // 判断两个结点是否相等 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; } } ~~~ HashMap其实就是一个Node数组,Node对象中包含了键和值,其中next也是一个Node对象,它用来处理hash冲突, 使具有相同hash值的结点连在一个链表或树中。 下面是红黑树结点: 它继承自LinkedListMap.Entry,这是一种双链表结点(具体可参考[【Java源码之LinkedHashMap】](http://blog.csdn.net/itismelzp/article/details/50554412))。 ~~~ /** * 红黑树结点,继承自LinkedHashMap.Entry */ static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // 指向父结点 TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; // 结点颜色(红或黑) TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); } /** * 返回当前节点所在树的树结点 */ final TreeNode<K,V> root() { for (TreeNode<K,V> r = this, p;;) { if ((p = r.parent) == null) return r; r = p; } } } ~~~ # 三、HashMap源码 ### 1.头文件 ~~~ package java.util; import java.io.IOException; import java.io.InvalidObjectException; import java.io.Serializable; import java.lang.reflect.ParameterizedType; import java.lang.reflect.Type; import java.util.function.BiConsumer; import java.util.function.BiFunction; import java.util.function.Consumer; import java.util.function.Function; ~~~ ### 2.继承情况 ~~~ public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable ~~~ ### 3.属性 ~~~ /** * 默认初始容量 - 必须是2的幂次方 */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16 /** * 最大容量 */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * 当构造函数不指定时,默认(Hash表)装载因子。 */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * 链表->红黑树的阈值 */ static final int TREEIFY_THRESHOLD = 8; /** * 红黑树->链表的阈值 */ static final int UNTREEIFY_THRESHOLD = 6; /** * The smallest table capacity for which bins may be treeified. * (Otherwise the table is resized if too many nodes in a bin.) * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts * between resizing and treeification thresholds. */ static final int MIN_TREEIFY_CAPACITY = 64; ~~~ ~~~ /** * 存放元素的Node数组 */ transient Node<K,V>[] table; /** * 装Map用Set集合(可用于迭代Map) */ transient Set<Map.Entry<K,V>> entrySet; /** * map中的包含的元素个数 */ transient int size; /** * HashMap的修改次数 */ transient int modCount; // fail-fast机制,下面有解释 /** * 阈值 - 当实际大小超过临界值时,会进行扩容。threshold = capacity * loadFactor(注意这里的capacity与size的区别) */ int threshold; // 默认情况下是12 /** * 装载因子,表示Hsah表中元素的填满的程度 */ final float loadFactor; ~~~ fail-fast机制:即快速失败机制。当多个线程对同一个集合的内容进行操作时,就可能会产生fail-fast事件。 例如:当某一个线程A通过iterator去遍历某集合的过程中,若该集合的内容被其他线程所改变了; 那么线程A访问集合时,就会抛出ConcurrentModificationException异常,产生fail-fast事件。 ### 4.构造函数(4个) ~~~ /** * 构造函数一:指定初始容量和装载因子 */ public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); // tableSizeFor方法会将initialCapacity转化成2的幂次方,详见tableSizeFor方法 } /** * 构造函数二:指定初始容量并使用默认装载因子(0.75) */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * 构造函数三:使用默认初始容量(16)和默认装载因子(0.75) */ public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } /** * 构造函数四:使用另一个Map来构造 */ public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); } ~~~ ### 5.常用方法 ### **(1)hash方法** 严版《数据结构》中提到的哈希函数的构造方法有: - 直接定址法 - 数字分析法 - 平方取中法 - 折叠法 - 除留取余法 在**Hashtable**中用的是 **除留取余法**, 即便于计算,又能减少冲突。 ~~~ index = (hash & 0x7FFFFFFF) % tab.length; ~~~ 但是取模中的除法运算效率很低,HashMap则通过h & (length - 1)替代取模,得到所在数组位置,这样效率会高很多。 ~~~ static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } ~~~ 代码中,首先由key值通过hashCode()方法获取h值,再通过h & (length - 1)来得到所在数组的位置。 在HashMap实现中还可以看到如下代码取代了jdk1.8以前用while循环来保证哈希表的容量一直是2的整数倍数,用移位操作取代了循环移位。 ~~~ /** * 根据给定的容量cap来构造符合2的次幂的值 */ static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; // ">>>"为右移填0操作,即不管符号位是什么都用0填充 n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } ~~~ 可以从源码看出,在HashMap的构造函数中,都直接或间接的调用了tableSizeFor函数。 下面分析原因:length为2的整数幂保证了length-1最后一位(当然是二进制表示)为**1**,从而保证了取索引操作 h & (length - 1)的最后一位同时有为0和为1的可能性,保证了散列的均匀性。反过来,如果length为奇数时,length-1最后一位为**0**,这样与h按位“与”的最后一位肯定为0,即索引位置肯定是偶数,这样数组的奇数位置全部没有放置元素,浪费了大量空间。 ### (2)数据读取:get和getNode方法 ~~~ /** * 根据key返回对应的value值 */ public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } /** * 实现Map.get和相关方法 */ final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // 使用hash & (length-1)得到所在位置 if (first.hash == hash && // 判断头结点 ((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; } ~~~ ### (3)存储数据:put和putValue方法 ~~~ /** * 实现Map.put和相关方法 * 参数hash:key的hash值 * 参数key:要设置的key值 * 参数value:要设置的value值 * 参数onlyIfAbsent if true, don't change existing value * 如果为假,则替换原来的value * 参数evict:if false, the table is in creation mode. * 返回:替换时返回oldValue,非替换时返回null */ 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) // 如果tab为空,则调用resize分配内存 n = (tab = resize()).length; // 使用hash & (lengt-1)得到存入位置,得到插入位置中的结点p if ((p = tab[i = (n - 1) & hash]) == null) // 结点p为null,直接插入 tab[i] = newNode(hash, key, value, null); else { // 插入位置冲突 Node<K,V> e; K k; // 与第一个结点相同:hash值与key值相同(1) if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 与第一个结点不相同 else if (p instanceof TreeNode) // 红黑树情况 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { // 链表情况 for (int binCount = 0; ; ++binCount) { // p从表头依次后移 if ((e = p.next) == null) { // 到达链尾 p.next = newNode(hash, key, value, null); // 接入链尾 if (binCount >= TREEIFY_THRESHOLD - 1) // 达到(链->树)阈值 treeifyBin(tab, hash); break; } // 找到"相同"对象:hash值与key值相同(2) if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; // p后移:p=p.next } } // 处理上述两处hash值与key值相同 if (e != null) { // 已有key值 V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) // 如果size>threshold时进行扩容,见后面的reise()函数 resize(); afterNodeInsertion(evict); return null; } ~~~ ### (4)扩容策略:resize方法 当**size > threshold**时调用resize()扩容。 ~~~ /** * 初始化或加倍容量大小。 * * 返回新的hash table数组 */ 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; // 阈值加倍 } else if (oldThr > 0) // 用阈值初始值新的容量 newCap = oldThr; else { // 当阈值==0时 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]; // 下面是将旧tab中的Node转移到新tab中,分链表和红黑树两种情况 table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) // 红黑树情况 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // 链表情况 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.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; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; } ~~~
';