在python中实现hashtable/dictionary

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

您需要将哈希和表格大小分开.哈希应仅基于密钥,而不是大小.每个键值条目存储以下信息:

• 钥匙
• 哈希 - 从密钥派生的常量值.确保它有呼吸以避免太多碰撞.
• 价值

您根据表大小和哈希选择一个插槽:

slot = hash % tablesize

然后,当您当前表中的空间不足时,生成一个新表(比如,大小增加一倍),以适应您不断增长的数据集,并重新绘制所有内容.您已经缓存了哈希值,您需要做的就是获取每个(key, hash, value)元组并使用上面的公式重新计算新的槽,现在使用更大的表格.

你还必须决定如何处理碰撞 ; 给出当前表大小的两个哈希最终在同一个槽中.Python dict使用开放式寻址,其中哈希以可重现的方式被"扰乱",直到找到另一个空槽.

您可能希望研究Python dict源代码以了解它们是如何执行此操作的,请参阅有关如何处理冲突的详尽注释.您还可以观看此PyCon演示文稿,其中Brandon Rhodes使用一些非常有启发性的图形解释所有这些细节.或者你可以拿起一本美丽的代码,其中有一章关于Python的dict实现.