Map集合源码解析与对比
2019-04-22 本文已影响0人
魏树鑫
HashMap数据结构
- HashMap是基于hashing的原理; value>插到table[i]中,如果有两个不同的key被算在了同一个i,那么就叫冲突,又叫碰撞,这样会在table[i]上形成一个链表
- 扩容原理:HashMap的扩容因子或负载因子为0.75,初容量1<<4=16,最大容量1<<30= 2^30 ;当一个map填满了75%的bucket时候,和其它集合类(如ArrayList等)一样,将会创建原来HashMap大小的两倍的bucket数组,来重新调整map的大小,并将原来的对象放入新的bucket数组中,也就是作rehashing,因为它调用hash方法找到新的bucket位置;
- 存储原理:put(key, value)方法存储时,会先对key调用hashCode()方法,返回的hashCode,然后根据table的长度进行取模,用于找到bucket位置来储存Entry对;
-
查找原理:拿key的hashCode来找到bucket位置,然后将会遍历链表,调用keys.equals()方法去找到链表中正确的节点,最终找到要找的值对象;
JDK1.7的HashMap数据结构图
HashMap指针碰撞问题
- 因为有equals()和hashCode()两个方法,所以两个对象就算hashcode相同,但是它们可能并不相等;
- 出现Hash碰撞后,两个值对象会存在同一个bucket中,并使用链表存储Map.Entry对象,这个Entry(包含有键值对的Map.Entry对象)会存储在链表中;
HashMap线程安全问题
- 当多线程的情况下,可能产生条件竞争(race condition);
- 当重新调整HashMap大小的时候,存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了;
Key不可变对象的好处
- hashCode()方法在存取时都会用到,但是equals()方法仅仅在获取值对象的时候才出现,所以使用不可变的、声明作final的对象,并且采用合适的equals()和hashCode()方法的话,将会减少碰撞的发生,提高效率
- 因为String是不可变的,也是final的,而且已经重写了equals()和hashCode()方法了,不可变性使得能够缓存不同键的hashcode,这将提高整个获取对象的速度,例如Interger其他的wrapper类也有这个特点。
- 不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashcode的话,那么就不能从HashMap中找到你想要的对象。
- 因为获取对象的时候要用到equals()和hashCode()方法,那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话,那么碰撞的几率就会小些,这样就能提高HashMap的性能。
- 使用自定义对象作为key,要注意重写equals()和hashCode()方法,要保证插入到map中后就不会在改变,否则会出现get时找不到值;
Collections对HashMap实现同步
- Collections.synchronizedMap可以实现对HashMap线程同步,返回的是一个Collections.SynchronizedMap类,直接将读写操作加了synchronized
HashMap 和 Hashtable
- HashMap初始容量16,Hashtable 11;
- HashMap扩容是
oldCap << 1
,扩容一倍,Hashtable(oldCapacity << 1) + 1
,扩容大小不一致是因为index计算方式不同,并且一定是要对奇数取膜; - HashMap的index计算是
e.hash & (newCap - 1)
,Hashtable(e.hash & 0x7FFFFFFF) % newCapacity
,实际e.hash & (newCap - 1) == e.hash % newCap
- HashMap可以接受null键值和值,而Hashtable则不能;
- HashMap是非synchronized,Hashtable是线程安全的,所以在单线程情况下,HashMap效率更高;
- HashMap的iterator在多线程下操作可能会抛出ConcurrentModificationException异常,因为Collection的Iterator使用了fail-fast机制;
http://www.importnew.com/24822.html
HashMap 和 LinkedHashMap
- LinkedHashMap 继承自HashMap,内部又维护了一条双向链表,此链接列表定义了迭代顺序,该迭代顺序可以是插入顺序或者是访问顺序;
- LinkedHashMap 遍历时遍历的记录顺序的双向链表,所以先得到的记录肯定是先插入的;
- LinkedHashMap 也可以在构造时带参数,按照应用次数排序;
- LinkedHashMap 数据量大时在查找的时候会比HashMap慢,因为HashMap会先找到bucket位,然后遍历链表,hash均匀时时间复杂度可能是O(1)
HashMap 和 TreeMap
- TreeMap 基于NavigableMap实现的红黑树
- TreeMap 实现SortMap接口,能够把它保存的记录根据键排序;
- TreeMap 默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator 遍历TreeMap时,得到的记录是排过序的
HashMap 和 HashSet
- HashSet是通过HashMap实现的,TreeSet是通过TreeMap实现的,只不过Set用的只是Map的key
HashMap 和 SparseArray
- SparseArray相比ArrayList查找时采用binary search查找key;
- 数据量特别大时性能不如HashMap,数据量超过几百时,性能差距不到50%;
- SparseArray在remove时,只是做了逻辑删除,key还是可以重用的;
SparseArray.java
private void gc() {
// Log.e("SparseArray", "gc start with " + mSize);
int n = mSize;
int o = 0;
int[] keys = mKeys;
Object[] values = mValues;
for (int i = 0; i < n; i++) {
Object val = values[i];
if (val != DELETED) {
if (i != o) {
keys[o] = keys[i];
values[o] = val;
values[i] = null;
}
o++;
}
}
mGarbage = false;
mSize = o;
// Log.e("SparseArray", "gc end with " + mSize);
}
HashMap和ArrayMap
- 主要是节省空间,因为内部用了4个数组维护,并且空间进行了复用,扩容时是通过
index+index>>1
,并不会扩容一倍 - mHashes的存在,主要是用来找到mArray中的key的hash值的index,因为mArray中是将key和value一起存入的,所以将index<<1+1就找到了value在mArray中的位置;
- 查找时使用二分查找,尽可能提高效率,在数据量大的情况下,如不HashMap
- ArrayMap原理具体可参考:https://www.cnblogs.com/huanyou/p/5985303.html
ConcurrentHashMap
- JDK1.7 的整个 ConcurrentHashMap 由一个个 Segment 组成,Segment 代表”部分“或”一段“的意思,所以很多地方都会将其描述为分段锁。
简单理解就是,ConcurrentHashMap 是一个 Segment 数组,Segment 通过继承 ReentrantLock 来进行加锁,所以每次需要加锁的操作锁住的是一个 segment,这样只要保证每个 Segment 是线程安全的,也就实现了全局的线程安全 - JDK1.8 的ConcurrentHashMap 取消segments字段,直接采用transient volatile HashEntry<K,V>[] table保存数据,采用table数组元素作为锁,从而实现了对每一行数据进行加锁,进一步减少并发冲突的概率
- ConcurrentHashMap基于ReentrantLock实现分段锁,所以ConcurrentHashMap在并发条件下性能相比Hashtable更好;
为什么Hashtable、ConcurrentHashmap不支持key或者value为null
ConcurrentHashmap、Hashtable不支持key或者value为null,而HashMap是支持的。为什么会有这个区别?在设计上的目的是什么?
在网上找到了这样的解答:
ConcurrentHashmap和Hashtable都是支持并发的,这样会有一个问题,当你通过get(k)获取对应的value时,如果获取到的是null时,你无法判断,它是put(k,v)的时候value为null,还是这个key从来没有做过映射。HashMap是非并发的,可以通过contains(key)来做这个判断。而支持并发的Map在调用m.contains(key)和m.get(key),m可能已经不同了。
另外HashTable在计算hash值时没有进行非空校验,为Null会报异常
JDK1.8新特性
- hash算法优化,通过hashCode()的高16位异或低16位实现的,1.7 使用hashCode() + 4次位运算 + 5次异或运算(9次扰动)
- resize优化,数据量过大或者运气不佳的情况下,还是会存在一些队列长度过长的情况,如果还是采用单向列表方式,那么查询某个节点的时间复杂度为O(n);因此,对于个数超过8(默认值)的列表,jdk1.8中采用了红黑树的结构,那么查询的时间复杂度可以降低到O(logN),可以改进性能。
- 通过增加tail指针,既避免了死循环问题(让数据直接插入到队尾),又避免了尾部遍历,但仍是非线程安全的,多线程时可能会造成数据丢失问题
- ConcurrentHashmap 取消segments字段,直接采用transient volatile HashEntry<K,V>[] table保存数据
计算index一定是对奇数取膜
length为2的整数次幂的话,则一定为偶数,那么 length-1 一定为奇数,奇数的二进制的最后一位是1,这样便保证了 h&(length-1) 的最后一位可能为0,也可能为1(这取决于h的值),即与后的结果可能为偶数,也可能为奇数,这样便可以保证散列的均匀,而如果length为奇数的话,很明显 length-1 为偶数,它的最后一位是0,这样 h&(length-1) 的最后一位肯定为0,即只能为偶数,这样导致了任何hash值都只会被散列到数组的偶数下标位置上,浪费了一半的空间,因此length取2的整数次幂,是为了使不同hash值发生碰撞的概率较小,这样就能使元素在哈希表中均匀地散列
JDK1.8 HashMap 部分关键源码
//计算Hash
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//put操作
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K, V>[] tab; //table数组
Node<K, V> p;//数组中链表的尾指针
int n, i;
//如果table为空,初始化table
if ((tab = table) == null || (n = tab.length) == 0) {
n = (tab = resize()).length;
}
//如果table中计算的hash没有冲突,直接放入数组最后一个
if ((p = tab[i = (n - 1) & hash]) == null) {
tab[i] = newNode(hash, key, value, null);
}
//出现hash冲突;一种情况是key相同替换,还可能是hash冲突,但是key不同
else {
Node<K, V> e;//待插入node的临时变量
K k;
//如果Hash值相同,比较key是否相同,如果相同,直接将尾指针赋给临时变量,用于后面的替换value
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
e = p;
}
//否则是放入新的key、value
//如果node是TreeNode,则是红黑树实现
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);
//TREEIFY_THRESHOLD默认为8,节点超过8,转成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) {// -1 for 1st
treeifyBin(tab, hash);
}
break;
}
//如果是key相同,直接跳出,替换尾指针
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
break;
}
p = e;
}
}
//临时变量赋值value,并调插入,如果key相同返回旧的值,key不同oldValue就为null
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) {
e.value = value;
}
//LinkedHashMap使用的
afterNodeAccess(e);
return oldValue;
}
}
//modCount是用来操作计数的,在foreach或者其他操作中出现modCount不一致时用来抛出ConcurrentModificationException,fail-fast机制
++modCount;
if (++size > threshold) {
resize();
}
//LinkedHashMap使用的
afterNodeInsertion(evict);
return null;
}
//查找
final HashMap.Node<K, V> getNode(int hash, Object key) {
HashMap.Node<K, V>[] tab;
HashMap.Node<K, V> first, e;
int n;
K k;
//table不为空
//计算index,index = (n - 1) & hash,找到bucket位
//first 链表的第一个节点
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
//先检查第一个节点
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k)))) {
return first;
}
//遍历链表
if ((e = first.next) != null) {
if (first instanceof HashMap.TreeNode) {
return ((HashMap.TreeNode<K, V>) first).getTreeNode(hash, key);
}
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
return e;
}
} while ((e = e.next) != null);
}
}
return null;
}
JDK1.8 SynchronizedMap部分源码
private static class SynchronizedMap<K,V> implements Map<K,V>, Serializable {
private final Map<K,V> m; // Backing Map
final Object mutex; // Object on which to synchronize
SynchronizedMap(Map<K,V> m) {
this.m = Objects.requireNonNull(m);
mutex = this;
}
SynchronizedMap(Map<K,V> m, Object mutex) {
this.m = m;
this.mutex = mutex;
}
public V get(Object key) {
synchronized (mutex) {return m.get(key);}
}
public V put(K key, V value) {
synchronized (mutex) {return m.put(key, value);}
}
public V remove(Object key) {
synchronized (mutex) {return m.remove(key);}
}
... ...
}
参考
- JDK1.7 的ConcurrentHashMap的设计可参考 http://www.importnew.com/28263.html
- JDK1.8 Hashing优化 可参考 https://www.jianshu.com/p/8324a34577a0
- JDK1.8 Map的红黑树 具体参考 https://mp.weixin.qq.com/s/l7Dg5TwfQCHZjjxMPJuAFw
- JDK1.8 修复HashMap并发可能导致的死循环和尾部遍历问题 可参考 https://www.cnblogs.com/gxyandwmm/p/9537669.html