基于哈希表的Map接口的实现。该实现提供所有Map相关操作,且允许空值(value)和空键)(key)。(HashMap类与Hashtable大致等效,不同之处在于它是异步的,并且允许为null。)该类不保证映射的顺序。尤其是,它不能保证顺序会随着时间的推移保持不变。
HashMap非线程安全,是无序的,key和value都允许null,如果你用一个HashMap表示每个节点(value)的父节点(key),就可以用null。
在多线程环境下若使用HashMap需要使用Collections.synchronizedMap()方法来获取一个线程安全的集合。
Note:Collections定义了一个SynchronizedMap的内部类,这个类实现了Map接口,在调用方法时使用synchronized来保证线程同步,当然了实际上操作的还是我们传入的HashMap实例,简单的说就是Collections.synchronizedMap()方法帮我们在操作HashMap时自动添加了synchronized来实现线程同步,类似的其它Collections.synchronizedXX方法也是类似原理。
0x7FFFFFFF 就是INT_MAX
最多允许一个Key为null,但允许多对键值对的value为null。
比如构建一个树结构,key为null就表示这是祖先节点。
地图上key为null表示默认情况。
HashMap以null作为key时,总是存储在table数组的第一个节点上。
死循环:扩容转移后,链表中节点顺序倒置,原节点引用关系发生变化。
但JDK1.8不会死循环,因为扩容转移,链表中节点顺序不变,原节点引用关系不变。(下文重点提到成环问题)
但是put()、get()没加同步锁,多线程操作还是会有问题。
多线程导致元素丢失:多个变成同时addEntry(hash, key, value, i)时,发生哈希碰撞,多个线程得到同样的bucketIndex来存储,就可能覆盖,导致丢失。
(1)HashTable
线程安全的类,但是是利用synchronized给所有方法加锁,性能很差。
(2)ConcurrentHashMap
并发包(rt.jar)下的java.util.concurrent.ConcurrentHashMap,是更好的线程安全方案。
(3)synchronizedMap()
用这个同步方法去包装HashMap Object,得到线程安全的Map,操作这个Map。
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { // 默认初始容量:16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 // 最大容量 static final int MAXIMUM_CAPACITY = 1 << 30; // 默认加载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 当桶(bucket)上的结点数大于这个值时会转成红黑树 static final int TREEIFY_THRESHOLD = 8; // 当桶(bucket)上的结点数小于这个值时树转链表 static final int UNTREEIFY_THRESHOLD = 6; // 桶中结构转化为红黑树对应的table的最小大小 static final int MIN_TREEIFY_CAPACITY = 64; // 存储元素的数组,总是2的幂次倍 transient Node<K,V>[] table; // 存放具体元素的集 transient Set<Map.Entry<K,V>> entrySet; // 存放元素的个数,注意这个不等于数组的长度 transient int size; // 每次扩容和更改map结构的计数器 transient int modCount; // 临界值 当实际大小(容量*填充因子)超过临界值时,会进行扩容 int threshold; // 加载因子 final float loadFactor;
public HashMap() { // 初始化填充因子 this.loadFactor = DEFAULT_LOAD_FACTOR; }
public HashMap(int initialCapacity) { // 调用HashMap(int, float)型构造函数 this(initialCapacity, DEFAULT_LOAD_FACTOR); }
public HashMap(Map<? extends K, ? extends V> m) { // 初始化填充因子 this.loadFactor = DEFAULT_LOAD_FACTOR; // 将m中的所有元素添加至HashMap中 putMapEntries(m, false); }
public HashMap(int initialCapacity, float loadFactor) { //初始容量不能小于0 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); // 如果出事容量大于最大容量,将初始容量置为最大容量 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; // 加载因子必须为大于0的数值 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // 初始化加载因子和扩容临界值 this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }
搞这么复杂,也是为了减少hash冲突。
// 直接用key和容量大小做hash运算的话,只会对低位进行计算,所以可以把key的hashcode右移16位或者做个异或,让高位也能参与hash,进一步减少碰撞率 static final int hash(Object key) { int h; /** * 获取对象的hashcode,然后将该hashcode无符号右移16位(舍弃右边16位,左边补0),然后将右移结果和原hashcode做异或运算(^,同为0,不同为1),并返回结果。 */ return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
// 返回>initialCapacity的最小二次幂值 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 < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { //s为m的实际元素个数 int s = m.size(); if (s > 0) { // 判断table是否已经初始化 if (table == null) { // pre-size // 未初始化,求出需要的容量,+1.0F是因为前面相除的结果通常包含小数部分。 float ft = ((float)s / loadFactor) + 1.0F; //判断容量大小是否超出上限 int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); // 初始化临界值,方法返回大于t且离其最近的2次幂的数 if (t > threshold) threshold = tableSizeFor(t); } // 已初始化,并且m元素个数大于阈值,进行扩容处理 else if (s > threshold) resize(); // 将m中的所有元素添加至HashMap中 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } }
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //tab是hash数组,p是桶的首节点,n是HashMap长度,i是数组下标 Node<K,V>[] tab; Node<K,V> p; int n, i; /** * 如果哈希表未初始化,就对其初始化 * i = (n - 1) & hash, 容量大小(也就是桶的个数)n总是2的次方,n - 1相当于是除了最高位,剩下的位全是1,相当于 hash % n * 但是hash后按位与 n-1,比%模运算取余要快, * 一个元素,它总是需要定位到容器大小范围内的,所以要对大于容量的哈希值取余,定位在数组中的位置。 * 如果这个位置没有元素,那么把put进来的元素,放在数组的这个位置 **/ //获取长度并扩容,其实是懒加载,可以看到table一开始是没有加载的,邓傲put这里才加载。 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //根据对象的哈希值计算对象的存储位置,如果该位置没有元素,就存储元素 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { //发生hash冲突 //临时节点e,k为当前节点的key Node<K,V> e; K k; /** * 存入的元素和以前的元素比较哈希值 * 如果哈希值不同,会继续向下执行,把元素添加到集合 * 如果哈希值相同,会调用对象的equals()方法比较 * 如果返回false,会继续向下执行,把元素添加到集合 * 如果返回true,说明元素重复,不存储 **/ //待插入key和当前节点的hash值相等,e=p即首节点。 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // hash值不等于首节点,那看看它是不是红黑树的节点 else if (p instanceof TreeNode) //是红黑树的节点,如果节点已存在(返回值非null),就返回该节点,put(添加)成功的话返回应该是null才对。 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // hash不等于首节点,是链表的节点 else { //遍历链表 for (int binCount = 0; ; ++binCount) { // 遍历到了尾部,说明key是新的,追加新节点到尾部 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; } } //如果e不是null,说明有需要覆盖的节点,进行覆盖,返回旧值 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; // 空方法,没实现,LinkedHashMap的时候有用到 afterNodeAccess(e); return oldValue; } } //能走到这里,说明key没重复,是新的,插入成功了e的值就是null,修改次数+1 ++modCount; // 如果新增一个元素后,实际长度+1,大小超过了 临界值(容量 * 负载因子),则需要扩容 if (++size > threshold) resize(); // 空方法,没实现 afterNodeInsertion(evict); //添加成功 return null; }
来个文字版看下:
(1)判断node数组是否空或者null,是的话就resize()扩容,默认初始容量16;
(2)根据key计算hash值,得到待插入节点在数组中的索引位置i,如果table[i] == null,就直接添加,跳到(6),不然就到(3);
(3)看看该key是不是和table[i]的首节点一样,一样则覆盖,这里说的一样是hashCode和equals,不然就到(4);
(4)看看table[i]是不是红黑树,是的话遍历看看有没有这个key,没的话直接插入,有的话就直接覆盖;
(5)看看table[i]是不是链表,是的话遍历看看有没有这个key,没的话直接加载链表尾端,再判断下链表长度大于8没,大于8了就转成红黑树,有的话直接覆盖;
(6)插入成功以后,看看键值数是不是超过了最大容量,超过了就扩容。
再重复一遍,初始化是懒加载的,也就是构造了HashMap后,并没有初始化table,一直到put方法执行的时候,才会去初始化或者扩容。
调用resize()的场景有俩:一个是第一次put的时候,发现table是空的,就会调用一次resize()来做初始化;另一个是每次添加完元素,看看size是不是超过阈值了,是的话也会扩容。
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; // old长度 int oldCap = (oldTab == null) ? 0 : oldTab.length; // old临界值 int oldThr = threshold; //new长度、临界值 int newCap, newThr = 0; // 非首次初始化 if (oldCap > 0) { // 超过int最大值,置为int最大值 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //通常情况长度扩容两倍,且如果新长度小于int最大值,old长度大于等于16,临界值也扩容两倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } //如果旧长度小于等于0,但是已经初始化过,比如把元素清空,那临界值还存在的,但是如果是第一次初始化,临界值应该是0才对 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); } // 前置条件就是上面old长度小于16,新临界值还没设置上 if (newThr == 0) { float ft = (float)newCap * loadFactor; // 看下新容量是不是小于最大值,新阈值是否小于int最大值,是的话新阈值就是容量*加载因子,不然就说int最大值 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) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; // 赋值且发现当前桶有值 if ((e = oldTab[j]) != null) { //设置该位置为null,为了方便回收、释放内存 oldTab[j] = null; // 如果没有下一个节点,就把变量值放到新表中,注意e.hash&(newCap-1)跟j没关系 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 { // preserve order 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; }
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; }
主要利用equals()和hashcode。
final Node<K,V> getNode(int hash, Object key) { // first 是头结点 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) { // 如果是头结点,直接返回就好 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; }
加载因子越大,填满的元素越多,空间利用率越高,但冲突的机会加大了。
反之,加载因子越小,填满的元素越少,冲突的机会减小,但空间浪费多了(因为需要经常扩容)。
所以这是一个时间和空间的均衡。
加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时,通过调用 rehash 方法将容量翻倍。
为16,哈希表中桶(Entry数组)的数量,初始容量只是哈希表在创建时的容量。
2^30。
hash桶数组,存储位桶的数组,长度必须为2的幂,在1.7中为Entry数组。
JDK1.8以前,HashMap是采用“数组+链表”存储的,如果hash值相同,那这些数据会存放到同一个链表中去,该链表又称为存储桶(buckets),当一个数据中要存储到Map的时候会根据它的Key的值来计算出它的hash,通过hash来确认存储到数组的位置,如果发生哈希碰撞(跟其他数据的hash值相同)就以链表的形式存储,但是这样如果链表过长来的话,查询效率就会大打折扣。
JDK1.8主要新特性之一就是HashMap引入了红黑树,故而结构变得复杂了,但是效率也大大提升,主要体现在数据量大的时候。当桶内元素达到8个(TREEIFY_THRESHOLD)的时候,HashMap会把这个链表转换成红黑树来存储。链表查找性能是O(n),而树结构能将查找性能提升到O(log(n))。
可以看看这篇文章:阿里面试题:为什么Map桶中个数超过8才转为红黑树
题外话:HashMap继承了AbstractMap,而AbstractMap类实现了Map接口,那为什么HashMap还要在实现Map接口呢?同样在ArrayList中LinkedList中都是这种结构。据说Josh Bloch自己说是写法错误。Why does LinkedHashSet extend HashSet and implement Set
※ Note:执行构造函数时,存储元素的数组并不会进行初始化,而是在第一次放入元素的时候,才会进行初始化操作。创建HashMap对象时,仅仅计算初始容量和新增阈值。
添加一个key-value时,先hash(key)得到hash值,然后indexFor(hash,length)得到存储位置,计算方式是先hash&0x7FFFFFFF,&0x7FFFFFFF是为了把负数转为正,其他位因为是1所以不受影响,再对length取模,相同位置存入链表。
涉及到size(当前数组已用槽数)、threshold(阈值,判断是否需要扩容,等于容量*加载因子)、DEFAULT_LOAD_FACTOR(默认加载因子0.75).
当size>threshold时,扩容。
原理:新建一个HashMap数组,调用transfer(),将旧HashMap的所有元素复制到新的HashMap中(重新计算元素在新数组中的索引位置),可见相当耗时,所以用HashMap的时候最好预估下元素个数,避免扩容。
HashMap中的数组元素和链表元素都是Entry。
差异 | JDK1.7 | JDK1.8 |
---|---|---|
结构 | 数组+链表 | 数组+链表+红黑树 |
查找时间复杂度 | O(N) | O(logN) |
数组元素类型 | Entry | Node or TreeNode |
null key | putForNullKey() | 无特殊调用 |
空hash表 | inflateTable()初始化 | resize()直接扩容 |
hash() | 直接用key的hashCode | key的hashCode异或、无符号右移16位,高低位结合,元素分布更均匀 |
扩容条件 | 容量超过阈值且hash冲突 | 容量超过阈值 |
扩容插值顺序 | 先扩容后插值 | 先插值再扩容 |
插入位置 | 头插法(易逆序且环型链表死循环) | 尾插法(避免逆序和链表死循环问题) |
扩容后存储位置计算方式 | 重新计算数组下表,hash&[需扩容的二进制数] | 扩容前位置+扩容大小值,看原来的hash新增的bit是0还是1,0不变,1的话就是old_index+oldCap |
在这里,说一下JDK1.7 成环的问题。
void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { //e为空时循环结束 while(null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); // 成环的代码主要是在这三行代码 // 首先插入是从头开始插入的 e.next = newTable[i]; newTable[i] = e; e = next; } } }
分析一波:
e.next = newTable[i]
newTable[i]的i是计算出来的,值为null,而e是链表的第一个元素,整句话就是把new table的第i个元素赋值给old table的指定链表上的元素e的下一个元素,第一次循环就是让old table中的某一链表的第一个元素的下一个元素值为null。
https://www.cnblogs.com/wen-he/p/11496050.html
有两个线程同时扩容,A线程执行到Entry<K,V> next = e.next; 的时候CPU时间片用完了,这时候e指向节点a,next指向节点b。
A线程:e=a,next=b
此时B线程执行,刚好a、b、c节点rehash后还是在这个位置,ok,开始移动节点,因为是头插法,复制后顺序反过来了,结束后B线程:
这时候A又开始执行了,e=a,next=b,执行循环体里剩下的逻辑
if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); // 成环的代码主要是在这三行代码 // 首先插入是从头开始插入的 e.next = newTable[i]; newTable[i] = e; e = next;
执行到newTable[i] = e; 时,A线程:
然后执行e = next; 也就是e=b,再执行一次循环, Entry<K,V> next = e.next; 中,b的next是a,哦豁,这样就死循环了。
e=b, next=a:
JDK1.8之前是头插法,而后是尾插法。
头插法可能导致环(死链);
用头插法是考虑热点数据(新插入数据更可能用到),但其实rehash时,迁移到新链表,顺序还是会乱。
目的:计算hash值是散列性更好,减少hash碰撞,结果分布均匀。
想想,2的幂减去1,除了符号位,都是1,再去和hashcode做&操作,得到的基本跟hashcode一样,分布均匀,
HashMap是根据key的hash值决策key放入到哪个桶(bucket)中,通过
tab = [(n - 1) & hash]
公式计算得出。其中tab是一个哈希表。
取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作。
也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方。而且
①&运算速度快,至少比%取模运算快,位运算直接对内存数据进行操作,不需要转成十进制,因此处理速度非常快。
②能保证 索引值 肯定在 capacity 中,不会超出数组长度;
③不同key计算的index相同几率变小,数据在数组上分布均匀,碰撞少些。
④(n - 1) & hash,当n为2次幂时,会满足一个公式:(n - 1) & hash = hash % n
假设n=2^x,x=3,
那么
n = 2^3 = 8,即1000
n - 1=7 ,即0111
hash & (n-1) = hash & 0111 ,结果其实就是hash最后三位,
hash / 8,相当于hash右移3位,得到其商,而这移除的三位就是上面说的最后三位,即余数。
用开放定址法解决冲突的做法是:当冲突发生时,使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找,直到找到给定的关键字,或者碰到一个开放的地址(即该地址单元为空)为止(若要插入,在探查到开放的地址,则可将待插入的新结点存人该地址单元)。查找时探查到开放的 地址则表明表中无待查的关键字,即查找失败。
再哈希法又叫双哈希法,有多个不同的Hash函数,当发生冲突时,使用第二个,第三个,….,等哈希函数
计算地址,直到无冲突。虽然不易发生聚集,但是增加了计算时间。
链地址法的基本思想是:每个哈希表节点都有一个next指针,多个哈希表节点可以用next指针构成一个单向链表,被分配到同一个索引上的多个结点用单向链表连接起来
这种方法的基本思想是:将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表