文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

python实现一个简易hashmap

2023-01-31 05:50

关注

python实现一个简易hashmap,不严谨、有问题之处请多多指出。。

近日把数据结构翻出来看看,发现自己这方面的知识很欠缺,算是自己的记录,也希望给正在学习数据结构的老铁们分享,共同学习。。。

简单说明原理
python语言中的dict底层是基于hashmap结构实现的,dict的使用就不说了。关键一点是,hashmap可以在一堆数据中,很快的根据key,找到value,这个关键点主要是由hash函数实现的。详细原理请看《大话数据结构》一书的8.9章节,我觉得讲得很好。。

简单实现
《大话数据结构》结构一书中主要用C语言来实现hashmap结构,下面我会给出用python语言实现的代码。并且为解决hash冲突问题,我使用了“链地址法”的结构。
MyHash内部使用items列表来存储数据,items是一个列表,并且每个元素也是一个列表,元素列表中存储了具体的(key,value)元组,不同的key根据hash函数先算出index,即存储在哪条列表中,插入时则直接append,查找时则根据equals方法将待查找的key与列表中的所有元组的第一个值(key)进行比较,找到相等的则返回元组的第二个值(value),找不到则raise KeyError异常。

# coding=utf-8


class MyHash(object):

    def __init__(self, length=10):
        self.length = length
        self.items = [[] for i in range(self.length)]

    def hash(self, key):
        """计算该key在items哪个list中,针对不同类型的key需重新实现"""
        return key % self.length

    def equals(self, key1, key2):
        """比较两个key是否相等,针对不同类型的key需重新实现"""
        return key1 == key2

    def insert(self, key, value):
        index = self.hash(key)
        if self.items[index]:
            for item in self.items[index]:
                if self.equals(key, item[0]):
                    # 添加时若有已存在的key,则先删除再添加(更新value)
                    self.items[index].remove(item)
                    break
        self.items[index].append((key, value))
        return True

    def get(self, key):
        index = self.hash(key)
        if self.items[index]:
            for item in self.items[index]:
                if self.equals(key, item[0]):
                    return item[1]
        # 找不到key,则抛出KeyError异常
        raise KeyError

    def __setitem__(self, key, value):
        """支持以 myhash[1] = 30000 方式添加"""
        return self.insert(key, value)

    def __getitem__(self, key):
        """支持以 myhash[1] 方式读取"""    
        return self.get(key)


myhash = MyHash()
myhash[1] = 30000
myhash.insert(2, 2100)
print myhash.get(1)
myhash.insert(1, 3)
print myhash.get(2)
print myhash.get(1)
print myhash[1]

几点说明

  • 以上实现仅支持key为int类型的情况,若要支持其他类型的key,需重新实现hash方法及equals方法

  • 仅实现了插入、读取方法,其他方法可以按照python中dict的接口方法再进行添加

  • 实现了_setitem__getitem_方法,使我们的对象也可像dict一样进行添加、读取

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯