python实现一个简易hashmap
- 2020 年 1 月 7 日
- 筆記
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一样进行添加、读取
