HashMap、HashTable、ConcurrentHashMap
本文目录
1 HashMap
2 HashTable
3 ConcurrentHashMap
1 HashMap
1.1 工作原理
存入操作(put)
(1) 调用key对象的hashCode()方法计算HashCode值;
(2) 根据HashCode值确定数组位置;
(3) 根据数组位置情况:
① 若为空(未冲突),直接将Entry对象(key-value对象)存入该位置;
② 若非空(冲突),将Entry对象作为链表头部存入该位置,并指向该位置的原Entry对象。
获取操作(get)
(1) 调用key对象的hashCode()方法计算HashCode值;
(2) 根据HashCode值确定数组位置;
(3) 根据数组位置情况:
① 若为空,表示该key不存在;
② 若非空,且仅一个元素,则返回该Entry对象中的value部分;
③ 若非空,且为链表结构,则遍历该链表,通过key对象的equals()方法寻找匹配的Entry对象:
若未寻找到匹配的Entry对象,则表示该key不存在;
若寻找到匹配的Entry对象,则返回Entry对象中的value部分;
1.2 容量相关
初始容量(initialCapacity)
默认为16,可通过构造方法指定初始容量(最大1<<30)。
负载因子(loadFactory)
默认0.75,可通过构造方法指定负载因子。
当负载量达到threshold = initialCapacity * loadFactory时,则进行扩容操作。
扩容操作
(1) 新创建一个2倍容量的数组;
(2) 将原数组中的对象转移至新创建的数组中。
Rehashing:该过程需要重新计算每个Entry中key的HashCode值,从而确定在新数组中的位置。
1.3 其它
(1) Key与Value都可以为null;
(2) HashMap不是同步安全的(非Synchronized),因此,多线程情况下,不适合使用HashMap。
(3) 对于key,在存入和获取操作时,要计算其HashCode值,因此,保证key不可变是必要的;
此外,作为key的类型,还需要实现hashCode和equals方法,以保证可以正常使用HashMap。
String类型最适合作Key,因为String是不可变(final)且重写了hashCode和equals方法。
1.4 JDK 1.8
(1) 对于链表结构部分进行优化,当链表长度达到指定值(默认为8),则将链表改为红黑树结构。
(2) 在对HashMap扩容操作上进行了优化,部分内容不需要重新计算HashCode值;
2 HashTable
2.1 工作原理
类似于HashMap工作原理
2.2 其它
(1) Key与Value不可以为null;
(2) HashTable是同步安全的(synchronized),因而,在单线程操作情况下,HashTable效率低于HashMap。
(3) HashTable已经被淘汰,若需要保证同步安全,可使用ConcurrentHashMap类。
3 ConcurrentHashMap
3.1 工作原理
synchronized方法是以当前对象作为资源锁,当某线程执行同步方法时,当前对象被锁,其它的同步方法无法被其它线程使用,造成性能下降。
在JDK 1.8之前,ConcurrentHashMap基于Lock操作,实现同步安全,在同步操作时,仅锁住部分内容,提高并发性能。
在JDK 1.8中,ConcurrentHashMap改为基于CAS和synchronized操作,实现同步安全。
对于无冲突结点,基于CAS操作;对于有冲突结点(已存在元素的位置),将链表头节点作为资源锁定,进行synchronized操作。
3.2 其它
(1) Key与Value不可以为null;