python 哈希表实现简单python字典代码实例

这篇文章主要介绍了python 哈希表实现简单python字典代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下

class Array(object):
  def __init__(self, size = 32, init = None):
    self._size = size
    self._items = [init] * size
  def __getitem__(self, index):
    return self._items[index]
  def __setitem__(self, index, value):
    self._items[index] = value
  def __len__(self):
    return self._size
  def clear(self, value = None):
    for i in range(self,_items):
      self._items[i] = value
  def __iter__(self):
    for item in self._items:
      yield item
class Slot(object):
  """
  定义一个哈希表数组的槽
  注意:一个槽有三种状态
  1. 从未被使用过,HashMap.UNUSED。 此槽没有被使用和冲突过,查找时只要找到UNUSED 就不用再继续探查了
  2. 使用过但是remove了, 此时是HashMap.EMPTY,该谈差点后面的元素仍可能是有key
  3. 槽正在使用Slot 节点
  """
  def __init__(self, key, value):
    self.key = key
    self.value = value
class HashTable(object):
  UNUSED = None # 表示slot 没有被使用过
  EMPTY = Slot(None, None) # 使用过被删除
  def __init__(self):
    self._table = Array(8, init = HashTable.UNUSED) # 初始化,数组的每个元素都是UNUSED
    self.length = 0
  @property # 内置装饰器,把方法变成属性
  def _load_factor(self):
    return self.length/float(len(self._table))
  def __len__(self):
    return self.length
  def _hash(self, key):
    return abs(hash(key)) % len(self._table) # abs函数返回绝对值 hash 是内置函数 _hash 直接使用内置的哈希函数,对数组的长度取模
  def _find_key(self, key):
    index = self._hash(key) # 先用 _hash方法计算出槽的位置
    _len = len(self._table) # 现保存下来长度
    while self._table[index] is not HashTable.UNUSED:  # 如果这个槽不是没有被使用过
      if self._table[index] is HashTable.EMPTY: # 如果这个槽是,曾经有过值,不过被删除了
        index = (index*5 +1 ) % _len    # cpython 使用的一种解决哈希冲突的方式
        continue
      elif self._table[index].key == key: # 正在使用, 如果key值相同
        return index
      else: # 这里就只剩最后一种可能, 正在使用,但是key没有找到
        index = (index *5 +1) % _len
    return None
  def _slot_can_insert(self, index): # 判断一个槽是否可以插入
    return (self._table[index] is HashTable.EMPTY or self._table[index] is HashTable.UNUSED)
  def _find_slot_for_insert(self,key):  # 寻找一个空槽,用来插入
    index = self._hash(key)
    _len = len(self._table)
    while not self._slot_can_insert(index):
      index = (index*5 + 1) % _len
    return index
  def __contains__(self, key):   # 实现一个in操作符
    index = self._find_key(key)
    return index is not None
  def add(self, key, value):
    if key in self:  # 上面实现的in操作符
      index = self._find_key(key)
      self._table[index].value = value
      return False  # 返回False 表示没有执行插入操作,执行的是更新操作
    else:
      index = self._find_slot_for_insert(key)
      self._table[index] = Slot(key, value) # 这两部可能会调用_slot_can_insert 函数,不管是哪种情况,EMPTY 或 是 UNUSEZD,都将这个节点声明为Slot类
      self.length += 1
      if self._load_factor >= 0.8:
        self._rehash()   # 当空间占用大于0.8 的时候,进行rehash 重新分配空间。
      return True
  def _rehash(self):
    old_table = self._table
    newsize = len(self._table) *2
    self._table = Array(newsize, HashTable.UNUSED)
    self.length = 0
    for slot in old_table:
      if slot is not HashTable.UNUSED and slot is not HashTable.EMPTY:  # 判断这个slot 是有值的
        index = self._find_slot_for_insert(slot.key)  # 找到一个可以插入的槽
        self._table[index] = slot
        self.length += 1
  def get(self, key, default = None):
    index = self._find_key(key)
    if index is None:
      return default
    else:
      return self._table[index].value
  def remove(self,key):
    index = self._find_key(key)
    if index is None:
      raise KeyError()
    value = self._table[index].value
    self.length -= 1
    self._table[index] = HashTable.EMPTY
    return value
  def __iter__(self):   # 遍历操作,python 字典默认遍历的是key,这里实现的也是遍历key
    for slot in self._table:
      if slot not in(HashTable.EMPTY, HashTable.UNUSED):
        yield slot.key
class DictADT(HashTable):

  def __setitem__(self, key, value):  # 设定给定键的值
    self.add(key, value)
  def __getitem__(self, key):   # 返回给定键的值
    if key not in self:
      raise KeyError()
    else:
      return self.get(key)
  def _iter_slot(self):
    for slot in self._table:
      if slot not in (HashTable.EMPTY, HashTable.UNUSED):
        yield slot
  def items(self):
    for slot in self._iter_slot():
      yield (slot.key, slot.value)
  def keys(self):
    for slot in self._iter_slot():
      yield slot.key
  def values(self):
    for slot in self._iter_slot():
      yield slot.value
def test_dict():
  import random
  d = DictADT()
  d['a'] = 1   # 这时候调用 __setitem__ 方法
  assert d['a'] == 1
  d.remove('a')
  l = list(range(30))
  random.suffle(l)  # 打乱l
  for i in l:
    d.add(i, i )
  for i in range(30):
    assert d.get(i) == i
  assert sorted (list(d.keys())) == sorted(l)

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • 用Python实现通过哈希算法检测图片重复的教程

    Iconfinder 是一个图标搜索引擎,为设计师.开发者和其他创意工作者提供精美图标,目前托管超过 34 万枚图标,是全球最大的付费图标库.用户也可以在 Iconfinder 的交易板块上传出售原创作品.每个月都有成千上万的图标上传到Iconfinder,同时也伴随而来大量的盗版图.Iconfinder 工程师 Silviu Tantos 在本文中提出一个新颖巧妙的图像查重技术,以杜绝盗版. 我们将在未来几周之内推出一个检测上传图标是否重复的功能.例如,如果用户下载了一个图标然后又试图通过上传

  • python修改字典键(key)的方法

    python字典中,值可任意更改:但键是唯一的,不支持直接修改.若真的需要修改字典中的键,可通过几种间接方式实现. 新建空白字典. info = {} 给字典添加键-值对. info["x"] = 1.5 info["y"] = 2 info 字典的键(key)不支持直接修改.如图,试图直接修改键会报错. info = {"x":1.5 ,"y":2} info["z"] = info("x&qu

  • python实现图像检索的三种(直方图/OpenCV/哈希法)

    简介: 本文介绍了图像检索的三种实现方式,均用python完成,其中前两种基于直方图比较,哈希法基于像素分布. 检索方式是:提前导入图片库作为检索范围,给出待检索的图片,将其与图片库中的图片进行比较,得出所有相似度后进行排序,从而检索结果为相似度由高到低的图片.由于工程中还包含Qt界面类.触发函数等其他部分,在该文档中只给出关键函数的代码. 开发系统:MacOS 实现方式:Qt + Python 方法一:自定义的直方图比较算法 a) 基本思路 遍历图片像素点,提取R\G\B值并进行对应的计数,得

  • Python 3 判断2个字典相同

    下面先给大家介绍下Python 3 判断2个字典相同的方法, Python自带的数据结构dict非常好用,之前不知道怎么比较2个字典是否相同,做法是一个一个key比较过去... 现在想到可以直接用==进行判断!!! a = dict(one=1, two=2, three=3) b = {'one': 1, 'two': 2, 'three': 3} c = dict(zip(['one', 'two', 'three'], [1, 2, 3])) d = dict([('two', 2), (

  • python将字典列表导出为Excel文件的方法

    将如下的字典列表内容导出为Excel表格文件形式: 关于上图字典列表的写入,请参考文章:https://www.jb51.net/article/169088.htm python将字典列表导出为Excel文件的方法,如下所示: 1.安装python官方Excel库------xlwt 直接在终端进行安装即可:pip install xlwt 安装完成后,在程序中引入xlwt的库 import xlwt 2将字典列表导出到excel文件中: import xlwt import pandas a

  • python实现哈希表

    复制代码 代码如下: #! /usr/bin/env python#coding=utf-8#实现哈希表(线性地址再散列) def ChangeKey(key,m,di):    key01=(key+di) % m    return key01 a=raw_input("Please entry the numbers:\n").split()m=len(a)dict01={}for i in a:    key=int(i)%m    if "%s"%key

  • python字典的遍历3种方法详解

    遍历字典: keys() .values() .items() 1. xxx.keys() : 返回字典的所有的key 返回一个序列,序列中保存有字典的所有的键 效果图: 代码: # keys() 该方法会返回字典的所有的key # 该方法会返回一个序列,序列中保存有字典的所有的键 d = {'name':'孙悟空','age':18,'gender':'男'} print(d.keys()) print() # 通过遍历keys()来获取所有的键 for k in d.keys() : pri

  • python 哈希表实现简单python字典代码实例

    这篇文章主要介绍了python 哈希表实现简单python字典代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 class Array(object): def __init__(self, size = 32, init = None): self._size = size self._items = [init] * size def __getitem__(self, index): return self._items[index

  • C语言基于哈希表实现通讯录

    本文为大家分享了C语言基于哈希表实现通讯录的具体代码,供大家参考,具体内容如下 1.需求分析 本演示程序用C语言编写,完成哈希表的生成,电话号码的插入.以及查找等功能. (1)按提示输入相应的联系人的相关资料: (2)以相应的输出形式输出所存储的的联系人的资料: (3)程序可以达到建立.添加.查找.打印的功能: (4)程序可以判断用户输入的非法数据并引导正确的输入. 2.概要设计 存储电话号码的记录时,若在存储位置和其关键字之间建立某种确定的对应关系使得每个关键字和存储结构中一个唯一的存储位置相

  • PHP哈希表实现算法原理解析

    在PHP内核中,其中一个很重要的数据结构就是HashTable.我们常用的数组,在内核中就是用HashTable来实现.那么,PHP的HashTable是怎么实现的呢?最近在看HashTable的数据结构,但是算法书籍里面没有具体的实现算法,刚好最近也在阅读PHP的源码,于是参考PHP的HashTable的实现,自己实现了一个简易版的HashTable,总结了一些心得,下面给大家分享一下. HashTable的介绍 哈希表是实现字典操作的一种有效数据结构. 定义 简单地说,HashTable(哈

  • Python使用smtp和pop简单收发邮件完整实例

    SMTP SMTP是发送邮件的协议,Python内置对SMTP的支持,可以发送纯文本邮件.HTML邮件以及带附件的邮件. Python对SMTP支持有smtplib和email两个模块,email负责构造邮件,smtplib负责发送邮件. pop 收取邮件就是编写一个MUA作为客户端,从MDA把邮件获取到用户的电脑或者手机上.收取邮件最常用的协议是POP协议,目前版本号是3,俗称POP3. Python内置一个poplib模块,实现了POP3协议,可以直接用来收邮件. 注意到POP3协议收取的不

  • python+pygame简单画板实现代码实例

    疑问:pygame已经过时了吗? 过没过时不知道,反正这玩意官方已经快四年没有更新了.用的人还是蛮多的(相对于其他同类项目),不过大家都是用来写写小东西玩一玩,没有人用这个做商业项目.pygame其实就是SDL的python绑定,SDL又是基于OpenGL,所以也有人用pygame+pyOpenGL做3D演示什么的.真的要写游戏的话pygame的封装比较底层,不太够用,很多东西都要自己实现(当然自由度也高).文档也不太好,好在前人留下了很多文章.拿来练手倒是很不错的选择,可以用来实践很多2D游戏

  • python使用beautifulsoup4爬取酷狗音乐代码实例

    这篇文章主要介绍了python使用beautifulsoup4爬取酷狗音乐代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 小编经常在网上听一些音乐但是有一些网站好多音乐都是付费下载的正好我会点爬虫技术,空闲时间写了一份,截止4月底没有问题的,会下载到当前目录,只要按照bs4库就好, 安装方法:pip install beautifulsoup4 完整代码如下:双击就能直接运行 from bs4 import BeautifulSoup

  • Python爬虫爬取煎蛋网图片代码实例

    这篇文章主要介绍了Python爬虫爬取煎蛋网图片代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 今天,试着爬取了煎蛋网的图片. 用到的包: urllib.request os 分别使用几个函数,来控制下载的图片的页数,获取图片的网页,获取网页页数以及保存图片到本地.过程简单清晰明了 直接上源代码: import urllib.request import os def url_open(url): req = urllib.reques

  • Python中join()函数多种操作代码实例

    这篇文章主要介绍了Python中join()函数多种操作代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 Python中有.join()和os.path.join()两个函数,具体作用如下: . join(): 连接字符串数组.将字符串.元组.列表中的元素以指定的字符(分隔符)连接生成一个新的字符串 os.path.join(): 将多个路径组合后返回 对序列进行操作(分别使用' ' .' - '与':'作为分隔符) a=['1aa','

  • Python爬取爱奇艺电影信息代码实例

    这篇文章主要介绍了Python爬取爱奇艺电影信息代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 一,使用库 1.requests 2.re 3.json 二,抓取html文件 def get_page(url): response = requests.get(url) if response.status_code == 200: return response.text return None 三,解析html文件 我们需要的电影信

  • Python编程实现线性回归和批量梯度下降法代码实例

    通过学习斯坦福公开课的线性规划和梯度下降,参考他人代码自己做了测试,写了个类以后有时间再去扩展,代码注释以后再加,作业好多: import numpy as np import matplotlib.pyplot as plt import random class dataMinning: datasets = [] labelsets = [] addressD = '' #Data folder addressL = '' #Label folder npDatasets = np.zer

随机推荐