Hashtable与ConcurrentHashMap区别
相同点: Hashtable 和 ConcurrentHashMap都是线程安全的,可以在多线程环境中运行; key跟value都不能是null
区别: 两者主要是性能上的差异,Hashtable的所有操作都会锁住整个对象,虽然能够保证线程安全,但是性能较差; ConcurrentHashMap内部使用Segment数组,每个Segment类似于Hashtable,在“写”线程或者部分特殊的“读”线程中锁住的是某个Segment对象,其它的线程能够并发执行其它的Segment对象。
下面从下面两个问题来具体了解下Hashtable和ConcurrentHashMap
1, Hashtable怎样实现线程安全?
2,ConcurrentHashMap怎样实现线程安全?为什么性能会比Hashtable好?
先来看第一个问题: Hashtable怎样实现线程安全?
下面是Hashtable的get和put方法
/** * The hash table data. */ //Hashtable使用Entry数组来保存数据 private transient Entry[] table; public synchronized V get(Object key) { Entry tab[] = table; int hash = key.hashCode(); //通过求模运算得到下标的索引值,保证下标在 【0,tab.length) 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; } public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { throw new NullPointerException(); } // Makes sure the key is not already in the hashtable. Entry tab[] = table; int hash = key.hashCode(); 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)) { V old = e.value; e.value = value; return old; } } modCount++; //元素数量超过阀值,需要增大散列表的大小 if (count >= threshold) { // Rehash the table if the threshold is exceeded rehash(); tab = table; index = (hash & 0x7FFFFFFF) % tab.length; } // Creates the new entry. Entry<K,V> e = tab[index]; tab[index] = new Entry<K,V>(hash, key, value, e); count++; return null; }
可以看到,Hashtable的方法都是声明为synchronized的,这样就能够保证Hashtable是线程安全的。 Hashtable的内部结构如下图所示:
Hashtable在put元素时,会根据定义的方法计算hash值,如果这个位置没有元素,直接添加,如d1,如果已经有元素,会按照链表的方式将元素插在链表的头部,如aa。
再来看第二个问题: ConcurrentHashMap怎样实现线程安全?为什么性能会比Hashtable好?
1,下面是ConcurrentHashMap的put方法
// ConcurrentHashMap的key 跟 value都不能是null public V put(K key, V value) { if (value == null) throw new NullPointerException(); int hash = hash(key.hashCode()); return segmentFor(hash).put(key, hash, value, false); }
好的hash算法很重要(对于Hashtable,HashMap等也同样),如果冲突的概率大,会严重影响性能,下面是ConcurrentHashMap的hash算法,不过为什么会冲突较小就不明白了,望高手解决
private static int hash(int h) { // Spread bits to regularize both segment and index locations, // using variant of single-word Wang/Jenkins hash. h += (h << 15) ^ 0xffffcd7d; h ^= (h >>> 10); h += (h << 3); h ^= (h >>> 6); h += (h << 2) + (h << 14); return h ^ (h >>> 16); } /** * Returns the segment that should be used for key with given hash * @param hash the hash code for the key * @return the segment */ final Segment<K,V> segmentFor(int hash) { return segments[(hash >>> segmentShift) & segmentMask]; }
在segmentFor的方法中,变量segmentShift和segmentMask在创建ConcurrentHashMap的时候初始化, 如下所示
//initialCapacity: 初始容量大小,默认为16 //loadFactor: 跟threshold的值相关,控制是否需要扩容的阀门值,默认为0.75f //concurrencyLevel: the estimated number of concurrently updating threads, 跟Segment数组大小相关,默认为16 public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) { if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0) throw new IllegalArgumentException(); if (concurrencyLevel > MAX_SEGMENTS) concurrencyLevel = MAX_SEGMENTS; // Find power-of-two sizes best matching arguments int sshift = 0; int ssize = 1; while (ssize < concurrencyLevel) { ++sshift; ssize <<= 1; //获取不小于concurrencyLevel的最小的2的幂,跟segmentFor计算相关 } segmentShift = 32 - sshift; segmentMask = ssize - 1; //二进制的低位都为1,在segmentFor方法中,保证(hash >>> segmentShift) & segmentMask结果在0~ssize-1之间(很好的算法,比求模的运算效率高) this.segments = Segment.newArray(ssize); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; int c = initialCapacity / ssize; if (c * ssize < initialCapacity) ++c; int cap = 1; while (cap < c) cap <<= 1; for (int i = 0; i < this.segments.length; ++i) this.segments[i] = new Segment<K,V>(cap, loadFactor); }
如果使用默认的参数构造ConcurrentHashMap,即initialCapacity=16,loadFactor=0.75f,concurrencyLevel=16, 得到的ssize=16,sshift=4, segmentMask=15, Segment数组长度为16。在表达式(hash >>> segmentShift) & segmentMask中,segmentMask的二进制为 00000000 00000000 00000000 00001111,通过位与运算得到的结果范围为0~15,相比Hashtable的模运算,效率更高。 但是可能会有疑问,为何需要保证ssize为2的幂?如果ssize不是2的幂,得到的segmentMask低位不是全部为1,比如ssize=14,segmentMask=13,二进制为00000000 00000000 00000000 00001101,此时位与运算肯定无法得到索引为 00000000 00000000 00000000 0000**1*的数值,比如2、3、6、7、10、11、14,会导致Segment数组的利用率低,产生较大的hash冲突。
再来看下Segment的put方法
V put(K key, int hash, V value, boolean onlyIfAbsent) { lock(); try { int c = count; // 判断是否需要扩容 if (c++ > threshold) // ensure capacity rehash(); HashEntry<K,V>[] tab = table; int index = hash & (tab.length - 1); HashEntry<K,V> first = tab[index]; HashEntry<K,V> e = first; while (e != null && (e.hash != hash || !key.equals(e.key))) e = e.next; V oldValue; if (e != null) { oldValue = e.value; if (!onlyIfAbsent) e.value = value; } else { oldValue = null; ++modCount; tab[index] = new HashEntry<K,V>(key, hash, first, value); count = c; // write-volatile } return oldValue; } finally { unlock(); } }
在put方法中,使用ReentrantLock的 lock()和unlock()方法控制同步,Segment的定义如下
/** * Segments are specialized versions of hash tables. This * subclasses from ReentrantLock opportunistically, just to * simplify some locking and avoid separate construction. */ static final class Segment<K,V> extends ReentrantLock implements Serializable
从上面代码可知,ConcurrentHashMap在并发修改时,锁住的是当前Segment的对象,其它Segment中的并发操作可以同时执行,性能会比使用Hashtable好。 ConcurrentHashMap的结构如下所示:
看到 kidneyball 分析的一段话,写得很好,哈哈,就搬过来了(勿怪)。
Q: Hashtable,ConcurrentHashMap 有什么区别,这两个都是hash表,都是同步的
A: Hashtable的任何操作都会把整个表锁住,是阻塞的。好处是总能获取最实时的更新,比如说线程A调用putAll写入大量数据,期间线程B调用get,线程B就会被阻塞,直到线程A完成putAll,因此线程B肯定能获取到线程A写入的完整数据。坏处是所有调用都要排队,效率较低。
ConcurrentHashMap 是设计为非阻塞的。在更新时会局部锁住某部分数据,但不会把整个表都锁住。同步读取操作则是完全非阻塞的。好处是在保证合理的同步前提下,效率很高。坏处 是严格来说读取操作不能保证反映最近的更新。例如线程A调用putAll写入大量数据,期间线程B调用get,则只能get到目前为止已经顺利插入的部分 数据。此外,使用默认构造器创建的ConcurrentHashMap比较占内存,如果程序需要创建巨量ConcurrentHashMap,应该在构造 时指定concurrencyLevel (详情参考 http://ria101.wordpress.com/2011/12/12/concurrenthashmap-avoid-a-common-misuse/ )。
相关推荐
HashTable、ConcurrentHashMap.pdf
HashMap,HashTable,ConcurrentHashMap之关联.docx
hashmap和hashtable的区别 HashMap和Hashtable都实现了Map接口,但决定用哪一个之前先要弄清楚它们之间的分别。...Java 5提供了ConcurrentHashMap,它是HashTable的替代,比HashTable的扩展性更好。
HashTable是一个线程安全的类,它使用...ConcurrentHashMap内部使用段(Segment)来表示这些不同的部分,每个段其实就是一个小的Hashtable,它们有自己的锁。只要多个修改操作发生在不同的段上,它们就可以并发进行。
ConcurrentHashMap具体是怎么实现线程安全的呢,肯定不可能是每个方法加synchronized,那样就变成了HashTable。
ConcurrentHashMap是一个线程安全的HashTable,它的主要功能是提供了一组和HashTable功能相同但是线程安全的方法。ConcurrentHashMap可以做到读取数据不加锁,并且其内部的结构可以让其在进行写操作的时候能够将锁的...
就是一些通用java集合知识点整理,ArrayList LinkedList,HashMap,HashTable ,ConcurrentHashMap,HashSet,LinkedHashSet类通过线程安全否: 底层: 初始值: 扩容 : 区别(对比优势) 图解
HashMap 和 Hashtable 的区别,HashSet如何检查重复,HashMap的底层实现,HashMap 多线程操作导致死循环问题,ConcurrentHashMap 和 Hashtable 的区别,ConcurrentHashMap线程安全的具体实现⽅式/底层具体实现,...
17.HashMap、Hashtable、ConcurrentHashMap底层实现原理及区别 18.HashMap底层数据结构 19.说说HashMap如何处理碰撞的,或者说说它的扩容? 20.jdk7/8中对HashMap做了哪些改变? 21.负载因子为什么会影响HashMap性能...
java_各个Map的区别 ConcurrentHashMap 支持检索的完全并发和更新的所期望可调整并发的哈希表。(线程安全)此类遵守与 Hashtable 相同的功能规范,并且包括对应于 Hashtable 的每个方法的方法版本。不过,尽管所有...
1. 经历了一个半月的时间学习,已拿到阿里,腾讯,...Hashmap和Hashtable和concurrentHashmap的区别 二面 简答Spring与Springboot之间的问题 回答JVM上的问题 回答Java中锁机制 回答Java中的数据库问题 三面 回答Java
1.说一下 HashMap 的实现原理?...15.HashMap 与 HashTable 有什么区别? 16.如何决定使用 HashMap 还是 TreeMap? 17.HashMap 和 ConcurrentHashMap 的区别? 18.ConcurrentHashMap 和 Hashtable 的区别?
HashMap,HashTable,ConcurrentHashMap 实现原理以及区别? HashSet 与 HashMap 怎么判断集合元素重复? String、StringBuffer、StringBuilder 之间的区别? 对反射的了解? 对注解的了解? 对依赖注入的了解? 对...
HashMap,Hashtable和ConcurrentHashMap的区别 在ArrayList和LinkedList尾部添加元素,谁的效率更高 如果HashMap或者hashTable的key是一个自定义的类该怎么办 为什么重写equals还要重写hashCode? 介绍一下volatile jdk...
进程与线程区别 线程状态 网络 TCP 四次挥手 SYN Flood 如何避免 HTTP 头部字段 HTTP 请求方式 AIO OSI 七层模型 ARP 协议 Mysql Mysql 数据存储原理 Mysql 索引 abc 复合索引 数据库隔离级别 InnoDB 与 MySAIM 区别...
Hashtable 本身比较低效,因为它的实现基本就是将 put、get、size 等各种方法加上 synchronized 锁。这就导致了所有并发操作都要竞争同一把锁,一个线程在进行同步操作时,其他线程只能等待,大大降低了并发操作的...
java8 源码 目录 Java 基础 容器 并发 JVM I/O Java ...数据结构与算法 ...中只有值传递、==与equals、 hashCode与equals) (String和StringBuffer、...的区别、ConcurrentHashMap线程安全的具体实现方式/底层具体实现、集
java8 源码 目录 Java 基础 容器 并发 JVM I/O Java ...数据结构与算法 ...中只有值传递、==与equals、 hashCode与equals) ...的区别、ConcurrentHashMap线程安全的具体实现方式/底层具体实现、集合框架底层数据结构总结
js如何实现页面刷新呢 什么是线程池 如何实现 Array 和 List 之间的转换 ...用过ConcurrentHashMap,讲一下他和HashTable的不同之处 线程的基本状态以及状态之间的关系 线程池中 submit() 和 execute() 方法有什么区别