散列(Hashing)
散列表（Hash Table），又称哈希表，是一种实现字典数据结构的方式。其中数据项的储存方式尤其有利于将来快速的查找定位。
散列表中的每个存储位置，称为槽（slot），可以用来保存数据项，每个槽有唯一的名称。
散列函数(Hash Function)
实现从数据项到存储槽名称的转换的，称为散列函数。
散列冲突(Hash Collision)
当散列函数将两个不同的数据项映射到同一个槽时，就会发生散列冲突。
完美散列函数(Perfect Hash Function)
给定一组数据项，如果一个散列函数能把每个数据项映射到不同的槽中，那么这个散列函数就可以称为完美散列函数。（最著名的近似完美散列函数是MD5和SHA系列函数）
散列函数设计
-
数项
a. 折叠法
将数据项分割为位数相同的子块，然后将子块相加，最后对散列表大小求余，得到散列值。有时候还会有隔数反转的步骤，对散列函数提供了一种微调的手段b. 平方取中法
首先对数据进行平方的运算，然后取平方中间两位，再对散列表大小求余，得到散列值。 -
非数项
可以通过把字符串里面每一个字符看作ascii码，然后相加，最后对散列表大小求余，得到散列值。
def hash(astring, tablesize):sum = 0for pos in range(len(astring)):sum = sum + ord(astring[pos])return sum % tablesize为了防止变位词的问题，可以将字符串所在的位置作为权重因子，乘以ord值
def hash(astring, tablesize):sum = 0for pos in range(len(astring)):sum = sum + ord(astring[pos]) * (pos + 1)return sum % tablesize
冲突解决方案
-
开放定址法（Open Addressing）
为冲突的数据项再找一个开放的空槽来保存，最简单的方法是线性探测法（Linear Probing），从冲突的槽开始，依次检查下一个槽，直到找到一个空槽为止。 如果到散列表末尾还未找到，则从首部接着扫描。
采用线性探测法来解决散列冲突的话，则散列表的查找也需要遵守相同的规则。 如果在散列位置没有找到查找项的话，就必须向后做顺序查找，直到找到查找项或者碰到空槽（查找失败）
线性探测法的缺点是有聚集现象，即：如果多个数据项最终散列到相同的槽，则这些数据项会聚集在一块，从而连锁式影响其他数据项的插入。
2. 数据项链（Chaining）
将容纳单个数据项的槽扩展为容纳数据项集合（或者对数据项链表的引用）
映射抽象数据类型及python实现
python中最有用的数据类型之一“字典”是一种可以保存key-data键值对的数据类型
其中关键码可用于查询关联的数据值data，这种键值关联称为映射Map。
ADT Map的结构是键-值关联的无序集合
- 关键码具有唯一性
- 通过关键码可以唯一确定一个数据值
ADT Map定义的操作如下：
Map()：创建一个空映射,返回空映射对象put(key, value)：将一个键值对存入映射中，如果关键码key已经存在，则更新其对应的值为valueget(key)：返回关键码对应的值，如果关键码不存在，则返回Nonedel：通过del map(key)删除键值对，如果关键码不存在，则抛出KeyError异常len()：返回映射中键值对的数量in：通过key in map的方法，检查映射中是否存在某个key，如果存在，则返回True，否则返回False
实现ADT Map
class HashTable: def __init__(self, size): self.size = size self.slots = [None] * self.size self.data = [None] * self.size
def __getitem__(self, key): return self.get(key)
def __setitem__(self, key, data): self.put(key, data)put()方法
#hashfunction方法采用了简单求余方法来实现散列函数，而冲突解决则采用线性探测“加1”法再散列函数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] == None: self.slots[hashvalue] = key self.data[hashvalue] = data else: if self.slots[hashvalue] == key: self.data[hashvalue] = data # replace else: nextslot = self.rehash(hashvalue) while self.slots[nextslot] != None and self.slots[nextslot] != key: nextslot = self.rehash(nextslot)
if self.slots[nextslot] == None: self.slots[nextslot] = key self.data[nextslot] = data else: self.data[nextslot] = data # replaceget()方法
def get(self, key): startslot = self.hashfunction(key)
data = None stop = False found = False position = startslot
while self.slots[position] != None and not found and not stop: if self.slots[position] == key: found = True data = self.data[position] else: position = self.rehash(position) if position == startslot: stop = True return datadel()方法
def __delitem__(self, key): self.put(key, None)如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时