python数据结构-hash

python学习笔记之hash

拉链法实现hash表数据结构

什么叫Hash

Hash一般翻译做“散列”，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

一个输入通过散列算法得到一个固定长宽的输出，这个散列值是有可能冲突的，也就是说输入值不同，而通过计算后得到的散列值有可能相同了，这样就产生了冲突，拉链法就能解决这样的冲突。拉链法把散列值所对应的数据又放在了一个链表里，放在链表的位置就是以散列值作为索引值，这样就能解决散列冲突的问题，要以下边的示意图来展示：

左边就是hash表的尺寸大小，可以把它看成一个数组，数组的每个成员指向一个链表，也可以指向一个空链表，链表里的元素主是实际存放的数据。

Hash表常用的方法：

• Map()方法，创建一个空Hash表
• put(key, value)方法，接收一个key和value，没有返回值
• get(key)方法，接收key，返回key对应的value值，如果没有此值默认返回None
• remove(key)方法，接收key，删除key对应的value

先来实现一个存放在链表中的元素类：

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value

Node类接收两个参数，一个是key，另一个Key对应的value。

Map类的实现

class Map:
    def __init__(self, init_size, hash=hash):
        self.__slot = [[] for _ in range(init_size)]
        self.__size = init_size
        self.hash = hash

如果计算散列值的函数不使用pyton的内建的hash函数，可以自己传入一个函数，这里默认采用hash函数。代码中的列表解析self.__slot = [[] for _ in range(init_size)]与下边的代码块等价，都是生成一个包含init_size个[]元素的列表。

self.__slot = []
for _ in range(init_size):
   self.__slot.append([])

put方法实现

def put(self, key, value):
    node = Node(key, value)
    address = self.hash(node.key) % self.__size
    self.__slot[address].append(node)

这里的address = self.hash(node.key) % self.__size是把散列值与Hash表尺寸做取模运算，这样address就一定能落到如上图中的数组元素中，接着再把node对象append到链表中。

get方法实现

def get(self, key, default=None):
    _key = self.hash(key)
    address = _key % self.__size
    for node in self.__slot[address]:
        if node.key == key:
            return node.value
    return default

要得到一个key的value值，首先得采用相同的hash函数计算出散列地址，再在这个地址上的链表中遍历key，有则返回其value，否则返回一个默认值。

remove方法实现

def remove(self, key):
    address = self.hash(key) % self.__size
    for idx, node in enumerate(self.__slot[address].copy()):
        if node.key == key:
            self.__slot[address].pop(idx)

此方法同样需要得到key的散列地址，再遍历链表，只是这里会删除key所对应的value。在使用python的可迭代对象时有一条定律，那就是永远都不要对迭代对象进行数据的修改，所以这里把链表进行了copy()，生成一个副本，对这个副本进行遍历，如果链表中有key，那就在原链表里弹出此key。

完整的代码如下：

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
 
 
class Map:
    def __init__(self, init_size, hash=hash):
        self.__slot = [[] for _ in range(init_size)]
        #self.__slot = []
        #for _ in range(init_size):
        #   self.__slot.append([])
        self.__size = init_size
        self.hash = hash
 
    def put(self, key, value):
        node = Node(key, value)
        address = self.hash(node.key) % self.__size
        self.__slot[address].append(node)
 
    def get(self, key, default=None):
        _key = self.hash(key)
        address = _key % self.__size
        for node in self.__slot[address]:
            if node.key == key:
                return node.value
        return default
 
    def remove(self, key):
        address = self.hash(key) % self.__size
        for idx, node in enumerate(self.__slot[address].copy()):
            if node.key == key:
                self.__slot[address].pop(idx)
 
if __name__ == '__main__':
    map = Map(16)
    for i in range(5):
        map.put(i, i)
 
    map.remove(3)
 
    for i in range(5):
        print(map.get(i, 'not set'))