我正在寻找一个关于哈希表如何工作的解释-用简单的英语为我这样的傻瓜!

例如,我知道它接受键,计算哈希(我正在寻找一个解释),然后执行某种模运算来计算出它在存储值的数组中的位置,但我的知识到此为止。

谁能解释一下过程吗?

编辑:我并不是特别问哈希码是如何计算的,而是对哈希表如何工作的一般概述。


当前回答

Hashtable inside contains cans in which it stores the key sets. The Hashtable uses the hashcode to decide to which the key pair should plan. The capacity to get the container area from Key's hashcode is known as hash work. In principle, a hash work is a capacity which when given a key, creates an address in the table. A hash work consistently returns a number for an item. Two equivalent items will consistently have a similar number while two inconsistent objects may not generally have various numbers. When we put objects into a hashtable then it is conceivable that various objects may have equal/ same hashcode. This is known as a collision. To determine collision, hashtable utilizes a variety of lists. The sets mapped to a single array index are stored in a list and then the list reference is stored in the index.

其他回答

这是另一种看待它的方式。

我假设你理解数组A的概念,它支持索引操作,你可以一步找到第I个元素,A[I],不管A有多大。

因此,例如,如果您想存储一组恰好年龄不同的人的信息,一个简单的方法是有一个足够大的数组,并使用每个人的年龄作为数组的索引。这样,你就可以一步获取任何人的信息。

But of course there could be more than one person with the same age, so what you put in the array at each entry is a list of all the people who have that age. So you can get to an individual person's information in one step plus a little bit of search in that list (called a "bucket"). It only slows down if there are so many people that the buckets get big. Then you need a larger array, and some other way to get more identifying information about the person, like the first few letters of their surname, instead of using age.

这是基本思想。不使用年龄,可以使用任何能产生良好价值观传播的人的函数。这就是哈希函数。比如你可以把这个人名字的ASCII表示的每三分之一,按某种顺序打乱。重要的是,您不希望太多人散列到同一个存储桶,因为速度取决于存储桶保持较小。

Hashtable inside contains cans in which it stores the key sets. The Hashtable uses the hashcode to decide to which the key pair should plan. The capacity to get the container area from Key's hashcode is known as hash work. In principle, a hash work is a capacity which when given a key, creates an address in the table. A hash work consistently returns a number for an item. Two equivalent items will consistently have a similar number while two inconsistent objects may not generally have various numbers. When we put objects into a hashtable then it is conceivable that various objects may have equal/ same hashcode. This is known as a collision. To determine collision, hashtable utilizes a variety of lists. The sets mapped to a single array index are stored in a list and then the list reference is stored in the index.

对于所有寻找编程用语的人,下面是它是如何工作的。高级哈希表的内部实现有许多复杂之处,并且对存储分配/释放和搜索进行了优化,但顶层的思想是非常相同的。

(void) addValue : (object) value
{
   int bucket = calculate_bucket_from_val(value);
   if (bucket) 
   {
       //do nothing, just overwrite
   }
   else   //create bucket
   {
      create_extra_space_for_bucket();
   }
   put_value_into_bucket(bucket,value);
}

(bool) exists : (object) value
{
   int bucket = calculate_bucket_from_val(value);
   return bucket;
}

其中calculate_bucket_from_val()是哈希函数,所有的惟一性魔术都必须在这里发生。

经验法则是: 对于要插入的给定值,bucket必须是唯一的,并且派生自它应该存储的值。

Bucket是存储值的任何空间-这里我将它保持int作为数组索引,但它也可能是一个内存位置。

我的理解是这样的:

这里有一个例子:把整个表想象成一系列的桶。假设您有一个带有字母-数字哈希码的实现,并且每个字母都有一个存储桶。该实现将哈希码以特定字母开头的每个项放入相应的bucket中。

假设你有200个对象,但只有15个对象的哈希码以字母“B”开头。哈希表只需要查找和搜索'B' bucket中的15个对象,而不是所有200个对象。

至于计算哈希码,没有什么神奇的。目标只是让不同的对象返回不同的代码,对于相同的对象返回相同的代码。您可以编写一个类,它总是为所有实例返回相同的整数作为哈希代码,但这实际上会破坏哈希表的用处,因为它只会变成一个巨大的桶。

到目前为止,所有的答案都很好,并且从不同的方面了解了哈希表的工作方式。这里有一个简单的例子,可能会有帮助。假设我们想要存储一些带有小写字母字符串的项作为键。

正如simon所解释的,哈希函数用于从大空间映射到小空间。对于我们的例子,一个简单的哈希函数实现可以取字符串的第一个字母,并将其映射为一个整数,因此“短吻鳄”的哈希代码为0,“蜜蜂”的哈希代码为1,“斑马”的哈希代码为25,等等。

接下来,我们有一个包含26个存储桶的数组(在Java中可以是数组列表),我们将项放入与键的哈希码匹配的存储桶中。如果我们有不止一个元素键以相同字母开头,它们就会有相同的哈希码,所以它们都会进入存储桶中寻找那个哈希码所以必须在存储桶中进行线性搜索才能找到一个特定的元素。

在我们的例子中,如果我们只有几十个项目,键横跨字母表,它会工作得很好。然而,如果我们有一百万个条目,或者所有的键都以'a'或'b'开头,那么我们的哈希表就不是理想的。为了获得更好的性能,我们需要一个不同的哈希函数和/或更多的桶。