1. 哈希查找算法

哈希查找算法就是使用哈希函数来计算一个键值所对应的地址，进而建立哈希表格，然后利用哈希函数来查找到各个键值存放在表格中的地址。简单来说，就是把一些复杂的数据，通过某种函数映射（与数学中的映射关系一样）关系，映射成更易于查找的方式。哈希查找算法的查找速度与数据多少无关，完美的哈希查找算法一般都可以做到一次读取完成查找。

哈希查找算法就是这样一种算法，例如，在一本书中查找内容，首先翻开这本书的目录，然后在目录上找到想要的内容，最后根据对应的页码就能找到所需要的内容。哈希查找算法具有保密性高的特点，因此哈希查找算法常被应用在数据压缩和加解密方面。常见的哈希算法有除留取余法、平方取中法以及折叠法。

1.1 哈希表和哈希函数

哈希表是一种存储键值和键值所对应地址的一种数据集合。哈希表中的位置，一般称为槽位，每个槽位都能保存一个数据元素并以一个整数命令（从0开始）。这样我们就有了0号槽位、1号槽位等。起始时，哈希表里没有数据，槽位是空的，这杨在构建哈希表时，可以把槽位的值都初始化成 None 。数据元素和保存的槽位之间的映射关系，称为哈希函数。哈希函数接受一个数据元素作为参数，返回一个0到n-1的整数作为槽位名。

1.2 除留余数法

除留余数法是哈希算法中最简单的一种算法。它是将每个数据除以某个常数后，取余数来当索引。除留取余法对应的哈希函数如下：

h(item)=item % num

• item：每个数据
• num：一个常数，一般会选择一个质数，例如取质数11

1.3 折叠法

对于给定的数据集，哈希函数将每个元素映射为单个槽位，称为 “完美哈希函数” 。但是对于任意一个数据集合，没有系统能构造出完美哈希函数。

对应的哈希函数也得到了哈希值，例如：h(54)=10, h(26)=4, h(93)=5 等等。

1.4 折叠法

对于给定的数据集，哈希函数将每个元素映射为单个槽位，称为 “完美哈希函数”。但是对于任意一个数据集合，没有系统能够构造出完美哈希函数。例如，在上述除留取余的例子中再加上一个数据44，该数字除以11后，得到的余数是0，这与数据77的哈希值相同。遇到这种情况时，解决办法之一就是扩大哈希表，但是这种做法太浪费空间。因此又有了扩展除留取余的方案，也就是折叠法。

折叠法是先将数据拆分成几组数据，再把他们加起来作为哈希地址，再使用除留取余法，这中做法称为“移动折叠法”。

对奇数或偶数进行反转，再将反转后的数字相加，再使用除留取余法，这中做法称为“边界折叠法”。

1.5 平方取中法

平方取中法是先将各个数据平方，将平方后数据取中间的某段数字作为索引，例如，对于数据集 54，26，93，17，77，31, 平方取中法如下：

• 先取平方：52² = 2916，26² = 676，…
• 取以上平方值的中间数，即取十位和百位：91，67，…
• 设置槽位11，分别除以11留余数，得到哈希值分别为：3，1，…

2. 用哈希查找算法查找七色光颜色

哈希算法理想的情况是所有数据经过哈希函数运算后得到不同的值，但是在实例情况中即使得到的哈希值不同，也有可能得到相同的地址，这种问题被称为 “碰撞问题”。使用哈希算法，将数据放到哈希表中存储数据对应位置，若该位置满了，就会溢出，这种问题被称为 “溢出问题”。（常见的处理方式后续再讲）

class HashTable:
# 创建哈希表
def __init__(self):
self.size = 11
# 哈希表长度
self.throw = [None] * self.size
# 哈希表数据键初始化
self.data = [None] * self.size
# 哈希表数据值初始化
# 假定最终将有一个空槽，除非 key 已经存在于
self. throw中。 它计算原始
# 哈希值，如果该槽不为空，则迭代 rehash 函数，直到出现空槽。如果非空槽已经包含 key，
# 则旧数据值将替换为新数据值。
def put(self, key, value):
# 输出键值
hashvalue = self.hashfunction(key, len(self.throw))
# 创建哈希值
if self.throw[hashvalue] is None:
self.throw[hashvalue] = key
# 将key值给哈希表的throw
self.data[hashvalue] = value
# 将value值给哈希表的data
else:
if self.throw[hashvalue] == key:
self.data[hashvalue] = value
else:
nextslot = self.rehash(hashvalue, len(self.throw))
while self.throw[nextslot] is not None and self.throw[nextslot] != key:
nextslot = self.rehash(nextslot, len(self.throw))
if self.throw[nextslot] is None:
self.throw[nextslot] = key
self.data[nextslot] = value
else:
self.data[nextslot] = value
# 重新加1，除以11，留余数
def rehash(self, oldhash, size):
return (oldhash + 1) % size
# 除以11，留余数
def hashfunction(self, key, size):
return key % size
# 从计算初始哈希值开始。如果值不在初始槽中，则 rehash 用
# 于定位下一个可能的位置。
def get(self, key):
startslot = self.hashfunction(key, len(self.throw))
data = None
found = False
stop = False
pos = startslot
while pos is not None and not found and not stop:
if self.throw[pos] == key:
found = True
data = self.data[pos]
else:
pos = self.rehash(pos, len(self.throw))
# 回到了原点，表示找遍了没有找到
if pos == startslot:
stop = True
return data
# 重载载 __getitem__ 和 __setitem__ 方法以允许使用 [] 访问
def __getitem__(self, key):
return self.get(key)
def __setitem__(self, key, value):
return self.put(key, value)
# 创建哈希表、给哈希表赋值
H = HashTable()
H[16] = "红"
H[28] = "橙"
H[32] = "黄"
H[14] = "绿"
H[56] = "青"
H[36] = "蓝"
H[71] = "紫"
print("key的数据是：",H.throw)
# 输出键key
print("value的数据是：",H.data)
# 输出值value
print("结果是:",H[28])
# 根据key=28查value
print("结果是:",H[71])
# 根据key=71查value
print("结果是:",H[93])
# 根据key=93查value

最后

以上就是要减肥泥猴桃为你收集整理的005.用哈希查找算法查找七色光颜色【哈希查找算法】1. 哈希查找算法2. 用哈希查找算法查找七色光颜色的全部内容，希望文章能够帮你解决005.用哈希查找算法查找七色光颜色【哈希查找算法】1. 哈希查找算法2. 用哈希查找算法查找七色光颜色所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。