HashMap相关知识

今天来讲HashMap是分JDK7和JDK8 对比着来讲的， 因为JDK8中针对于HashMap有些小的改动， 这也是一些面试会经常问到的点。

一：JDK7中的HashMap：

HashMap底层维护一个数组table， 数组中的每一项是一个key，value形式的Entry。

我们往HashMap中所放置的对象实际是存储在该数组中。

Map中的key，value则以Entry的形式存放在数组中。

这个Entry应该放在数组的哪一个位置上， 是通过key的hashCode来计算的。这个位置也成为hash桶。

通过hash计算出来的值将通过indexFor方法找到它所在的table下标：

这个方法其实是对table.length取模， 当两个key通过hashCode计算相同时，则发生了hash冲突(碰撞)，HashMap解决hash冲突的方式是用链表。当发生hash冲突时，则将存放在数组中的Entry设置为新值的next（这里要注意的是，比如A和B都hash后都映射到下标i中，之前已经有A了，当map.put(B)时，将B放到下标i中，A则为B的next，所以新值存放在数组中，旧值在新值的链表上）。

例如上图， 一个长度为16的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。它的内部其实是用一个Entity数组来实现的，属性有key、value、next。

接着看看put方法：

469行， 如果key为空， 则把这个对象放到第一个数组上。

471行， 计算key的hash值

472行， 通过indexFor方法返回分散到数组table中的下标

473行， 通过table[i]获取新Entry的值， 如果值不为空，则判断key的hash值和equals来判断新的Entry和旧的Entry值是否相同， 如果相同则覆盖旧Entry的值并返回。

484行， 往数组上添加新的Entry。

添加Entry时，当table的容量大于theshold((int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1))， 这里实际上就是16*0.75=12

如上， 当满足一定条件后 table就开始扩容， 这个过程也称为rehash， 具体请看下图：

559行： 创建一个新的Entry数组

564行： 将数组转移到新的Entry数组中

565行： 修改resize的条件threshold

再具体的实现大家可以看下jdk7中HashMap的相关源码。

二：JDK8中的HashMap：

一直到JDK7为止，HashMap的结构都是这么简单，基于一个数组以及多个链表的实现，hash值冲突的时候，就将对应节点以链表的形式存储。

这样子的HashMap性能上就抱有一定疑问，如果说成百上千个节点在hash时发生碰撞，存储一个链表中，那么如果要查找其中一个节点，那就不可避免的花费O(N)的查找时间，这将是多么大的性能损失。这个问题终于在JDK8中得到了解决。再最坏的情况下，链表查找的时间复杂度为O(n),而红黑树一直是O(logn),这样会提高HashMap的效率。

JDK7中HashMap采用的是位桶+链表的方式，即我们常说的散列链表的方式，而JDK8中采用的是位桶+链表/红黑树的方式，也是非线程安全的。当某个位桶的链表的长度达到某个阀值的时候，这个链表就将转换成红黑树。

JDK8中，当同一个hash值的节点数大于等于8时，将不再以单链表的形式存储了，会被调整成一颗红黑树（上图中null节点没画）。这就是JDK7与JDK8中HashMap实现的最大区别。

public V put(K key, V value) {

return putVal(hash(key), key, value, false, true);

}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
//如果当前map中无数据，执行resize方法。并且返回n
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果要插入的键值对要存放的这个位置刚好没有元素，那么把他封装成Node对象，放在这个位置上就完事了
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//否则的话，说明这上面有元素
else {
Node<K,V> e; K k;
//如果这个元素的key与要插入的一样，那么就替换一下，也完事。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//1.如果当前节点是TreeNode类型的数据，执行putTreeVal方法
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//还是遍历这条链子上的数据，跟jdk7没什么区别
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//2.完成了操作后多做了一件事情，判断，并且可能执行treeifyBin方法
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) //true || –
e.value = value;
//3.
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//判断阈值，决定是否扩容
if (++size > threshold)
resize();
//4.
afterNodeInsertion(evict);
return null;
}

treeifyBin()就是将链表转换成红黑树。

之前的indefFor()方法消失 了，直接用(tab.length-1)&hash，所以看到这个，代表的就是数组的角标。

具体红黑树的实现大家可以看下JDK8中HashMap的实现。

三：需要注意的地方：

再谈HashCode的重要性

前面讲到了，HashMap中对Key的HashCode要做一次rehash，防止一些糟糕的Hash算法生成的糟糕的HashCode，那么为什么要防止糟糕的HashCode？

糟糕的HashCode意味着的是Hash冲突，即多个不同的Key可能得到的是同一个HashCode，糟糕的Hash算法意味着的就是Hash冲突的概率增大，这意味着HashMap的性能将下降，表现在两方面：

1、有10个Key，可能6个Key的HashCode都相同，另外四个Key所在的Entry均匀分布在table的位置上，而某一个位置上却连接了6个Entry。这就失去了HashMap的意义，HashMap这种数据结构性高性能的前提是，Entry均匀地分布在table位置上，但现在确是1 1 1 1 6的分布。所以，我们要求HashCode有很强的随机性，这样就尽可能地可以保证了Entry分布的随机性，提升了HashMap的效率。

2、HashMap在一个某个table位置上遍历链表的时候的代码：

if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

看到，由于采用了"&&"运算符，因此先比较HashCode，HashCode都不相同就直接pass了，不会再进行equals比较了。HashCode因为是int值，比较速度非常快，而equals方法往往会对比一系列的内容，速度会慢一些。Hash冲突的概率大，意味着equals比较的次数势必增多，必然降低了HashMap的效率了。

HashMap的table为什么是transient的

一个非常细节的地方：

transient Entry[] table;

看到table用了transient修饰，也就是说table里面的内容全都不会被序列化，不知道大家有没有想过这么写的原因？

在我看来，这么写是非常必要的。因为HashMap是基于HashCode的，HashCode作为Object的方法，是native的：

public native int hashCode();

这意味着的是：HashCode和底层实现相关，不同的虚拟机可能有不同的HashCode算法。再进一步说得明白些就是，可能同一个Key在虚拟机A上的HashCode=1，在虚拟机B上的HashCode=2，在虚拟机C上的HashCode=3。

这就有问题了，Java自诞生以来，就以跨平台性作为最大卖点，好了，如果table不被transient修饰，在虚拟机A上可以用的程序到虚拟机B上可以用的程序就不能用了，失去了跨平台性，因为：

1、Key在虚拟机A上的HashCode=100，连在table[4]上

2、Key在虚拟机B上的HashCode=101，这样，就去table[5]上找Key，明显找不到

整个代码就出问题了。因此，为了避免这一点，Java采取了重写自己序列化table的方法，在writeObject选择将key和value追加到序列化的文件最后面：

private void writeObject(java.io.ObjectOutputStream s)

throws IOException

{

Iterator<Map.Entry<K,V>> i =

(size > 0) ? entrySet0().iterator() : null;
// Write out the threshold, loadfactor, and any hidden stuff
s.defaultWriteObject();

// Write out number of buckets
s.writeInt(table.length);

// Write out size (number of Mappings)
s.writeInt(size);

// Write out keys and values (alternating)
if (size &gt; 0) {
    for(Map.Entry&lt;K,V&gt; e : entrySet0()) {
        s.writeObject(e.getKey());
        s.writeObject(e.getValue());
    }
}

}

而在readObject的时候重构HashMap数据结构：

private void readObject(java.io.ObjectInputStream s)

throws IOException, ClassNotFoundException

{

// Read in the threshold (ignored), loadfactor, and any hidden stuff

s.defaultReadObject();

if (loadFactor <= 0 || Float.isNaN(loadFactor))

throw new InvalidObjectException("Illegal load factor: " +

loadFactor);
// set hashSeed (can only happen after VM boot)
Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET,
        sun.misc.Hashing.randomHashSeed(this));

// Read in number of buckets and allocate the bucket array;
s.readInt(); // ignored

// Read number of mappings
int mappings = s.readInt();
if (mappings &lt; 0)
    throw new InvalidObjectException(&quot;Illegal mappings count: &quot; +
                                      mappings);

int initialCapacity = (int) Math.min(
        // capacity chosen by number of mappings
        // and desired load (if &gt;= 0.25)
        mappings * Math.min(1 / loadFactor, 4.0f),
        // we have limits...
        HashMap.MAXIMUM_CAPACITY);
int capacity = 1;
// find smallest power of two which holds all mappings
while (capacity &lt; initialCapacity) {
    capacity &lt;&lt;= 1;
}

table = new Entry[capacity];
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
useAltHashing = sun.misc.VM.isBooted() &amp;&amp;
        (capacity &gt;= Holder.ALTERNATIVE_HASHING_THRESHOLD);

init();  // Give subclass a chance to do its thing.

// Read the keys and values, and put the mappings in the HashMap
for (int i=0; i&lt;mappings; i++) {
    K key = (K) s.readObject();
    V value = (V) s.readObject();
    putForCreate(key, value);
}

}

一种麻烦的方式，但却保证了跨平台性。

这个例子也告诉了我们：尽管使用的虚拟机大多数情况下都是HotSpot，但是也不能对其它虚拟机不管不顾，有跨平台的思想是一件好事。

HashMap和Hashtable的区别

HashMap和Hashtable是一组相似的键值对集合，它们的区别也是面试常被问的问题之一，我这里简单总结一下HashMap和Hashtable的区别：

1、Hashtable是线程安全的，Hashtable所有对外提供的方法都使用了synchronized，也就是同步，而HashMap则是线程非安全的

2、Hashtable不允许空的value，空的value将导致空指针异常，而HashMap则无所谓，没有这方面的限制

3、上面两个缺点是最主要的区别，另外一个区别无关紧要，我只是提一下，就是两个的rehash算法不同，Hashtable的是：

这个hashSeed是使用sun.misc.Hashing类的randomHashSeed方法产生的。HashMap的rehash算法上面看过了，也就是：