算法与数据结构——哈希表

哈希表（hash）是一种数据结构
可以快速的实现插入删除查找，
工作原理：
基于数组的，通过一种计算方式进行储存，

class Array():
    def __init__(self,size = 4):
        self.size = size  # 记录容器大小
        self.item = [None]*size  # 分配空间
        self.length = 0
    def setitem(self,key,value):
        self.item[key] = value
        self.length += 1
    def getitem(self,key):
        return self.item[key]
    def len(self):
        return self.length
    def iter(self):
        for value in self.item:
            yield value
class Slot():
    def __init__(self,key = None,value = None):
        self.key = key
        self.value = value
    def str():
        return 'key: {} value: {}'.format(self.key,self.value)
class HashTable():
    def __init__(self):
        self.size = 4
        self.items = Array(self.size)
    def get_index(self,key):
        return hash(key) % self.size
    def put(self,key,value):
        s = Slot(key,value)
        index = self.get_index(key)
        self.items[index] = s
    def get(self,key):
        index = self.get_index(key)  # 获得key对应的索引
        return self.items[index]
if __name__ == "__main__"
    h = HashTable()
    h.put('name','卢布')
    h.put('sex','男')
    print(h.get('name'))
    print(h.get('name'))

哈希冲突怎么办？
有好几种方法
哈希扩容
数据量太大怎么办，就得扩容也叫重哈希，什么时候开始扩容呢不能等满了在开始扩容
达到一定的容量之后，就开始扩容
用装载因子判断是否开始扩容