哈希码.如何使用它

Question

虽然我非常了解HashCode是什么以及哈希表的作用,但我不得不承认我不知道如何使用它(超越常用词典).我想实现自己的哈希表,所以首先我想知道关于哈希的基本知识:

• 我知道我可以在Java和Scala中使用getHashCode()/ 获取哈希码hashCode().这个数字是如何确定的.(只是出于好奇)
• 如果我知道HashCode某个对象,我该如何访问它？也就是说,我该如何调用该内存桶？
• 我可以更改/设置变量HashCode吗？

现在,我有一个非常大的(大约10 ^ 9)Int列表.我将访问其中一些(从无到有),我需要尽可能以最快的方式完成.哈希表是最好的方法吗？

PS:我不想讨论它,我只是想知道HashTable是否被认为是最有效的.如果存在其他好的方法,也许你可以指点我.

谢谢,

Answer 1

哈希码只是一个数字,保证与原始对象"相同"的每种类型的对象相同.

这意味着为每个哈希代码调用返回"0"将是有效的,但是会弄巧成拙.关键是可以(并且在大多数情况下)可以重复.

如果您知道对象的哈希码,则无法访问它.根据上面的例子,如果所有对象都返回"0",你仍然无法询问哪个对象有哈希码0.但是,你可以要求哈希码为0的所有对象并查看它们(这是哈希表的作用,它通过只获取具有相同哈希码的那些来减少迭代量,然后查看那些).

如果您要设置(更改)HashCode,它将不是哈希码,因为给定"State"的对象的值不能更改.

至于执行此操作的"最佳方式",返回相同哈希码的唯一对象越少,哈希表的执行效果就越好.如果你有一个很长的"int"列表,你可以使用那个int值作为你的哈希码,你将拥有那个罕见的完美哈希 - 每个对象只映射一个哈希码.

请注意,哈希表并不适合这种存储int的情况.对于您尝试存储不易于使用其他机制进行唯一标识或比较的复杂对象的情况,这种情况会更好.

你的"Int of List"的问题在于,如果你有5号并且你想在你的表中查找它,你就会在那里找到5号.

现在,如果你想查看表中是否存在数字5,那就是另一回事了.

对于一组具有少数孔的数字,您可以创建一个简单的布尔数组.如果[5]存在(是真),则列表中有a.如果你的数字组很稀疏(1,5,10002930304),那么这不是一个很好的解决方案,因为你在第2,3,4点存储"False",然后在最后一个存储它们中的一大堆数字,但它是一个直接查找,无论你添加多少个数字,都不会再花费一个步骤 - O(1).

您可以通过对字节数组进行二进制查找来使这种类型的存储更加密集,但除非您对位操作非常好,否则请跳过它.它会涉及看起来像这样的东西:

public boolean doesNumberExist(int number) {
    return bytes[number / 8] & ( 1 << number % 8);
}

如果您的最高数字非常大,这仍然会耗尽内存.

所以,对于一个大的稀疏列表,我会使用一个排序的整数数组而不是一个轻度填充的布尔数组.一旦它被排序为数组,你只需进行二分查找; 从排序数组的中间开始,如果您想要的数字更高,则将中间列表的上半部分划分并检查该数字,重复.

已排序的int数组需要更多步骤,但不会太多,并且不会为不存在的数字浪费任何内存.