美文网首页
HashMap 1.8与1.7不同

HashMap 1.8与1.7不同

作者: 专职掏大粪 | 来源:发表于2020-07-19 09:55 被阅读0次

    4.4 1.8 hash方法
    作者:牛客7380095号
    链接:https://www.nowcoder.com/discuss/151172?source_id=profile_create&channel=-2
    来源:牛客网

    Java 8中的散列值优化函数


    image

    只做一次16位右位移异或
    key.hashCode()函数调用的是key键值类型自带的哈希函数,返回int型散列值

    理论上散列值是一个int型,如果直接拿散列值作为下标访问HashMap主数组的话,考虑到2进制32位带符号的int范围大概40亿的映射空间。只要哈希函数映射得比较均匀松散,一般应用是很难出现碰撞的。
    但问题是一个40亿长度的数组,内存是放不下的.HashMap扩容之前的数组初始大小才16,所以这个散列值是不能直接拿来用的.
    用之前还要先做对数组的长度取模运算,得到的余数才能用来访问数组下标
    源码中模运算就是把散列值和数组长度做一个"与"操作,


    image

    这也正好解释了为什么HashMap的数组长度要取2的整次幂
    因为这样(数组长度-1)正好相当于一个“低位掩码”
    “与”操作的结果就是散列值的高位全部归零,只保留低位值,用来做数组下标访问

    以初始长度16为例,16-1=15
    2进制表示是00000000 00000000 00001111
    和某散列值做“与”操作如下,结果就是截取了最低的四位值


    image

    但这时候问题就来了,这样就算我的散列值分布再松散,要是只取最后几位的话,碰撞也会很严重

    这时候“扰动函数”的价值就体现出来了


    image

    右位移16位,正好是32位一半,自己的高半区和低半区做异或,就是为了混合原始hashCode的高位和低位,以此来加大低位的随机性
    而且混合后的低位掺杂了高位的部分特征,这样高位的信息也被变相保留下来。

    index的运算规则是

    e.hash & (newCap - 1)
    

    newCap是2的幂,所以newCap - 1的高位全0

    若e.hash值只用自身的hashcode,index只会和e.hash的低位做&操作.这样一来,index的值就只有低位参与运算,高位毫无存在感,从而会带来哈希冲突的风险
    所以在计算key的hashCode时,用其自身hashCode与其低16位做异或操作
    这也就让高位参与到index的计算中来了,即降低了哈希冲突的风险又不会带来太大的性能问题

    三、为何HashMap的数组长度一定是2的次幂?

    我们来继续看上面提到的resize方法

    void resize(int newCapacity) {
            Entry[] oldTable = table;
            int oldCapacity = oldTable.length;
            if (oldCapacity == MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return;
            }
    
            Entry[] newTable = new Entry[newCapacity];
            transfer(newTable, initHashSeedAsNeeded(newCapacity));
            table = newTable;
            threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
        }
    
    

    如果数组进行扩容,数组长度发生变化,而存储位置 index = h&(length-1),index也可能会发生变化,需要重新计算index,我们先来看看transfer这个方法

    void transfer(Entry[] newTable, boolean rehash) {
            int newCapacity = newTable.length;
         //for循环中的代码,逐个遍历链表,重新计算索引位置,将老数组数据复制到新数组中去(数组不存储实际数据,所以仅仅是拷贝引用而已)
            for (Entry<K,V> e : table) {
                while(null != e) {
                    Entry<K,V> next = e.next;
                    if (rehash) {
                        e.hash = null == e.key ? 0 : hash(e.key);
                    }
                    int i = indexFor(e.hash, newCapacity);
                    //将当前entry的next链指向新的索引位置,newTable[i]有可能为空,有可能也是个entry链,如果是entry链,直接在链表头部插入。
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                }
            }
        }
    
    

    这个方法将老数组中的数据逐个链表地遍历,扔到新的扩容后的数组中,我们的数组索引位置的计算是通过 对key值的hashcode进行hash扰乱运算后,再通过和 length-1进行位运算得到最终数组索引位置。

    HashMap的数组长度一定保持2的次幂,比如16的二进制表示为 10000,那么length-1就是15,二进制为01111,同理扩容后的数组长度为32,二进制表示为100000,length-1为31,二进制表示为011111。从下图可以我们也能看到这样会保证低位全为1,而扩容后只有一位差异,也就是多出了最左位的1,这样在通过 h&(length-1)的时候,只要h对应的最左边的那一个差异位为0,就能保证得到的新的数组索引和老数组索引一致(大大减少了之前已经散列良好的老数组的数据位置重新调换),个人理解。

    在这里插入图片描述

    还有,数组长度保持2的次幂,length-1的低位都为1,会使得获得的数组索引index更加均匀

    在这里插入图片描述

    我们看到,上面的&运算,高位是不会对结果产生影响的(hash函数采用各种位运算可能也是为了使得低位更加散列),我们只关注低位bit,如果低位全部为1,那么对于h低位部分来说,任何一位的变化都会对结果产生影响,也就是说,要得到index=21这个存储位置,h的低位只有这一种组合。这也是数组长度设计为必须为2的次幂的原因。


    在这里插入图片描述

    如果不是2的次幂,也就是低位不是全为1此时,要使得index=21,h的低位部分不再具有唯一性了,哈希冲突的几率会变的更大,同时,index对应的这个bit位无论如何不会等于1了,而对应的那些数组位置也就被白白浪费了。

    get方法

     public V get(Object key) {
         //如果key为null,则直接去table[0]处去检索即可。
            if (key == null)
                return getForNullKey();
            Entry<K,V> entry = getEntry(key);
            return null == entry ? null : entry.getValue();
     }
    
    

    get方法通过key值返回对应value,如果key为null,直接去table[0]处检索。我们再看一下getEntry这个方法

    final Entry<K,V> getEntry(Object key) {
    
            if (size == 0) {
                return null;
            }
            //通过key的hashcode值计算hash值
            int hash = (key == null) ? 0 : hash(key);
            //indexFor (hash&length-1) 获取最终数组索引,然后遍历链表,通过equals方法比对找出对应记录
            for (Entry<K,V> e = table[indexFor(hash, table.length)];
                 e != null;
                 e = e.next) {
                Object k;
                if (e.hash == hash && 
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            }
            return null;
        }    
    
    

    可以看出,get方法的实现相对简单,key(hashcode)–>hash–>indexFor–>最终索引位置,找到对应位置table[i],再查看是否有链表,遍历链表,通过key的equals方法比对查找对应的记录。要注意的是,有人觉得上面在定位到数组位置之后然后遍历链表的时候,e.hash == hash这个判断没必要,仅通过equals判断就可以。其实不然,试想一下,如果传入的key对象重写了equals方法却没有重写hashCode,而恰巧此对象定位到这个数组位置,如果仅仅用equals判断可能是相等的,但其hashCode和当前对象不一致,这种情况,根据Object的hashCode的约定,不能返回当前对象,而应该返回null,后面的例子会做出进一步解释。

    四、重写equals方法需同时重写hashCode方法

    最后我们再聊聊老生常谈的一个问题,各种资料上都会提到,“重写equals时也要同时覆盖hashcode”,我们举个小例子来看看,如果重写了equals而不重写hashcode会发生什么样的问题

    
    public class MyTest {
        private static class Person{
            int idCard;
            String name;
    
            public Person(int idCard, String name) {
                this.idCard = idCard;
                this.name = name;
            }
            @Override
            public boolean equals(Object o) {
                if (this == o) {
                    return true;
                }
                if (o == null || getClass() != o.getClass()){
                    return false;
                }
                Person person = (Person) o;
                //两个对象是否等值,通过idCard来确定
                return this.idCard == person.idCard;
            }
    
        }
        public static void main(String []args){
            HashMap<Person,String> map = new HashMap<Person, String>();
            Person person = new Person(1234,"乔峰");
            //put到hashmap中去
            map.put(person,"天龙八部");
            //get取出,从逻辑上讲应该能输出“天龙八部”
            System.out.println("结果:"+map.get(new Person(1234,"萧峰")));
        }
    }
    
    实际输出结果:null
    
    

    https://www.cnblogs.com/vi3nty/p/10642456.html

    所以,在重写equals的方法的时候,必须注意重写hashCode方法,同时还要保证通过equals判断相等的两个对象,调用hashCode方法要返回同样的整数值。而如果equals判断不相等的两个对象,其hashCode可以相同(只不过会发生哈希冲突,应尽量避免)。

    五、JDK1.8中HashMap的性能优化

    假如一个数组槽位上链上数据过多(即拉链过长的情况)导致性能下降该怎么办?
    JDK1.8在JDK1.7的基础上针对增加了红黑树来进行优化。即当链表超过8时,链表就转换为红黑树,利用红黑树快速增删改查的特点提高HashMap的性能,其中会用到红黑树的插入、删除、查找等算法。
    关于这方面的探讨我们以后的文章再做说明。

    https://www.jianshu.com/p/ee0de4c99f87

    https://mp.weixin.qq.com/s/keA-xNOHxMUPAFxKnna-Bg

    相关文章

      网友评论

          本文标题:HashMap 1.8与1.7不同

          本文链接:https://www.haomeiwen.com/subject/msklkktx.html