Java集合之一——HashMap（辨析）

2023-07-30 21:30 由 TheBigSeven 发表于 #后端开发

看到一篇讲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，链表变红黑树。

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