时间:2021-05-22
前言
字典也叫散列表,最大的特点是通过key来查找其对应的值其时间复杂度是O(1),下面这篇文章就来给大家介绍介绍python利用拉链法实现字典的方法。
在Python中怎样用列表实现字典?
用列表实现字典最大的问题就是解决hash冲突,如果在列表中通过计算不同的key得到相同的相同了位置,这时候应该怎么办?
最简单的办法就是使用拉链法.
拉链法:就是在一个列表中每个位置再添加一个列表,这样就算是有hash冲突也能够存储进去,当选取的hash函数足够好,
num的数足够大,就能够保证列表中的每一个列表里面只有一个元素。根据key计算的元素所在的位置,然后来取值就能达
到O(1)的时间。
方法示例
class MyDict: def __init__(self, num=100): # 指定列表大小 self._num = num self._lst = [] for _ in range(self._num): self._lst.append([]) def update(self, key, value): # 添加 key-value key_index = hash(key) % self._num for i, (k, v) in enumerate(self._lst[key_index]): if key == k: self._lst[key_index][i] = [key, value] break else: self._lst[key_index].append([key, value]) def get(self, key): # 根据指定的 key 弹出值 key_index = hash(key) % self._num for k, v in self._lst[key_index]: if k == key: return v else: raise KeyError('No such {} key'.format(key)) def pop(self, key): # 根据 key 弹出元素 并且删除 key_index = hash(key) % self._num for i, (k, v) in enumerate(self._lst[key_index]): if k == key: result = v self._lst.pop(i) return result else: raise KeyError('No such {} key'.format(key)) def __getitem__(self, key): # 可以通过下标来取值 key_index = hash(key) % self._num for k, v in self._lst[key_index]: if k == key: return v else: raise KeyError('No such {} key'.format(key)) def keys(self): # 取得所有的key for index in range(self._num): for k, v in self._lst[index]: yield k def values(self): # 取得所有的 value for index in range(self._num): for k, v in self._lst[index]: yield v def items(self): # 取得所有的条目 for index in range(self._num): for item in self._lst[index]: yield item通过key查到的时间,可见下图
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流,谢谢大家对的支持。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
python中没有swich..case,若要实现一样的功能,又不想用if..elif来实现,可以充分利用字典进行实现主要是想要通过不同的key调用不同的方法,
本文实例讲述了Python实现合并字典的方法。分享给大家供大家参考。具体实现方法如下:#将两个字典合并#!/usr/bin/pythondefadddict(d
本文实例讲述了python实现给字典添加条目的方法,是针对字典操作中比较实用的技巧。分享给大家供大家参考。具体实现方法如下:defaddWord(theInde
python中没有swich..case,若要实现一样的功能,又不想用if..elif来实现,可以充分利用字典进行实现主要是想要通过不同的key调用不同的方法,
python是解释型语言,本文介绍了Python下利用turtle实现绘图功能的示例,本例所示为Python绘制一个树枝,具体实现代码如下:python是解释型