HashMap和ConcurrentHashMap总结思考

朱雀 2022-09-08 11:45 36阅读 0赞

**1.背景知识：**  
当集合要添加新的对象时，先调用这个对象的hashCode方法，得到对应的hashcode值，在算出Hash值，然后计算数组元素下表的位置。

**2.HashMap中如何计算hash值？如何计算数组元素下表位置？**  
要计算HashMap中对应的数组下标，必然要进行获取哈希值，HashMap对key的哈希值做了离散处理  
**对于HashMap中 key值的hash计算源码如下：**

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

可以看到 HashMap 中的key值可以为null，key值的hash值的计算方法为：key的hash值高16位不变，低16位与高16位异或作为key最终的hash值。（h>>>16，表示无符号右移16位，高位补0）

JDK 8：将原哈希值和左移16位的值，一起异或运算(^)。  
**下标计算：(put方法中摘抄)**

n = tab.length
    i = (n - 1) & hash

是再数组长度减一后，做与运算(&)。因为配合数组长度位2的次方数，所以相当于length-1取余

\**为什么HashMap的容量是2的n次幂？*

当 n 是2的次幂时， n - 1 通过 二进制表示即尾端一直都是以连续1的形式表示的。当(n - 1) 与 hash 做与运算时，会保留hash中 后 x 位的 1，这样就保证了索引值 不会超出数组长度。

**这样做的好处在于：**

&运算速度快，至少比%取模运算快

能保证索引值肯定在HashMap的容量大小范围内

(n - 1) & hash的值是均匀分布的，可以减少hash冲突  
**同时当n为2次幂时，会满足一个公式：(n - 1) & hash = hash % n。**

**3.HashMap中put进一个元素的过程？**  
1）先进行容量的判断，如果当前容量达到了阈值，先进性2倍扩容操作，重新计算hash值，和数组存储的位置，扩容后的链表顺序与扩容前的链表顺序相反。在1.8之前用头插法将Entry对象插入到链表的头部。  
但是这种操作在高并发的环境下容易导致死锁，所以1.8之后，新插入的元素都放在了链表的尾部

2）判断table\[i\]的首个元素是否和key一样，如果相同直接覆盖value，否则转向3，这里的相同指的是hashCode以及equals；

3）.判断table\[i\] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向4；

4）.遍历table\[i\]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；

5）.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

**ConcurrentHashMap：**  
以Node数组 或者 红黑树的方式存储对象，当存储的键值对出现冲突 ，且冲突的数量比较多时，用红黑树的方式能够提升数据读写的性能

1.ConcurrentHashMap底层存储元素时，Node数组存储节点，Node数组实现了Map.Entry<K,V>

static class Node<K,V> implements Map.Entry<K,V> {
        
    
        final int hash;
    
        final K key;
    
        volatile V val;
    
        volatile Node<K,V> next;

**通过volatile 修饰val 和next，为什么要使用volatile？**

因为：多个线程会先把对象保存在本线程内部的内存中，随后再回写到主内存，这样操作的弊端是，当多线程并发时，就有可能引发数据问题  
而变量一旦被 volatile 修饰，那么多个线程会直接读写主内存中的该变量，这样就避免了引发数据冲突

**2.ConcurrentHashMap底层put进一个元素的过程？如何确保多线程安全性？**

通过源码可以得知  
put 方法 调用putVal方法实现了向 Node 数组或 TreeBin 红黑树中 添加数据。

1.首先如果Node数组为空 则调用init方法 初始化数组，同时计算hash值，并定位到Node中的位置， 如果Node 位置为空则没有冲突，则以 CAS 方式插入，多个线程尝试使用 CAS 同时更新同一个变量时， 只有其中一个线程能更新变量的值，而其他线程都失败，失败的线程并不会被挂起，而是被告知这次竞争中失败， 可以再次进行尝试  
2.如果Node数组不为空，则对该 Node 加 synchronized 锁，并加入到该 Node 所指向的链表里， 如当前 Node 里包含的链表节点数大于 8，则用 treeifyBin 方法把链表转红黑树，

**3.读一个元素的过程？**  
在读数据时，首先会计算 key 的 hash 值，如果 Node 数组里匹配到首结点即返回，否则调用 next 方法遍历链表或红黑树，由于可能会有冲突，因此需调用 equals 方法

**底层实现多线程安全的原理机制：synchronized+CAS 的并发策略**

**三：面试常问的问题**  
**1. 你了解volatile,Synchronized或CAS机制吗？**

我知道，另外我还知道 ConcurrentHashMap 对象中用到这些

**2.当问及任何HashMap或者集合的时候，我们引出来ConCurrentHashMap， 谈及并发，线程安全性。多线程写操作**

讲到ConcurrentHashMap的底层， Node, 红黑树，volatile

ConcurrentHashMap 对象是根据哈希表结构存储键值对数据，以及用桶链路的方式处理冲突

**加分调优项：**

**1）展示内存性能调优方面的技能**  
在项目上线前，我们做了压力测试，从中发现订单等模块的内存用量过大，通过观察日志，我们发现是由于 ConcurrentHashMap 对象保存的数据过多，用完以后没及时 clear 掉，由此引发了 OOM 问题。  
因此当我们用好数据以后，应该立即 clear 掉该 ConcurrentHashMap 对象，内存性能就会好很多了。

**2）展示多线程环境下数据读写方面的调优技能**

在项目的数据同步模块中，需要把客户文件缓存到本地读写。一开始我们用的是 HashMap，但 HashMap 不是线程安全的，所以读写时都用了 Synchronized 关键字，这样处理的弊端是，当读写线程个数变多时，由于只有一个线程能读写，因此其他线程会阻塞。不仅性能慢，而且还会导致死锁。

后来我们改用 ConcurrentHashMap 对象，该对象对读操作不加锁，对写操作时会采用 synchronized+CAS 的并发策略，所以一定程度上提升了读写性能。

https://blog.csdn.net/q5706503/article/details/85171474

**什么是CAS:**

else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
        
        if (casTabAt(tab, i, null, 
            new Node<K,V>(hash, key, value)))
            break;                   // no lock when adding to empty bin
    
    }

CAS 的含义是 Compare And Swap，CAS(V,E,N)，若 V 等于 E，则将 V 设为 N。若 V 和 E 不等，则说明已有其他线程做了更新，当前线程什么都不做，或更改 V、E 和 N 参数再重试。  
https://blog.csdn.net/qq\_41345773/article/details/92066554

**HashCode背景知识**

**1.判断两个对象相等可以用hashcode比较吗？**  
回答是不可以。你必须用equals方法！两个不同对象可能hashcode相等，但两个不同hashcode的对象一定不同。  
另外一点，如果覆写了equals方法，必须覆写hashcode方法，原因是默认的hashcode是将对象的存储地址进行映射。  
而且逻辑上，如果两个对象的equals方法返回是相等的，那么它们的hashcode必须相等；反之不一定成立

**2.什么是HashCode**  
Java中的hashCode方法就是根据一定的规则将与对象相关的信息（比如对象的存储地址，对象的字段等）映射成一个数值，  
这个数值称作为散列值。即在散列集合包括HashSet、HashMap以及HashTable里，  
对每一个存储的桶元素都有一个唯一的"块编号"，即它在集合里面的存储地址；当你调用contains方法的时候，  
它会根据hashcode找到块的存储地址从而定位到该桶元素

**设计hashCode()时最重要的因素就是：无论何时，对同一个对象调用hashCode()都应该产生同样的值。**  
如果在讲一个对象用put()添加进HashMap时产生一个hashCdoe值，而用get()取出时却产生了另一个hashCode值，  
那么就无法获取该对象了。所以如果你的hashCode方法依赖于对象中易变的数据，用户就要当心了，因为此数据发生变化时，  
hashCode()方法就会生成一个不同的散列码。