当前位置： 首页>后端>正文

HashMap与ConcurrentHashMap的故事

后端2024-05-04 06:06:37

要说面试过程中最常出现的身影当属HashMap与ConcurrentHashMap，有时候也会把HashTable拉进来掺和比较一下。有人可能会想为啥是常客，大概率是因为实际工作中确实使用比较多，另外一方面应该是这个话题确实有料可聊吧。

1、HashTable、HashMap与ConcurrentHashMap的分析与比较

HashTable

  • （1）身世：HashTable产生于JDK 1.1，从java.util.HashTable源码来看，这个容器的作者有Arthur van Hoff、Josh Bloch和Neal Gafter。
  • （2）实现：Hashtable 是一个散列表，基于数组+链表的结构实现，它存储的内容是键值对(key-value)映射；初始容量为11，加载因子为0.75；扩容规则为：newsize = olesize*2+1 ；Hashtable采用“链地址法”来解决哈希冲突的。
  • （3）特点：Hashtable 的函数都是同步的，基于synchronized加锁实现，这意味着它是线程安全的；它的key、value都不可以为null；Hashtable中的映射不是有序的。
  • （4）继承体系：Hashtable 继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口。注意其中Dictionary是一个已经被废弃的类。
HashMap与ConcurrentHashMap的故事,第1张
图片.png

HashMap

  • （1）身世：HashMap产生于JDK 1.2，从java.util.HashMap源码来看，作者有Doug Lea、Arthur van Hoff、Josh Bloch和Neal Gafter，多了一个大神Doug Lea，他的杰作之一就是concurrent包。

  • （2）实现：HashMap同样是一个散列表，基于数组+链表的结构实现，其重要的属性有 key , value和用于单向链表的 next；初始容量为16，加载因子为0.75；扩容规则保证数组大小一定是2的n次方；HashMap采用“链地址法”来解决哈希冲突的。

  • （3）特点：实现不是同步的，意味着它不是线程安全的；它的key、value都可以为null；HashMap同样不能保证随着时间的推移Map中的元素次序是不变的。

  • （4）HashMap 1.7与1.8源码区别

    • 存储结构：JDK1.7是数组+链表，JDK1.8是数组+（链表+红黑树）形成，具体来说就是链表长度大于 8 时，有可能会转化成树。在哈希表扩容时，如果发现链表长度小于 6，则会由树重新退化为链表。在转变成树之前，还会有一次判断，只有键值对数量大于64 才会发生转换。

    • 扩容方法：JDK1.8优化了扩容方法，在扩容时保持了原来链表中的顺序，避免出现死循环。(JDK1.7 链表头插 JDK1.8 链表尾插 )

    • Hash方法：Hash算法加入了高位运算，在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

 //JDK1.7 Hash方法，单独考虑了字符串，为字符串设计了Hash方法，
        // 其他类型的变量用一连串的异或操作增加Hash结果的随机性，使得分布尽量均匀
        final int hash(Object k) {     
            int h = hashSeed;  //默认为0      
            if (0 != h && k instanceof String) {    
                return sun.misc.Hashing.stringHash32((String) k); 
            }    
            h ^= k.hashCode();   
            h ^= (h >>> 20) ^ (h >>> 12);   
            return h ^ (h >>> 7) ^ (h >>> 4); 
        }

//JDK1.8 Hash方法，hash方法实现简单得多
static final int hash(Object key) {
        int h;
        return (key == null) 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
  • （5）继承体系：HashMap继承于AbstractMap类，实现了Map接口。实现了Cloneable、java.io.Serializable接口。
HashMap与ConcurrentHashMap的故事,第2张
图片.png

ConcurrentHashMap

  • （1）身世：ConcurrentHashMap是java.util.concurrent包中的重要组成成员。

  • （2）实现：底层采用分段的数组+链表的结构，ConcurrentHashMap是使用了锁分段技术来保证线程安全的，包含三个重要属性，如果用户不指定则会使用默认值，initialCapacity为16，loadFactor为0.75，concurrentLevel为16。

  • （3）特点：get操作不用加锁，put和remove操作需要加锁，size()和containsValue()需要跨段，可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁，这里“按顺序”是很重要的，否则极有可能出现死锁。

  • （4）ConcurrentHashMap 1.7与1.8源码区别

    • 存储结构：JDK1.7版本为Segment分段锁的数据结构；JDK1.8版本是数组+（链表+红黑树）的结构。
    • 线程安全机制：JDK1.7采用segment的分段锁机制实现线程安全，其中segment继承自ReentrantLock；JDK1.8采用CAS+Synchronized保证线程安全。
    • 初始化：JDK1.8初始化操作大大简化，修改为 lazy-load 形式，这样可以有效避免初始开销。
    • 计数方法：JDK1.8新增了一个用与高并发情况的计数工具类java.util.concurrent.atomic.LongAdder，通过空间换时间的优化方式，比java的原子类AtomicLong更加高效。

常见问题分析

  • （1）为什么HashMap的容量一定要是2的整数次幂
    length为2的整数次幂的话，h&(length-1)就相当于对length取模，这样便保证了散列的均匀，同时也提升了效率。

  • （2）HashMap存储对象时，为什么要同时重写hashCode和equals
    即使两个对象的 equals 方法时一致的，但是两个对象的hashCode 返回的 int 值不一致，导致put操作和get操作时，最终存和取的数组下标不同，取出来就是null 。

  • （3）解决hash冲突的办法

    • 1）开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）
    • 2）再哈希法（双重散列，多重散列）：当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。
    • 3）链地址法：HashMap的解决办法就是采用的链地址法，新添加的节点要添加到链表头部。

  • （4）JDK1.7 HashMap扩容时可能存在什么问题
    当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，由于采用头插法，存储在LinkedList中的元素的次序会反过来，容易发生死循环。

  • （5）为什么Key多采用String类型
    由于String是final的，并且重写了equals()和hashCode()方法，不可变可以防止键的改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。重写那两个方法可以减少碰撞的几率。

  • （6）HashMap如何进行扩容
    容量扩充为原来的两倍，然后对每个节点重新计算哈希值，原来 table[i] 中的链表的所有节点，分拆到新的数组的 newTable[i] 和 newTable[i + oldLength] 位置上。

  • （7）迭代器使用的安全问题
    HashMap的迭代器(Iterator)是fail-fast迭代器，迭代器在遍历时，其它线程如果改变了HashMap的结构（增加/移除），将抛出ConcurrentModificationException。
    ConcurrentHashMap迭代器是fail-safe，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。因此无需在迭代期间锁定，ConcurrentHashMap返回的迭代器也是弱一致的。


https://www.xamrdz.com/backend/3a41941472.html

相关文章：