python - python中哈希表/字典的实现

Question

我一直在研究 python 中的数据结构，我创建了一个字典的简单实现，如下所示。虽然这个实现最终没有用(可以只使用 hash() 而不是创建哈希函数等)，但我对它们如何组合在一起的细节很感兴趣。

此实现选择的起始大小为 11。self.capacity 跟踪剩余的空闲插槽数。当添加一个(key, value) 对时，它会减 1，一旦它达到 0，它会在每次需要时触发创建一个新插槽。

我的问题是:从散列函数计算的散列值取决于len(self.slots)，但是当我添加时这个值不断增加我的字典有更多空间。我没有使用 len(self.slots) 来计算哈希函数，而是尝试使用初始大小 (11)，但是一旦字典尝试添加第 12 个(键，值)对，该程序似乎卡住了。这似乎表明哈希函数需要基于表的大小，并且为了不断添加元素我需要能够增加表的大小。这让我想到了以下问题。

1. 字典是否必须初始化为固定长度并保持该长度？如果不是，添加元素时增加长度的首选方法是什么？
2. 如果字典的长度是可以改变的，是否应该在不使用字典大小的情况下构造散列函数？我如何确保值仍然会减少到表槽范围内的值而不通过模数表大小减少？

任何解释、有趣的见解或有用的花絮都将不胜感激。

#

class HashTable:
    def __init__(self):
        self.size = 11
        self.capacity = self.size
        self.slots = [None] * self.size
        self.data =  [None] * self.size

    def hashfunction(self, key, size):
        return key%size

    def rehash(self, oldhash, size):
        return (oldhash+1)%size

    def put(self, key, value):
        hashvalue = self.hashfunction(key,len(self.slots))

        if self.capacity < 1:
            self.slots += [None]
            self.data += [None]
            self.capacity += 1

        if self.slots[hashvalue] == None:
            self.slots[hashvalue] = key
            self.data[hashvalue] = value
            self.capacity -= 1
        else:
            if self.slots[hashvalue] == key:
                self.data[hashvalue] = data
            else:
                rehashed = self.rehash(hashvalue, len(self.slots))
                while self.slots[rehashed] != None and self.slots[rehashed] != key:
                    rehashed = self.rehash(rehashed, len(self.slots))
                if self.slots[rehashed] == None:
                    self.slots[rehashed] = key
                    self.data[rehashed] = value
                    self.capacity -= 1
                else:
                    self.data[rehashed] = value

    def get(self, key):
        startslot = self.hashfunction(key, len(self.slots))
        data = None
        found = False
        stop = False
        position = startslot
        while self.slots[position] != None and not found and not stop:
            if self.slots[position] == key:
                data = self.data[key]
                found = True
            else:
                position = self.rehash(position, len(self.slots))
                if position == startslot:
                    stop = True
        return data

    def __delitem__(self, key):
        hashvalue = self.hashfunction(key, len(self.slots))

        if self.slots[hashvalue] == key:
            self.slots[hashvalue] = None
            self.data[hashvalue] = None
        else:
            rehashed = self.hashfunction(hashvalue, len(self.slots))
            while self.slots[rehashed] != key:
                rehashed = self.hashfunction(rehashed, len(self.slots))
            if self.slots[rehashed] == key:
                self.slots[rehashed] == None
                self.data[rehashed] == None

    def __contains__(self, key):
        return key in self.slots

    def __getitem__(self, key):
        return self.get(key)

    def __setitem__(self, key, value):
        self.put(key, value)

Answer 1

您需要将散列和表大小分开。散列应仅基于 key ，而不是大小。每个键值条目存储以下信息:

• key
• 散列 - 从键派生的常量值。确保它有呼吸以避免太多碰撞。
• 值(value)

您根据表大小和散列选择一个插槽:

slot = hash % tablesize

然后，当您用完当前表中的空间时，生成一个新表(例如，将大小加倍)，以容纳您不断增长的数据集，并重新分配 一切。您已经缓存了哈希值，您所要做的就是获取每个 (key, hash, value) 元组并使用上述公式重新计算新槽，现在具有更大的表大小。

您还必须决定 how to handle collisions ;给定当前表大小的两个散列最终位于同一个槽中。 Python 的 dict 使用 open addressing ，其中哈希以可重现的方式“扰乱”，直到找到另一个空槽。

您可能想研究 Python dict 源代码以了解它们是如何做到这一点的，请参阅 extensive comments on how collisions are handled .您还可以观看 this PyCon presentation Brandon Rhodes 用一些非常有启发性的图形解释了所有这些细节。或者你可以拿一份 Beautiful Code其中有一整章是关于 Python dict 实现的。