python字典相关操作的复杂度_字典查找的时间复杂度-程序员宅基地

最近对大量数据做处理时，耗时较大，后来通过改进用了字典，一定程度上提高了效率。
字典与列表的不同之处在于，可以通过键而不是位置来访问字典中的项。字典上的get item和set item操作是O（1）。另一个重要的字典操作是contains操作，即检查一个键是否在字典中也是O（1）。下图总结了所有字典操作的效率。该图中提供的效率是针对平均性能的。在一些罕见的情况下，contains、get item和set item操作可能会退化为O（n）性能。
在这里插入图片描述
字典相关操作的代码：

# dictionary 类似Map哈希表
d = {
    'cat': 'cute', 'dog': 'furry'}
print(d['cat'])
print('cat' in d)
d['fish'] = 'wet'
print(d['fish'])
# print(d['monkey'])  # KeyError: 'monkey' not a key of d
print(d.get('monkey', 'N/A'))
print(d.get('fish', 'N/A'))
del d['fish']
print(d.get('fish', 'N/A'))

d = {
    'person': 2, 'cat': 4, 'spider': 8}
for animal in d:
    legs = d[animal]
    print('A %s has %d legs' % (animal, legs))
    
d = {
    'person': 2, 'cat': 4, 'spider': 8}
for animal, legs in d.items():
    print('A %s has %d legs' % (animal, legs))
    
nums = [0, 1, 2, 3, 4]
even_num_to_square = {
    x: x ** 2 for x in nums if x % 2 == 0}
print(even_num_to_square)

使用python字典来进行查找的话速度非常快，是O(1)级别，因为是用hash实现的。
哈希表也叫散列表，可理解为借助哈希函数对数组这种数据结构进行扩展，利用的是数组支持按照下标随机访问元素的特性，是存储 Key-Value 键值对的集合。参考文章：知乎：什么是哈希表？
存放记录的哈希表结构如图所示（数组下标index与[key,value]键值对）：
在这里插入图片描述

关于哈希表的基本原理可简单理解为：当我们用字典当中的key去获取对应的value时，会将key转换为列表当中的index，通过index去准确快速地获取到value。这里面的关键在于哈希函数与冲突检测。
将key转化为index的函数就称为哈希函数，其中key既可以为数字，也可以为字符串，哈希函数通过计算模值或计算字符串哈希值得到对应的数组下标(存储地址)。可见，不需要遍历地址，而只通过一次计算即得到地址，从而方便取该地址存放的值，则在不冲突的理想情况下，时间复杂度为O(1)。总体来说，若设计好哈希函数减少冲突次数，则时间复杂度的平均性能为O(1)。
而在计算index的时候要注意冲突检测(例如多个key通过哈希函数后同时对应到同一index)，这时候主要通过index与其存放的key进行处理(可参考如下代码)。根据冲突检测的处理方法可以将检测方法分为开放寻址法和拉链法。
我们可以通过如下数组模拟散列表的问题进行理解，该问题实现了加入元素与判断元素是否存在的功能。通过计算得到要查找的key所对应的数组的下标k，并进行冲突检测(若有冲突，则k++)，从平均性能上来说，确实可以达到O(1)。这种冲突检测方法为开放寻址法，除此之外还有基于链表的拉链法。该问题中存放的是key，即仅存放不重复的元素，其实就类似于hashset。若加入value，每个数组位置存放一个键值对[key, value]，其实就类似于hashtable，key通常用来冲突检测与快速查找，而value用于存储对应于key的值。而hashtable与dictionary是较为相近的，具体区别之后再具体调研。
数组模拟散列表问题链接如下：
AcWing 840. 模拟散列表
该问题C++代码：

#include <cstring>
#include <iostream>

using namespace std;
// N为模数，null为空位置的初始值
// N通常取大于范围的质数，取质数冲突的概率最小
const int N = 2e5 + 3, null = 0x3f3f3f3f;

int h[N];

int find(int x) // 哈希函数：通过key得到对应的数组下标索引值(k)
{
    
    int k = ((x % N) + N) % N; // key->index(k)
    while(h[k] != null && h[k] != x) // 冲突检测
    {
    
        k ++;
        if(k == N) k = 0;
    }
    return k; // 返回地址
}

int main()
{
    
    int n;
    scanf("%d", &n);
    
    // 数组初始化为无穷大，无穷大表示不存放值
    memset(h, 0x3f, sizeof h); 
      
    while(n --)
    {
    
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        int k = find(x);
        if(*op == 'I') h[k] = x; // 插入元素
        else // 判断存在
        {
    
            if(h[k] != null) puts("Yes");
            else puts("No");
        }
    }
    
    return 0;
}

本文链接：https://blog.csdn.net/whq___/article/details/116244384

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

获取大于等于一个整数的最小2次幂算法（HashMap#tableSizeFor）_整数最小的2的几次方-程序员宅基地

文章浏览阅读2w次，点赞51次，收藏33次。一、需求给定一个整数，返回大于等于该整数的最小2次幂（2的乘方）。例：输入输出 -1 1 1 1 3 4 9 16 15 16二、分析当遇到这个需求的时候，我们可能会很容易想到一个"笨"办法：..._整数最小的2的几次方

Linux 中 ss 命令的使用实例_ss@,,x,, 0-程序员宅基地

文章浏览阅读865次。选项，以防止命令将 IP 地址解析为主机名。如果只想在命令的输出中显示 unix套接字连接，可以使用。不带任何选项，用来显示已建立连接的所有套接字的列表。如果只想在命令的输出中显示 tcp 连接，可以使用。如果只想在命令的输出中显示 udp 连接，可以使用。如果不想将ip地址解析为主机名称，可以使用。如果要取消命令输出中的标题行，可以使用。如果只想显示被侦听的套接字，可以使用。如果只想显示ipv4侦听的，可以使用。如果只想显示ipv6侦听的，可以使用。_ss@,,x,, 0

conda activate qiuqiu出现不存在activate_commandnotfounderror: 'activate-程序员宅基地

文章浏览阅读568次。CommandNotFoundError: 'activate'_commandnotfounderror: 'activate

Kafka 实战 - Windows10安装Kafka_win10安装部署kafka-程序员宅基地

文章浏览阅读426次，点赞10次，收藏19次。完成以上步骤后，您已在 Windows 10 上成功安装并验证了 Apache Kafka。在生产环境中，通常会将 Kafka 与外部 ZooKeeper 集群配合使用，并考虑配置安全、监控、持久化存储等高级特性。在生产者窗口中输入一些文本消息，然后按 Enter 发送。ZooKeeper 会在新窗口中运行。在另一个命令提示符窗口中，同样切换到 Kafka 的。Kafka 服务器将在新窗口中运行。在新的命令提示符窗口中，切换到 Kafka 的。，应显示已安装的 Java 版本信息。_win10安装部署kafka

【愚公系列】2023年12月 WEBGL专题-缓冲区对象_js 缓冲数据 new float32array-程序员宅基地

文章浏览阅读1.4w次。缓冲区对象（Buffer Object）是在OpenGL中用于存储和管理数据的一种机制。缓冲区对象可以存储各种类型的数据，例如顶点、纹理坐标、颜色等。在渲染过程中，缓冲区对象中存储的数据可以被复制到渲染管线的不同阶段中，例如顶点着色器、几何着色器和片段着色器等，以完成渲染操作。相比传统的CPU访问内存，缓冲区对象的数据存储和管理更加高效，能够提高OpenGL应用的性能表现。_js 缓冲数据 new float32array

四、数学建模之图与网络模型_图论与网络优化数学建模-程序员宅基地

文章浏览阅读912次。（1）图（Graph）：图是数学和计算机科学中的一个抽象概念，它由一组节点（顶点）和连接这些节点的边组成。图可以是有向的（有方向的，边有箭头表示方向）或无向的（没有方向的，边没有箭头表示方向）。图用于表示各种关系，如社交网络、电路、地图、组织结构等。（2）网络（Network）：网络是一个更广泛的概念，可以包括各种不同类型的连接元素，不仅仅是图中的节点和边。网络可以包括节点、边、连接线、路由器、服务器、通信协议等多种组成部分。网络的概念在各个领域都有应用，包括计算机网络、社交网络、电力网络、交通网络等。_图论与网络优化数学建模

随便推点

android 加载布局状态封装_adnroid加载数据转圈封装全屏转圈封装-程序员宅基地

文章浏览阅读1.5k次。我们经常会碰见正在加载中，加载出错， “暂无商品”等一系列的相似的布局，因为我们有很多请求网络数据的页面，我们不可能每一个页面都写几个“正在加载中”等布局吧，这时候将这些状态的布局封装在一起就很有必要了。我们可以将这些封装为一个自定布局，然后每次操作该自定义类的方法就行了。首先一般来说，从服务器拉去数据之前都是“正在加载”页面，加载成功之后“正在加载”页面消失，展示数据；如果加载失败，就展示_adnroid加载数据转圈封装全屏转圈封装

阿里云服务器（Alibaba Cloud Linux 3）安装部署Mysql8-程序员宅基地

文章浏览阅读1.6k次，点赞23次，收藏29次。PS: 如果执行sudo grep 'temporary password' /var/log/mysqld.log 后没有报错，也没有任何结果显示，说明默认密码为空，可以直接进行下一步（后面设置密码时直接填写新密码就行）。3.（可选）当操作系统为Alibaba Cloud Linux 3时，执行如下命令，安装MySQL所需的库文件。下面示例中，将创建新的MySQL账号，用于远程访问MySQL。2.依次运行以下命令，创建远程登录MySQL的账号，并允许远程主机使用该账号访问MySQL。_alibaba cloud linux 3