哈希查找算法
一、算法分析基础算法名称 时间复杂度 空间复杂度（序列）
顺序 O(N)黄金 O(log2N)二分 O(logN) 插补 O(log (logN) )常规查找算法中，插补是极限，但并不是说没有更好的查找算法了。顺序查找是一个一个往下找，当总量大的时候，我们要找的目标target又靠后的时候，负担就很重 --- 大海捞针。
散列表：散列表是一种牺牲空间换取时间的存储结构，也是一种提升效率的常用的方法---算力（片面的理解为计算空间有多大）散列表使用技巧：“效率” 和 “占用空间大小” 二者权衡。dict = {key1:value1,key2:value2.....}中---> z ---> z开头一大堆 --->h.....
举例：通讯录找人，第一步找z，赵、张--->肉眼去看“张”这个字 ---->点开“张三”这个人，然后你就看到了他的电话号码。0 1 2 3 4 5 6 7 ...
v1 v2 v3 v4 v5 v6 v7 v8 ...data = [ 12 ,45, 56 ,66 ,77, 80 ,97 ,101 ,120, 101]
在普通查找算法中我们看到的就是值本身，而哈希表中我们看到的不是值本身，只是一个值的标记。
散列函数又称为哈希函数，是给定一个x（包裹本身）,它都会相应的输出H(x) （那个编码）。x--->H(x)的过程我们需要保证以下这么几点：①输入的x是任意的字符串。②输出结果即H(x)的长度是固定的。③计算H(x)的过程是高效的。④尽可能输入一个x就能得到唯一的H(x)。For example:数据集：alist = [77 ,26 , 93 , 17 , 31 , 54]中的每个数据都通过散列函数计算出各个索引值，计算过程如下：x--->H(x)的过程： "77" ---> H(x) = x % 6 = 5"26" ---> H(x) = x % 6 = 2....“x” --->H(x) = 5此时，由5,2...构成的序列就是哈希表的值，也就是替换v1....vn0 1 2 3 4 5 6 7 ...v1 v2 v3 v4 v5 v6 v7 v8 ...由于x到H(x)的方法不同就会产生不同的哈希算法：①开放定址法----线性探测法②开放定址法----平方探测法③开放定址法----伪随机探测法④链地址法⑤再散列函数法⑥建立公共溢出区1.开放定址法的概念：开放定址法：当数据求出来的H(x)冲突的时候怎么办的问题？① 线性探测法--->假设散列表足够大，如果遇到冲突，那么就找下一个空的地址。“张三” ....新增“张三” * 3 ，2 ... 有空位就让第二张三坐下，再往下，第三个张三坐下.....key: 0 1 2 3 4 5 6 7 ...11.....101value:5 v2 v3 v4 v5 v6 v7 v8 ... 5......52.开放定址法的公式：H(i) = (H(key) + d(i)) MOD m公式参数解释：key:要存储的数据H(key):散列函数m:散列表长度d(i):增长序列MOD: %研究d(i)的获取方法：(1): d(i) = 1,2,3,4,....,m-1,这种取法称为线性探测法。线性探测法的缺点是：相类似的值变多以后，会出现聚集的情况，有聚合就有冲突。eg: 26 36 41 37 55,将这些数据放到数据长度为11的散列表中，步骤如下：step 1:确定散列函数H(i) = (H(key) + d(i)) MOD mH(i) = (H(key) + 1) MOD 11 -->意思就是先去放1号位。step 2:计算出H(key)的值,求法：数据集中的每个元素除以11取余数。H(key) ： 4 3 8 4 0 前提是：0 1 2 3 4 5 6 7 8 9 10step 3:将数据37求得的索引值4带入step1的散列函数中去，求得：H(i) = (4 + 1) % 11 = 5fina-data:0 1 2 3 4 5 6 7 8 9 1055 None None 36 26 37 None None 41 None None(2): d(i) = 1²，2²，3²，4²,....,或者d(i) = -1²，-2²，-3²，-4².....，这种取法称为平方探测法。为了防止线性探测法出现大规模的数据聚集而产生冲突，所以改良后出现了平方探测法。平方探测法，又称为“二次探测法”，d(i)部分与线性探测法不同。eg:有一组这样的数据：26 36 41 37 55。使用平方探测法d(i) = 4²时，将这组数据放在长度为11的散列表中，步骤如下：step 1:确定散列函数H(i) = (H(key) + 4²) MOD 11step 2:计算H(key)的值，将这个散列表中的每个数据除以11取余数，得到的索引值如下：4 3 8 4 0setp 3:将37求得的索引值4带入step1,得到的H(i) = (4 + 4²) % 11 = 9结论是：将37放入索引值为9的位置。fina-data:0 1 2 3 4 5 6 7 8 9 1055 None None 36 26 None None None 41 37 None练习：26 36 41 37 55 26 36 41 37 55要求1：使用线性探测法将数据放好。fina-data:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 55 None None 36 26 None None None 41 37 None要求2：使用平方探测法将数据放好。fina-data:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 55 None None 36 26 None None None 41 37 None(3): d(i) = 伪随机数序列，这种方法称为伪随机探测法。不好拿捏。effect: 假设真的有一种问题，是线性探测法解决不了的，我们使用平方探测法解决，使用线性+平方，最后都解决不了在使用伪随机探测。3.总结①数据线性跨度大、重复数据少、集合（排重性），建议使用线性探测法。②数据量够大的时候，空间浪费足够小，因为d(i)是我们自定义的，平方数越大索引计算出来的位置间隔越大，产生数据冲突的可能性越小，同时也就会留下更多的空隙，那就是牺牲了一部分空间来换取了很小的冲突，说白了就是牺牲空间换取时间的做法。建议使用平方探测法。
二、哈希算法应用举例
以下是几个关于哈希查找算法的编程题目：1.实现一个简单的哈希表设计并实现一个简单的哈希表，包括插入、查找和删除操作。哈希函数可以使用简单的取模运算。处理哈希冲突时，可以采用链地址法或开放地址法。
# 1. 实现一个简单的哈希表
# SimpleHashTable类：不存在
class SimpleHashTable: # 构造方法# self--->SimpleHashTable# capacity = 10 #创造了就一直存在的# self.capacity = 10# capacity只要没实例化对象，都一直存在的def __init__(self, capacity=10): # 天生# 将天生的capacity属性给了类的属性capacity，# 反过来说SimpleHashTable就天生具有了capacity这个属性self.capacity = capacity # 说明SimpleHashTable天生就是个表self.table = [[] for _ in range(capacity)] # [[], [], [], [], [], [], [], [], [], []]'''[[], [], [], [], [], [], [], [], [], []]'''# for _ in range(10): [[0] [1] [2] [3] [4] [5]]print(self.table)def hash_function(self, key): return key % self.capacity # 往hashTable中插入索引和值def insert(self, key, value): index = self.hash_function(key) for item in self.table[index]: if item[0] == key: item[1] = value return self.table[index].append([key, value]) print("插入完毕后的哈希表:",self.table)def search(self, key): index = self.hash_function(key) for item in self.table[index]: if item[0] == key: return item[1] return None def delete(self, key): index = self.hash_function(key) for i, item in enumerate(self.table[index]): if item[0] == key: del self.table[index][i] return True return Falsesht = SimpleHashTable()
sht.insert(8,"水警")
sht.insert(3,"火警")
# search(3)就是哈希查找算法,它的时间复杂度是O(1). 插补算法的平均时间复杂度是多少：O(Log(logN))
returnValue = sht.search(3)
print("返回的值是：",returnValue)2.实现LRU缓存机制利用哈希表和双向链表实现一个LRU（最近最少使用）缓存机制。需要实现获取数据get和写入数据put两个操作。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，并为新的数据值留出空间。
# 2. 实现LRU缓存机制
class LRUCache: # 写个计算器，只能进行整数加减# def __init__(self, capacity: float): 10 int("10")def __init__(self, capacity: int): # capacity: typeself.capacity = capacity self.cache = {} self.keys = [] def get(self, key: int) -> int: if key in self.cache: self.keys.remove(key) self.keys.append(key) return self.cache[key] return -1 # 作用：将新的数据塞入电池def put(self, key: int, value: int) -> None: if key in self.cache: # 字典中不允许有重复的键self.keys.remove(key) # ？字典中不允许有重复的键elif len(self.cache) >= self.capacity: # 电池装不下了怎么办？删掉占着茅坑不拉屎的数据oldest_key = self.keys.pop(0) # 为了找到那些是占着茅坑的 # pop(按下标删0)del self.cache[oldest_key] # 删除这些值self.cache[key] = value self.keys.append(key)# 实例化---将类变成对象的过程---等同于---执行调用了__init__()【初始化】
# lr = LRUCache() 等同于 LRUCache.__init__()
# c1 = 10
# c2 = 100
# lr1 = LRUCache(c1) # capacity = 10
# lr2 = LRUCache(c2) # capacity = 100
# 请问lr1.put() 是否等于 lr2.put() ？ 答案：相等的
# 用手摸头function#这个过程：将类变成对象的过程---实例化：生了一个孩子，“ac”class Car:# 初始化def __init__(self):pass # lr2 = LRUCache(10)
# LRUCache是类，lr和lr2是对象，不能仅仅按照值是否相等来进行判断是否是同一个对象
# lr.get() == LRUCache.get()
# lr2.get() == LRUCache.get()
# lr.get() != lr2.get()# n1 = lr.get() #等同 LRUCache.get()
# n2 = lr2.get() #是不是等同于 LRUCache.get()# lr.get() != lr2.get() # lr.get() 等同于 LRUCache.get()
# LRUCache.get()
# LRUCache.__init__()
# myCar = Car()3.哈希表的应用：两数之和给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，但是，数组中同一个元素不能使用两遍。有两个值x、y,他们的和x + y == target，返回x和y在数组中的下标。提示：可以使用哈希表来优化查找过程。
# 3. 哈希表的应用：两数之和
def two_sum(nums, target): hash_table = {} # 问hash_table是什么类型？for i, num in enumerate(nums): complement = target - num if complement in hash_table: return [hash_table[complement], i] hash_table[num] = i return []4.哈希表的应用：快乐数编写一个算法来判断一个数 n 是不是快乐数。「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。提示：使用哈希表来检测循环。
# 4. 哈希表的应用：快乐数
def is_happy(n): def get_next(number): total_sum = 0 while number > 0: number, digit = divmod(number, 10) total_sum += digit ** 2 return total_sum seen = set() while n != 1 and n not in seen: seen.add(n) n = get_next(n) return n == 15.设计哈希集合不使用任何内建的哈希表库设计一个哈希集合[表逻辑]（HashSet）。实现MyHashSet类：void add(key) 向哈希集合中插入值 key。bool contains(key) 返回哈希集合中是否存在这个值 key。void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。
# 5. 设计哈希集合
class MyHashSet: def __init__(self): self.size = 1000 self.buckets = [[] for _ in range(self.size)] def hash(self, key): return key % self.size def add(self, key): if not self.contains(key): self.buckets[self.hash(key)].append(key) def remove(self, key): bucket = self.buckets[self.hash(key)] if key in bucket: bucket.remove(key) def contains(self, key): bucket = self.buckets[self.hash(key)] return key in bucket