0

有没有办法在不篡改Java函数的情况下严格保证每个Hashmap桶的条目数object.hashcode()？

负载因子是平均值：（条目数）/（桶数）。本质上，假设我有一个容量为 1000 的 Hashmap。为了这个示例，假设我使用 1 的负载因子。我将要存储在 HashMap 中的 100 个对象具有错误的哈希码函数，它总是返回每个对象的值相同。当我存储完 100 个对象后，它们都将映射到同一个 HashMap 存储桶，我最终会获得 LinkedList 的性能。负载因子将保持沉默，因为 100 个条目 / 1000 个桶 = 0.1 < 1。现在如果我放置 1 M 个相同的对象会发生什么。HashMap 永远不会调整大小（无论如何都不会使用），因为永远不会触发LF 。

我知道这是现实世界中不常见的情况，但想提高我的理解。HashMap 有没有办法防止这种情况发生，或者至少从结构本身得到一些警告？

4

2 回答 2

5

AHashMap将始终根据密钥的哈希码计算要使用的存储桶。如果每个键具有相同的哈希码，它们都将映射到同一个桶。hashCode()如果不提供更好的实现，您将无法阻止您描述的行为。

您可以查看使用开放寻址的 Map 实现（例如Trove的THashMap）。他们总是每个桶只有一个条目。但是性能不会提高，它们只是以不同的方式处理冲突，而且它们也不会解决您的根本问题：哈希码错误。

于 2012-12-25T21:31:21.470 回答
0

编写一个完美的 HashFunction 是实现您所寻找的唯一方法。

给定一组小的特权输入，可以调整排列表，以便这些输入产生不同的哈希值，从而产生所谓的完美哈希函数。

查看Pearson 的哈希

于 2012-12-25T23:00:27.060 回答