哈希 table 中的桶是否包含指针或值？

Question

我正在学习 python 并且提出的要点之一是变量名称在内存中与它们引用的对象分开存储；那就是它们有一些指针指向内存中实际存储它们引用的对象的不同区域。

我现在正在阅读什么是哈希 table 以及它们是如何实现的（基础知识）。这个问题的答案真的很有帮助：How does a hash table work?

我从中得出的结论是，如果我有一个键值对，那么哈希实际上会将索引转换为一个键，然后将该键存储在一个数组中。因此，如果 'key1' 的索引为 0，则 a[0] 包含实际值 'value1'.

但是，我不确定是否确实如此，或者如果像 python 中的变量一样，数组中的值实际上并不表示 'value1'，而是一些指向的指针到内存中存储 'value1' 的位置。那么它是 'key1' --> array index --> a[array index] --> value 还是 'key1' --> array index --> a[array index] -- > 指针地址 --> 'value1' 存储在由指针地址确定的内存位置？

作为后续问题，如果是后者，那么是否意味着存储在散列 table 中的值实际上分散在整个内存中而不是按顺序存储？非常感谢，抱歉，如果问题很明显。

Answer 1

警告：这个答案可能有点令人困惑，因为有两件事需要考虑：

Python 具有内置哈希 table 类型 dict。它的内部实现是用 C 语言编写的（至少对于 CPython）并且使用了一些你不能直接用 Python 编写的技巧。有关多年来使用的（多个）实现的详细信息，请参阅 How are Python's Built In Dictionaries Implemented.
Python 作为一种语言，大多数情况下没有数组。¹ 链接问题的一些答案是用数组表示的，并且 Python 的内置 list 类型可以像数组一样使用，因此可以用作模型。这就是我要做的。

所以让我们从创建一个空的伪数组开始：[]。我们会将其绑定到某个 "array-like" 名称：

a = []

然后继续你的问题。

¹array 模块提供了 C 风格的数组。有关详细信息，请参阅 the array documentation。

My takeaway from that is that if I have a key-value pair, then the hash essentially converts the index into a key, and then that key is stored in an array.

恰恰相反：哈希将密钥（即 "too big"）转换为 更小的，即计算机可以处理更多的哈希值轻松直接。将键转换为索引。不过，您在问题的下一部分是正确的：

So if the index is for 'key1' is 0, then a[0] contains the actual value 'value1'.

一般来说，是的。但是，如果散列 table 既适用于命中也适用于未命中，并且其他一些键（例如 '1frotz'）可能也转换为索引 0，我们必须在 a[0] 中存储两个项目，或者保留实际键的并行数组，或类似的东西，以确保 a[0] 持有 'key1' 而不是其他一些键值一对。也就是说，在 Python 中，我们可能会这样做：

i = hash(key) % tablesize   # assuming a fixed table size
assert i < len(a)           # this is going to fail since len(a) == 0!
kv_pair = a[i]
assert kv_pair[0] == key
... use kv_pair[1], which holds the value ...

当然，我们还需要能够将项目放入哈希table。通常，当我们这样做时，如果键值对不适合，我们将扩展 table，因此我们不使用上面的 assert，而是：

def find_value(key):
    if len(a) > 0:
        i = hash(key) % len(a)
        kv_pair = a[i]
        if kv_pair is not None and kv_pair[0] == key:
            return kv_pair[1]
    return None

def insert_kv_pair(key, value):
    if len(a) > 0:
        i = hash(key) % len(a)
        kv_pair = a[i]
        if kv_pair is None:       # not in the table yet
            a[i] = [key, value]   # so put it in
            return
        if kv_pair[0] == key:     # already in the table
            kv_pair[1] = value    # so replace the value
            return
    ... the complicated parts go here ...

当我们点击 "complicated parts" 时，要么数组本身太小，要么我们要使用的插槽已被某些 other 键占用。

这里是散列 table 变得有趣的地方。有些使用辅助哈希函数，做一些叫做 re-hashing 的事情并探测其他 table 槽（在这种情况下，我们想从非零 table 大小开始).一些扩展 table 到位。同样，要查看 Python 的实际作用，请查看其他问题及其答案。

However, I am not sure if this is actually the case, or if like variables in python the value in the array doesn't actually represent 'value1', but instead some pointer which points to the location in memory where 'value1' is stored. ...

因为 Python 允许字典中的动态类型，所以任何散列键的值槽肯定存储指向实际值的指针，而不是值的副本。不同类型的值具有不同的底层大小。您可以使用 sys.getsizeof 查看类型的大小（但也可以查看 How do I determine the size of an object in Python?）：

>>> import sys
>>> sys.getsizeof(int)
400
>>> sys.getsizeof(1)
28
>>> sys.getsizeof('str')
52
>>> sys.getsizeof('string')
55

由于整个地图的大小各不相同，Python 只是在字典的 "value" 槽中为给定键存储一个指针。

... does that mean the values in stored in a hash table are actually scattered throughout memory rather than stored sequentially?

是的。只有散列值和一对key/value指针在内部Python实现中顺序存储。

Answer 2

如果你看一下你看到的 Python 字典的基本查找函数的 source code，它们会分配一个指向实际值的指针。

在该方法中，您还可以看到使用给定键查找的所有步骤。所以我认为你的假设

'key1' --> array index --> a[array index] --> pointer address --> 'value1'

是正确的。

哈希 table 中的桶是否包含指针或值？

Does the bucket in a hash table contain a pointer or a value?

python

hashtable