Android面试必读

HashMap的几个灵魂拷问

2020-10-03  本文已影响0人  千淘萬漉

之前是写过一篇HashMap的原理文章的，比较基础 java基础之数据结构3（Map篇），这篇文章算是对之前内容的一个补充吧。主要讲讲HashMap的数据结构，jdk8改进优化项，以及扩容机制和线程安全问题。

数据结构

数据结构

JDK1.8哈希函数和寻址算法的优化

1、哈希函数优化

hash函数源代码是通过h >>> 16将 h 右移 16 位，因为 int 是 4 字节，32 位，所以右移 16 位后变成：左边 16 个 0 + 右边原 h 的高 16 位；最后把这两个进行异或返回。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

2、寻址算法的优化

putVal() 方法寻找数组中索引位置

tab[i = (n - 1) & hash]

其中n 是这个数组的长度 length，hash 就是上面hash() 方法返回
的值；

3、为啥不用取模运算，为啥要这样设计？

如果采用取模运算，源代码思路就是先对key生成一个整数的hash值，然后对hash值和数组大小做一个相关运算，生成一个索引值。

public int hash(Object key){
    return hash_code(key) % table.length;
}

但是计算机的取模运算不如位运算效率高，而且有一个数学公式，当哈希表长度 length 为 2 的整次幂时， hash & (length - 1) 的计算结果跟 hash % length 一样（前提就是数组的长度必须是2的指数次幂）。

public int hash(Object key){
    return hash_code(key) & (table.length - 1);
}

HashMap的初始大小为16，也就是2^4指数次幂，进行&位运算时，有这么一个特征：

1100 1010
   & 1111
--------------
1100 1010

由于数组长度太小，基本上只利用到了低4位的信息，只有当hashMap的长度达到2的10次、20次才会用到高位信息，因此hash算法进行了改进：

h = key.hashCode() ^ (h >>> 16)

先把16->32的高位向右顺移动16位，然后与原HashCode进行异或（值不相同为1。值相同为0。）运算。这样的话，HashMap 中让 hashCode 的高位也参与了寻址计算（进行扰动），即把 hashCode 高 16 位与 hashCode 进行异或算出 hash，然后根据 hash 来做寻址。

PUT元素的流程

扩容机制和扩容的优化

当HashMap中的元素个数超过容量*loadFactor时（容量=数组大小=bucket数量），就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为 2*16=32，即扩大一倍。具体的扩容流程是啥样的呢？核心源码和文字说明如下：

    /*新容量数组桶大小为旧的table的2倍*/
    void transfer(HashMapEntry[] newTable) {
        /*遍历旧的数组桶table*/
        int newCapacity = newTable.length;
        /*如果这个数组位置上有元素且存在哈希冲突的链表结构则继续遍历链表*/
        for (HashMapEntry<K, V> e : table) {
            /*取当前数组索引位上单向链表的下一个元素*/
            while (null != e) {
                /*重新依据hash值计算元素在扩容后数组中的索引位置*/
                HashMapEntry<K, V> next = e.next;
                /*将数组i的元素赋值给当前链表元素的下一个节点*/
                int i = indexFor(e.hash, newCapacity);
                /*将链表元素放入数组位置*/
                e.next = newTable[i];
                /*将当前数组索引位上单向链表的下一个元素赋值给e进行新的一圈链表遍历*/
                newTable[i] = e;
                e = next;
            }
        }
    }

扩容为什么要引入红黑树呢？因为在元素放置过程中，如果一个对象哈希冲突，都被放置到同一个桶里，则会形成一个链表，我们知道链表查询是线性的（时间复杂度会退化到 O(n)），会严重影响存取的性能。由于红黑树的特点，查找某个特定元素，也只需要O(log n)的开销。

用哈希碰撞发起拒绝服务攻击(DOS，Denial-Of-Service attack),常见的场景是攻击者可以事先构造大量相同哈希值的数据，然后以JSON数据的形式发送给服务器，服务器端在将其构建成为Java对象过程中，通常以Hashtable或HashMap等形式存储，哈希碰撞将导致哈希表发生严重退化，算法复杂度可能上升一个数据级，进而耗费大量CPU资源。

加载因子为何设置为0.75

所以综合了空间利用率和碰撞几率，就取了一个 0.5 到 1.0 的平均数 0.75 作为加载因子。

HashMap是线程安全的吗？

HashMap在put的时候，插入的元素超过了容量（由负载因子决定）的范围就会触发扩容操作，就是rehash，这个会重新将原数组的内容重新hash到新的扩容数组中，在多线程的环境下，存在同时其他的元素也在进行put操作，如果hash值相同，可能出现同时在同一数组下用链表表示，造成闭环，导致在get时会出现死循环，所以HashMap是线程不安全的。

如果想要使用线程安全的HashMap，可以采用ConcurrentHashMap类，这里也有一个比较热门的知识点，这篇文章已经总结的非常简练了，直接看这个文章即可！ConcurrentHashMap面试题

JDK8的ConcurrentHashMap和JDK7的ConcurrentHashMap有什么区别？

ConcurrentHashMap是如何保证并发安全的？

JDK7中ConcurrentHashMap是通过ReentrantLock+CAS+分段思想来保证的并发安全的，在JDK7的ConcurrentHashMap中，首先有一个Segment数组，存的是Segment对象，Segment相当于一个小HashMap，Segment内部有一个HashEntry的数组，也有扩容的阈值，同时Segment继承了ReentrantLock类，同时在Segment中还提供了put，get等方法，比如Segment的put方法在一开始就会去加锁，加到锁之后才会把key,value存到Segment中去，然后释放锁。

同时在ConcurrentHashMap的put方法中，会通过CAS的方式把一个Segment对象存到Segment数组的某个位置中。

同时因为一个Segment内部存在一个HashEntry数组，所以和HashMap对比来看，相当于分段了，每段里面是一个小的HashMap，每段公用一把锁，同时在ConcurrentHashMap的构造方法中是可以设置分段的数量的，叫做并发级别concurrencyLevel.

JDK8中ConcurrentHashMap是通过synchronized+cas来实现了。在JDK8中只有一个数组，就是Node数组，Node就是key，value，hashcode封装出来的对象，和HashMap中的Entry一样，在JDK8中通过对Node数组的某个index位置的元素进行同步，达到该index位置的并发安全。同时内部也利用了CAS对数组的某个位置进行并发安全的赋值。

为何使用synchronized？

JDK8中使用synchronized加锁时，是对链表头结点和红黑树根结点来加锁的，而ConcurrentHashMap会保证，数组中某个位置的元素一定是链表的头结点或红黑树的根结点，所以JDK8中的ConcurrentHashMap在对某个桶进行并发安全控制时，只需要使用synchronized对当前那个位置的数组上的元素进行加锁即可，对于每个桶，只有获取到了第一个元素上的锁，才能操作这个桶，不管这个桶是一个链表还是红黑树。

想比于JDK7中使用ReentrantLock来加锁，因为JDK7中使用了分段锁，所以对于一个ConcurrentHashMap对象而言，分了几段就得有几个ReentrantLock对象，表示得有对应的几把锁。

而JDK8中使用synchronized关键字来加锁就会更节省内存，并且jdk也已经对synchronized的底层工作机制进行了优化，效率更好。

上一篇 下一篇

猜你喜欢

热点阅读