码谱记录HashMap 是一种功能强大的数据结构，具有广泛的应用，尤其是在需要快速查找时间时。然而，如果我们不注意细节，它可能会使 HashMap 变慢。
因此，我们需要了解如何使 HashMap 尽可能地快。
HashMap 的瓶颈
HashMap 在最优情况下可以达到 O(1)的时间复杂度。对于每个元素，HashMap计算哈希码并将元素放入与该哈希码关联的桶中。
桶实际上是一个简单的链表，在链表中查找元素不是很快O(n)，但如果链表非常小，这就不是问题。当我们有很多哈希码冲突时，问题就产生了。所以我们希望有少量的大桶，而不是大量的小桶。
在最坏的情况下，我们将所有内容都放在一个桶中，我们的HashMap会降级为链表。因此，我们得到的不是O(1)查找时间，而是非常不令人满意的 O(n)。
链表优化
从 Java 8 开始，HashMap内置了一项优化： 当桶变得太大时，它们被转换为树，而不是链表。这将O(n)的悲观时间带到了O(log(n))，这要好得多。为此，HashMap的键需要实现Comparable接口。
这是一个很好的自动解决方案，但它并不完美。O(log(n)) 仍然比期望的常数时间差，并且转换和存储树需要额外的功率和内存。
hashCode 优化
hashCode 的优化，我们需要考虑两个方面：生成的哈希码的质量和速度。
哈希码的质量
哈希码存储在 int 变量中，因此可能的哈希数受限于int类型的容量。因为哈希用于计算带有桶的数组的索引，这意味着我们可以在没有哈希冲突的情况下，存储在HashMap中的键数量也是有限的。
为了尽可能避免冲突，我们希望尽可能均匀地分布散列。换句话说，我们要实现均匀分布。这意味着每个哈希码值与任何其他值具有相同的发生机会。
一个糟糕的 hashCode 方法会有一个非常不平衡的分布。在最坏的情况下，它总是会返回相同的数字。
自定义哈希码
通常，我们想要重写equals方法时，我们还需要重写 hashCode 方法。
有时，我们可以利用类的特定身份，轻松制作一个非常快速的hashCode方法。
假设我们的对象的身份完全基于它的整数id。然后，我们可以只使用这个id作为哈希函数：
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
MemberWithId that = (MemberWithId) o;
return id.equals(that.id);
}
@Override
public int hashCode() {
return id;
}
它将非常快并且不会产生任何碰撞。我们的HashMap将表现得像它有一个整数键而不是一个复杂的对象。
有时，我们可能需要多个字段来确定哈希值：
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
MemberWithNameAndAge that = (MemberWithNameAndAge) o;
if (!age.equals(that.age)) return false;
return name != null ? name.equals(that.name) : that.name == null;
}
@Override
public int hashCode() {
int result = age.hashCode();
result = 31 * result + (name != null ? name.hashCode() : 0);
return result;
}
上面例子中，我们以某种方式组合 age 和 name 的哈希值，值得注意的是，里面有一个乘数 31，它可是精挑细选的值。
它是质数，可以产生更好的分布情况，乘以它可以使用位运算进行优化，当然它也足够小：
31 * i == (i << 5) - i
位运算的效率极高，要是想得到更加分散的散列，也可以选择一下较大的质数，如 524287 ：
524287 * i == (i << 19) - i
利用 Objects
java.util.Objects 是 JDK 1.7 中加入的工具类，它已经实现了一个自定义的 hash() 方法：
@Override
public int hashCode() {
return Objects.hash(name, age);
}
该方法底层选用的乘数为 31。
