logo标签列表

HashMap在重写hashcode方法时的性能表现

javadictionarycollections
6
在HashMap中，如果我将自定义对象作为键，那么如果我覆盖hashCode()方法并将其实现为传递值'1'，那么会有任何性能影响吗？如果我更改hashCode()方法以使用Math.random()函数返回随机值，对性能会产生什么影响？
1
试一试就知道了。不过，这只能出于好奇心，因为hashCode并不是任意的。 - Marko Topolnik
如果你将 hashCode() 方法更改为返回随机值，性能可能会发生很多事情——但是你的程序将完全崩溃，因为它不再获得正确的结果。 - Louis Wasserman
5个回答
6

添加Math.random()不会对性能造成太大的影响，但是通过random()函数构建hashCode值是一个坏习惯。相反，您可以使用一些好的哈希函数来最小化碰撞，这些函数也要快得多。您可以查看以下链接进行参考：http://www.partow.net/programming/hashfunctions/

5
如果你在提到渐进时间复杂度，那么：
由于 HashMap 使用 hashCode 来计算哈希表中要使用哪个桶，如果你从 hashCode 返回 1，则会使你的 HashMap 的性能类似于（未排序的）LinkedList。
返回随机值将简单地使你的 HashMap 失效，因为相等的对象将不再具有相等的 hashCode。
摘自维基百科：Wikipedia。
+----------------------+----------+------------+----------+--------------+
|                      |  Insert  |   Delete   |  Search  | Space Usage  |
+----------------------+----------+------------+----------+--------------+
| Unsorted linked list | O(1)*    | O(1)*      | O(n)     | O(n)         |
| Hash table           | O(1)     | O(1)       | O(1)     | O(n)         |
+----------------------+----------+------------+----------+--------------+

总之，你会失去以下内容：

  • 在搜索你的HashMap时时间复杂度从O(1)变为O(n)
  • 在HashMap中查找（它将不再起作用）
你在这里插入表格的目的是什么？ - Robert Harvey
好的，我已经删除了无关部分。 - Adam Arold
2

hashCode()总是返回1会降低HashMap的性能。每个对象默认为相同的bucket，导致哈希表成为链表。根据Effective Java, item 9，这将导致时间复杂度为二次方而不是线性的。

返回随机值将违反相等的对象具有相等的hashCodes的规定，您将无法检索存储的对象。

1
你稍微误解了Effective Java中的那个句子。平均而言，哈希访问是O(1)，而链表（或退化的哈希表）的访问时间为O(n)。因此，如果你有一个算法需要进行n次哈希访问，这将具有*O(n)的平均复杂度（因为O(n) = O(n) · O(1)），但最坏情况下的复杂度为O(n²)*。 - amon
0
如果您总是返回1（或任何其他常量值）以供插入的所有对象，那么HashMap将在内部降级为“链接列表”。这意味着插入、删除和查询不再具有O(1)的复杂度，而是具有O(n)的复杂度，并可能对性能造成严重影响。
如果您返回随机值，则HashMap将变得不一致。可能会出现“相同”的键出现两次（尽管根据规范，每个键只能出现一次）。也可能发生这样的情况：您找不到某个键的值，尽管您之前已经使用不同的hashCode插入了它。
然后确切的行为也取决于equals方法的实现，但这些是这种实现可能产生的主要影响。
0
在hashcode()中返回固定值肯定会使你的哈希表运行变慢。所有的值都将被分配到同一个bin中，因此查找操作将需要线性时间（而不是使用良好的哈希函数的平均常数时间）。
返回随机值将完全破坏哈希映射协议。值将被分配到随机的bin中，并在随机的bin中查找，因此没有任何保证你能找到之前存储的值。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接