一、哈希表
哈希表是一个通过哈希函数来计算数据存储位置的数据结构，通常支持如下操作：
- insert（key, value）:插入键值对（key， value）。
- get (key) : 如果存在键值对为key的键值对则返回其value， 否则返回空值。
- delete (key):删除键为key的键值对。
1. 直接寻址法
当关键字的全域U比较小时，直接寻址是一种简单而有效的方法。
U: 关键字可能出现的所有的集合。
T:根据U建立相关的T。
然后关键字在相应的T中找值。
直接寻址法的缺点：
- 当域U很大的时候，需要消耗大量的内存，很不实际。
- 如果域U很大而实际出现的key很少，则大量空间被浪费。
- 无法处理关键字不是数字的情况。
2. 哈希
直接寻址表 + 哈希函数 = 哈希
直接寻址表：key为k的元素放在k位置上
改进直接寻址表：哈希（Hashing）
- 构建大小为m的寻址表T
- key为k的元素放在h（k）位置上
- h (k) 是一个函数，其将域U映射到表T[0, 1,....,m-1]
3. 哈希表
哈希表（Hash Table, 又称为散列表），是一种线性表的存储结构。哈希表由一个直接寻址表和一个哈希函数组成。哈希函数 h(k) 将元素关键字k作为自变量，返回元素的存储下标。
示例：
假设有一个长度为7的哈希表，哈希函数 h(k) = k % 7。元素集合{14， 22， 3， 5}的存储方式如下图所示：
3.1 哈希冲突
由于哈希表的大小是有限的，而要存储的值的总数量是无限的，因此对于任何哈希函数，都会出现两个不同元素映射到同一个位置上的情况，这种情况叫做哈希冲突。
例如：h (k) = k % 7, h (0) = h(7) = h(14)
3.2 解决哈希冲突 -- 开放寻址法
开放寻址法：如果哈希函数返回的位置已经有值，则可以向后探查新的位置来存储这个值。
- 线性探查：如果位置i被占用，则探查i+1， i+2 ......（查找也是按照线性查找）
- 二次探查：如果位置i被占用，则探查i+
，i -
， i-
- 二度哈希：有n个哈希函数，当时也第1个哈希函数h1发生冲突时，则尝试使用h2，h3。
3.3 解决哈希冲突 -- 拉链法（重点）
拉链法：哈希表每个位置都连接一个链表，当冲突发生时，冲突的元素都将被加到该位置链表的最后。
查找的复杂度不好计算（可能不是平均分配）
4. 常见的哈希函数
- 除法哈希法：h (k) = k % m
- 乘法哈希法：h (k) = floor(m * (A * key % 1)) --- floor表示向下取整，m为哈希表大小，A是一个介于0~1之间的常数。
- 全域哈希法：ha,b(k) = ((a*key + b) % p) % m a, b = 1,2,......p-1
5. 自定义哈希表
# 创建一个可以迭代的链表
class LinkList:
class Node: # 定义一个单链表
def __init__(self, item=None): #
self.item = item
self.next = None
class LinkListIterator:
def __init__(self, node):
self.node = node
def __next__(self):
if self.node:
cur_node = self.node
self.node = cur_node.next
return cur_node.item
else:
raise StopIteration
def __iter__(self):
return self
def __init__(self, iterable=None):
self.head = None
self.tail = None
if iterable:
self.extend(iterable)
def append(self, obj):
s = LinkList.Node(obj)
if not self.head:
self.head = s
self.tail = s
else:
self.tail.next = s
self.tail = s
def extend(self, iterable):
for obj in iterable:
self.append(obj)
def find(self, obj):
for n in self:
if n == obj:
return True
else:
return False
def __iter__(self): # 迭代器
return self.LinkListIterator(self.head)
def __repr__(self): # 转化为字符串
return "<<" + ",".join(map(str, self)) + ">>"
# 根据拉链法创建一个哈希表
class HashTable:
def __init__(self, size=101):
self.size = size
self.T = [LinkList() for i in range(self.size)] # 直接寻址法中的T
def h(self, k): # 哈希表中的哈希函数
return k % self.size
def insert(self, k): # 插入函数
i = self.h(k)
if self.find(k):
print("Duplicacted Insert")
else:
self.T[i].append(k)
def find(self, k):
i = self.h(k)
return self.T[i].find(k)
# 添加迭代器后，创建的链表可以被迭代
lk = LinkList([1, 2, 3, 4, 5])
for element in lk:
print(element)
print(lk)
# numbers = [1, 2, 3, 4, 5]
# str_numbers = map(str, numbers)
# print(str_numbers)
# print(list(str_numbers))
ht = HashTable()
ht.insert(0)
ht.insert(1)
ht.insert(2)
ht.insert(4)
ht.insert(507)
print(",".join(map(str, ht.T)))
print(ht.find(3))6. 哈希表的应用
6.1集合和字典
字典和集合都是通过哈希表来实现的。
- a = {'name':'Alex', 'age':18, 'gender':'Man'}
- 使用哈希表存储字典，通过哈希函数将字典的键映射为下标。假如h('name') = 3, h('age') = 1 , h('gender') = 4, 则哈希表存储为[None, 18, None, 'Alex', 'Man']
- 如果发生哈希冲突，则通过拉链发或开发寻址法解决。
- 相同的查找元素，集合和字典肯定比列表要快（因为是按照哈希表的查找）
6.2 md5算法
MD5(Message-Digest Algorithm 5)曾经是密码学中常用的哈希函数，可以把任意长度的数据映射为128的哈希值，其曾经包括如下特征：
- 同样的消息，其MD5值必定相同；
- 可以快速计算出任意给定消息的MD5值；
- 除非暴力的美剧所有可能的消息，否则不可能从哈希值反推消息本身；
- 两条消息之间即使只要微小的差别，其对应的MD5值也应该完全不同、完全不相关；
- 不能在有意义的时间内人工的构造两个不同的消息， 使其具有相同的MD5值。