1.我了解不同的哈希映射机制,并在键冲突的处理方式(无论是开放寻址 - 线性/二次探测,链接,扩展哈希等哪一个不HashSet的/ HashMap的使用?
2.我认识到,一个良好的HashMap依赖于一个好的哈希函数。如何Java的HashSet的/ HashMap的哈希的对象?我知道有一个哈希函数,但到目前为止字符串来实现这个我没有必要。如果我现在想的哈希我创建一个Java对象 - 做我需要实现哈希函数?抑或是Java的有一个内置在创造一个哈希码的方法是什么?
我知道,因为它立足于这是不恒定的内存地址散列函数的默认实现不能依靠。
你能回答许多这些问题自己,通过阅读the source code for HashMap
。
(提示:你通常可以找到使用谷歌的Java SE类的源代码,例如搜索“java.util.HashMap source
”)
我理解的不同哈希映射机制,并在键冲突的处理方式(无论是开放寻址 - 线性/二次探测,链接,扩展哈希等哪一个不HashSet的/ HashMap的使用?
链接。看到源代码。 (154行中的版本我挂)。
如何Java的HashSet的/ HashMap的哈希的对象?
事实并非如此。该对象的hashCode
方法被调用来做到这一点。看到源代码。 (线360)。
如果你看一下代码,你会看到一些有趣的皱纹:
Object.hashCode()
调用返回的哈希码被“炒”进一步减少冲突的机会。 (阅读评论!)如果我现在想的哈希我创建一个Java对象 - 做我需要实现哈希函数?
你可以做到这一点。
无论你需要做的这取决于你如何定义equals
为类。具体地讲,Java的HashMap
,HashSet
和相关的类放在hashcode()
和equals(Object)
以下要求:
a.equals(b)
然后a.hashCode() == b.hashCode()
。a
处于HashSet
或处于HashMap
的关键,通过a.hashCode()
返回的值不得改变。!a.equals(b)
,那么概率a.hashCode() == b.hashCode()
应该是低的,特别是如果a
和b
可能是为应用哈希键。(由于性能原因的最后一个要求。如果你有一个“穷”的哈希函数,结果在一个高概率,不同的关键字散列相同的hashCode,你会得到大量的碰撞。散列链将变得不平衡了,你不会得到通常预期哈希表操作的平均O(1)
表现在最坏的情况下,性能会O(N)
;即相当于一个线性搜索链表)。
抑或是Java的有一个内置在创造一个哈希码的方法是什么?
每个类都继承hashCode()
默认Object
方法(除非被覆盖)。它采用了被称为“身份的散列码”;即,其基于所述对象的标识(其参考)的散列值。这符合equals(Object)
的默认实现...简单的使用==
比较引用。
我知道,因为它立足于这是不恒定的内存地址散列函数的默认实现不能依靠。
这是不正确。
默认hashCode()
方法返回“身份哈希码”。这通常是基于在某个时间点的对象的内存地址,但它不是该对象的内存地址。
特别地,如果一个对象是由垃圾收集器移动时,它的“身份哈希码”保证不会发生变化。是。这是正确的,它不会改变......即使对象是感动!
(他们是如何有效地实现,这是相当聪明的。见https://stackoverflow.com/a/3796963/139985了解详情。)
底线是默认Object.hashCode()
方法满足所有我上面列出的要求。它可以依靠。
问题1)
Java的HashMap
实现使用链实施应对冲突。把它看成是链表的数组。
问题2
Object
具有equals和hashCode
的默认实现。 equals
被实现为return this == other
和hashcode
是(所有意图和目的)作为分配随机标识符的每个实例,并使用该实现为hashCode
。
正如在Java中extends Object
所有类,他们都继承了这些实现。
有些类默认覆盖这些实现。 String
,正如你所说,是一个很好的例子。另一种是在集合API的类 - 所以ArrayList
实现了基于其包含的元素这些方法。
至于落实的好hashCode
,这是一个黑暗艺术的一点点。最佳实践Here's a pretty good summary。
你最后的评论:
我知道,因为它立足于这是不恒定的内存地址散列函数的默认实现不能依靠。
这是不正确的。 hashCode
的默认实现是恒定的,因为这是该方法的合同的一部分。从the Javadoc:
每当它是一个Java应用程序的执行期间,在同一对象上调用一次以上,hashCode方法必须一致地返回相同的整数,没有设置中使用的信息等于在对象上比较被修改。该整数不必从一个应用的执行保持一致,以同一应用程序的另一执行。