Java中常见数据结构Map之HashMap

java

之前很早就在博客中写过HashMap的一些东西:

彻底搞懂HashMap,HashTableConcurrentHashMap关联:

http://www.cnblogs.com/wang-meng/p/5808006.html

HashMap和HashTable的区别:

http://www.cnblogs.com/wang-meng/p/5720805.html

 

今天来讲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 > 0) {

for(Map.Entry<K,V> 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 < 0)

throw new InvalidObjectException("Illegal mappings count: " +

mappings);

int initialCapacity = (int) Math.min(

// capacity chosen by number of mappings

// and desired load (if >= 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 < initialCapacity) {

capacity <<= 1;

}

table = new Entry[capacity];

threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);

useAltHashing = sun.misc.VM.isBooted() &&

(capacity >= 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<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算法上面看过了,也就是:

以上是 Java中常见数据结构Map之HashMap 的全部内容, 来源链接: utcz.com/z/394618.html

回到顶部