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更好；
JDK1.7 的ConcurrentHashMap数据结构图
为什么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
网友评论