1.简介
HashMap是一种功能强大的数据结构，具有广泛的应用，尤其是在需要快速查找时间的情况下。但是，如果我们不注意细节，它可能会变得不理想。
在本教程中，我们将研究如何使HashMap尽可能快。
2. HashMap的瓶颈
HashMap的元素检索的最佳恒定时间（ O(1) ）来自散列的能力。对于每个元素， HashMap计算哈希码并将元素放入与该哈希码关联的存储桶中。由于不相等的对象可以具有相同的哈希码（这种现象称为哈希码冲突），因此存储桶的大小可能会增加。
存储桶实际上是一个简单的鍊表。在链接列表中查找元素不是很快（ O(n) ），但是如果列表很小，这不是问题。当我们遇到很多哈希码冲突时，问题就开始了，因此，我们有大量的大桶，而不是大量的小桶。
在最坏的情况下，我们将所有内容都放在一个存储桶中，我们的HashMap被降级为链接列表。因此，我们得到的不是O(1)查找时间，而是非常不令人满意的O(n) 。
3.树而不是LinkedList
从Java 8开始， HashMap内置了一种优化：当存储桶变得太大时，它们将被转换为树，而不是鍊表。这将O(n)的悲观时间带到O(log(n)) ，这要好得多。为此， HashMap的键需要实现Comparable接口。
这是一个不错的自动解决方案，但并不完美。 O(log(n))仍然比所需的恒定时间差，并且转换和存储树需要更多的功能和内存。
4.最佳hashCode实现
选择散列函数时，我们需要考虑两个因素：产生的散列码的质量和速度。
4.1。测量hashCode容量
哈希码存储在int变量中，因此可能的哈希数限制为int类型的容量。一定要这样，因为哈希值用于计算带有存储桶的数组的索引。这意味着我们可以在没有哈希冲突的情况下将数量有限的键存储在HashMap 。
为了尽可能避免冲突，我们希望尽可能均匀地散布哈希。换句话说，我们要实现均匀分布。这意味着每个哈希码值都具有与其他任何哈希值相同的机会。
同样，糟糕的hashCode方法将具有非常不平衡的分布。在最坏的情况下，它将始终返回相同的数字。
4.2。默认Object的hashCode
通常，我们不应该使用默认的Object's hashCode方法，因为我们不想在equals方法中使用对象标识。但是，在不太可能发生的情况下，我们真的想对HashMap键使用对象标识，则默认的hashCode函数可以正常工作。否则，我们将需要一个自定义实现。
4.3。自定义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行为就像它具有整数键而不是复杂的对象。
如果我们需要考虑更多字段，情况将变得更加复杂。假设我们要基于id和name相等：
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
MemberWithIdAndName that = (MemberWithIdAndName) o;
if (!id.equals(that.id)) return false;
return name != null ? name.equals(that.name) : that.name == null;
}现在，我们需要以某种方式组合id和name哈希值。
首先，我们将获得与以前相同的id的哈希值。然后，我们将其乘以一些精心选择的数字，并添加name的哈希值：
@Override
public int hashCode() {
int result = id.hashCode();
result = PRIME * result + (name != null ? name.hashCode() : 0);
return result;
}如何选择一个数字并不是一个容易回答的简单问题。从历史上看，最受欢迎的数字是31.它是质数，它导致分布良好，很小，并且可以通过位移运算来优化乘以它：
31 * i == (i << 5) - i但是，既然我们不需要为每个CPU周期而战，那么可以使用一些更大的素数。例如，也可以优化524287 ：
524287 * i == i << 19 - i并且，它可以提供质量更好的哈希，从而减少碰撞的机会。请注意，这些移位优化是由JVM自动完成的，因此我们不需要使用它们来混淆我们的代码。
4.4。 Objects实用程序类
我们刚刚实现的算法已经很好地建立了，我们通常不需要每次都手动重新创建它。相反，我们可以使用Objects类提供的帮助方法：
@Override
public int hashCode() {
return Objects.hash(id, name);
}在引擎盖下，它完全使用前面所述的算法（将数字31作为乘法器）。
4.5。其他哈希函数
与前面所述的哈希函数相比，有许多哈希函数提供的冲突机会更少。问题在于它们的计算量更大，因此无法提供我们寻求的速度增益。
如果出于某种原因我们确实需要质量，而又不太在乎速度，那么可以看一下Guava库中的Hashing类：
@Override
public int hashCode() {
HashFunction hashFunction = Hashing.murmur3_32();
return hashFunction.newHasher()
.putInt(id)
.putString(name, Charsets.UTF_8)
.hash().hashCode();
}选择32位函数非常重要，因为无论如何我们都无法存储更长的哈希。
5.结论
现代Java的HashMap是功能强大且经过优化的数据结构。但是，设计hashCode方法可能会使它的性能恶化。在本教程中，我们研究了使散列快速有效的可能方法。
0 评论