黑马程序员技术交流社区

标题: 【黑马程序员杭州】HashTable和ConcurrentHashTable的区别 [打印本页]

---

作者: 小江哥    时间: 2018-2-4 14:37
标题: 【黑马程序员杭州】HashTable和ConcurrentHashTable的区别


最近同学出去面试老师被问到HashTable和ConcurrentHashTable的区别，所以今天在这里给大家整理一下
1、空间数据结构
      ConcurrentHashTable可以看作是多个HashTable的组合，每个"HashTable"单元被成为一个段,一个段的大小为“HashTable”数组的长度，默认是InitailCapacity/16，在ConcurrentHashTable中InitialCapacity是用户创建时传进去的，容量和大小是不一样的，大小指元素的总个数，容量指的所有段中slot的总个数（小于InitialCapacity的最大的2的n次幂）。

2、锁机制
      HashTable的线程安全使用的是一个单独的全部Map范围的锁，这个锁在所有的插入、删除、查询操作中都会持有，甚至在使用Iterator遍历整个Map时也会持有这个单独的锁。当锁被一个线程持有时，就能够防止其他线程访问该Map，即便其他线程都处于闲置状态。这种单个锁机制极大的限制了并发的性能。
      ConcurrentHashMap抛弃了HashTable的单锁机制，使用了锁分离技术，使得多个修改操作能够并发进行。ConcurrentHashMap内部使用段(Segment)，默认是16个段，来表示这些不同的部分，每个段其实就是一个小的hash table，即通过多个锁来控制对不同段的hash表的修改，每个锁只负责一部分key的hash值范围。只要多个修改操作发生在不同的段上，它们就可以并发进行。

3、put和get操作
      HashTable的put和get方法都是同步方法，多个线程不能并发操作，必须等到当前执行线程释放完锁之后，下一个线程才能进行存或取，并发性能及吞吐量大大下降。
      而ConcurrentHashTable的get方法多数情况都不用锁，put方法需要锁。get操作分析如下：
     V get(Object key, int hash) {  
    if (count != 0) { // read-volatile  
        HashEntry<K,V> e = getFirst(hash);  
        while (e != null) {  
            if (e.hash == hash && key.equals(e.key)) {  
                V v = e.value;  
                if (v != null)  
                    return v;  
                return readValueUnderLock(e); // recheck  
            }  
            e = e.next;  
        }  
    }  
    return null;  
}  
第一步是访问count变量，这是一个volatile变量，由于所有的修改操作在进行结构修改时都会在最后一步写count变量，通过这种机制保证get操作能够得到几乎最新的结构更新。对于非结构更新，也就是结点值的改变，由于HashEntry的value变量是volatile的，也能保证读取到最新的值。接下来就是对hash链进行遍历找到要获取的结点，如果没有找到，直接访回null。对hash链进行遍历不需要加锁的原因在于链指针next是final的。但是头指针却不是final的，这是通过getFirst(hash)方法返回，也就是存在table数组中的值。这使得getFirst(hash)可能返回过时的头结点，例如，当执行get方法时，刚执行完getFirst(hash)之后，另一个线程执行了删除操作并更新头结点，这就导致get方法中返回的头结点不是最新的。这是可以允许，通过对count变量的协调机制，get能读取到几乎最新的数据，虽然可能不是最新的。要得到最新的数据，只有采用完全的同步。

最后，如果找到了所求的结点，判断它的值如果非空就直接返回，否则在有锁的状态下再读一次。这似乎有些费解，理论上结点的值不可能为空，这是因为put的时候就进行了判断，如果为空就要抛NullPointerException。空值的唯一源头就是HashEntry中的默认值，因为HashEntry中的value不是final的，非同步读取有可能读取到空值。仔细看下put操作的语句：tab[index] = new HashEntry<K,V>(key, hash, first, value)，在这条语句中，HashEntry构造函数中对value的赋值以及对tab[index]的赋值可能被重新排序，这就可能导致结点的值为空。这种情况应当很罕见，一旦发生这种情况，ConcurrentHashMap采取的方式是在持有锁的情况下再读一遍，这能够保证读到最新的值，并且一定不会为空值。
4、保持数据结构一致性的方式
      HashTable使用同步来保证独占式访问一个数据结构（以及保持数据结构的一致性）。
        同步在 JMM 中也扮演着很重要的角色，会引起 JVM 在获得和释放监视器的时候执行内存壁垒（memory barrier）。一个线程在获得一个监视器之后，它执行一个读屏障（read barrier）――使得缓存在线程局部内存（比如说处理器缓存或者处理器寄存器）中的所有变量都失效，这样就会导致处理器重新从主存中读取同步代码块使用的变量。与此类似，在释放监视器时，线程会执行一个写屏障（write barrier）――将所有修改过的变量写回主存。互斥独占和内存壁垒结合使用意味着只要您在程序设计的时候遵循正确的同步法则（也就是说，每当写一个后面可能被其他线程访问的变量，或者读取一个可能最后被另一个线程修改的变量时，都要使用同步），每个线程都会得到它所使用的共享变量的正确的值。ConcurrentHashMap 没有采用独占性和一致性的同步。如果没有同步的话，在一个给定线程中某种顺序的写操作对于另外一个不同的线程来说可能呈现出不同的顺序， 并且对内存变量的更新从一个线程传播到另外一个线程的时间是不可预测的。它利用JMM不确定的特性对链表字段进行精心设计，将key，hash，next字段定义final，将value定义为volatile。可以检测到它的列表是否一致或者已经过时。如果它检测到它的列表出现不一致或者过时，或者干脆就找不到它要找的条目，它就会对适当的 bucket 锁进行同步并再次搜索整个链。这样做在一般的情况下可以优化查找，所谓的一般情况是指大多数检索操作是成功的并且检索的次数多于插入和删除的次数。


这篇文章讲的十分详细，我想大家对这个问题一定很清晰了，那我们下次见；
转载自 ：http://blog.csdn.net/zcc_0015/article/details/46932667

校区捷报

众览群雄，唯我杭城独秀—一贴汇总杭州校区所有就业薪资

http://bbs.itheima.com/thread-345570-1-1.html

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2