小编Нек*_*кто的帖子

我一直在研究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 …