python利用拉链法实现字典方法示例

前言

字典也叫散列表,最大的特点是通过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查到的时间，可见下图

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作能带来一定的帮助，如果有疑问大家可以留言交流，谢谢大家对我们的支持。

赞 (0)

相关推荐

  • python中将字典转换成其json字符串

    #这是Python中的一个字典 dic = { 'str': 'this is a string', 'list': [1, 2, 'a', 'b'], 'sub_dic': { 'sub_str': 'this is sub str', 'sub_list': [1, 2, 3] }, 'end': 'end' } //这是javascript中的一个JSON对象 json_obj = { 'str': 'this is a string', 'arr': [1, 2, 'a', 'b'],

  • python 将字符串转换成字典dict

    复制代码 代码如下: JSON到字典转化:dictinfo = simplejson.loads(json_str) 输出dict类型 字典到JSON转化:jsoninfo = simplejson.dumps(dict)输出str类型 比如:info = {'name' : 'jay', 'sex' : 'male', 'age': 22}jsoninfo = simplejson.dumps(info)print jsoninfo print type(jsoninfo)

  • python通过字典dict判断指定键值是否存在的方法

    本文实例讲述了python通过字典dict判断指定键值是否存在的方法.分享给大家供大家参考.具体如下: python中有两种方法可以判断指定的键值是否存在,一种是通过字典对象的方法 has_key 判断,另外一种是通过 in 方法,下面是详细的范例. d={'site':'http://www.jb51.net','name':'jb51','is_good':'yes'} #方法1:通过has_key print d.has_key('site') #方法2:通过in print 'body'

  • Python中使用item()方法遍历字典的例子

    Python中使用item()方法遍历字典的例子

    Python字典的遍历方法有好几种,其中一种是for...in,这个我就不说明,在Python了几乎随处都可见for...in.下面说的这种遍历方式是item()方法. item() item()方法把字典中每对key和value组成一个元组,并把这些元组放在列表中返回. DEMO 代码: 复制代码 代码如下: person={'name':'lizhong','age':'26','city':'BeiJing','blog':'www.jb51.net'}   for key,value i

  • Python中字典和JSON互转操作实例

    JSON是一种轻量级的数据交换格式,各种语言都有良好的支持.字典是Python的一种数据结构.可以看成关联数组. 有些时候我们需要设计到字典转换成JSON序列化到文件,或者从文件中读取JSON.简单备忘一下. Dict转JSON写入文件 复制代码 代码如下: #!/usr/bin/env python # coding=utf-8 import json d = {'first': 'One', 'second':2} json.dump(d, open('/tmp/result.txt', '

  • python创建和使用字典实例详解

    字典是python中唯一内建的映射类型.字典中的值并没有特殊的顺序,但是都存储在一个特定的键(key)里.键可以是数字,字符串甚至是元组.1. 创建和使用字典字典可以通过下面的方式创建: 复制代码 代码如下: phonebook = {'Alice':'2341','Beth':'9102','Ceil':'3258'} 字典由多个键及与其对应的值构成的对组成.每个键和它的值之间用冒号(:)隔开,项之间用逗号(,)隔开,而整个字典是由一对大括号括起来.空字典:{} 1.1 dict函数可以用di

  • python两种遍历字典(dict)的方法比较

    python以其优美的语法和方便的内置数据结构,赢得了不少程序员的亲睐.其中有个很有用的数据结构,就是字典(dict),使用非常简单.说到遍历一个dict结构,我想大多数人都会想到 for key in dictobj 的方法,确实这个方法在大多数情况下都是适用的.但是并不是完全安全,请看下面这个例子: 复制代码 代码如下: #这里初始化一个dict>>> d = {'a':1, 'b':0, 'c':1, 'd':0}#本意是遍历dict,发现元素的值是0的话,就删掉>>&

  • python提取字典key列表的方法

    本文实例讲述了python提取字典key列表的方法.分享给大家供大家参考.具体如下: 这段代码可以把字典的所有key输出为一个数组 d2 = {'spam': 2, 'ham': 1, 'eggs': 3} # make a dictionary print d2 # order is scrambled print d2.keys() # create a new list of my keys 希望本文所述对大家的Python程序设计有所帮助.

  • python中的字典详细介绍

    一.什么是字典? 字典是Python语言中唯一的映射类型. 映射类型对象里哈希值(键,key)和指向的对象(值,value)是一对多的的关系,通常被认为是可变的哈希表. 字典对象是可变的,它是一个容器类型,能存储任意个数的Python对象,其中也可包括其他容器类型. 字典类型与序列类型的区别: 1.存取和访问数据的方式不同. 2.序列类型只用数字类型的键(从序列的开始按数值顺序索引): 3.映射类型可以用其他对象类型作键(如:数字.字符串.元祖,一般用字符串作键),和序列类型的键不同,映射类型的

  • Python 字典(Dictionary)操作详解

    Python字典是另一种可变容器模型,且可存储任意类型对象,如字符串.数字.元组等其他容器模型.一.创建字典字典由键和对应值成对组成.字典也被称作关联数组或哈希表.基本语法如下: 复制代码 代码如下: dict = {'Alice': '2341', 'Beth': '9102', 'Cecil': '3258'} 也可如此创建字典: 复制代码 代码如下: dict1 = { 'abc': 456 };dict2 = { 'abc': 123, 98.6: 37 }; 注意:每个键与值用冒号隔开

随机推荐