Java中常见数据结构Map之HashMap

之前很早就在博客中写过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算法上面看过了,也就是:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券