携手创作，共同成长！这是我参与「掘金日新计划 · 8 月更文挑战」的第1天，点击查看活动详情

前言

自信满满的体验了字节的一面，挫败的一轮游了。其中遇到一个代码题，其实考的也不是很难，但是比较考察细节，知识的理解度。感觉很值得和大家分享一下。

面试全经过&题目

```java public class Test { class Item{

    private int code = 1;

    public Item(int code){
        this.code =  code;
    }

    override public int hashCode() {
        return code;
    }
}

public static void main(String[] args) {
    Set<Item> set = new HashSet<>();
    set.add(new Item(0));
    set.add(new Item(0));
    set.add(new Item(1));

    System.out.println(set.size());

}

}

```

面试官：这有一道代码题，你看下，你觉得最终会输出什么呢？
我：2
面试官：为什么？谈谈原因？
我：因为重写了hash,HashSet 内部会认为传递同样的code是同一个对象，所以第一个new Item(0)和第二个new Item(0) 会被认为是同一个对象，然后后者会覆盖前者，所以是2
面试官：实际上这段代码是不能运行的，现在需要你修改正确，并输出结果
我：编写代码中....(Item 改成了 static,override 关键字修改为 @Override注释)
我：改完了，运行一看，发现是 3，你说尴尬不尴尬.....
面试官：你觉得为啥和你之前设想的不一样
我：应该是还需要实现equals方法
面试官：为什么呢？
我：...

问题解惑

虽然中间有些修改语法的操作，但是那对于大家应该都是小Case,主要的核心问题是：

HashSet 中add() 方法中对同一对象的判定逻辑
hashCode() 和 equals() 的理解

接下来一一都为大家介绍下。

HashSet.add() 内部逻辑

实际上 HashSet 的实现是依靠 HashMap 实现的，具体逻辑可以看下面的代码： ``` public class HashSet{ //内部实现依靠HashMap private transient HashMap map;

//固定的value值
private static final Object PRESENT = new Object();

HashSet(int initialCapacity, float loadFactor, boolean dummy) { //初始化的时候声明 map = new LinkedHashMap<>(initialCapacity, loadFactor); }

//添加方法，实际上，将数据作为key存储到  HashMap 中
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

} ```

所以咱们要看的逻辑，实际上就 HashMap 怎么判定 key 相等的，具体代码在 java.util.HashMap#putVal 中

看下分支条件

if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

分解下：

p.hash == hash

先看这个hash 是什么？ HashMap() 中提供了一个哈希算法，将传入的 key 通过这个算法转成了一个 Int 值，然后存储到数据节点中了。

哈希算法的实现是将 key 的 hashCode() 值右位移16位，然后和自身异或。为啥这样实现的原理很复杂，此处按下不表，但是可以明确知道的是，内部使用了 hashCode()，所以这个方法很重要。

//put 的时候进行hash() public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } //hash算法的实现 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

(k = p.key) == key || (key != null && key.equals(k))

代码中内部赋值了k，看起来有点长，咱们简化以下，其实发现就两个条件 p.key == key 和 key.equals(p.key)，两者只要有一个成立就可以了。

所以根据以上分析，只有 hashCode() 和 equals() 两者都相等，HashMap 才会认为是同个key。

hashCode() 和 equals() 的理解

首先它们是什么？

这俩方法都是 Object 类内的方法，它们本身代表的含义是

```

public boolean equals(Object obj) {
    return (this == obj);
}

@HotSpotIntrinsicCandidate
public native int hashCode();

```

equals() ：内部使用了 “==”。判断是否是同个对象，如果是值类型，判断内容是否一致，如果是引用类型，则是引用地址是否相等。 hashCode()：一个本地方法，主要看native 中的实现。

之前我理解的是，hashCode返回的就是对象的存储地址，但是看到一篇文章上公布了 JVM中代码的实现，发现事实并不是这样。

它内部提供了多种实现方式供选择，可以通过JVM启动参数中添加-XX:hashCode=x，但是 JDK8 默认的是 hashCode=5

随机数
内存地址做移位再和一个随机数做异或
固定值1
自增序列的当前值
内存地址
当前线程有关的一个随机数+三个确定值，运用xorshift随机数算法得到的一个随机数。

以上是个知识小拓展吧，问题核心是 hashCode()这个方法为什么会被设计出来？

然后看为什么？两个方法的设计目的

关于 hashCode()方法的使用，我目前只在 HashMap 的源码中看到过。以及在源码中对此方法的注释中，也可以窥见一斑。它的主要目的是为了服务于散列表的实现，例如最典型的 HashMap。

那 HashMap 特殊在哪里？这个取决于它的数据结构的特殊-哈希表。

首先从最基础的数据结构看起，我们知道数组和链表的概念，但是这两者使用起来各有优劣，例如： - 数组查找遍历快，但是插入删除慢。 - 链表插入删除快，查找遍历慢。

咱们用的时候，需要根据场景决定使用哪个。但是有时候就是既要查询快，又要插入删除快。有没有一种东西，能够将两者的优点结合起来呢？

有，那就是哈希表。它使用使用数组查询，链表插入和删除，充分结合了这两者的优点。

哈希表有多种不同的实现方法，最常用的一种方法——拉链法，我们可以理解为“链表的数组”，HashMap 用的正是这个一个方法，示意图如下：

哈希表的一个关键定义是：

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表

生成这个关键码值(Key value)的地方就用到了 hashCode()。大家从上面的结构示意图上也可以知道，不同的对象 hashCode 有可能是一致的。所以会在同个数据下标下，多个数据节点串在一起。这就是所谓的哈希碰撞。

好的哈希算法要尽量避免哈希碰撞，但是呢，也从来不能保证说是完全避免的，这可能就是提高性能必须要付出的代价吧。

那我们使用 equals() 代替 hashCode() 可以吗？这个是内存地址是不是就可以减少碰撞的几率了呢？

答案是不可以！！！

有以下原因：

equals() 的默认实现是用的内存地址，但是也有很多类改写了，例如 String 就修改了。
equals() 允许重写后，逻辑可能会变得复杂，所以就性能上来说，大概率没有 hashCode() 的性能高。

所以这两个方法的职责是完全不一样的 - equals() 主要负责判断是否是同个对象，绝对可靠，但是性能可能较差 - hashCode() 主要负责在提高判断效率（主要是在哈希表数据结构中），但是只能大概率保证是同个对象，不可靠

然后再看Hashmap 源码中的判断逻辑，细节就来了,优先判断 hash,hash 一样再判断 equals(),这样就可以提高性能，真是妙啊！

if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

对应咱们经常在网上看到的两者关系总结，是不是就十分清晰了呢 - equals()相等，hashCode()肯定相等 - hashCode()相等，equals()不一定相等

然后怎么用？重写 equals() 和 hashCode() 的注意事项

在多数情况下，这两个函数是不用考虑的。直接使用它们的默认设计就能够了。

但凡事总有特殊，例如 String 就针对其进行了重写。

``` // String.java public boolean equals(Object anObject) { //内存地址相等，肯定是同个对象 if (this == anObject) { return true; } //否则逐个判断字符是否一致 if (anObject instanceof String) { String aString = (String)anObject; if (!COMPACT_STRINGS || this.coder == aString.coder) { return StringLatin1.equals(value, aString.value); } } return false; }

public int hashCode() {
    int h = hash;
    if (h == 0 && !hashIsZero) {
        h = isLatin1() ? StringLatin1.hashCode(value)
                       : StringUTF16.hashCode(value);
        if (h == 0) {
            hashIsZero = true;
        } else {
            hash = h;
        }
    }
    return h;
}

//StringLatin1.java

//哈希算法的真正实现
public static int hashCode(byte[] value) {
    int h = 0;
    for (byte v : value) {
        h = 31 * h + (v & 0xff);
    }
    return h;
}

//逐个判断字符是否一致
public static boolean equals(byte[] value, byte[] other) {
    if (value.length == other.length) {
        for (int i = 0; i < value.length; i++) {
            if (value[i] != other[i]) {
                return false;
            }
        }
        return true;
    }
    return false;
}

```

除了源码，真实项目中，也有重写的需求，例如我负责的购物车，购物车商品模型中，针对是否是同个商品对象的逻辑，就写在了 equals() 方法中。

一般咱们的需求出发点，基本都是需要改造 equals()。但是一旦修改了 equals(), 就要一定要考虑修改 hashCode()，不然你用在散列表中就可能出现奇奇怪怪的问题。

equals()重写的时候需要满足以下规则：

内存地址相同，一定返回true (使用“==”操作符检查)
类型不一致，一定返回false(使用instanceof 操作符检查)
类型转换后，判断类中每个关键属性，符合预设，返回 true , 否则 false

hashCode()重写的时候需要满足以下规则：

保证同一个对象，多次调用 Hashcode 是一致的。
equals()相等，hashCode()肯定相等

另外，阿里巴巴开发规范也有对这俩方法的重写制订了一些规范，咱们开发的时候也可以做个参考：

总结

以上都是我的事后分析，再回头看这个面试题，需要做的就是

不受重写 hashCode() 的干扰，给出正确的列表长度答案
说出对 hashCode() 和 equals() 的理解

以及最关键的，基础知识理解透彻的重要性，平时要认真对待，多学习多思考，多问为什么。

参考资料

Effective Java 中文版

Java Object.hashCode()返回的是对象内存地址？

浅谈Java中的hashcode方法

看似简单的hashCode和equals面试题，竟然有这么多坑！

最简单的易懂的技术干货，好玩的事情，都会在公众号「浅浅同学的开发笔记」分享，快来呀～期待与你共同成长！

一道代码题对考察Java HashCode 的深度理解

前言