Hash table 哈希表

1. 散列表基础：

用途：对于数据项查找，时间复杂度为O(1)，用于快速查找定位

结构：哈希表每一个储存位置成为slot，将数据项存储在槽里
。
散列方法1：求余数，将数据项除于散列表大小，将得到的余数作为槽号。将每个数映射至不同槽内。（完美散列函数）

冲突：不同的数据都可能进入相同的槽，引起collision

Python中的库：
import hashlib
包括MD5与SHA系列函数

2. 散列函数设计

1. 折叠法：
   通过将数据项按照位数分为几段，再将几段相加后对散列表总体大小求余，得到散列值，放入槽内
   （有时对某一段值进行反转）
2. 平方取中法：
   对数据项平方，取平方数的中间两个数据项，求余。
   注意：字符串可用ASCII表示，字符顺序可加入权重因子进行区分。

3冲突解决方案

1. 开放定址法：对冲突的数据项往后再找一个空槽存放数据项。

   
   image.png
   

   为了防止聚集出现，也可每隔一定的间隔进行存放冲突的数据项
   （线性探测、跳跃式探测、二次探测）

1. rehash(pos) = (pos+1) % sizeoftable
2. rehash(pos) = (pos+gap) % sizeoftable
3. for i in range(N):
      rehash(pos) = (pos+gap) % sizeoftable

注意散列表大小取为素数，这样不被gap整除，就可以取到所有值。

2. 数据项链法
   将有冲突的槽扩展为容纳数据项的集合，或者增加链表的引用。这样就不会占据其他槽，槽可以容纳多个数据项。

   
   image.png
   

   会牺牲时间复杂度。O(1)~O(N)

应用：字典

实现ADT Map
代码：

class HashTable:
    def __init__(self):
        self.size = 11
        # 素数
        self.slots = [None] * self.size
        self.data = [None] * self.size

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

    def rehash(self, oldhash):
        return (oldhash + 1) % self.size

    def put(self, key, data):
        hashvalue = self.hashfunction(key)
        if self.slots[hashvalue] is None:
            self.slots[hashvalue] = key
            self.data[hashvalue] = data
        # 如果取到槽为空槽，将数据项放入槽内，并在数据表对应槽的位置放入数据
        else:
            if self.slots[hashvalue] == key:
                self.data[key] = data
            # 如果该槽已有记录，在对应数据表位置修改数据
            else:
                nextslot = self.rehash(hashvalue)
                while self.slots[nextslot] is not None and self.slots[nextslot] != key:
                    nextslot = self.rehash(nextslot)
                # 如果出现冲突，则线性探测下一个槽
                if self.slots[nextslot] is None:
                    self.slots[nextslot] = key
                    self.data[nextslot] = data
                    # 如果探测的新槽是空槽，则放入该数据项
                else:
                    self.data[nextslot] = data
                    # 如果新槽已被记录，则修改数据项

    def get(self, key):
        hashvalue = self.hashfunction(key)
        startslot = hashvalue
        found = False
        stop = False
        data = None
        pos = hashvalue
        while self.slots[pos] is not None and not found and not stop:
            if self.slots[pos] == key:
                data = self.data[pos]
                found = True
                # 如果找到了对应的槽，把数据表中的对应数据项返回
            else:
                pos = self.rehash(pos)
                if pos == startslot:
                    stop = True
                # 没找到槽：1. 进行线性探测，找到了就返回数据项 2. 线性探测后回到初始位置，仍没有对应数据项，返回None
        return data

时间复杂度注意：
① 线性探测解决冲突：查找比对次数在1/2（1+1/(λ-1)) ~ 1/2（1+1/((λ-1)^2))
② 数据链：查找次数：1+λ/2 ~ λ
（其中负载因子λ代表冲突情况）