[原]哈系表的实现

李余通 18/10/09 20:17:14

哈希表的实现

何为哈希表

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

  1. 使用一个较大的一维数组存储value,这个数组为Array
  2. 实现一个哈希函数,使得hash(key)的值在上一步的一维数组下标范围内
  3. 如此,对于任意的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
作者:baidu_35085676 发表于 2018/10/09 20:17:14 原文链接 https://blog.csdn.net/baidu_35085676/article/details/82980140
阅读:69