哈希表的基本原理？ [英] The fundamentals of Hash tables?

问题描述

我对哈希表的基本概念感到很困惑。如果我要编写一个哈希，我怎么会开始呢？ Hash表和普通数组之间有什么区别？

I'm quite confused about the basic concepts of a Hash table. If I were to code a hash how would I even begin? What is the difference between a Hash table and just a normal array?

基本上如果有人回答了这个问题，我认为我的所有问题都会得到解答：
如果我有100个随机生成的数字（作为键），我将如何实施一个哈希表，为什么这对数组有利？

Basically if someone answered this question I think all my questions would be answered: If I had 100 randomly generated numbers (as keys), how would I implement a hash table and why would that be advantageous over an array?

Psuedo-code或Java作为一种学习工具将被赞赏...

Psuedo-code or Java would be appreciated as a learning tool...

推荐答案

到目前为止，答案有助于定义哈希表并解释一些理论，但我认为一个例子可以帮助你更好地感受它们。

The answers so far have helped to define hash tables and explain some theory, but I think an example may help you get a better feeling for them.

哈希表和普通数组有什么区别？

A哈希表和数组都是允许您存储和检索数据的结构。两者都允许您指定索引并检索与其关联的值。正如Daniel Spiewak指出的那样，差异在于数组的索引是顺序，而散列表的索引是基于与它们相关联的数据的值。

A hash table and an array are both structures that allow you to store and retrieve data. Both allow you to specify an index and retrieve a value associated with it. The difference, as Daniel Spiewak noted, is that the indices of an array are sequential, while those of a hash table are based on the value of the data associated with them.

为什么我会使用哈希表？

哈希表可以提供一种非常有效的方法来搜索大量数据中的项目，特别是那些无法轻易搜索的数据。 （大在这里意味着 ginormous ，因为它会需要很长时间才能执行顺序搜索。

A hash table can provide a very efficient way to search for items in large amounts of data, particularly data that is not otherwise easily searchable. ("Large" here means ginormous, in the sense that it would take a long time to perform a sequential search).

如果我要编写哈希代码，我怎么才能开始？

没问题。最简单的方法是发明一个可以对数据执行的任意数学运算，返回一个数字 N （通常是一个整数）。然后使用该数字作为桶数组的索引，并将数据存储在存储桶＃ N 中。诀窍在于选择一种操作，该操作倾向于将值放在不同的存储桶中，以便您以后轻松找到它们。

No problem. The simplest way is to invent an arbitrary mathematical operation that you can perform on the data, that returns a number N (usually an integer). Then use that number as the index into an array of "buckets" and store your data in bucket #N. The trick is in selecting an operation that tends to place values in different buckets in a way that makes it easy for your to find them later.

示例：大型商场保留了顾客车辆和停车位置的数据库，以帮助购物者记住他们停放的位置。数据库存储 make ，颜色，牌照，以及停车位置。在离开商店时，购物者通过输入其颜色和颜色来找到他的汽车。数据库返回（相对较短的）车牌和停车位列表。快速扫描可以找到购物者的汽车。

Example: A large mall keeps a database of its patrons' cars and parking locations, to help shoppers remember where they parked. The database stores make, color, license plate, and parking location. On leaving the store a shopper finds his car by entering the its make and color. The database returns a (relatively short) list of license plates and parking spaces. A quick scan locates the shopper's car.

您可以使用SQL查询实现此功能：

You could implement this with an SQL query:

SELECT license, location FROM cars WHERE make="$(make)" AND color="$(color)"

如果数据存储在一个数组中，基本上只是一个列表，你可以想象通过扫描一个数组来查找所有匹配的条目来实现查询。

If the data were stored in an array, which is essentially just a list, you can imagine implementing the query by scanning an array for all matching entries.

另一方面，设想一个哈希规则：

On the other hand, imagine a hash rule:

添加make中所有字母的ASCII字符代码color，除以100，并使用余数作为哈希值。

Add the ASCII character codes of all the letters in the make and color, divide by 100, and use the remainder as the hash value.

此规则将每个项目转换为0到0之间的数字99，基本上将数据排序到100个桶中。每次客户需要找到汽车时，您都可以对品牌和颜色进行散列，以找到包含该信息的100个 one 桶。你已经立即将搜索量缩减了100倍！

This rule will convert each item to a number between 0 and 99, essentially sorting the data into 100 buckets. Each time a customer needs to locate a car, you can hash the make and color to find the one bucket out of 100 that contains the information. You've immediately reduced the search by a factor of 100!

现在将示例扩展为大量数据，比如一个数据库，其中包含数百万条搜索条目几十个标准。 良好的哈希函数会以最小化任何其他搜索的方式将数据分发到存储桶中，从而节省大量时间。

Now scale the example to huge amounts of data, say a database with millions of entries that is searched based on tens of criteria. A "good" hash function will distribute the data into buckets in a way that minimizes any additional searching, saving a significant amount of time.

这篇关于哈希表的基本原理？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！