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 条评论
登录 后参与评论

相关文章

来自专栏aCloudDeveloper

算法导论第十四章 数据结构的扩张

一、概要   我们在教科书上所学的所有数据结构都是最常规、最精简的数据结构,即便如此,基本上所有能遇上的问题都能用这些数据结构来解决。但是有一些特殊的问题,需要...

21470
来自专栏xcywt

《大话数据结构》一些基础知识

第一章 数据结构绪论 1.4 基本概念和术语 1.4.1 数据 数据:描述客观事物的符号,是计算机中可以操作的对象,是能被极端及识别,并输入给计算机处理的符号集...

35790
来自专栏数据结构与算法

P3808 【模版】AC自动机(简单版)

题目背景 这是一道简单的AC自动机模版题。 用于检测正确性以及算法常数。 为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。 题目描述 给定n个模...

33350
来自专栏开发之途

Java集合框架源码解析之HashMap

17030
来自专栏算法channel

深度优先搜索和回溯结合后的终极模板

昨天 这5道算法题 都可以套用这个模板 推送了一个深度搜索和回溯结合的题目和另4道类似题,今天,逐个分析后4道题,最后提炼出模板。

14400
来自专栏数据结构与算法

P3808 【模版】AC自动机(简单版)

题目背景 这是一道简单的AC自动机模版题。 用于检测正确性以及算法常数。 为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。 题目描述 给定n个模...

29160
来自专栏owent

线段树相关问题 (引用 PKU POJ题目) 整理

如果(a < b – 1){分别计算a、b的次数和线段树[a + 1, b – 1)的次数,取大(小)的一项};

19720
来自专栏LanceToBigData

Java集合源码分析(四)HashMap

一、HashMap简介 1.1、HashMap概述   HashMap是基于哈希表的Map接口实现的,它存储的是内容是键值对<key,value>映射。此类不保...

31550
来自专栏来自地球男人的部落格

[LeetCode] 119. Pascal's Triangle II

【原题】 Given an index k, return the kth row of the Pascal’s triangle. For exampl...

21060
来自专栏Android知识点总结

Java总结之映射家族--Map概览

12240

扫码关注云+社区

领取腾讯云代金券