HashMap覆盖hashcode方法时的性能 [英] HashMap Performance when overriding hashcode method

问题描述

在 HashMap 中，如果我将自定义对象作为键。

如果我覆盖
hashCode（）方法并实现它， 1 ';会有任何性能损失吗？如果我更改 hashCode（）方法以使用返回随机值，则



< ） function
性能会发生什么变化？

解决方案

渐近时间复杂度：

因为 HashMap 使用 hashCode 如果您从 hashCode 中返回 1 ，您将有效地使您的 HashMap 的性能类似于（未排序） LinkedList 的性能。

由于等于对象将不再具有等于的对象，返回随机值将会简单地破坏 HashMap hashCode 。

摘录自维基百科：

  + ----------------- ----- + ---------- + ------------ + ---------- + --------- ----- + 
 | |插入|删除|搜索|空间使用| 
 + ---------------------- + ---------- + ----------- -  + ---------- + -------------- + 
 |未排序链表| O（1）* | O（1）* | O（n）| O（n）| 
 |哈希表| O（1）| O（1）| O（1）| O（n）| 
 + ---------------------- + ---------- + ----------- -  + ---------- + -------------- + 
  

因此，总结你失去：

• 搜索 / code>（从 O（1）到 O（n））



In a HashMap, if I put custom objects as a key.

What would happen if I override hashCode() method and implement it to pass value as '1'; would there be any performance hit ?

if I change hashCode() method to return random value using Math.random() function what would happen to performance ?

解决方案

If you are referring to the asymptotic time complexity then:

since HashMap uses hashCode to calculate which bucket to use in the hashtable if you return 1 from hashCode you effectively make your HashMap's performance be like an (unsorted) LinkedList's performance.

Returning random values will simply blow your HashMap up since equal objects will no longer have equal hashCodes.

Excerpt from 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)         |
+----------------------+----------+------------+----------+--------------+

So to sum it up you lose:

• Time complexity when searching your HashMap (from O(1) to O(n))
• lookup in your HashMap (it won't work anymore)

这篇关于HashMap覆盖hashcode方法时的性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！