拉链法实现哈希表

拉链法简要原理如下图所示： 哈希表底层数组存储的是一个链表。若出现哈希冲突，则key指向所有该key的键值对

将问题简化如下： hash函数简化为简单取模操作，即hash(key) = key % table.length，这么操作还有一个好处即为模拟哈希冲突操作，比如若table.length = 10时hash(1) = hash(11) = 1

Python实现如下：

class MyChainHashMap:
    
    class KVNode:
        def __init__(self, key, value):
            self.key = key
            self.value = value
            
    def __init__(self, InitCap = 2):
        self.count = 0
        #因为该实现方法中hash函数是对key取模，应避免除数为0的情况
        self.size = max(InitCap, 1)
        self.table = [[] for _ in range(self.size)]
        
    #增
    def add(self, key, value):
        if key == None:
            raise ValueError("Key is null")
        index = self.Hash(key)
        bucket = self.table[index]
        for node in bucket:
            if node.key == key:
                node.value = value
                return
        bucket.append(self.KVNode(key, value))
        self.count += 1
        
        if self.count >= self.size * 0.75:
            self.reSize(self.size * 2)
            
    #删
    def remove(self, key):
        if key == None:
            raise ValueError("Key is null")
        index = self.Hash(key)
        bucket = self.table[index]
        for node in bucket:
            if node.key == key:
                bucket.remove(node)
                self.count -= 1
        if self.count <= self.size * 0.25:
            self.reSize(max(self.size // 2, 1))
            
    #查
    def get(self, key):
        if key == None:
            raise ValueError("Key is null")
        index = self.Hash(key)
        bucket = self.table[index]
        for node in bucket:
            if node.key == key:
                return node.value
            
    def getKeys(self):
        keys = []
        for bucket in self.table:
            for node in bucket:
                keys.append(node.key)
        return keys
        
    #工具
    def Hash(self, key):
        return hash(key) % self.size
    
    def reSize(self, newSize):
        newMap = MyChainHashMap(newSize)
        for bucket in self.table:
            for node in bucket:
                newMap.add(node.key, node.value)
        self.table = newMap.table
        self.size = newSize
        
        
#测试
if __name__ == "__main__":
    map = MyChainHashMap()
    map.add(1, 1)
    map.add(2, 2)
    map.add(3, 3)
    print(map.get(1))   # 1
    print(map.get(2))   # 2
    
    map.add(1, 100)
    print(map.get(1))   # 100
    
    map.remove(2)
    print(map.get(2))   # None
    
    map.remove(1)
    map.remove(2)
    map.remove(3)
    print(map.get(1))   # None