HashCode。如何使用它

Question

尽管我非常了解HashCode是什么以及Hash Table是做什么的，但我不得不承认我不知道如何使用它（除了普通字典之外）。我想实现自己的哈希表所以首先我想知道的非常基本的关于哈希：

• 我知道我可以在Java和Scala getHashCode()/hashCode()得到的哈希码。这个数字是如何确定的。 （只是出于好奇）
• 如果我知道一个对象的HashCode，我该如何访问它？也就是说，我怎样称之为内存桶？
• 我可以更改/设置变量HashCode？

现在，我有一个非常大的（约10^9）诠释列表。我将访问其中的一些（从无到有），并且我需要以最快的方式进行操作。哈希表是实现它的最佳方式吗？

PS：我不想讨论它，我只是想知道如果HashTable是知道是最有效的。如果还有其他好方法，也许你可以指点我。

谢谢，

Answer 1

哈希码是只是保证是为每一个类型的对象的“相同”与原始对象相同的数字。

这意味着为每个哈希码调用返回“0”将是有效的，但是自我毁灭。问题是可以（并且在大多数情况下会）是重复的。

如果您知道对象的哈希码，则无法访问它。按照我上面的例子，如果所有的对象都返回“0”，你仍然不能问哪个对象有散列码0.然而，你可以要求所有具有散列码0的对象并查看它们（这是散列表的作用，它通过获得具有相同哈希代码的代码来减少迭代次数，然后查找这些代码）。

如果您要设置（更改）HashCode，它不会是散列码，因为给定的“状态”对象的值不能更改。

至于“最好的办法”做到这一点，返回相同哈希码的唯一对象越少，您的哈希表将执行得越好。如果你有一个很长的“int”列表，你可以使用这个int值作为你的哈希码，并且你会得到这个罕见的完美哈希值 - 其中每个对象都映射到一个哈希码。

请注意，哈希表不适合存储ints的这种情况。对于那些试图存储复杂对象的情况来说更好，因为这些复杂对象不易通过其他机制进行唯一标识或比较。

你的“Int列表”的问题是，如果你有数字5并且你想在你的表格中查找它，你只需要在那里找到一个数字5。

现在，如果你想看看数字5是否存在于你的表格中，那就是另一回事了。

对于一组数值很少的孔，您可以制作一个简单的布尔数组。如果[5]存在（是），则列表中的a比a更大。如果你的一组数字非常稀疏（1，5，10002930304），那么这将不是一个很好的解决方案，因为你会在第2,3,4点存储“False”，然后在最后一堆点中存储“False”数字，但它是一个直接查找，无论您添加多少个数字，O（1）都不再需要一个步骤。

通过将这种类型的存储变成二进制查找到字节数组，您可以使这种类型的存储变得更加密集，但除非您对位操作非常好，否则可以跳过它。它会涉及这样的东西：

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

如果您的最高号码真的很大，这仍然会用完内存。

因此，对于一个大的稀疏列表，我会使用排序的整数数组而不是轻度填充的布尔数组。一旦它被排序为一个数组，你只需进行二分搜索;从排序后的数组中间开始，如果你想要的数字更高，那么将中间的上半部分分在中间，并检查该数字，重复。

排序后的int数组需要更多的步骤，但不会有太多的步骤，它不会浪费任何内存来存储不存在的数字。

Answer 2

哈希函数返回一个整数。您使用该整数（键）作为索引来存储您的信息。在java中，你可以使用java.util.Hashtable。您始终可以自行滚动，它可以像使用键作为索引的数组一样简单。

对于您的程序，您确实需要弄清楚您需要如何访问元素。散列表提供给特定项目超快速访问，但没有如果您使用的是Java，检查哈希表，看看方法足以满足您的应用程序（应该）提供顺序访问

：

http://java.sun.com/j2se/1.4.2/docs/api/java/util/Hashtable.html

Answer 3

INT的大名单作为工作中，我通过索引来访问查找表。那么我猜索引是关键，列表元素是值。希望澄清一下

在这种情况下，java.util.HashTable并不比java.util.ArrayList更好。 A HashTable将消耗至少两倍的内存，同时提供稍微较慢的访问。

甚至比ArrayList更好是一个普通的int[]，因为不需要创建和存储整数实例。我估计这会减少3倍的内存消耗。

但是，保持内存10^9 int仍然是一个令人生畏的主张，因为每个int消耗4个字节的内存。这是4 GB。您可能希望至少将列表的一部分保存在磁盘而不是内存中，然后使用RandomAccessFile来查找正在查找的索引。