The most common way to construct a hash table on a CPU works as follows.
So we have a bunch of buckets here, and we have a hash function h.
And this hash function takes a key and maps that key into one of those buckets.
So if the the hash function of the key k returns 0, h of k is 0,
then that key is associated with bucket 0.
If h of k is 1, then that key is associated with bucket 1 and so on.
Within a bucket, we store a bunch of items as a linked list, and this is called chaining.
So we might have multiple items in this bucket, multiple keys.
So key 12, key 29, key 123
all have a hash function that's equal to 1,
so they're placed in bucket 1, and we store them as this chained, linked list.
Then when we want to look up a key, we take that key.
We run it through the hash function
to get a particular value out of the hash function
that's going to refer us to a particular bucket, so we have this key.
It's going to return; oh, he's in bucket 1.
Then we will look through all these chained items
to find the key that we're looking for.
在CPU构建散列(哈希)表最常用方法的工作方式如下。
我们这里有一堆桶,我们有一个散列函数h。
这个散列函数有一个关键字,并将关键字映射到其中一个桶。
如果散列关键字,关键字k的散列函数返回0,
h(k)是0,那么这个键和桶0关联。
如果h(k)是1,那么这个键和1关联,以此类推。
在桶中,我们存储了一些项作为一个链表。
这称为链接。我们可能在这个桶里有多个项、
多个关键字。关键字12、关键字29、关键字123都有一个散列公式等于1。
所有,他们被放入桶1,我们把它们存储为链表。
然后,当我们想查询某个关键字,我们取那个关键字。
通过散列函数运行它,从散列函数得到特定值。
这将指引我们到特定的桶。我们有这个关键字,
它将返回,哦,他在桶1。然后我们会查看所有这些链接项
来找到我们正在寻找的关键字。