顺序查找非常简单，只是个开胃菜，今天主要练习的是哈希查找
先上顺序查找代码：
def sequence_search(array, num): for i in range(len(array)): if array[i] == num: return i return False array_0 = [23, 43, 12, 54, 65, 48] print(sequence_search(array_0, 12)) >>> 2
在来看hash查找：
算法思想哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。
算法流程
1）用给定的哈希函数构造哈希表；
2）根据选择的冲突处理方法解决地址冲突；
常见的解决冲突的方法：拉链法和线性探测法。
3）在哈希表的基础上执行哈希查找。
单纯论查找复杂度：对于无冲突的Hash表而言，查找复杂度为O(1)（注意，在查找之前我们需要构建相应的Hash表）。
class HashSearch:
def __init__(self, num):
if isinstance(num, int):
self.num = abs(num)
self.empty = self.num
self._list = [None] * self.num
else:
raise TypeError('num must be a int number')
def __hash(self, key):
return key % self.num
def put(self, key):
assert self.empty > 0, 'this array is full'
index = self.__hash(key)
while self._list[index]:
index = self.__hash(index+1)
self._list[index] = key
self.empty -= 1
def find(self, key):
index = self.__hash(key)
temp = indexwhile self._list[index] != key:
index = self.__hash(index+1)
if index == temp:
return False
return index
class HashTable:
def __init__(self):
# 哈希表的初始大小已经被选择为 11。尽管这是任意的，但是重要的是，
# 大小是质数，使得冲突解决算法可以尽可能高效。
self.size = 11
self.slots = [None] * self.size
self.data = [None] * self.size
# hash 函数实现简单的余数方法
def hash(self, key, size):
return key % size
# 冲突解决技术是 加1 rehash 函数的线性探测
def rehash(self, old_hash, size):
return (old_hash+1) % size
# 假定最终将有一个空槽，除非 key 已经存在于 self.slots 中。 它计算原始
# 哈希值，如果该槽不为空，则迭代 rehash 函数，直到出现空槽。如果非空槽已经包含 key，
# 则旧数据值将替换为新数据值。
def put(self, key, data):
hash_value = self.hash(key, len(self.slots))
if self.slots[hash_value] is None:
self.slots[hash_value] = key
self.data[hash_value] = data
else:
if self.slots[hash_value] == key:
self.data[hash_value] = data
else:
next_slot = self.rehash(hash_value, len(self.slots))
while self.slots[next_slot] is not None and \
self.slots[next_slot] != key:
next_slot = self.rehash(next_slot, len(self.slots))
if self.slots[next_slot] is None:
self.slots[next_slot] = key
self.data[next_slot] = data
else:
self.data[next_slot] = data
# 从计算初始哈希值开始。如果值不在初始槽中，则 rehash 用
# 于定位下一个可能的位置。
def get(self, key):
start_slot = self.hash(key, len(self.slots))
data = None
stop = False
found = False
pos = start_slot
while self.slots[pos] is not None and not found and not stop:
if self.slots[pos] == key:
found = True
data = self.data[pos]
else:
pos = self.rehash(pos, len(self.slots))
if pos == start_slot:
stop = True
return data
# 我们重载 __getitem__ 和 __setitem__ 方法以允许使
# 用 [] 访问。 这意味着一旦创建了HashTable，索引操作符将可用。
def __getitem__(self, item):
return self.get(item)
def __setitem__(self, key, value):
self.put(key, value)
