哈希表的实现

何为哈希表

简单来说，哈希表是一种存储结构，它存储的数据是 key:value 类型的。通过空间换时间的方法来加快查询速度，具体思想是如下：

使用一个较大的一维数组存储value，这个数组为Array
实现一个哈希函数，使得hash(key)的值在上一步的一维数组下标范围内
如此，对于任意的key:value，使用hash(key)，之后就可以知道value在数组中存储的下标，存取速度快过线性查找Array[hash(key)]

哈希表的注意要点

哈希函数的选取

由于我们期望，两个不同的key，hash(key)之后的结果尽量不相同，这样才能使得哈希表存储空间的利用率提高，另一点，哈希表的空间换时间的主要原因就是他使用了哈希函数来确定value在数组中的下标而非普通的线性查找。那么，基于以上两点，哈希函数的选取就有以下条件：

hash函数运行速度不能过慢
对于不同的key(即便两个key只是字母顺序不一致)，哈希函数须尽量保证hash(key)的值不一致

处理哈希碰撞

由于是无论key的个数有多少，hash(key) 的结果都在一个有限的集合内，即将一个无限的集合映射在一个有限的集合，所以必定会产生不同key但hash(key)结果一样的情况，这称为哈希碰撞，哈希表的另一要点就是要解决哈希碰撞。
解决哈希碰撞一般有以下方法：

开放地址法
再散列法
链地址法
建立公共溢出区

本文主要将2种解决冲突的方法。

链地址法

这种方法可以说是最为简单的，较为容易理解，并且，这种方法无需担心初始期间开辟的数组大小不够，那么下面具体来讲他。

链地址法顾名思义，即使用链接的方式，将产生冲突的元素链接起来，这样就好比我们初始的数组里面，存放的都是链表的头节点，如果出现冲突，只需要在链表的尾部进行增加节点就好了。

下面贴出一个用Python实现的链地址法处理冲突的哈希表：

# 包含next属性的节点
class MyLinkDictEntry:
    def __init__(self):
    # -1:Unused 0:Dummy 1:Active
        self.state = -1
        self.hash = None
        self.key = None
        self.value = None
        self.next = None

# 哈希函数
def hash_func(key,mask):
    hash_val = 0
    for i in key.encode('utf-8'):
        hash_val << 4
        hash_val += i
    return hash_val % mask

# 基础字典对象
class MyDictObject:
    def __init__(self,length=1024):
        # 生成大小为length的数组来存储MyDictEntry
        length = int(length)
        self.mask = length # all
        self.fill = 0 # 0 + 1
        self.used = 0 # 1
        self.data = [MyLinkDictEntry() for _ in range(length)]

    def __str__(self):
        # 打印字典中的值
        s = ''
        s += '{\n'
        for i in [item for item in self.data if item.state == 1]:
            s += i.key + ':' + str(i.value) + '\n'
        s += '}'
        return s


# 链地址法的字典
class MyLinkDictObject(MyDictObject):
    def set(self,key, value):
        # 字典增添元素
        hash_val = hash_func(key, self.mask)
        item = self.data[hash_val]
        first_item = None
        while True:
            if item.state == 1 and item.key == key:
                # 该节点被使用并且key一致（更新操作）
                break
            if item.state == 0:
                # 该节点伪删除 记录第一个伪删除的
                first_item = item if first_item == None else first_item
            if item.state == -1:
                # 该结点未使用，增加
                break

            if item.next:
                item = item.next
            else:
                break
        if item.state == 1:
            # 更新操作
            item.key = key
            item.value = value
            item.state = 1
        elif not item.next:
            # 增加操作
            if first_item:
                # 增加到第一个伪删除节点
                item = first_item
                item.state = 1
                item.key = key
                item.value = value
            else:
                # 增加到最后
                if item.state != -1:
                    item.next = MyLinkDictEntry()
                    item = item.next
                item.state = 1
                item.key = key
                item.value = value
        else:
            raise Exception('未考虑到的情况！')

    def get(self,key):
        # 字典获取元素
        hash_val = hash_func(key, self.mask)
        item = self.data[hash_val]
        while item:
            if item.state == 1 and item.key == key:
                break
            else:
                item = item.next
        if not item:
            KeyError("没有这个键")
        else:
            return item.value

    def delete(self,key):
        # 字典删除元素
        hash_val = hash_func(key, self.mask)
        item = self.data[hash_val]
        while item:
            if item.state == 1 and item.key == key:
                break
            else:
                item = item.next
        if not item:
            KeyError("没有这个键")
        else:
            item.state = 0
            self.used -= 1

    def __str__(self):
        # 打印字典中的值
        s = ''
        s += '{\n'
        for item in self.data:
            while item:
                if item.state == 1:
                    s += item.key + ':' + str(item.value) + '\n'
                item = item.next
        s += '}'
        return s