实现哈希表之前需要解释一下哈希的概念：
哈希，当给一个函数提供任意大小的数据时，都能得到一个小的化简值。这个函数就被称作哈希函数。哈希使用一个哈希函数，该函数将给定数据映射到另一个范围的数据，这样一个新的数据范围就可以用作哈希表中的索引。

简单来说，给一个数据，返回一个具有代表性且不会重复的序号用作索引。

例如：

def hash(str):
    return sum(map(ord, str))

print(hash("hello world"))

这里我们通过累加每个字母的编码和来进行哈希，但这样是具有局限性的，如果字符串是world hello，则返回结果也是1116，这就不符合我们上述所说的唯一性。

故此，我们在哈希转换的过程中会添加额外的变量来使其尽量达到唯一性，例如有一种方法便是每个字母都先乘以其序号后再累计：

def hash(str):
    n = 0
    for i in range(len(str)):
        n += ((i+1) * ord(str[i]))

    return n

虽然这样可以避免大部分的重叠，但还是会有概率出现重复，例如ad和ga的哈希函数返回值：

def hash(str):
    n = 0
    for i in range(len(str)):
        n += ((i+1) * ord(str[i]))

    return n

print(hash("ad"))
print(hash("ga"))

运行结果：

297
297

我们也会在哈希表上做特殊处理，以此达到某种意义上的唯一，下面接着说哈希表

哈希表是一种通过关键字而不是索引来引用数据值的。在整个数据结构中，数据项存储在键值对中，哈希表使用哈希函数来查找存储和检索元素的位置。

哈希数据结构中的每个位置通常被称为桶或槽，可以存储一个元素。

实现哈希表：

首先我们创建一个类来保存哈希表的每一项，也可以抽象的理解为“节点”，但实际上这是一个键值对

class HashItem:
    
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value

哈希表的构造函数：

class HashTable:
    
    def __init__(self):
        self.size = 256
        # 初始表的大小
        self.slots = [None for i in range(self.size)]
        # 按照表的大小初始化n个槽
        self.count = 0
        # 统计共有多少个键值对

现在，我们来构造一个可用的哈希函数，因为我们的大小设置在256，所以返回的哈希值也必须在这个范围内：

    def _hash(self, key):
        hash_num = 0
        for i in range(len(key)):
            hash_num += ((i + 1) * ord(key[i]))
        
        return hash_num % self.size     # 返回和size的余数，确保哈希值在可用范围内

当然，这样也是有可能出现重复现象的，所以在哈希表中还有一个概念——开放定址，当哈希函数返回的哈希值所在位置已经有值的时候，通过线性查找下一个可用的槽位来实现这一点。即在得到冲突的哈希之前+1，这种方法称之为线性嗅探。

将键值对添加入表中的put函数：
 

    def put(self, key, value):
        item = HashItem(key, value)     # 新建一个键值对
        h = self._hash(key)             # 获取哈希值
        while self.slots[h]:            # 循环实现开放定址
            h = (h + 1) % self.size
        self.slots[h] = item            # 找到位置后存放键值对
        self.count += 1

从哈希表中检索元素的get函数：

    def get(self, key):
        h = self._hash(key)             # 获取key的哈希，根据哈希去找value
        while self.slots[h]:            # 循环判断
            if self.slots[h].key is key:
                return self.slots[h].value
            
            h = (h + 1) % self.size
        
        return None

完整代码：

class HashItem:

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

class HashTable:

    def __init__(self):
        self.size = 256
        # 初始表的大小
        self.slots = [None for i in range(self.size)]
        # 按照表的大小初始化n个槽
        self.count = 0
        # 统计共有多少个键值对

    def _hash(self, key):
        hash_num = 0
        for i in range(len(key)):
            hash_num += ((i + 1) * ord(key[i]))

        return hash_num % self.size     # 返回和size的余数，确保哈希值在可用范围内

    def put(self, key, value):
        item = HashItem(key, value)     # 新建一个键值对
        h = self._hash(key)             # 获取哈希值
        while self.slots[h]:            # 循环实现开放定址
            h = (h + 1) % self.size
        self.slots[h] = item            # 找到位置后存放键值对
        self.count += 1

    def get(self, key):
        h = self._hash(key)             # 获取key的哈希，根据哈希去找value
        while self.slots[h]:            # 循环判断
            if self.slots[h].key is key:
                return self.slots[h].value

            h = (h + 1) % self.size

        return None

测试：

test_ = HashTable()
test_.put("a", "apple")
test_.put("b", "black")
test_.put("c", "call")
test_.put("d", "dis")
for i in range(97, 101):
    print(test_.get(chr(i)))

运行结果：
apple
black
call
dis

但是这样用起来怪怪的，我们通过特殊方法来优化一下：

    def __setitem__(self, key, value):
        self.put(key, value)
    
    def __getitem__(self, key):
        return self.get(key)

于是就可以将测试例子改为：

test_ = HashTable()
test_["a"] = "apple"
test_["b"] = "black"
test_["c"] = "call"
test_["d"] = "dis"
for i in range(97, 101):
    print(test_.get(chr(i)))

当然，目前的哈希表是由固定长度的，为256，当需要存储的数据大于该大小是，我们就要扩展哈希表，这个我们后续和解决哈希冲突的连接还有符号表等一起讲，目前仅限于了解基本的哈希结构