设计一个哈希表

原文链接
作为演示代码，做了以下的简化处理：

• 键类型仅支持int
• 哈希冲突处理使用链存储
• 不设置装载因子的处理
• 不对输入进行校验
• 默认数据大小可以完全放在内存中

class Item(object):

    def __init__(self, key, value):
        self.key = key
        self.value = value


class HashTable(object):

    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(self.size)]

    def _hash_function(self, key):
        return key % self.size

    def set(self, key, value):
        hash_index = self._hash_function(key)
        for item in self.table[hash_index]:
            if item.key == key:
                item.value = value
                return
        self.table[hash_index].append(Item(key, value))

    def get(self, key):
        hash_index = self._hash_function(key)
        for item in self.table[hash_index]:
            if item.key == key:
                return item.value
        raise KeyError('Key not found')

    def remove(self, key):
        hash_index = self._hash_function(key)
        for index, item in enumerate(self.table[hash_index]):
            if item.key == key:
                del self.table[hash_index][index]
                return
        raise KeyError('Key not found')

简单说明一下，这里使用list的数据结构存放数据，哈希函数是最简单的key值对存储大小取余（这也是为什么key值仅支持int类型的原因）。
需要注意的几点是，哈希函数可以选用更为通用的函数，这样就能够支持更多的键数据类型；这里对于哈希冲突的解决采用了链式存储，在极端条件下（即所有哈希值都映射到同一个位置），set和get方法的时间复杂度将从O(1)退化到O(n)；随着数据量的增加，哈希冲突发生的概率越来越大，所以应当引入装载因子进行动态扩容。