Java集合之一——HashMap(辨析)

看到一篇讲hashmap的文章,讲的很不错,但是有一点我觉得作者没有讲清楚,这里我说一下自己的理解。

原文,先看原文:

https://blog.csdn.net/woshimaxiao1/article/details/83661464

前文概述,该博客的主要内容如下:

1. 什么是哈希表(主干为数组)、什么是哈希冲突、如何解决哈希冲突。这些大都是数据结构的基础知识,这里不再赘述

2.hashmap的实现原理:

简要概述一下:

主干是数组,冲突用链表解决。

每个元素其实都一个entry对象。

默认容量为16,负载因子0.75,当前元素数量大于等于容量*负载因子,扩容。

扩容后的大小为最接近当前size的二次幂。

在扩容之后,会进行元素迁移,从旧hashmap迁移到新hashmap。

为什么扩容后的大小要是二次幂?

1)在迁移的时候,会根据key重新计算hashcode,重新获取新的index。此时如果最大容量每次都是2的二次幂,那么在计算index的时候(默认情况下),有50%的概率其位置不发生改变,可以与原数组保持一致。

2)同时,如果最大长度保持为二次幂,那么散列的会更均匀,如果不是二次幂,会导致某些位置永远不会被散列到,浪费地址空间。

3.关于重写equals必须要重写hashcode的辨析。

作者通过get_entry方法引出的这个问题,但是我觉得并不很合适,原因如下:

首先我们看代码:

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;
    }    

通过代码可以看到,在获取元素的时候,首先是根据key计算hashcode,然后根据hashcode找到index,之后进行两个判断

1)hashcode是否相等

2)key是否equal

作者提到,这里有些人会认为再次判断hashcode是否相等多此一举,仅通过equals即可,这是不对的。但是作者后面又说这和重写equals没重写hashcode相关,因为只重写equals不重写hashcode,那么equals可能相等,但是hashcode不等,此时按照Object的HashCode约定,不能返回元素。

我认为这里说的是对的,但是不够清晰。为了讲清楚,我们把其分为两中情况。

1)hashcode和equals都不重写,此时二者比较的都是key的地址(如果key是对象)

此时对于某一次get,可以得到一个hashcode,通过hashcode,得到index,然后进行判断

1】hashcode是否相等

2】key是否equal

此时,如果舍弃判断1】,我们会发现,因为此时equals和hashcode等价,舍弃其中任何一个都不会违背Object的HashCode约定。

2)重写equals,不重写hashcode

此时对于某一次get,可以得到一个hashcode,通过hashcode,得到index,然后进行判断

1】hashcode是否相等

2】key是否equal

此时,如果舍弃判断1】,我们会发现,因为此时equals和hashcode不等价,同时因为index是由hashcode计算出来的,不同的hashcode可能得到同样的index,没有判断1】,得到的返回值的hashcode不一定等,但是因为内容相同,可以得到返回值,此时得到的返回值是不符合Object的HashCode约定,该约定要求hashcode的范围一定要比equals大。

4.关于为什么重写equals必须要重写hashcode

如果不重写,我们会发现,在hashmap的主干(数组)上的key-value对key可能相等,但是因为hashcode不等,得到的index也不等,因为计算hashcode用的是地址,不是值。按照要求,此时应该出现hash冲突。这也导致key正确,但是定位不到正确的位置,得到正确的值,得到null。

【讲得不好,后续接着改】

5. JDK1.8中HashMap的性能优化

链表>=8,数组长>=64,链表变红黑树。

 

热门相关:冉冉心动   隔壁的女人   修真界败类   买妻种田:山野夫君,强势宠!   异世修真邪君