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

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

谁能解释一下过程吗?

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


当前回答

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.

其他回答

用法和行话:

哈希表用于快速存储和检索数据(或记录)。 记录使用散列键存储在桶中 哈希键是通过对记录中包含的选定值(键值)应用哈希算法来计算的。所选值必须是所有记录的公共值。 每个桶可以有多条记录,这些记录按照特定的顺序组织。

现实世界的例子:

哈希公司成立于1803年,当时没有任何计算机技术,只有300个文件柜来保存大约3万名客户的详细信息(记录)。每个文件夹都清楚地标识其客户端编号,从0到29,999的唯一编号。

当时的档案管理员必须迅速为工作人员获取和存储客户记录。工作人员决定使用哈希方法来存储和检索他们的记录会更有效。

要归档客户记录,档案管理员将使用写在文件夹上的唯一客户编号。使用这个客户端编号,他们将哈希键调整300,以识别包含它的文件柜。当他们打开文件柜时,他们会发现里面有很多按客户号排序的文件夹。在确定正确的位置后,他们会简单地把它塞进去。

要检索客户记录,档案管理员将在一张纸上获得客户号码。使用这个唯一的客户端编号(哈希键),他们会将其调整300,以确定哪个文件柜拥有客户端文件夹。当他们打开文件柜时,他们会发现里面有很多按客户号排序的文件夹。通过搜索记录,他们可以快速找到客户端文件夹并检索它。

在我们的实际示例中,桶是文件柜,记录是文件夹。


需要记住的一件重要的事情是,计算机(及其算法)处理数字比处理字符串更好。因此,使用索引访问大型数组要比按顺序访问快得多。

正如Simon提到的,我认为非常重要的是哈希部分是转换一个大空间(任意长度,通常是字符串等),并将其映射到一个小空间(已知大小,通常是数字)进行索引。记住这一点非常重要!

因此,在上面的示例中,大约30,000个可能的客户机被映射到一个较小的空间中。


这样做的主要思想是将整个数据集划分为几个部分,以加快实际搜索的速度,而实际搜索通常是耗时的。在我们上面的例子中,300个文件柜中的每个(统计上)将包含大约100条记录。搜索100条记录(不管顺序)要比处理3万条记录快得多。

你可能已经注意到有些人已经这样做了。但是,在大多数情况下,他们只是使用姓氏的第一个字母,而不是设计一个哈希方法来生成哈希键。因此,如果您有26个文件柜,每个文件柜都包含从a到Z的一个字母,理论上您只是将数据分割并增强了归档和检索过程。

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

(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作为数组索引,但它也可能是一个内存位置。

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

我假设你理解数组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表示的每三分之一,按某种顺序打乱。重要的是,您不希望太多人散列到同一个存储桶,因为速度取决于存储桶保持较小。

其实比这更简单。

哈希表不过是一个包含键/值对的向量数组(通常是稀疏数组)。此数组的最大大小通常小于哈希表中存储的数据类型的可能值集中的项数。

哈希算法用于根据将存储在数组中的项的值生成该数组的索引。

This is where storing vectors of key/value pairs in the array come in. Because the set of values that can be indexes in the array is typically smaller than the number of all possible values that the type can have, it is possible that your hash algorithm is going to generate the same value for two separate keys. A good hash algorithm will prevent this as much as possible (which is why it is relegated to the type usually because it has specific information which a general hash algorithm can't possibly know), but it's impossible to prevent.

因此,您可以使用多个键来生成相同的散列代码。当这种情况发生时,将遍历向量中的项,并在向量中的键和正在查找的键之间进行直接比较。如果找到,则返回与该键关联的值,否则不返回任何值。

我的理解是这样的:

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

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

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