问题14:haspMap和hashTable的区别,hashTable和concurrentHashMap区别、原理

HashMap原理
HashMap是基于哈希表实现的,每一个元素是一个key-value对,其内部通过单链表解决冲突问题,容量不足(超过了阀值)时,同样会自动增长。

HashMap是非线程安全的,只是用于单线程环境下,多线程环境下可以采用concurrent并发包下的concurrentHashMap。

HashMap 实现了Serializable接口,因此它支持序列化,实现了Cloneable接口,能被克隆。

HashMap存数据的过程是:HashMap内部维护了一个存储数据的Entry数组,HashMap采用链表解决冲突,每一个Entry本质上是一个单向链表。当准备添加一个key-value对时,首先通过hash(key)方法计算hash值,然后通过indexFor(hash,length)求该key-value对的存储位置,计算方法是先用hash&0x7FFFFFFF后,再对length取模,这就保证每一个key-value对都能存入HashMap中,当计算出的位置相同时,由于存入位置是一个链表,则把这个key-value对插入链表头。

HashMap中key和value都允许为null。key为null的键值对永远都放在以table[0]为头结点的链表中

Hashtable原理:

Hashtable同样是基于哈希表实现的,同样每个元素是一个key-value对,其内部也是通过单链表解决冲突问题,容量不足(超过了阀值)时,同样会自动增长。

Hashtable也是JDK1.0引入的类,是线程安全的,能用于多线程环境中。

Hashtable同样实现了Serializable接口,它支持序列化,实现了Cloneable接口,能被克隆。

ConcurrentHashMap原理:

· 底层采用分段的数组+链表实现,线程安全

· 通过把整个Map分为NSegment,可以提供相同的线程安全,但是效率提升N倍,默认提升16倍。(读操作不加锁,由于HashEntryvalue变量是 volatile的,也能保证读取到最新的值。)

· Hashtablesynchronized是针对整张Hash表的,即每次锁住整张表让线程独占,ConcurrentHashMap允许多个修改操作并发进行,其关键在于使用了锁分离技术

· 有些方法需要跨段,比如size()containsValue(),它们可能需要锁定整个表而而不仅仅是某个段,这需要按顺序锁定所有段,操作完毕后,又按顺序释放所有段的锁

· 扩容:段内扩容(段内元素超过该段对应Entry数组长度的75%触发扩容,不会对整个Map进行扩容),插入前检测需不需要扩容,有效避免无效扩容


HashMapHashTable区别:

1、继承的父类不同

Hashtable继承自Dictionary类,而HashMap继承自AbstractMap类。但二者都实现了Map接口。

2、线程安全性不同

HashMap是非线程安全的,Hashtable是线程安全的

3、是否提供contains方法

HashMap把Hashtable的contains方法去掉了,改成containsValue和containsKey,因为contains方法容易让人引起误解。

 Hashtable则保留了contains,containsValue和containsKey三个方法,其中contains和containsValue功能相同。

 4、key和value是否允许null值

Hashtable中,key和value都不允许出现null值,HashMap中,null可以作为键,这样的键只有一个;可以有一个或多个键所对应的值为null

5、两个遍历方式的内部实现上不同

 Hashtable、HashMap都使用了 Iterator。而由于历史原因,Hashtable还使用了Enumeration的方式 。

6、hash值不同

ashtable计算hash值,直接用key的hashCode(),而HashMap重新计算了key的hash值

7、内部实现使用的数组初始化和扩容方式不同

 HashTable在不指定容量的情况下的默认容量为11,而HashMap为16,Hashtable不要求底层数组的容量一定要为2的整数次幂,而HashMap则要求一定为2的整数次幂。

 Hashtable扩容时,将容量变为原来的2倍加1,而HashMap扩容时,将容量变为原来的2倍。

hashTable和concurrentHashMap区别

1HashtableHashMap都实现了Map接口,但是Hashtable的实现是基于Dictionary抽象类的。Java5提供了ConcurrentHashMap,它是HashTable的替代,比HashTable的扩展性更好

2ConcurrentHashMap提供了与HashtableSynchronizedMap不同的锁机制。Hashtable中采用的锁机制是一次锁住整个hash表,从而在同一时刻只能由一个线程对其进行操作;而ConcurrentHashMap中则是一次锁住一个桶,ConcurrentHashMap默认将hash表分为16个桶,诸如getputremove等常用操作只锁住当前需要用到的桶。这样,原来只能一个线程进入,现在却能同时有16个写线程执行,并发性能的提升是显而易见的。

3Hashtable通过使用synchronized修饰方法的方式来实现多线程同步,因此,Hashtable的同步会锁住整个数组。在高并发的情况下,性能会非常差,Java5中引入了java.util.concurrent.ConcurrentHashMap作为高吞吐量的线程安全HashMap实现,它采用了锁分离的技术允许多个修改操作并发进行。