时间戳

首页 > 解决方案 > 哈希表中的桶是否包含指针或值？

python - 哈希表中的桶是否包含指针或值？

问题描述

我正在学习python，其中一个要点是变量名分别存储在内存中它们所引用的对象；也就是说，它们有一些指针指向内存中实际存储它们所引用的对象的不同区域。

我现在正在阅读什么是哈希表以及它们是如何实现的（基础知识）。这个问题的答案真的很有帮助：哈希表是如何工作的？

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

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

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

标签： pythonhashtable

解决方案

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

  • Python 有一个内置的哈希表类型，dict. 它的内部实现是用 C 语言编写的（至少对于 CPython 而言），并使用了您无法直接在 Python 中编写的技巧。有关多年来使用的（几种）实现的详细信息，请参阅Python 的内置字典是如何实现的。

  • Python 作为一门语言大多没有数组。1 链接问题的一些答案以数组的形式表示，Python 的内置列表类型可以像数组一样使用，因此可以用作模型。这就是我将在这里做的。

所以让我们从创建一个空的伪数组开始：[]。我们将其绑定到一些“类似数组”的名称：

a = []

然后继续你的问题。

1该array模块提供 C 风格的数组。有关详细信息，请参阅阵列文档。

我从中得出的结论是，如果我有一个键值对，那么哈希本质上会将索引转换为一个键，然后将该键存储在一个数组中。

反之亦然：散列将“太大”的键转换为计算机可以更轻松、更直接地处理的更小的值，即散列值。这会将键转换为索引。不过，您在问题的下一部分中是正确的：

因此，如果索引为'key1'0，则a[0]包含实际值'value1'。

一般来说，是的。但是，如果哈希表既适用于命中也适用于未命中，并且某些其他键（例如'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 ...

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

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 ...

当我们点击“复杂部分”时，要么数组本身太小，要么我们要使用的插槽已被其他键使用。

这就是哈希表变得花哨的地方。有些使用辅助散列函数，执行称为重新散列的操作并探测其他表槽（在这种情况下，我们希望从非零表大小开始）。一些扩展表。同样，要查看 Python 实际做了什么，请查看其他问题及其答案。

但是，我不确定这是否真的如此，或者如果像python中的变量一样，数组中的值实际上并不代表“value1”，而是一些指向内存中存储“value1”的位置的指针. ...

因为 Python 允许在字典中使用动态类型，所以任何散列键的值槽肯定会存储指向实际值的指针，而不是值的副本。不同类型的值具有不同的底层大小。您可以使用以下方法查看类型的大小sys.getsizeof（但也请参阅如何在 Python 中确定对象的大小？）：

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

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

...这是否意味着存储在哈希表中的值实际上分散在整个内存中，而不是按顺序存储？

是的。只有哈希值和键/值指针对按顺序存储在内部 Python 实现中。

推荐阅读