① 创建时如果不指定容量初始值,Hashtable 默认的初始大小为11,之后每次扩充,容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充,容量变为原来的2倍。
② 创建时如果给定了容量初始值,那么 Hashtable 会直接使用你给定的大小,而 HashMap 会将其扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂次方作为哈希表的大小,后面会介绍到为什么是2的幂次方。
底层数据结构: JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。Hashtable 没有这样的机制。
HashMap的迭代器(Iterator)是fail-fast迭代器,但是 Hashtable的迭代器(enumerator)不是 fail-fast的。如果有其它线程对HashMap进行的添加/删除元素,将会抛出ConcurrentModificationException,但迭代器本身的remove方法移除元素则不会抛出异常。这条同样也是 Enumeration 和 Iterator 的区别。
ConcurrentHashMapHashMap在多线程情况下,在put的时候,插入的元素超过了容量(由负载因子决定)的范围就会触发扩容操作,就是rehash,这个会重新将原数组的内容重新hash到新的扩容数组中,在多线程的环境下,存在同时其他的元素也在进行put操作,如果hash值相同,可能出现同时在同一数组下用链表表示,造成闭环,导致在get时会出现死循环,所以HashMap是线程不安全的。
Hashtable,是线程安全的,它在所有涉及到多线程操作的都加上了synchronized关键字来锁住整个table,这就意味着所有的线程都在竞争一把锁,在多线程的环境下,它是安全的,但是无疑是效率低下的。
JDK1.7 实现Hashtable 容器在竞争激烈的并发环境下表现出效率低下的原因,是因为所有访问 Hashtable 的线程都必须竞争同一把锁,那假如容器里有多把锁,每一把锁用于锁容器其中一部分数据,那么当多线程访问容器里不同数据段的数据时,线程间就不会存在锁竞争,,这就是ConcurrentHashMap所使用的锁分段技术。
在 JDK1.7版本中,ConcurrentHashMap 的数据结构是由一个 Segment 数组和多个 HashEntry 组成。Segment 数组的意义就是将一个大的 table 分割成多个小的 table 来进行加锁。每一个 Segment 元素存储的是 HashEntry数组+链表,这个和 HashMap 的数据存储结构一样。
ConcurrentHashMap 类中包含两个静态内部类 HashEntry 和 Segment。
HashEntry 用来封装映射表的键值对,Segment 用来充当锁的角色,每个 Segment 对象守护整个散列映射表的若干个桶。每个桶是由若干个 HashEntry 对象链接起来的链表。一个 ConcurrentHashMap 实例中包含由若干个 Segment 对象组成的数组。每个 Segment 守护着一个 HashEntry 数组里的元素,当对 HashEntry 数组的数据进行修改时,必须首先获得它对应的 Segment 锁。
Segment 类继承于 ReentrantLock 类,从而使得 Segment 对象能充当可重入锁的角色。一个 Segment 就是一个子哈希表,Segment 里维护了一个 HashEntry 数组,并发环境下,对于不同 Segment 的数据进行操作是不用考虑锁竞争的。
从源码可以看到,Segment 内部类和我们上边看到的 HashMap 很相似。也有负载因子,阈值等各种属性。
static final class Segment<K,V> extends ReentrantLock implements Serializable { static final int MAX_SCAN_RETRIES = Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1; transient volatile HashEntry<K,V>[] table; transient int count; transient int modCount; //记录修改次数 transient int threshold; final float loadFactor; Segment(float lf, int threshold, HashEntry<K,V>[] tab) { this.loadFactor = lf; this.threshold = threshold; this.table = tab; } //put 方法会有加锁操作, final V put(K key, int hash, V value, boolean onlyIfAbsent) { HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value); // ... } @SuppressWarnings("unchecked") private void rehash(HashEntry<K,V> node) { // ... } private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) { //... } private void scanAndLock(Object key, int hash) { //... } final V remove(Object key, int hash, Object value) { //... } final boolean replace(K key, int hash, V oldValue, V newValue) { //... } final V replace(K key, int hash, V value) { //... } final void clear() { //... } } HashEntry 类HashEntry 是目前我们最小的逻辑处理单元。一个ConcurrentHashMap 维护一个 Segment 数组,一个Segment维护一个 HashEntry 数组。
static final class HashEntry<K,V> { final int hash; final K key; volatile V value; // value 为 volatie 类型,保证可见 volatile HashEntry<K,V> next; //... } ConcurrentHashMap 类