什么是哈希表

根据设定的哈希函数H(key)和处理冲突的方法将关键字映像到一个有限的连续的地址集区间上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便成为哈希表，这一映像过程称为哈希造表或散列，所得存储位置称为哈希地址或散列地址。

简而言之，就是通过一个函数计算数据的存储位置，需要时再计算直接取出。

三个关键：哈希函数、处理冲突的办法、哈希表的填装因子（表中填入的记录数、哈希表的长度）

需要注意的是：哈希表的平均查找长度是填装因子的函数，而不是n的函数。因此，不管n多大，我们总可以选择一个合适的填装因子以便将平均查找长度限定在一个范围之内。

参考：严蔚敏, 吴伟民. 数据结构 (C语言版)[M]. 清华大学出版社, 2007.

哈希表几种构造方法

参考：https://www.cnblogs.com/xiaozhongfeixiang/p/11571902.html

• 直接定址法

适用条件：所得地址集合和关键字集合的大小相同，不会发生冲突。实际中很少使用。

• 数字分析法

适用条件：所有关键字都事先已知。

• 平方取中法

这是一种较常用的构造哈希函数的方法，取得位置和表长有关系。
适用条件：不一定能知道关键字的全部情况，关键字的各位重复出现的频率高。

• 折叠法

折叠法有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部位的最低位对齐，然后相加。间界叠加是从一端向另外一端沿着分割界来回折叠，然后对齐相加。

例：元素42751896, 用法1： 427＋518＋96=1041 用法2： 427 518 96—> 724+518+69 =1311

适用条件：关键字很多，而且关键字中每一位上数字分布大致均匀。

• 除留余数法

这是最简单也最常用的构造哈希函数的方法，不仅可以直接取模，也可以在折叠、平方取中等运算之后取模。p的选择很重要，一般情况下，可以选择P为质数或不包含小于20的质因数的合数。

• 随机数法

处理冲突的方法

懒得码字了直接上图！

Python实现一个简答的哈希表

参考：

# 实现hashtable,指定在key位置存入data
# 构造方法：除留余数法  冲突处理方法：开放定址法中的线性探测再散列方法
# 但是这里没有设置容量递增表

class HashTable:
    def __init__(self):
        self.size = 11
        self.slots = [None] * self.size  # hold the key items
        self.data = [None] * self.size  # hold the data values

    def hashfunction(self, key, size):
        return key % size

    def rehash(self, oldhash, size):  # 线性探测再散列
        return (oldhash + 1) % size

    def put(self, key, data):
        hashvalue = self.hashfunction(key, len(self.slots))
        if self.slots[hashvalue] == None:  # 如果slot内是empty，就存进去
            self.slots[hashvalue] = key
            self.data[hashvalue] = data
        else:  # slot内已有key
            if self.slots[hashvalue] == key:  # 如果已有值等于key,更新data
                self.data[hashvalue] = data  # replace
            else:  # 如果slot不等于key,找下一个为None的地方
                nextslot = self.rehash(hashvalue, len(self.slots))
                while self.slots[nextslot] != None and self.slots[nextslot] != key:
                    nextslot = self.rehash(nextslot, len(self.slots))  # 会不会就是找不到？？？
                    print('while nextslot:', nextslot)
                if self.slots[nextslot] == None:
                    self.slots[nextslot] = key
                    self.data[nextslot] = data
                    print('slots None')
                else:
                    self.data[nextslot] = data
                    print('slots not None')

    def get(self, key):  # 能不能把存操作和取操作给合并了？？
        startslot = self.hashfunction(key, len(self.slots))
        data = None
        stop = False
        found = False
        position = startslot
        while self.slots[position] != None and not found and not stop:
            if self.slots[position] == key:
                found = True
                data = self.data[position]
            else:
                position = self.rehash(position, len(self.slots))
                if position == startslot:
                    stop = True
        return data

    # 如果在类中定义了__getitem__()方法
    # 那么他的实例对象（假设为P）就可以这样P[key]取值
    # 当实例对象做P[key]运算时，就会调用类中的__getitem__()方法
    # 将这两个函数去掉了之后，H[54] = 'cat'这样的赋值就会出错
    def __getitem__(self, key):
        return self.get(key)

    def __setitem__(self, key, data):
        print('key:', key)
        print('data:', data)
        self.put(key, data)


H = HashTable()
H[54] = 'cat'
H[54] = 'kat'
H[65] = 'lion'
print(H[54])