浅析HashMap和concurrenthashmap的线程安全问题

Bertha 。 2023-07-22 03:55 4阅读 0赞

**一.hash碰撞和解决方案**  
**对象Hash的前提是实现equals()和hashCode()两个方法，那么HashCode()的作用就是保证对象返回唯一hash值，但当两个对象计算值一样时，这就发生了碰撞冲突**  
解决方案:  
**1.开放地址法**  
开放地执法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)  
其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,…m-1，称线性探测再散列。  
如果di取1，则每次冲突之后，向后移动1个位置.如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,…k*k,-k*k(k<=m/2)，称二次探测再散列。  
如果di取值可能为伪随机数列。称伪随机探测再散列。

**2.再哈希法**  
当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。  
比如上面第一次按照姓首字母进行哈希，如果产生冲突可以按照姓字母首字母第二位进行哈希，再冲突，第三位，直到不冲突为止

**3.链地址法（拉链法）**  
将所有关键字为同义词的记录存储在同一线性链表中。如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTU4ODc1MQ_size_16_color_FFFFFF_t_70]  
4.建立一个公共溢出区  
假设哈希函数的值域为\[0,m-1\],则设向量HashTable\[0…m-1\]为基本表，另外设立存储空间向量OverTable\[0…v\]用以存储发生冲突的记录。

拉链法的优缺点：  
优点：  
①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；  
②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；  
③开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；  
④在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结 点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

缺点：  
指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。

**二.HashMap为什么是线程不安全的？**  
HashMap底层是一个Entry数组，当发生hash冲突的时候，hashmap是采用**链表**的方式来解决的，**在对应的数组位置存放链表的头结点**。对链表而言，新加入的节点会从头结点加入

1.在hashmap做put操作的时候会调用下面方法：

// 新增Entry。将“key-value”插入指定位置，bucketIndex是位置索引。 
        void addEntry(int hash, K key, V value, int bucketIndex) {       
            // 保存“bucketIndex”位置的值到“e”中 
            Entry<K,V> e = table[bucketIndex];      
            // 设置“bucketIndex”位置的元素为“新Entry”， 
            // 设置“e”为“新Entry的下一个节点” 
            table[bucketIndex] = new Entry<K,V>(hash, key, value, e);      
            // 若HashMap的实际大小 不小于 “阈值”，则调整HashMap的大小 
            if (size++ >= threshold)      
                resize(2 * table.length);      
        }

在hashmap做put操作的时候会调用到以上的方法。现在假如A线程和B线程同时对同一个数组位置调用addEntry，两个线程会同时得到现在的头结点，然后A写入新的头结点之后，B也写入新的头结点，那B的写入操作就会覆盖A的写入操作造成A的写入操作丢失

2.删除键值对的代码

final Entry<K,V> removeEntryForKey(Object key) {       
            // 获取哈希值。若key为null，则哈希值为0；否则调用hash()进行计算 
            int hash = (key == null) ? 0 : hash(key.hashCode());      
            int i = indexFor(hash, table.length);      
            Entry<K,V> prev = table[i];      
            Entry<K,V> e = prev;      
         
            // 删除链表中“键为key”的元素 
            // 本质是“删除单向链表中的节点” 
            while (e != null) {       
                Entry<K,V> next = e.next;      
                Object k;      
                if (e.hash == hash &&      
                    ((k = e.key) == key || (key != null && key.equals(k)))) {       
                    modCount++;      
                    size--;      
                    if (prev == e)      
                        table[i] = next;      
                    else     
                        prev.next = next;      
                    e.recordRemoval(this);      
                    return e;      
                }      
                prev = e;      
                e = next;      
            }      
         
            return e;      
        }

当多个线程同时操作同一个数组位置的时候，也都会先取得现在状态下该位置存储的头结点，然后各自去进行计算操作，之后再把结果写会到该数组位置去，其实写回的时候可能其他的线程已经就把这个位置给修改过了，就会覆盖其他线程的修改。

3.addEntry中当加入新的键值对后键值对总数量超过门限值的时候会调用一个resize操作，代码如下：

// 重新调整HashMap的大小，newCapacity是调整后的容量 
        void resize(int newCapacity) {       
            Entry[] oldTable = table;      
            int oldCapacity = oldTable.length;     
            //如果就容量已经达到了最大值，则不能再扩容，直接返回 
            if (oldCapacity == MAXIMUM_CAPACITY) {       
                threshold = Integer.MAX_VALUE;      
                return;      
            }      
         
            // 新建一个HashMap，将“旧HashMap”的全部元素添加到“新HashMap”中， 
            // 然后，将“新HashMap”赋值给“旧HashMap”。 
            Entry[] newTable = new Entry[newCapacity];      
            transfer(newTable);      
            table = newTable;      
            threshold = (int)(newCapacity * loadFactor);      
        }

这个操作会新生成一个新的容量的数组，然后对原数组的所有键值对重新进行计算和写入新的数组，之后指向新生成的数组。  
当多个线程同时检测到总数量超过门限值的时候就会同时调用resize操作，各自生成新的数组并rehash后赋给该map底层的数组table，结果最终只有最后一个线程生成的新数组被赋给table变量，其他线程的均会丢失。而且当某些线程已经完成赋值而其他线程刚开始的时候，就会用已经被赋值的table作为原始数组，这样也会有问题。

**三.concurrenthashmap怎么实现线程安全的?**  
ConcurrentHashMap定义了Segment内部类，看一下代码：

//Segment继承了ReentrantLock重入锁（这个概念这次先不看）
    static final class Segment<K,V> extends ReentrantLock implements Serializable { 
        //HashEntry与HashMap中类似，可以理解为一个单向链表元素，作为存放相同hash值,不同key的键值对,因为:ConcurrentHashMap通过数组形式存放多个Segment，用key的hash值做一次再hash,当做下标,识别当前键值对存放在segments数组中的哪个segment里。
        //这样一个Segment就相当于一个HashMap
        transient volatile HashEntry<K,V>[] table;
        V put(K key, int hash, V value, boolean onlyIfAbsent) { 
            //在对Segment进行操作时，对当前对象Segment加锁
            lock();
            try { 
            //数据操作
            } finally { 
               unlock();
            }
        }
    
    }

ConcurrentHashMap通过数组形式存放多个Segment，用key的hash值做一次再hash当做下标识别当前键值对存放在哪个segment里。

final Segment<K,V>[] segments;
      public V put(K key, V value) { 
            if (value == null)
                throw new NullPointerException();
            //用key的hashCode再做一次hash
            int hash = hash(key.hashCode());
            return segmentFor(hash).put(key, hash, value, false);
        }

在对segment元素进行操作时加锁，这样当其它人线程操作当前ConcurrentHashMap对象时，只要key1的hash值(hash(key1.hashCode()))与加锁key2的值(hash(key2.hashCode()))不同，就可以直接操作其它Segment元素。  
ConcurrentHashMap 有 16 个 Segments ，所以理论上，这个时候，最多可以同时支持 16 个线程并发写，只要它们的操作分别分布在不同的 Segment 上。这个值可以在初始化的时候设置为其他值，但是一旦初始化以后，它是不可以扩容的。

面试题:  
**为什么String, Interger这样的wrapper(封装)类适合作为键?**  
答:因为String是不可变的，也是final的，而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点

**hashmap的工作原理?**  
HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，让后找到bucket位置来储存值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用LinkedList来解决碰撞问题，当发生碰撞了，对象将会储存在LinkedList的下一个节点中。 HashMap在每个LinkedList节点中储存键值对对象。

当两个不同的键对象的hashcode相同时会发生什么？ 它们会储存在同一个bucket位置的LinkedList中。键对象的equals()方法用来找到键值对。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTU4ODc1MQ_size_16_color_FFFFFF_t_70]: /images/20230528/13c0c3e61b114e11b6a33c499241b43f.png