HashMap、TreeMap、HashTable、ConcurrentHashMap对比(jdk1.8)

欢迎查看Eetal的第十篇博客–HashMap、TreeMap、HashTable、ConcurrentHashMap对比(jdk1.8)

HashMap

HashMap是java中经常用来存取键值对形式的一个集合类
1.8以后实现方式为 数组(Node<K,V>[])+链表(Node)
首先计算出要存储的key应该到数组中哪个位置的链表下

1
2
3
4
static final int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }

静态方法hash将key的hashCode的高16位与低16位异或的值作为其hash值,异或是为了减少在map的hash数组长度较小时的hash碰撞，使其更均匀
如果key是null则为0，这也是为什么HashMap可以使用null作为key而ConcurrentHashMap不行的原因
在putVal方法中使用这个hash的值去与当前的数组大小求余计算出其位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
				   boolean evict) {
		Node<K,V>[] tab; Node<K,V> p; int n, i;
		if ((tab = table) == null || (n = tab.length) == 0)
			n = (tab = resize()).length;
		if ((p = tab[i = (n - 1) & hash]) == null) //---计算数组位置
			tab[i] = newNode(hash, key, value, null);
		else {
			Node<K,V> e; K k;
			if (p.hash == hash &&
				((k = p.key) == key || (key != null && key.equals(k))))
				e = p;
			else if (p instanceof TreeNode)
				e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
			else {
				for (int binCount = 0; ; ++binCount) {
					if ((e = p.next) == null) {
						p.next = newNode(hash, key, value, null);
						if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
							treeifyBin(tab, hash);
						break;
					}
					if (e.hash == hash &&
						((k = e.key) == key || (key != null && key.equals(k))))
						break;
					p = e;
				}
			}
			if (e != null) { // existing mapping for key
				V oldValue = e.value;
				if (!onlyIfAbsent || oldValue == null)
					e.value = value;
				afterNodeAccess(e);
				return oldValue;
			}
		}
		++modCount;
		if (++size > threshold)
			resize();
		afterNodeInsertion(evict);
		return null;
	}

重要参数

1
2
3
4
5
6
7
8
9
10
11
12
13
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30.
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

重要构造函数

hashmap限制容量CAPACITY为2的幂，每次扩容为乘以2,这样可以保证数据的均匀分布，同时使得hashmap只有resize方法而不需要rehash,下面详谈
第一个DEFAULT_INITIAL_CAPACITY默认的数组大小，也就是不指定时默认开辟的hash数组大小为2的4次方
第二个MAXIMUM_CAPACITY，最大扩容至的hash数组大小,如果指定的数组大小大于这个值，会被替换为这个值,原因是,数组的下表要求是int类型,而int在java中是4个字节,共32位，而第一位表示符号位，因此可以表示的最大2的幂为2的30次方
最后DEFAULT_LOAD_FACTOR代表负载因子,当put操作以后 map的size > hash数组的长度*负载因子时,就会触发扩容，
当然hashmap提供了指定initialCapacity的构造函数,但在1.8里，这个参数并不会改变其capacity，只会改变threshold的值以下为源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
    * Constructs an empty <tt>HashMap</tt> with the specified initial
    * capacity and load factor.
    *
    * @param  initialCapacity the initial capacity
    * @param  loadFactor      the load factor
    * @throws IllegalArgumentException if the initial capacity is negative
    *         or the load factor is nonpositive
    */
   public HashMap(int initialCapacity, float loadFactor) {
       if (initialCapacity < 0)
           throw new IllegalArgumentException("Illegal initial capacity: " +
                                              initialCapacity);
       if (initialCapacity > MAXIMUM_CAPACITY)
           initialCapacity = MAXIMUM_CAPACITY;
       if (loadFactor <= 0 || Float.isNaN(loadFactor))
           throw new IllegalArgumentException("Illegal load factor: " +
                                              loadFactor);
       this.loadFactor = loadFactor;
       this.threshold = tableSizeFor(initialCapacity);
   }

   /**
    * Returns a power of two size for the given target capacity.
    */
   static final int tableSizeFor(int cap) {
       int n = cap - 1;
       n |= n >>> 1;
       n |= n >>> 2;
       n |= n >>> 4;
       n |= n >>> 8;
       n |= n >>> 16;
       return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
   }

指定initialCapacity只能改变扩容时机，而并不改变hash数组长度

put操作与resize

put操作较简单，计算到对应Node,为null则新建,不为null则根据该Node类型为TreeNode还是普通Node执行不同的插入操作
当put以后，如果size大于threshold扩容时机，则进行扩容（数组长度乘以2）
同时进行rehash,此处源码使用了一个快捷的办法，因为数组的长度必定为2的倍数
假设长度为2的x次方,则旧hash数组第i个位置上的链表的所有Node的hash都应该为 Nj(2的x次方)+i
因为新扩容的数组长度为原来的两倍(重点),则 长度为 2(2的x次方)，此时进行resize
hash%(2(2的x次方)) == (hash%(2的x次方))+(2的x次方)(hash&(2的x+1次方))
而hash%(2的x次方)为node所在旧hash数组下标i,oldCap为旧数组的长度，式子可写为
新数组的位置下标 newI = i + oldCap * (hash & oldCap)
官方实现代码如下,将旧数组每个位置上的链表拆分为高低两条新链表，分别代表hash & oldCap为0和为1的节点
再把这两条链表对应到新数组的位置 newTab[j] 和 newTab[oldCap + j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// j from 0 to oldCap-1
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
	next = e.next;
	if ((e.hash & oldCap) == 0) {
		if (loTail == null)
			loHead = e;
		else
			loTail.next = e;
		loTail = e;
	}
	else {
		if (hiTail == null)
			hiHead = e;
		else
			hiTail.next = e;
		hiTail = e;
	}
} while ((e = next) != null);
if (loTail != null) {
	loTail.next = null;
	newTab[j] = loHead;
}
if (hiTail != null) {
	hiTail.next = null;
	newTab[j + oldCap] = hiHead;
}

HashMap死锁问题

因为HashMap中的put和remove都是不加对象锁的，也就是非线程安全的
且其table属性(hash数组的引用)也没有使用volatile修饰(修饰了也不能百分百解决并发问题,因此官方默认HashMap为非线程安全的map以提高其效率)
如果在resize的过程,另一个线程拿到的是oldTable，并对其进行如删除元素或新增元素
因为原有的单条链表hi拆分重新组建为高低两条链表，这期间对oldTable节点的插入和删除操作可能会导致把新构建的链表中的部分节点形成环(因为新链表的序列与oldTable原有不一样)
最终导致在get和put时，遍历链表时进入无限死循环
因此在多线程下应使用ConcurrentHashMap代替HashMap

TreeMap

TreeMap为有序的map,本质是一条链表
可以在构造是传入一个比较器，或者每个元素的类都有实现Comparable接口
HashMap的插入为计算到数组位置后,添加到对应Node链表末端
TreeMap为比较计算位置后插入对应链表位置
在未传入比较器的情况下，key不允许为null

简介ConcurrentHashMap和HashTable

HashTable为HashMap的线程安全版,其中会有线程安全问题的方法都采用使用this对象作为锁的方式来实现互斥
而ConcurrentHashMap1.5以前为使用分段锁，即双数组,原本存放Entry的地方改为存放segemant数组，代码1000多行
segemant对象继承了ReentrantLock，包含有一个与Entry数组的属性
插入和删除修改时,只锁被Hash到的segemant对象，再hash元素到segemant的Entry数组对应的位置，插入到对应位置链表中去
jdk1.5开始，Doug Lea 大牛改为和HashMap一样的Node结构,往类里注入了Unsafe对象
修改时只锁被hash到的对应的链表头指针Node，通过各种cas操作和synchronized检验和修改插入等操作
jdk1.5以后的ConcurrentHashMap的源码足足来到6312行，TQL，到处都是使用unsafe的cas和计算对象偏移来完成原语操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
   // Unsafe mechanics
   private static final sun.misc.Unsafe U;
   private static final long SIZECTL;
   private static final long TRANSFERINDEX;
   private static final long BASECOUNT;
   private static final long CELLSBUSY;
   private static final long CELLVALUE;
   private static final long ABASE;
   private static final int ASHIFT;

   static {
       try {
           U = sun.misc.Unsafe.getUnsafe();
		...
		}
	...	
}

因此效率上而言ConcurrentHashMap会优于HashTable

请移步

个人主页: yangyitao.top