HashCode的一些理解

HashCode是什么？

首先，Hash 是指哈希算法算法，这种算法可以输入任意数据，输出固定长度的字符串，这一输出结果就是 HashCode ，即哈希码。这个算法有这样几条规则：

同样的输入内容，通过这一算法，总是能够得到相同的结果。
不同的输入内容，得到的输出结果可能会相同。
如果两次的输出结果不同，则他们的输入内容也一定不同。

在Java/Kotlin中，所有类的基类 Object / Any 有一个方法：


/**
 * Returns a hash code value for the object.  The general contract of `hashCode` is:
 *
 * * Whenever it is invoked on the same object more than once, the `hashCode` method must consistently return the same integer, provided no information used in `equals` comparisons on the object is modified.
 * * If two objects are equal according to the `equals()` method, then calling the `hashCode` method on each of the two objects must produce the same integer result.
 */
public open fun hashCode(): Int

这个方法，会返回当前对象的哈希值。这个“当前对象的哈希值”，实际上是用当前对象存储的地址来计算得出的，所以哈希值可以简单的看做一个对象地址的映射。

HashCode有什么用？

基于哈希码的这些特性，很自然的想到，可以用来作为一个对象的唯一标识，来进行对比/查找。在Java中， hashCode() 方法正是这个用途。在Java的集合中，有一种无序但不可重复的集合，比如Set，Map等。这些集合因为插入的对象不能重复，所以在每次插入时都要跟原集合中的对象进行比较，不同或者不存在，才可以插入。如果每次插入时都很粗鲁的遍历一遍集合，每个对象挨个对比，那在集合中元素非常多时，代价会很大， HashCode 便在这里有了用武之地。

具体而言，因为 HashCode 间接的代表了对象的地址，所以每次插入新对象时，可以不用去查找有没有重复的对象，而是直接计算新对象的 HashCode ，然后在指定位置查看是否有对象存在；没有？那就直接插入。有？那就跟这个位置上已经存储的对象进行比较，如果确实是相同的对象，那就不用再进行重复插入了。如果是不同的对象，那还是要插入的，于是会基于这个地址，再使用一个新的地址来存储这个对象。在这一过程汇总，两个对象进行比较时，是用的 equals() 方法，而地址相同后的处理，则被称为 碰撞处理。

equals

equals() 方法也跟 hashCode() 方法类似，都是基类提供的可供重写的方法，这一方法用来对比两个对象是否相同。这里相同指的是概念上的相同。 equals() 方法默认的实现是：


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

用 == 来对比两个对象的地址，这是很简单的对比方式了。在我们实际使用过程中，可能有些场景下，不如如果一个对象他本身地址并没有变，而是内部一些字段发生了变化，那么为了让 equals() 方法能正确的反映这一事实，我们就需要重写 equlas() 方法了。而为了满足前面提到的 hashCode() 的特性，我们在重写 equlas() 方法时，都要同时重写 hashCode() 方法。只有这样，才能保证 hashCode() 方法有效，否则在像集合中这些情况，会有异常。也因此，我们可以得出一个结论：

两个对象，equals() 比较相等，那 hashCode() 也一定相等。
两个对象的 hashCode() 不同，则 equals() 是可能会相同的。

重写 `hashCode()` 方法

首先要明白，重写 hashCode() 方法，目的在于让计算的结果满足那一特性。除此之外，还要考虑计算出的结果尽量不要发生碰撞，切计算速度快，占用资源少等因素。因此虽然没有规定怎么写，但是我们可以参考 String 类来写：


public int hashCode() {
    int h = hash;
    final int len = length();
    if (h == 0 && len > 0) {
        for (int i = 0; i < len; i++) {
            h = 31 * h + charAt(i);
        }
        hash = h;
    }
    return h;
}

这一方式在《ffective Java》一书中也有提到，思路都是一样的。下面举个栗子：


data class Book(
    val name:String,
    val author:String,
    val date:Long
){

    override fun hashCode(): Int {
        var result = 31
        result = 31 * result + name.hashCode()
        result = 31 * result + author.hashCode()
        result = 31 * result + date.hashCode()
        return result
    }
}

这里用的是31，一般用一个不大不小的质数，比如17也可以，这样计算出来的结果长度适中，可以尽量避免碰撞，也不至于太长。这个模板很实用，在日常开发中需要重写时都可以按这个方法来实现。

碰撞

哈希算法有碰撞，而这个碰撞是不能避免的。道理也很简单，输出的数据是定长的，那输入结果必然是有限的，而输入的数据是无限的，所以就像一个经典的生日问题————有n个人不断进入同一个房间，房间内出现生日相同的人的概率问题————一样，随着输入数据的增加，发生碰撞的概率也会越来越高。虽然不能完全避免的，但是可以通过改变输出长度或算法等，尽力来降低碰撞的概率。而一旦真的发生了碰撞，就需要其他方式来解决碰撞了。比较常见的一个栗子是Java中的 HashMap ，他解决碰撞的方法是，Map中Value存储的是一个链表的头节点。当插入的数据不存在碰撞时，他可以直接存在这一Key对应的链表的头结点；当插入的数据已经存在，即发生碰撞时，头节点是已经保存了数据的，那么就跟在头结点后面增加一个节点来保存，以此类推。

HashCode是什么？

HashCode有什么用？

equals

重写 hashCode() 方法

碰撞

重写 `hashCode()` 方法