专栏首页python3哈希表的原理及实现代码

哈希表的原理及实现代码

哈希表可以表述为,是一种可以根据关键字快速查询数据的数据结构

一. 哈希表有哪些优点?

不论哈希表中数据有多少,增加,删除,改写数据的复杂度平均都是O(1),效率非常高

二. 实现哈希表

1. 哈希表原理

如果说每一个数据它都对应着一个固定的位置,那我们查找特定一个数据时,就可以直接查看这个数据对应的位置是否存在数据。一个形象的例子就是学生在教室中的位置,开学的时候,老师会给学生每一个人分配一个位置,而且不允许学生随便乱坐位置,以后老师要查看今天李刚同学有没有上课,直接看李刚同学的位置是不是有人就可以判断,没必要点了全班同学的名才可以知道李刚同学来了没有。

2. 实现简单的哈希表

根据上面的原理,首先,我们要分配一片空间用来存储我们数据,比如是一个空的数组

然后,有数据存进来的时候,按照特定规则得出这个数据在数组中的位置,将数据存进这个位置

我们就以存进一个整型数据为例,特定规则就是取余

根据计算出来的值,将这些数据放入对应的位置,我们的数组变为

我们已经把数据插入到了哈希表中,现在,我们要查找一个数据,只要按照取余规则计算出这个数据在数组中对应的位置,然后查看数组的这个位置,就可以取出这个数据了,比如我们要从哈希表中取出52,根据取余规则,52的计算出来的位置是8,数组中8这个位置是空的,52不在哈希表中,找不到52的数据;从哈希表中取出77,77计算出来的位置是0,数组中0这个位置有值,而且值就是77,从哈希表中取出77的值。

至此,我们知道实现了一个很简单的哈希表的原理,其实还存在很多问题,这个我们接下来讨论,这儿先把我们前面的一些概念用专业的术语替换一下,前面我们所说的特定规则,我们称之为哈希函数,用特定股则计算出来的值称之为哈希值。

3. 还存在哪些问题?

  1. 有可能两个数据通过哈希函数计算出来的哈希值有可能相等,比如77,88计算出来的位置值都是0

  2. 如果哈希表满了,该怎么扩容

第一个问题就是如何解决这种冲突

有开放定址法,链定址法,我们说一下开放定址法,就是将这个冲突的数据再重新计算一个空的位置,将其存进去,比如我们要存放88,哈希值是0,数组这个位置已经有值了,那我们再获取一个哈希值,比如在原哈希值的基础上加1,得到1,1的位置是空,我将88放进去。有人会问,1这个位置被占了,那下一个数据是1这个位置怎么办,这时候,我们还是同样的做法,给这个数据再计算一个哈希值。

插入88后的数组变为

冲突解决了,但我们读取数据的时候,好像又出现问题了,88的哈希值是0,发现数组0位置不是空的,那我们确定88在哈希表中?肯定不行,0这个位置存储的是77,不是88。我们的解决方法是判断0这个位置的值是不是88,不是的话,再计算88的哈希值是1,判断是1这个位置是否为空,为空,则88不在哈希表中;不为空,判断值是否为88,若是88,确定在哈希表中;如果值不是88,我们则继续计算哈希值是2,依次下去,直到找到88或者值为空的位置。

第二个问题,哈希表扩容

一个简单的解决办法是,当插入数据时,发现所有的位置都满了,我们就再分配一个大于原先空间的一片空间,把原来空间中的值重新哈希到新的空间中。

4. 哈希表的python实现

python中的字典就是哈希表,下面代码实现了一个简单的字典

class Dict:
    def __init__(self, size=10):
        self.size = size
        self.key = [None] * self.size
        self.data = [None] * self.size

    def __setitem__(self, key, value):
        assert isinstance(key, int)
        index = self.hash(key)
        if not self.key[index]:
            self.key[index] = key
            self.data[index] = value
        elif self.key[index] == key:
            self.data[index] = value
        else:
            start = index
            while self.key[index] and self.key[index] != key:
                index = self.re_hash(index)
                if index == start:
                    raise Exception('dict is full')

            if self.key[index]:
                self.data[index] = value
            else:
                self.key[index] = key
                self.data[index] = value

    def __getitem__(self, item):
        assert isinstance(item, int)
        index = self.hash(item)
        if not self.key[index]:
            raise KeyError(item)
        else:
            if self.key[index] == item:
                return self.data[index]
            else:
                start = index
                while self.key[index] and self.key[index] != item:
                    index = self.re_hash(index)
                    if start == index:
                        raise KeyError(item)

                if self.key[index] == item:
                    return self.data[index]
                else:
                    raise KeyError(item)

    def __contains__(self, item):
        assert isinstance(item, int)
        index = self.hash(item)
        if not self.key[index]:
            return False
        else:
            if self.key[index] == item:
                return True
            else:
                start = index
                while self.key[index] and self.key[index] != item:
                    index = self.re_hash(index)
                    if start == index:
                        break

                if self.key[index] == item:
                    return True
                else:
                    return False

    def hash(self, key):
        index = key % self.size
        return int(index)

    def re_hash(self, index):
        return index+1


a = Dict()
a[1]='3'
a[2]='4'
print(a[5])

三. 总结:

哈希表对于数据的插入,删除,更新操作复杂的平均是O(1),效率非常高,如果不关心数据的存储顺序,我们可以选取这种数据结构。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • python 中的嵌套类

    能够看到 类中 又定义了 类 ,这种情况我们称之为嵌套类 。给一个简单 demo 来认识嵌套类 。

    py3study
  • Python中接口定义和依赖注入

    首先,我们必须明确的一点是:python里无接口类型,定义接口只是一个人为规定,在编程过程自我约束

    py3study
  • 35个高级Python知识点总结

    众所周知,Java中强调“一切皆对象”,但是Python中的面向对象比Java更加彻底,因为Python中的类(class)也是对象,函数(function)也...

    py3study
  • 数据结构-数组

    工作了一段时间后,发现基础实在是太重要了,老话说: 万丈高楼平地起。地基不牢,肯定跑不快,天花板也愈发明显。

    用户1081422
  • NLPer 国际度假指南 2020

    在前几日举行的 ACL2019 大会闭幕式中,重头戏自然是宣布各个论文奖得主(具体获奖名单请看这篇文章),但也有一个环节是轻松愉快且让观众们喜闻乐见的,那就是 ...

    AI科技评论
  • 聚类模型--K 均值

    黑泽君
  • Kafka系列3-python版本pro

    py3study
  • 想做好直播间搭建,推流与拉流的详细过程你都知道吗

    直播间搭建的成功离不开基本的流媒体传输,随着网络技术的不断提高,对音视频传输的质量与速度要求也不断提高,想做好一套直播系统,推流与拉流的详细过程原理你都知道吗?

    云豹短视频嘉兴
  • 一种全新的点击率建模方案

    ? 本文作者:branxu,腾讯 CDG 应用研究员 2018 年和 2019 年腾讯算法广告大赛都可以看做推荐系统问题。这类问题最重要的特征是点击率,最大的...

    腾讯技术工程官方号
  • 【技术解读】大赛TOP团队方案技巧大揭秘!

    推荐系统和广告算法中,对于新用户或者新内容,记录很少,如果我们直接将历史点击率作为特征,会存在问题。比如

    腾讯智能钛AI开发者

扫码关注云+社区

领取腾讯云代金券