跳至主要內容

HashMap(一)

ZnyoungJava集合HashMap

HashMap的数据结构

在Java中，保存数据有两种比较简单的数据结构：数组和链表。

数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。

常用的哈希函数的冲突解决办法中有一种方法叫做链地址法，其实就是将数组和链表组合在一起，发挥了两者的优势，我们可以将其理解为链表的数组。在JDK 1.8之前，HashMap就是通过这种结构来存储数据的。

我们可以从上图看到，左边很明显是个数组，数组的每个成员是一个链表。该数据结构所容纳的所有元素均包含一个指针，用于元素间的链接。我们根据元素的自身特征把元素分配到不同的链表中去，反过来我们也正是通过这些特征找到正确的链表，再从链表中找出正确的元素。其中，根据元素特征计算元素数组下标的方法就是哈希算法，即本文的主角hash()函数（当然，还包括indexOf()函数）。

HashMap、Hashtable和ConcurrentHashMap的区别

HashMapHashtableConcurrentHashMap
线程安全否是，基于方法锁是，基于分段锁
继承关系AbstractMapDictionaryAbstractMap，ConcurrentMap
允许null值K-V都允许K-V都不允许K-V都不允许
默认初始容量161116
默认加载因子0.750.750.75
扩容后容量原来的两倍原来的两倍加1原来的两倍
是否支持fail-fast支持不支持fail-safe

线程安全

HashMap是非线程安全的。

Hashtable 中的方法是同步的，所以它是线程安全的。

ConcurrentHashMap在JDK 1.8之前使用分段锁保证线程安全， ConcurrentHashMap默认情况下将hash表分为16个桶（分片），在加锁的时候，针对每个单独的分片进行加锁，其他分片不受影响。锁的粒度更细，所以他的性能更好。

ConcurrentHashMap在JDK 1.8中，采用了一种新的方式来实现线程安全，即使用了CAS+synchronized，这个实现被称为"分段锁"的变种，也被称为"锁分离"，它将锁定粒度更细，把锁的粒度从整个Map降低到了单个桶。

继承关系

HashTable是基于陈旧的Dictionary类继承来的。

HashMap继承的抽象类AbstractMap实现了Map接口。

ConcurrentHashMap同样继承了抽象类AbstractMap，并且实现了ConcurrentMap接口。

是否允许null值

HashTable中，key和value都不允许出现null值，否则会抛出NullPointerException异常。

HashMap中，null可以作为键或者值都可以。

ConcurrentHashMap中，key和value都不允许为null。

默认初始容量和扩容机制

HashMap的默认初始容量为16，默认的加载因子为0.75，即当HashMap中元素个数超过容量的75%时，会进行扩容操作。扩容时，容量会扩大为原来的两倍，并将原来的元素重新分配到新的桶中。

Hashtable，默认初始容量为11，默认的加载因子为0.75，即当Hashtable中元素个数超过容量的75%时，会进行扩容操作。扩容时，容量会扩大为原来的两倍加1，并将原来的元素重新分配到新的桶中。

ConcurrentHashMap，默认初始容量为16，默认的加载因子为0.75，即当ConcurrentHashMap中元素个数超过容量的75%时，会进行扩容操作。扩容时，容量会扩大为原来的两倍，并会采用分段锁机制，将ConcurrentHashMap分为多个段(segment)，每个段独立进行扩容操作，避免了整个ConcurrentHashMap的锁竞争。

遍历方式实现的不同

HashMap使用EntrySet进行遍历，即先获取到HashMap中所有的键值对(Entry)，然后遍历Entry集合。支持fail-fast，也就是说在遍历过程中，若HashMap的结构被修改（添加或删除元素），则会抛出ConcurrentModificationException。如果只需要遍历HashMap中的key或value，可以使用KeySet或Values来遍历。

Hashtable使用Enumeration进行遍历，即获取Hashtable中所有的key，然后遍历key集合。遍历过程中，Hashtable的结构发生变化时，Enumeration会失效。

ConcurrentHashMap使用分段锁机制，因此在遍历时需要注意，遍历时ConcurrentHashMap的某个段被修改不会影响其他段的遍历。可以使用EntrySet、KeySet或Values来遍历ConcurrentHashMap，其中EntrySet遍历时效率最高。遍历过程中，ConcurrentHashMap的结构发生变化时，不会抛出ConcurrentModificationException异常，但是在遍历时可能会出现数据不一致的情况，因为遍历器仅提供了弱一致性保障。

HashMap在get和put时经过哪些步骤？

对于HashMap来说，底层是基于散列算法实现，散列算法分为散列再探测和拉链式。HashMap 则使用了拉链式的散列算法，即采用数组+链表/红黑树来解决hash冲突，数组是HashMap的主体，链表主要用来解决哈希冲突。这个数组是Entry类型，它是HashMap的内部类，每一个Entry包含一个key-value键值对。

get方法

对于get方法来说，会先查找桶，如果hash值相同并且key值相同，则返回该node节点，如果不同，则当node.next!=null时，判断是红黑树还是链表，之后根据相应方法进行查找。

put方法

  • 如果数组没有被初始化，先初始化数组

  • 首先通过定位到要put的key在哪个桶中，如果该桶中没有元素，则将该要put的entry放置在该桶中

  • 如果该桶中已经有元素，则遍历该桶所属的链表：

    • 如果该链表已经树化，则执行红黑树的插入流程

  • 如果仍然是链表，则执行链表的插入流程，如果插入后链表的长度大于等于8，并且桶数组的容量大于等于64，则执行链表的树化流程

  • 注意：在上面的步骤中，如果元素和要put的元素相同，则直接替换

  • 校验是新增KV还是替换老的KV，如果是后者，则设置callback扩展（LinkedHashMap的LRU即通过此实现）

  • 校验++size是否超过threshold，如果超过，则执行扩容流程

HashMap如何定位key

通过源码发现，hashMap定位tableIndex的时候，是通过 (table.length - 1) & (key.hashCode ^ (key.hashCode >> 16))，而不是常规的key.hashCode % (table.length)呢？

  • 为什么是用&而不是用%：因为&是基于内存的二进制直接运算，比转成十进制的取模快的多。以下运算等价：X % 2^n = X & (2^n – 1)。这也是hashMap每次扩容都要到2^n的原因之一
  • 为什么用key.hash ^ (key.hash >> 16)而不是用key.hash：这是因为增加了扰动计算，使得hash分布的尽可能均匀。因为hashCode是int类型，虽然能映射40亿左右的空间，但是，HashMap的table.length毕竟不可能有那么大，所以为了使hash%table.length之后，分布的尽可能均匀，就需要对实例的hashCode的值进行扰动，说白了，就是将hashCode的高16和低16位，进行异或，使得hashCode的值更加分散一点。

为什么HashMap的容量是2^n，如何保证

为什么是2^n

HashMap是通过(table.length - 1) & (key.hashCode ^ (key.hashCode >> 16))定位tableIndex的。

为什么是用&而不是用%呢？因为&是基于内存的二进制直接运算，比转成十进制的取模快的多。又因为X % 2^n = X & (2^n – 1)，可以把%运算转换为&运算。所以，hashMap的capcatiy一定要是2^n。这样，HashMap计算hash的速度才够快。

如何保证

初始化时期保证

当我们通过HashMap(int initialCapacity)设置初始容量的时候，HashMap并不一定会直接采用我们传入的数值，而是经过计算，得到一个新值，目的是提高hash的效率。(1->1、3->4、7->8、9->16)

在JDK 1.7和JDK 1.8中，HashMap初始化这个容量的时机不同。JDK 1.8中，在调用HashMap的构造函数定义HashMap的时候，就会进行容量的设定。而在JDK 1.7中，要等到第一次put操作时才进行这一操作。

扩容时期保证

除了初始化的时候回指定HashMap的容量，在进行扩容的时候，其容量也可能会改变。
HashMap有扩容机制，就是当达到扩容条件时会进行扩容。HashMap的扩容条件就是当HashMap中的元素个数（size）超过临界值（threshold）时就会自动扩容。
在HashMap中，threshold = loadFactor * capacity。
loadFactor是装载因子，表示HashMap满的程度，默认值为0.75f，设置成0.75有一个好处，那就是0.75正好是3/4，而capacity又是2的幂。所以，两个数的乘积都是整数。
对于一个默认的HashMap来说，默认情况下，当其size大于12(16*0.75)时就会触发扩容。

为什么HashMap的默认负载因子设置成0.75

因为当key被hash之后，是非常有可能产生碰撞的，当容量满了的时候，size是非常有可能大于capacity的，这样就会导致某个Entry下引用了很长的链表，最终的结果就是虽然节省了空间，但是查询和插入都会很耗时间。

一般来说，默认的负载因子(0.75)在时间和空间成本之间提供了很好的权衡。更高的值减少了空间开销，但增加了查找成本(反映在HashMap类的大多数操作中，包括get和put。

为什么最终选定了0.75呢？因为threshold=loadFactor*capacity，并且capacity永远都是2的幂，为了保证负载因子（loadFactor） * 容量（capacity）的结果是一个整数，这个值是0.75(3/4)比较合理，因为这个数和任何2的幂乘积结果都是整数。

HashMap是如何扩容的

为什么需要扩容？假设现在散列表中的元素已经很多了，但是现在散列表的链化已经比较严重了，哪怕是树化了，时间复杂度也没有O(1)好，所以需要扩容来降低Hash冲突的概率，以此来提高性能。

当++size > threshold 之后(详见java.util.HashMap#putVal方法)，HashMap就会初始化新的新的桶数组，该桶数组的size为原来的两倍，在扩大桶数组的过程中，会涉及三个部分：

桶元素重新映射

如果桶中只有一个元素，没有形成链表，则将原来的桶引用置为null，同时，将该元素进行rehash即可。

链表重新链接

假设有4个key，分别为a，b，c，d，且假定他们的hash值如下：

hash(a) = 3; hash(a) & 7 = 3; hash(a) & 8 = 0
hash(b) = 11; hash(b) & 7 = 3; hash(a) & 8 = 1
hash(c) = 27; hash(c) & 7 = 3; hash(c) & 8 = 1
hash(d) = 59; hash(d) & 7 = 3; hash(d) & 8 = 1

假如此时HashMap的cap为8，某个桶中已经形成链表，则可得到：table[3]=a->b->c->d
如果此时扩容，将newCap设为16，我们可以看到如下结果：

hash(a) = 3; hash(a) & 15 = 3; 
hash(b) = 11; hash(b) & 15 = 11
hash(c) = 27; hash(c) & 15 = 11
hash(d) = 59; hash(d) & 15 = 11

我们会发现，当hash(k) & oldCap = 0时，这些链表的节点还是在原来的节点中，同时如果hash(k) & oldCap = 1时，这些链表的节点会到桶新增的位置中，且都是同一个桶。
所以，对于链表来说，我们就不用逐个节点重新映射，而是直接通过hash(k) & oldCap进行分类，之后统一移动他们的位置即可。

取消树化

有了上面链表重新连接的经验，我们会发现，其实树化后的节点，也可以使用该操作来降低红黑树每个节点rehash时的时间复杂度，所以红黑树的TreeNode继承了链表的Node类，有了next字段，这样就可以像链表一样重新链接。

当操作完结后，HashMap会检测两个链表的长度，当元素小于等于6的时候，就会执行取消树化的操作，否则就会将新生成的链表重新树化。

上次编辑于:
贡献者: 麦正阳