您现在的位置是:首页 > 正文

数据结构与算法——21. 抽象数据类型:映射(Map)

2024-04-01 03:46:40阅读 4

一、抽象数据类型:映射(Map)

字典(Dict)是Python最有用的数据类型之一,可以保存key-vaule键值对,key可用于查询关联的数据值value。这种键值关联的方法称为“映射(Map)”。

ADT(抽象数据类型) Map的结构是键-值关联的无序集合,关键码具有唯一性,通过关键码可以唯一确定一个数据值。

二、实现ADT Map

使用字典的优势在于,给定关键码key,能够很快得到关联的数据值value。为了达到快速查找的目标,需要一个支持高效查找的ADT实现。可以采用列表数据结构加顺序查找或者二分查找。当然,更为合适的是使用前述的散列表来实现,这样查找可以达到最快 O ( 1 ) O(1) O(1)的性能。

下面,我们用一个HashTable类来实现ADT Map,该类包含了两个列表作为成
员:slot列表用于保存key、value列表用于保存数据项。在slots列表查找到一个key的位置以后,在values列表对应相同位置的数据项即为关联数据。

保存key的列表就作为散列表来处理,这样可以迅速查找到指定的key。注意散列表的大小,虽然可以是任意数,但考虑到要让冲突解决算法能有效工作(避免周期现象),应该选择为素数

python代码实现

class HashTable:
    def __init__(self):
        self.size = 11
        self.slots = [None] * self.size
        self.values = [None] * self.size

    def put(self, key, value):
        """添加键值对"""
        # 获取key的散列值
        hashvalue = self.hash_function(key, len(self.slots))

        # key不存在,没有冲突
        if self.slots[hashvalue] is None:
            self.slots[hashvalue] = key
            self.values[hashvalue] = value
        # key存在,出现冲突
        else:
            # key的值相同,替换value
            if self.slots[hashvalue] == key:
                self.values[hashvalue] = value
            # key的值不同,则寻找槽放置key
            else:
                # 再散列,直到找到空槽或相同的key
                next_slot = self.rehash(hashvalue, len(self.slots))
                while self.slots[next_slot] is not None and \
                        self.slots[next_slot] != key:
                    next_slot = self.rehash(next_slot, len(self.slots))

                # 找到槽后,如果为空,槽中放入key
                if self.slots[next_slot] is None:
                    self.slots[next_slot] = key
                    self.values[next_slot] = value
                # 槽不为空,说明与当前key相同
                else:
                    self.values[next_slot] = value

    def hash_function(self, key, size):
        """散列函数,采用简单求余方法"""
        return key % size

    def rehash(self, oldhash, size):
        """再散列函数,冲突解决则采用线性探测“加1” """
        return (oldhash + 1) % size

    def get(self, key):
        """获取键对应的值"""
        # 标记散列值为查找起始点
        start_slot = self.hash_function(key, len(self.slots))

        value = None
        stop = False
        found = False
        position = start_slot
        # 寻找key,直到遇到空槽或回到起点
        while self.slots[position] is not None and \
                not found and not stop:
            # 如果找到,将值保存下来
            if self.slots[position] == key:
                found = True
                value = self.values[position]
            # 没找到就继续找
            else:
                position = self.rehash(position, len(self.slots))
            # 如果回到起点,停止寻找
            if position == start_slot:
                stop = True
        return value

    # 通过重写魔法方法,实现[]操作
    def __getitem__(self, key):
        return self.get(key)

    # 通过重写魔法方法,实现[]操作
    def __setitem__(self, key, value):
        self.put(key, value)

三、散列算法分析

散列在最好的情况下,可以提供 O ( 1 ) O(1) O(1)常数级,时间复杂度的查找性能。由于散列冲突的存在,查找比较次数就没有这么简单。

评估散列冲突的最重要信息就是负载因子λ(槽被数据项占据的比例),一般来说:

  • 如果λ较小,散列冲突的几率就小,数据项通常会保存在其所属的散列槽中;
  • 如果λ较大,意味着散列表填充较满,冲突会越来越多,冲突解决也越复杂,也就需要更多的比较来找到空槽;如果采用数据链的话,意味着每条链上的数据项增多。

如果采用线性探测的开放定址法来解决冲突(λ在0~1之间):

  • 成功的查找,平均需要比对次数为: 1 2 ( 1 + 1 1 − λ ) \frac{1}{2}(1+\frac{1}{1-\lambda}) 21(1+1λ1)
  • 不成功的查找,平均比对次数为: 1 2 ( 1 + ( 1 1 − λ ) 2 ) \frac{1}{2}(1+(\frac{1}{1-\lambda})^2) 21(1+(1λ1)2)

如果采用数据链来解决冲突(λ可大于1):

  • 成功的查找,平均需要比对次数为: 1 + λ 2 1+\frac{\lambda}{2} 1+2λ
  • 不成功的查找,平均比对次数为: λ \lambda λ

网站文章

  • Linux数据恢复

    Linux数据恢复

    博客:https://silentx.gitee.io/一.概述此次是使用不同工具对不同Linux系统进行数据恢复环境准备:系统:centos7,Ubuntu20,kali2022软件:testdis...

    2024-04-01 03:46:32
  • spring boot视图html传参,spring boot 配置视图jsp

    spring boot视图html传参,spring boot 配置视图jsp

    image.png目录结构image.pngprom.xmlxsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">4.0.0com.exampledemo0.0.1-SNAPSHOTwardemoDemo project for Spring Boo...

    2024-04-01 03:45:53
  • 中序表达式转为后序表达式

    中序表达式转为后序表达式

    中序表达式计算以及中序表达式转为后序表达式。

    2024-04-01 03:45:47
  • 思维训练3

    思维训练3

    我们可以进行一个构造,题目要求在所有的区间中尽量使所有的素数结果最多我们可以将2和3放在两边,将1放在中间,这样中间的大部分经过了1,但是未到达两边的2,3区间都是有贡献的,或者经过了1,2,但是没经...

    2024-04-01 03:45:38
  • 腾讯 IMWEB 前端团队一站式 Serverless 开发解决方案

    腾讯 IMWEB 前端团队一站式 Serverless 开发解决方案

    IMWeb 团队隶属腾讯公司,是国内最专业的前端团队之一。 IMWeb 团队专注前端领域多年,负责过 QQ 资料、QQ 注册、QQ 群等亿级业务。目前聚焦于在线教育领域,精心打磨 腾讯课堂、企鹅辅导及...

    2024-04-01 03:45:32
  • react 应用中使用装饰器

    1. 在不eject的情况下,网友给出了一个修改node_modules的解决方案:找到node_modules/babel-preset-react-app/index.js,然后加入装饰器支持;接...

    2024-04-01 03:44:52
  • Mysql主从同步时Slave_IO_Running:Connecting ; Slave_SQL_Running:Yes的情况故障排除 热门推荐

    Mysql主从同步时Slave_IO_Running:Connecting ; Slave_SQL_Running:Yes的情况故障排除 热门推荐

    今天在测试主从服务器Mysql同步时遇到了从数据库显示Slave_IO_Running:Connecting的问题,下面列举几种可能的错误原因: 1.网络不通 2.账户密码错误 3.防火墙问题 4.m...

    2024-04-01 03:44:43
  • 严蔚敏数据结构C语言版教材精讲考研真题串讲视频

    本课程是严蔚敏《数据结构》(C语言版)网授精讲班,为了帮助参加研究生招生考试指定考研参考书目为严蔚敏《数据结构》(C语言版)的考生复习专业课,我们根据教材和名校考研真题的命题规律精心讲解教材章节内容。

    2024-04-01 03:44:35
  • 如何使用css实现三角形

    如何使用css实现三角形

    如何使用css实现三角形

    2024-04-01 03:43:56
  • 史上最详细Docker部署Mysql主从复制,带每一步骤图!!!

    史上最详细Docker部署Mysql主从复制,带每一步骤图!!!

    没有夸大标题哈,能够成功的,实测后发文????本文主要讲怎么用Docker部署Mysql的主从复制,看起来很长,实际非常简单的,看一遍,立马就能懂的。直接CV也能搭建起来,莫慌。我们一起加油!!!封面...

    2024-04-01 03:43:48