有很多答案，但没有一个是非常可视化的，而哈希表在可视化时很容易“点击”。

哈希表通常实现为链表数组。如果我们想象一个存储人名的表，经过几次插入之后，它可能会被放置在内存中，其中()包含的数字是文本/姓名的哈希值。

bucket#  bucket content / linked list

[0]      --> "sue"(780) --> null
[1]      null
[2]      --> "fred"(42) --> "bill"(9282) --> "jane"(42) --> null
[3]      --> "mary"(73) --> null
[4]      null
[5]      --> "masayuki"(75) --> "sarwar"(105) --> null
[6]      --> "margaret"(2626) --> null
[7]      null
[8]      --> "bob"(308) --> null
[9]      null

以下几点:

each of the array entries (indices [0], [1]...) is known as a bucket, and starts a - possibly empty - linked list of values (aka elements, in this example - people's names) each value (e.g. "fred" with hash 42) is linked from bucket [hash % number_of_buckets] e.g. 42 % 10 == [2]; % is the modulo operator - the remainder when divided by the number of buckets multiple data values may collide at and be linked from the same bucket, most often because their hash values collide after the modulo operation (e.g. 42 % 10 == [2], and 9282 % 10 == [2]), but occasionally because the hash values are the same (e.g. "fred" and "jane" both shown with hash 42 above) most hash tables handle collisions - with slightly reduced performance but no functional confusion - by comparing the full value (here text) of a value being sought or inserted to each value already in the linked list at the hashed-to bucket

链表长度与负载因子有关，而不是值的数量

如果表的大小增加，上面实现的哈希表倾向于调整自己的大小(即创建一个更大的桶数组，在那里创建新的/更新的链表，删除旧的数组)，以保持值与桶的比率(又名负载因子)在0.5到1.0的范围内。

Hans gives the actual formula for other load factors in a comment below, but for indicative values: with load factor 1 and a cryptographic strength hash function, 1/e　(~36.8%) of buckets will tend to be empty, another 1/e (~36.8%) have one element, 1/(2e) or ~18.4% two elements, 1/(3!e) about 6.1% three elements, 1/(4!e) or ~1.5% four elements, 1/(5!e) ~.3% have five etc.. - the average chain length from non-empty buckets is ~1.58 no matter how many elements are in the table (i.e. whether there are 100 elements and 100 buckets, or 100 million elements and 100 million buckets), which is why we say lookup/insert/erase are O(1) constant time operations.

哈希表如何将键与值关联

Given a hash table implementation as described above, we can imagine creating a value type such as `struct Value { string name; int age; };`, and equality comparison and hash functions that only look at the `name` field (ignoring age), and then something wonderful happens: we can store `Value` records like `{"sue", 63}` in the table, then later search for "sue" without knowing her age, find the stored value and recover or even update her age - happy birthday Sue - which interestingly doesn't change the hash value so doesn't require that we move Sue's record to another bucket.

当我们这样做的时候，我们使用哈希表作为一个关联容器，也就是map，它存储的值可以被认为是由一个键(名称)和一个或多个其他字段组成，仍然被称为值(在我的例子中，只是年龄)。用作映射的哈希表实现称为哈希映射。

这与前面我们存储离散值的例子形成了对比，比如“sue”，你可以把它看作是它自己的键:这种用法被称为散列集。

还有其他方法来实现哈希表

并不是所有的哈希表都使用链表(称为独立链表)，但大多数通用哈希表都使用链表，因为主要的替代封闭哈希(又名开放寻址)-特别是支持擦除操作-与易于冲突的键/哈希函数相比性能不太稳定。

---

简单讲一下哈希函数

强大的散列…

一个通用的、最小化最坏情况碰撞的哈希函数的工作是有效地随机地在哈希表桶周围散布键，同时总是为相同的键生成相同的哈希值。理想情况下，即使在键的任何位置改变一个位，也会随机地翻转结果哈希值中的大约一半位。

This is normally orchestrated with maths too complicated for me to grok. I'll mention one easy-to-understand way - not the most scalable or cache friendly but inherently elegant (like encryption with a one-time pad!) - as I think it helps drive home the desirable qualities mentioned above. Say you were hashing 64-bit doubles - you could create 8 tables each of 256 random numbers (code below), then use each 8-bit/1-byte slice of the double's memory representation to index into a different table, XORing the random numbers you look up. With this approach, it's easy to see that a bit (in the binary digit sense) changing anywhere in the double results in a different random number being looked up in one of the tables, and a totally uncorrelated final value.

// note caveats above: cache unfriendly (SLOW) but strong hashing...
std::size_t random[8][256] = { ...random data... };
auto p = (const std::byte*)&my_double;
size_t hash = random[0][p[0]] ^
              random[1][p[1]] ^
              ... ^
              random[7][p[7]];

弱但通常快速的哈希…

Many libraries' hashing functions pass integers through unchanged (known as a trivial or identity hash function); it's the other extreme from the strong hashing described above. An identity hash is extremely collision prone in the worst cases, but the hope is that in the fairly common case of integer keys that tend to be incrementing (perhaps with some gaps), they'll map into successive buckets leaving fewer empty than random hashing leaves (our ~36.8% at load factor 1 mentioned earlier), thereby having fewer collisions and fewer longer linked lists of colliding elements than is achieved by random mappings. It's also great to save the time it takes to generate a strong hash, and if keys are looked up in order they'll be found in buckets nearby in memory, improving cache hits. When the keys don't increment nicely, the hope is they'll be random enough they won't need a strong hash function to totally randomise their placement into buckets.

简短而甜蜜:

哈希表封装了一个数组，我们称之为internalArray。将项以如下方式插入数组:

let insert key value =
    internalArray[hash(key) % internalArray.Length] <- (key, value)
    //oversimplified for educational purposes

有时两个键会散列到数组中的同一个索引，而您希望保留这两个值。我喜欢把两个值都存储在同一个索引中，通过将internalArray作为一个链表数组来编码很简单:

let insert key value =
    internalArray[hash(key) % internalArray.Length].AddLast(key, value)

所以，如果我想从哈希表中检索一个项，我可以这样写:

let get key =
    let linkedList = internalArray[hash(key) % internalArray.Length]
    for (testKey, value) in linkedList
        if (testKey = key) then return value
    return null

删除操作写起来也很简单。正如你所知道的，从我们的链表数组中插入、查找和删除几乎是O(1)。

当我们的internalArray太满时，可能在85%左右的容量，我们可以调整内部数组的大小，并将所有项目从旧数组移动到新数组中。

哈希表完全基于这样一个事实，即实际计算遵循随机访问机模型，即内存中任何地址的值都可以在O(1)时间或常数时间内访问。

因此，如果我有一个键的宇宙(我可以在应用程序中使用的所有可能的键的集合，例如，滚动no。对于学生来说，如果它是4位，那么这个宇宙就是从1到9999的一组数字)，并且一种将它们映射到有限大小的数字集的方法可以在我的系统中分配内存，理论上我的哈希表已经准备好了。

Generally, in applications the size of universe of keys is very large than number of elements I want to add to the hash table(I don't wanna waste a 1 GB memory to hash ,say, 10000 or 100000 integer values because they are 32 bit long in binary reprsentaion). So, we use this hashing. It's sort of a mixing kind of "mathematical" operation, which maps my large universe to a small set of values that I can accomodate in memory. In practical cases, often space of a hash table is of the same "order"(big-O) as the (number of elements *size of each element), So, we don't waste much memory.

现在，一个大集合映射到一个小集合，映射必须是多对一的。因此，不同的键将被分配相同的空间(?? ?不公平)。有几种方法可以解决这个问题，我只知道其中最流行的两种:

Use the space that was to be allocated to the value as a reference to a linked list. This linked list will store one or more values, that come to reside in same slot in many to one mapping. The linked list also contains keys to help someone who comes searching. It's like many people in same apartment, when a delivery-man comes, he goes to the room and asks specifically for the guy. Use a double hash function in an array which gives the same sequence of values every time rather than a single value. When I go to store a value, I see whether the required memory location is free or occupied. If it's free, I can store my value there, if it's occupied I take next value from the sequence and so on until I find a free location and I store my value there. When searching or retreiving the value, I go back on same path as given by the sequence and at each location ask for the vaue if it's there until I find it or search all possible locations in the array.

CLRS的《算法导论》对这个主题提供了非常好的见解。

有很多答案，但没有一个是非常可视化的，而哈希表在可视化时很容易“点击”。

哈希表通常实现为链表数组。如果我们想象一个存储人名的表，经过几次插入之后，它可能会被放置在内存中，其中()包含的数字是文本/姓名的哈希值。

bucket#  bucket content / linked list

[0]      --> "sue"(780) --> null
[1]      null
[2]      --> "fred"(42) --> "bill"(9282) --> "jane"(42) --> null
[3]      --> "mary"(73) --> null
[4]      null
[5]      --> "masayuki"(75) --> "sarwar"(105) --> null
[6]      --> "margaret"(2626) --> null
[7]      null
[8]      --> "bob"(308) --> null
[9]      null

以下几点:

each of the array entries (indices [0], [1]...) is known as a bucket, and starts a - possibly empty - linked list of values (aka elements, in this example - people's names) each value (e.g. "fred" with hash 42) is linked from bucket [hash % number_of_buckets] e.g. 42 % 10 == [2]; % is the modulo operator - the remainder when divided by the number of buckets multiple data values may collide at and be linked from the same bucket, most often because their hash values collide after the modulo operation (e.g. 42 % 10 == [2], and 9282 % 10 == [2]), but occasionally because the hash values are the same (e.g. "fred" and "jane" both shown with hash 42 above) most hash tables handle collisions - with slightly reduced performance but no functional confusion - by comparing the full value (here text) of a value being sought or inserted to each value already in the linked list at the hashed-to bucket

链表长度与负载因子有关，而不是值的数量

如果表的大小增加，上面实现的哈希表倾向于调整自己的大小(即创建一个更大的桶数组，在那里创建新的/更新的链表，删除旧的数组)，以保持值与桶的比率(又名负载因子)在0.5到1.0的范围内。

Hans gives the actual formula for other load factors in a comment below, but for indicative values: with load factor 1 and a cryptographic strength hash function, 1/e　(~36.8%) of buckets will tend to be empty, another 1/e (~36.8%) have one element, 1/(2e) or ~18.4% two elements, 1/(3!e) about 6.1% three elements, 1/(4!e) or ~1.5% four elements, 1/(5!e) ~.3% have five etc.. - the average chain length from non-empty buckets is ~1.58 no matter how many elements are in the table (i.e. whether there are 100 elements and 100 buckets, or 100 million elements and 100 million buckets), which is why we say lookup/insert/erase are O(1) constant time operations.

哈希表如何将键与值关联

Given a hash table implementation as described above, we can imagine creating a value type such as `struct Value { string name; int age; };`, and equality comparison and hash functions that only look at the `name` field (ignoring age), and then something wonderful happens: we can store `Value` records like `{"sue", 63}` in the table, then later search for "sue" without knowing her age, find the stored value and recover or even update her age - happy birthday Sue - which interestingly doesn't change the hash value so doesn't require that we move Sue's record to another bucket.

当我们这样做的时候，我们使用哈希表作为一个关联容器，也就是map，它存储的值可以被认为是由一个键(名称)和一个或多个其他字段组成，仍然被称为值(在我的例子中，只是年龄)。用作映射的哈希表实现称为哈希映射。

这与前面我们存储离散值的例子形成了对比，比如“sue”，你可以把它看作是它自己的键:这种用法被称为散列集。

还有其他方法来实现哈希表

并不是所有的哈希表都使用链表(称为独立链表)，但大多数通用哈希表都使用链表，因为主要的替代封闭哈希(又名开放寻址)-特别是支持擦除操作-与易于冲突的键/哈希函数相比性能不太稳定。

---

简单讲一下哈希函数

强大的散列…

一个通用的、最小化最坏情况碰撞的哈希函数的工作是有效地随机地在哈希表桶周围散布键，同时总是为相同的键生成相同的哈希值。理想情况下，即使在键的任何位置改变一个位，也会随机地翻转结果哈希值中的大约一半位。

This is normally orchestrated with maths too complicated for me to grok. I'll mention one easy-to-understand way - not the most scalable or cache friendly but inherently elegant (like encryption with a one-time pad!) - as I think it helps drive home the desirable qualities mentioned above. Say you were hashing 64-bit doubles - you could create 8 tables each of 256 random numbers (code below), then use each 8-bit/1-byte slice of the double's memory representation to index into a different table, XORing the random numbers you look up. With this approach, it's easy to see that a bit (in the binary digit sense) changing anywhere in the double results in a different random number being looked up in one of the tables, and a totally uncorrelated final value.

// note caveats above: cache unfriendly (SLOW) but strong hashing...
std::size_t random[8][256] = { ...random data... };
auto p = (const std::byte*)&my_double;
size_t hash = random[0][p[0]] ^
              random[1][p[1]] ^
              ... ^
              random[7][p[7]];

弱但通常快速的哈希…

Many libraries' hashing functions pass integers through unchanged (known as a trivial or identity hash function); it's the other extreme from the strong hashing described above. An identity hash is extremely collision prone in the worst cases, but the hope is that in the fairly common case of integer keys that tend to be incrementing (perhaps with some gaps), they'll map into successive buckets leaving fewer empty than random hashing leaves (our ~36.8% at load factor 1 mentioned earlier), thereby having fewer collisions and fewer longer linked lists of colliding elements than is achieved by random mappings. It's also great to save the time it takes to generate a strong hash, and if keys are looked up in order they'll be found in buckets nearby in memory, improving cache hits. When the keys don't increment nicely, the hope is they'll be random enough they won't need a strong hash function to totally randomise their placement into buckets.

你们已经很接近完整地解释了这个问题，但是遗漏了一些东西。哈希表只是一个数组。数组本身将在每个槽中包含一些内容。至少要将哈希值或值本身存储在这个插槽中。除此之外，您还可以存储在此插槽上碰撞的值的链接/链表，或者您可以使用开放寻址方法。您还可以存储一个或多个指针，这些指针指向您希望从该槽中检索的其他数据。

It's important to note that the hashvalue itself generally does not indicate the slot into which to place the value. For example, a hashvalue might be a negative integer value. Obviously a negative number cannot point to an array location. Additionally, hash values will tend to many times be larger numbers than the slots available. Thus another calculation needs to be performed by the hashtable itself to figure out which slot the value should go into. This is done with a modulus math operation like:

uint slotIndex = hashValue % hashTableSize;

这个值是该值将要进入的槽。在开放寻址中，如果槽位已经被另一个哈希值和/或其他数据填充，将再次运行模运算来查找下一个槽:

slotIndex = (remainder + 1) % hashTableSize;

我想可能还有其他更高级的方法来确定槽索引，但这是我见过的最常见的方法……会对其他表现更好的公司感兴趣。

With the modulus method, if you have a table of say size 1000, any hashvalue that is between 1 and 1000 will go into the corresponding slot. Any Negative values, and any values greater than 1000 will be potentially colliding slot values. The chances of that happening depend both on your hashing method, as well as how many total items you add to the hash table. Generally, it's best practice to make the size of the hashtable such that the total number of values added to it is only equal to about 70% of its size. If your hash function does a good job of even distribution, you will generally encounter very few to no bucket/slot collisions and it will perform very quickly for both lookup and write operations. If the total number of values to add is not known in advance, make a good guesstimate using whatever means, and then resize your hashtable once the number of elements added to it reaches 70% of capacity.

我希望这对你有所帮助。

PS - In C# the GetHashCode() method is pretty slow and results in actual value collisions under a lot of conditions I've tested. For some real fun, build your own hashfunction and try to get it to NEVER collide on the specific data you are hashing, run faster than GetHashCode, and have a fairly even distribution. I've done this using long instead of int size hashcode values and it's worked quite well on up to 32 million entires hashvalues in the hashtable with 0 collisions. Unfortunately I can't share the code as it belongs to my employer... but I can reveal it is possible for certain data domains. When you can achieve this, the hashtable is VERY fast. :)

哈希的计算方式通常不取决于哈希表，而是取决于添加到哈希表中的项。在框架/基类库(如。net和Java)中，每个对象都有一个GetHashCode()(或类似)方法，返回该对象的哈希码。理想的哈希码算法和准确的实现取决于对象中表示的数据。