`

concurrentHashMap and Hashtable简单总结

 
阅读更多
参考 : 探索 ConcurrentHashMap 高并发性的实现机制

 

这两个类都是线程安全的,但是 Hashtable 是通过给每一个方法加锁,(synchronized) ,这样每次操作都会锁住整个表!

   看源码 :

     

public synchronized V get(Object key) {
        Entry tab[] = table;
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return e.value;
            }
        }
        return null;
    }

 

    而 concurretHashMap ,同样它也要加锁,但是它并不是这么霸道,每次不会把整个表都会给锁住!而是只锁住一部分!那么,它是怎么做到的了?

     ConcurrentHashMap 类中包含两个静态内部类 HashEntry 和 Segment。HashEntry 用来封装映射表的键 / 值对;Segment 用来充当锁的角色,每个 Segment 对象守护整个散列映射表的若干个桶。每  个桶是由若干个 HashEntry 对象链接起来的链表。一个 ConcurrentHashMap 实例中包含由若干个 Segment 对象组成的数组。

     HashEntry :

    

static final class HashEntry<K,V> { 
        final K key;                       // 声明 key 为 final 型 ,他们是线程安全的
        final int hash;                   // 声明 hash 值为 final 型 
        volatile V value;                 // volatile ,对所有线程都是可见的
        final HashEntry<K,V> next;      // 声明 next 为 final 型 

        HashEntry(K key, int hash, HashEntry<K,V> next, V value) { 
            this.key = key; 
            this.hash = hash; 
            this.next = next; 
            this.value = value; 
        } 
 }

   Segment类 :如果键能均匀散列,每个 Segment 大约守护整个散列表中桶总数的 1/16。

static final class Segment<K,V> extends ReentrantLock implements Serializable { 
        /** 
         * 在本 segment 范围内,包含的 HashEntry 元素的个数
         * 该变量被声明为 volatile 型
         */ 
        transient volatile int count; 

        /** 
         * table 被更新的次数
         */ 
        transient int modCount; 

        /** 
         * 当 table 中包含的 HashEntry 元素的个数超过本变量值时,触发 table 的再散列
         */ 
        transient int threshold; 

        /** 
         * table 是由 HashEntry 对象组成的数组
         * 如果散列时发生碰撞,碰撞的 HashEntry 对象就以链表的形式链接成一个链表
         * table 数组的数组成员代表散列映射表的一个桶
         * 每个 table 守护整个 ConcurrentHashMap 包含桶总数的一部分
         * 如果并发级别为 16,table 则守护 ConcurrentHashMap 包含的桶总数的 1/16 
         */ 
        transient volatile HashEntry<K,V>[] table; 

        /** 
         * 装载因子
         */ 
        final float loadFactor; 

        Segment(int initialCapacity, float lf) { 
            loadFactor = lf; 
            setTable(HashEntry.<K,V>newArray(initialCapacity)); 
        } 

        /** 
         * 设置 table 引用到这个新生成的 HashEntry 数组
         * 只能在持有锁或构造函数中调用本方法
         */ 
        void setTable(HashEntry<K,V>[] newTable) { 
            // 计算临界阀值为新数组的长度与装载因子的乘积
            threshold = (int)(newTable.length * loadFactor); 
            table = newTable; 
        } 

        /** 
         * 根据 key 的散列值,找到 table 中对应的那个桶(table 数组的某个数组成员)
         */ 
        HashEntry<K,V> getFirst(int hash) { 
            HashEntry<K,V>[] tab = table; 
            // 把散列值与 table 数组长度减 1 的值相“与”,
 // 得到散列值对应的 table 数组的下标
            // 然后返回 table 数组中此下标对应的 HashEntry 元素
            return tab[hash & (tab.length - 1)]; 
        } 
 }

    concurrentHashMap的结构示意图:

       

    在 ConcurrentHashMap 中,线程对映射表做读操作时,一般情况下不需要加锁就可以完成,因为hashEntry的value是volatile的!一定读到的是最新的值!

    对容器做结构性修改的操作才需要加锁,像put(),看下面的源码就知道,它锁住的不是整个表,而是这个segment,同样,这个map包含一个segment数组,

    访问其他的segment的线程还是可以并发的访问的!

    

public V put(K key, V value) { 
        if (value == null)          //ConcurrentHashMap 中不允许用 null 作为映射值
            throw new NullPointerException(); 
        int hash = hash(key.hashCode());        // 计算键对应的散列码
        // 根据散列码找到对应的 Segment 
        return segmentFor(hash).put(key, hash, value, false); 
 }

 

   总结 :

  

ConcurrentHashMap 的高并发性主要来自于三个方面:

  1. 分离锁实现多个线程间的更深层次的共享访问。
  2. HashEntery 对象的不变性(final)来降低执行读操作的线程在遍历链表期间对加锁的需求。
  3. 通过对同一个 Volatile 变量的写 / 读访问,协调不同线程间读 / 写操作的内存可见性。

使用分离锁,减小了请求 同一个锁的频率。

通过 HashEntery 对象的不变性及对同一个 Volatile 变量的读 / 写来协调内存可见性,使得 读操作大多数时候不需要加锁就能成功获取到需要的值。由于散列映射表在实际应用中大多数操作都是成功的 读操作,所以 2 和 3 既可以减少请求同一个锁的频率,也可以有效减少持有锁的时间。

通过减小请求同一个锁的频率和尽量减少持有锁的时间 ,使得 ConcurrentHashMap 的并发性相对于 HashTable 和用同步包装器包装的 HashMap有了质的提高。

   

分享到:
评论

相关推荐

    Java并发编程笔记之ConcurrentHashMap原理探究.docx

    而从Java 8开始,ConcurrentHashMap改用CAS(Compare and Swap)无锁算法,进一步减少了锁的使用,提高了并发性能。在Java 8中,内部结构也发生了变化,将Segment的概念替换为更细粒度的Node链表,使用了更高效的...

    ConcurrentHashMap的实现原理(JDK1.7和JDK1.8).pdf

    - `HashTable`是线程安全的,但其线程安全的实现方式过于简单,所有操作都使用`synchronized`关键字,这使得在高并发环境下性能低下,因为所有操作都被串行化。 **ConcurrentHashMap**: `ConcurrentHashMap`在设计...

    Java-并发容器之ConcurrentHashMap

    此外,`sun.misc.Unsafe`类在ConcurrentHashMap的实现中扮演重要角色,其提供的原子操作方法(如compareAndSwap*)利用CAS算法确保线程安全,这种方法在没有竞争的情况下效率极高,即使发生冲突,重试次数也是有限的...

    concurrenthashmap1.7.docx

    `segment`是`ConcurrentHashMap`内部的一个子类,它继承自`ReentrantLock`,实现了`HashTable`的特性,但支持并发操作。 如果`segment`对象为`null`,`put`方法会调用`ensureSegment(j)`来创建新的`segment`对象。`...

    Java 多线程与并发(13-26)-JUC集合- ConcurrentHashMap详解.pdf

    总结来说,`ConcurrentHashMap`是Java并发编程中的核心组件,它的设计理念和实现方式随着时间的推移不断演进,以适应更高的并发需求和性能优化。理解和掌握其工作原理对于编写高性能并发代码至关重要。

    第二章 ConcurrentHashMap源码分析(JDK8版本)1

    在JDK8中,`ConcurrentHashMap`的实现方式与之前的版本(如JDK6)有了显著变化,去除了Segment锁段的概念,转而采用了一种基于CAS(Compare And Swap)算法的新机制,以提高并发性和效率。 1. **重要的属性** - `...

    Java集合面试题全集

    - **线程安全性**:`ConcurrentHashMap`相比`Hashtable`有更好的性能和可伸缩性,在多线程环境下表现更佳。 #### 十、ConcurrentHashMap线程安全的实现方式 - **JDK1.7**:使用`Segment`作为分段锁,每个`Segment`...

    Java面试

    2. **ConcurrentHashMap与Hashtable**: - **Hashtable**:它是Java中一个古老的线程安全容器,但性能较低,因为全局锁使得所有操作都需要同步。当容器大小增加,遍历时锁定整个表导致性能下降。 - **...

    一文精通HashMap灵魂七问,你学还是不学.doc

    7. **ConcurrentHashMap和HashTable如何实现线程安全?有何不同?** - **ConcurrentHashMap** 使用分段锁(Segment)实现线程安全,每个Segment相当于一个小的HashMap,它们可以并行操作。在Java 8之后,进一步引入...

    并发编程atomic&collections-课上笔记1

    本文主要讲述了 Java 中的并发编程,包括 atomic 包的介绍、CAS 算法的原理、ABA 问题的解决方案,以及 collections 中的 HashMap、HashTable 和 ConcurrentHashMap 的源码分析。 Atomic 包的介绍 ----------------...

    Java并发编程-并发容器1

    总结起来,Java并发编程中的并发容器,尤其是ConcurrentHashMap,通过巧妙的设计和高效的并发机制,如 CAS 操作和synchronized的使用,实现了线程安全且高性能的键值存储。在面临高并发场景时,ConcurrentHashMap...

    2018年阿里一面面试题整理集合

    HashTable则简单使用哈希值模容量。 - **线程安全性**:HashMap是非线程安全的;HashTable是线程安全的,通过`synchronized`关键字实现。 #### HashMap与ConcurrentHashMap **主要区别** - **线程安全性**:...

    阿里一面题目+答案

    以上介绍了阿里Java一面中涉及的一些关键知识点,涵盖了JVM类加载机制、双亲委派模型、`HashMap`与`ConcurrentHashMap`的区别及其线程安全机制、`HashMap`与`HashTable`的区别,以及进程间通信的各种方式。...

    Java进阶知识点汇总.pdf

    - **性能**:`ConcurrentHashMap`相比`HashTable`具有更好的并发性能。 - **key和value是否允许null值**:`ConcurrentHashMap`允许key和value为null,而`HashTable`不允许。 ##### AtomicInteger的实现原理 - `...

    面试真题目录大全,详细版

    1. HashMap 和 Hashtable 的区别 2. HashMap 的底层实现(JDK 1.8 之前和之后) 3. ConcurrentHashMap 的底层原理(CAS+Synchronized) 4. Redis 的数据结构(String、List、Set、Hash、ZSet 等) 5. ZSet 和 Set 的...

    笔记-5、并发容器2

    Segment被移除,取而代之的是一个更简单的基于CAS(Compare and Swap)操作的非阻塞锁结构。新的实现采用了树化(红黑树)的链表,当链表长度超过一定阈值时,链表会自动转换为红黑树,以进一步提高查找、插入和删除...

    一些java面试经验pdf

    - **线程安全的集合**:Vector、HashTable和ConcurrentHashMap是线程安全的。但是,Vector的性能较差,因为它的所有操作都是同步的;ConcurrentHashMap则通过更精细的同步策略提供高效的安全性。 3. **HashMap的...

    Java面经.适用于校招

    - ConcurrentHashMap在性能上优于Hashtable。 2.7 LinkedHashMap - LinkedHashMap是HashMap的子类,内部维护了一个双向链表来维护插入顺序或访问顺序。 2.8 Linkedhashmap与hashmap的区别 - LinkedHashMap维护元素...

Global site tag (gtag.js) - Google Analytics