当前位置： 首页 > 编程日记 > 正文

【Python】12、字典的实现

编程日记 2024-09-25 06:20:00

一、字典的实现

dic 可以使用list来实现 

i（索引） = hash(key) % solt(槽位数)

此时i重复了怎么办（hash冲突）？


1、拉链法

 每个槽位上拉一个List，就是拉链法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
In [6]: solts = []        # 初始化一个list
In [7]: solts_num = 32    # 假设32个槽位
In [8]: for _ in range(solts_num):
   ...:     solts.append([])
   ...:     
In [9]: solts            # 每个槽位上都是一个list
Out[9]: 
[[],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 []]
 
## 定义dict的put方法 
In [10]: def put(solts, key, value):
    ...:     i = hash(key) % solts_num
    ...:     solts[i].append((key, value))
    ...:     
    
## 定义dict的get方法
In [12]: def get(solts, key):
    ...:     i = hash(key) % solts_num
    ...:     for k, v in solts[i]:
    ...:         if k == key:
    ...:             return v
    ...:     raise KeyError(key)
    ...: 
    
    
## 测试
In [23]: put(solts, 'a', 1)
In [24]: solts
Out[24]: 
[[('a', 1)],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 []]
In [25]: put(solts, 'b', 2)
In [26]: put(solts, 'f', 9)
In [27]: solts
Out[27]: 
[[('a', 1)],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [('f', 9)],
 [],
 [('b', 2)],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 []]
In [28]: get(solts, 'b')
Out[28]: 2
In [29]: get(solts, 'f')
Out[29]: 9
In [107]: get(solts, 'x')
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-107-bdc41302b4b3> in <module>()
----> 1 get(solts, 'x')
<ipython-input-100-31c1edecb2ae> in get(solts, key)
      4         if k == key:
      5             return v
----> 6     raise KeyError(key)
      7 
KeyError: 'x'

 

此时put一个已存在的key时：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
In [33]: put(solts, 'a', 11)
In [34]: solts
Out[34]: 
[[('a', 1), ('a', 11)],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [('f', 9)],
 [],
 [('b', 2)],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 []]
 
In [35]: get(solts, 'a')
Out[35]: 1


重新定put方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
In [87]: def put(solts, key, value):
    ...:     i = hash(key) % solts_num
    ...:     for p, (k, v) in enumerate(solts[i]):
    ...:         if k == key:
    ...:             solts[i][p] = (key, value)
    ...:     else:
    ...:         solts[i].append((key, value))
    
    
In [89]: solts
Out[89]: []
In [90]: for _ in range(solts_num):
    ...:     solts.append([])
    ...:     
In [92]: put(solts, 'a', 1)
In [94]: put(solts, 'b', 2)
In [95]: put(solts, 'f', 8)
In [96]: solts
Out[96]: 
[[('a', 1)],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [('f', 8)],
 [],
 [('b', 2)],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 []]
 
 
In [101]: get(solts, 'b')
Out[101]: 2
In [102]: get(solts, 'f')
Out[102]: 8
In [103]: get(solts, 'a')
Out[103]: 11
In [104]: put(solts, 'b', 22)
In [105]: get(solts, 'b')
Out[105]: 22
In [106]: solts
Out[106]: 
[[('a', 11), ('a', 11)],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [('f', 8)],
 [],
 [('b', 22), ('b', 22)],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 [],
 []]
In [107]: get(solts, 'x')
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-107-bdc41302b4b3> in <module>()
----> 1 get(solts, 'x')
<ipython-input-100-31c1edecb2ae> in get (solts, key)
      4         if k == key:
      5             return v
----> 6     raise KeyError(key)
      7 
KeyError: 'x'

    set在底层的实现就是一个忽略了value的dict


2、开地址法

使用某个算法重新计算i，就交开地址法

常用，效率更高，

i = fn(key, i)


待后续学习
























本文转自xiexiaojun51CTO博客，原文链接：http://blog.51cto.com/xiexiaojun/1933230 ，如需转载请自行联系原作者




https://www.dkcj.cn/info/20234.html

相关文章：

Numpy入门教程：03.数组操作

背景 什么是 NumPy 呢&#xff1f; NumPy 这个词来源于两个单词 – Numerical和Python。其是一个功能强大的 Python 库&#xff0c;可以帮助程序员轻松地进行数值计算&#xff0c;通常应用于以下场景&#xff1a; 执行各种数学任务&#xff0c;如&#xff1a;数值积分、微分、…

编程日记2024/09/25 06:10:00

13个JavaScript图表图形绘制插件

由于绘制矢量图的不同技术愈发成熟以及现代浏览器所具备的更强大的计算能力等原因&#xff0c;目前网上出现了越来越多免费 的JavaScript图表和图形绘制解决方案。在本文中就将分享13个优秀实用的JavaScript图表和图形绘制插件&#xff0c;它们少数是独立的框架&#xff0c;大多…

编程日记2024/09/25 06:00:00

Java swing是什么?有什么作用?

在早期JDK1.0发布时&#xff0c;Sun公司就为GUI开发提供了一套基础类库&#xff0c;这套类库被称为AWT(Abstract Window Toolkit)&#xff0c;即抽象窗口工具包。AWT的起初设想就是为了统一实现不同操作系统的图像界面&#xff0c;但问题是&#xff0c;不同操作系统图形库的功能…

编程日记2024/09/25 05:50:00

python之网络爬虫

一、演绎自已的北爱 踏上北漂的航班&#xff0c;开始演奏了我自已的北京爱情故事 二、爬虫1 1、网络爬虫的思路 首先&#xff1a;指定一个url&#xff0c;然后打开这个url地址&#xff0c;读其中的内容。 其次&#xff1a;从读取的内容中过滤关键字&#xff1b;这一步是关键&a…

编程日记2024/09/25 05:40:00

Numpy入门教程：04. 数学函数

背景 什么是 NumPy 呢&#xff1f; NumPy 这个词来源于两个单词 – Numerical和Python。其是一个功能强大的 Python 库&#xff0c;可以帮助程序员轻松地进行数值计算&#xff0c;通常应用于以下场景&#xff1a; 执行各种数学任务&#xff0c;如&#xff1a;数值积分、微分、…

编程日记2024/09/25 05:30:00

SAXParserFactory之求解

SAX是Simple API for XML的简称,在Android里面提供对XML文件的解析接口方法&#xff0c;如果给我们一个XML文件&#xff0c;要求把里面我们关心的数据解析出来&#xff0c;我们就可以使用SAX技术&#xff0c;在具体使用中&#xff0c;会对XML文件的每一个字符逐一读取并出发相应…

编程日记2024/09/25 05:20:00

学习Java知识应该注意哪些基础原则

想要做java程序猿&#xff0c;学习起来没有那么快的&#xff0c;尤其是零基础学员&#xff0c;java技术在学习的过程中是比较枯燥的&#xff0c;下面小编就为大家详细的介绍一下学习Java知识应该注意哪些基础原则&#xff0c;方便大家在学习的时候能够更加有效率! 学习Java知识…

编程日记2024/09/25 05:10:00

Numpy入门教程：05. 逻辑函数

背景 什么是 NumPy 呢&#xff1f; NumPy 这个词来源于两个单词 – Numerical和Python。其是一个功能强大的 Python 库&#xff0c;可以帮助程序员轻松地进行数值计算&#xff0c;通常应用于以下场景&#xff1a; 执行各种数学任务&#xff0c;如&#xff1a;数值积分、微分、…

编程日记2024/09/25 05:00:00

git获取指定release版本代码

首先手里必须有release的版本的备份出来的/.repo/manifests/default.xml文件&#xff0c;该文件记录了每个git库的在该版本下的具体的版本情况&#xff0c;整个代码的sync都是依据他来的&#xff1b; 1、repo sync 将本地代码更新至最新&#xff1b; 2、将手里的manifests.xml&…

编程日记2024/09/25 04:50:00

【内网福音】如何离线部署Rancher

2019独角兽企业重金招聘Python工程师标准>>> 对于在公司内网环境中、无法访问互联网的用户而言&#xff0c;离线安装部署Rancher是解决问题的关键。本文是Rancher离线部署教程&#xff0c;专为内网用户排坑解难。 版本说明 OS&#xff1a;Centos7.3 Docker version:…

编程日记2024/09/25 04:40:00

JAVA工资高吗

JAVA工资高吗?很多人都是非常关注这个问题的&#xff0c;近几年&#xff0c;java技术在互联网行业有了自己的一席之地&#xff0c;越来越多的人都投身到java技术行业&#xff0c;下面我们来看看详细的介绍。 JAVA工资高吗? 近年来,在美国、加拿大、澳大利亚、新加坡等发达国家…

编程日记2024/09/25 04:30:00

Numpy入门教程：06. 排序，搜索和计数

背景 什么是 NumPy 呢&#xff1f; NumPy 这个词来源于两个单词 – Numerical和Python。其是一个功能强大的 Python 库&#xff0c;可以帮助程序员轻松地进行数值计算&#xff0c;通常应用于以下场景&#xff1a; 执行各种数学任务&#xff0c;如&#xff1a;数值积分、微分、…

编程日记2024/09/25 04:20:00

活动目录在构建核心过程中的八个关键点（下）

活动目录是一个面向Windows Server级别的目录服务。在之前的博客文章中介绍了活动目录设计中需要遵循的七个原则&#xff0c;今天在这里讲解有关《活动目录构建核心关键点》。 全文请见专题&#xff1a;http://os.51cto.com/art/201104/254054.htm 5. LDAP协议简介 LDAP的英文全…

编程日记2024/09/25 04:10:00

smarty变量调节器--count_words[计算词数]

计算变量里的词数 。 Example 5-7. count_words <?php$smarty->assign(articleTitle, Dealers Will Hear Car Talk at Noon.);?>Where template is:{$articleTitle}{$articleTitle|count_words}This will output:Dealers Will Hear Car Talk at Noon.7 See also cou…

编程日记2024/09/25 04:00:00

如何开发属于自己的第一个Java程序

学习java技术都是循序渐进的&#xff0c;搭建好了Java开发环境之后&#xff0c;下面就来学习一下如何开发Java程序。为了让初学者更好地完成第一个Java程序&#xff0c;接下来小编通过几个步骤进行逐一讲解。 1.编写Java源文件 在D盘根目录下新建一个test文件夹&#xff0c;并在…

编程日记2024/09/25 03:50:00

Numpy入门教程：07. 随机抽样

背景 什么是 NumPy 呢&#xff1f; NumPy 这个词来源于两个单词 – Numerical和Python。其是一个功能强大的 Python 库&#xff0c;可以帮助程序员轻松地进行数值计算&#xff0c;通常应用于以下场景&#xff1a; 执行各种数学任务&#xff0c;如&#xff1a;数值积分、微分、…

编程日记2024/09/25 03:40:00

如何成为一个Android高手

很多Android开发者已经度过了初级、中级&#xff0c;如何成为一个Android高手呢&#xff1f; eoeAndroid就各个级别的程序员应该掌握哪些内容作为下面分类. 一、初级 1. 拥有娴熟的Java基础&#xff0c;理解设计模式&#xff0c;比如OOP语言的工厂模式要懂得. 2. 掌握Android U…

编程日记2024/09/25 03:30:00

云终端处理器——Atom

由于上周展会的缘故&#xff0c;开始对云终端【I】处理器产生兴趣&#xff0c;接下来在“物理层”【II】来理解下X86-Atom&#xff0c;ARM&#xff0c;MIPS三种处理器&#xff0c;这是第一篇&#xff0c;主Atom Intel公司的官网简单介绍了一句 “英特尔 凌动【III】 处理器&am…

编程日记2024/09/25 03:20:00

Java培训的学费标准是多少

​ 很多想要进入到互联网行业的小伙伴都会选择java这门编程语言&#xff0c;java编程语言技术在互联网公司是起着非常重要的作用的&#xff0c;那么如今市面上的java培训机构有很多&#xff0c;选择报Java培训的学费标准是多少呢?来看看下面的详细介绍。 ​　　Java培训的学费…

编程日记2024/09/25 03:10:00

Numpy入门教程：08. 集合操作

背景 什么是 NumPy 呢&#xff1f; NumPy 这个词来源于两个单词 – Numerical和Python。其是一个功能强大的 Python 库&#xff0c;可以帮助程序员轻松地进行数值计算&#xff0c;通常应用于以下场景&#xff1a; 执行各种数学任务&#xff0c;如&#xff1a;数值积分、微分、…

编程日记2024/09/25 03:00:00

iPhone开发技巧之工具篇（4）--- 使用afconvert转换WAV文件

转载自&#xff1a;http://www.yifeiyang.net/iphone-development-skills-of-tool-papers-4-wav-file-conversion-using-afconvert/ 程序中经常使用 .WAV 的音效文件&#xff0c;虽然可以直接使用它&#xff0c;但是最好转换为 apple 推荐的 .CAF 格式。 这个时候我们就可以使用…

编程日记2024/09/25 02:50:00

SQLite与pandas

以下链接对SQLite使用方法总结的很棒&#xff1a; http://www.cnblogs.com/yuxc/archive/2011/08/18/2143606.html 有关利用pandas读写QSLite的内容&#xff0c;可参考以下链接&#xff1a; http://pandas.pydata.org/pandas-docs/stable/generated/pandas.read_sql.html http:…

编程日记2024/09/25 02:40:00

零基础学习java，这些书一定要看!

学习java技术除了看视频&#xff0c;看书也是非常重要的&#xff0c;尤其是零基础同学&#xff0c;本文包含学习Java各个阶段的书籍推荐&#xff0c;史上最全&#xff0c;学习Java&#xff0c;没有书籍怎么行&#xff0c;就好比出征没带兵器一个道理&#xff0c;这些书籍整理出…

编程日记2024/09/25 02:30:00

Numpy入门教程：练习作业01

序言 什么是 NumPy 呢&#xff1f; NumPy 这个词来源于两个单词 – Numerical和Python。其是一个功能强大的 Python 库&#xff0c;可以帮助程序员轻松地进行数值计算&#xff0c;通常应用于以下场景&#xff1a; 执行各种数学任务&#xff0c;如&#xff1a;数值积分、微分、…

编程日记2024/09/25 02:20:00

转乱码UTF8和UTF-8网页编码

http://www.lovelucy.info/utf8-vs-utf-8.html#more-794 一、遇到的问题 曾经被字符集间复杂的转换搞怕了&#xff0c;正好新项目要求国际化&#xff0c;需要能够显示多种语言&#xff0c;于是一开始就规定统统使用 UTF-8 编码。 所有代码文件使用 UTF-8 编码存盘MySQL数据库所…

编程日记2024/09/25 02:10:00

linux管道的执行顺序

最近有个疑问&#xff0c;netstat -antup|head -500 类似这条命令中&#xff0c;是netstat 执行完然后截取前500条记录还是&#xff0c;netstat 与head 并行执行&#xff0c;netstat 执行完500条就不再继续&#xff1f; 最终答案由酷学园darkdanger大大提供&#xff1a; 唔…

编程日记2024/09/25 02:00:00

为什么学习Python数据分析

为什么学习Python数据分析?这是很多人都比较关注的一个问题&#xff0c;Python编程语言近几年在互联网行业是非常火爆的&#xff0c;尤其是在人工智能这一领域&#xff0c;它会大大的提高我们的工作效率等等&#xff0c;具体来看看下面的详细介绍就知道了。 为什么学习Python数…

编程日记2024/09/25 01:50:00

Python自动化开发学习6

引子 假设我们要在我们的程序里表示狗&#xff0c;狗有如下属性&#xff1a;名字、品种、颜色。那么可以先定义一个模板&#xff0c;然后调用这个模板生成各种狗。 def dog(name,d_type,color):data {name:name,d_type:d_type,color:color}return data d1 dog(小七,拉布拉多,…

编程日记2024/09/25 01:40:00

Numpy入门教程：09. 输入和输出

背景 什么是 NumPy 呢&#xff1f; NumPy 这个词来源于两个单词 – Numerical和Python。其是一个功能强大的 Python 库&#xff0c;可以帮助程序员轻松地进行数值计算&#xff0c;通常应用于以下场景&#xff1a; 执行各种数学任务&#xff0c;如&#xff1a;数值积分、微分、…

编程日记2024/09/25 01:30:00

第二语言综合征

前些天在看一本书&#xff0c;温伯格的《理解专业程序员》&#xff0c;其中提到有的程序员得了第二语言综合征——在学习第三、第四门语言的时候很容易&#xff0c;但是学习第二门简直能要了他们的命。我当时就确定我患了这个毛病&#xff0c;因为我一直想了解Java语言&#xf…

编程日记2024/09/25 01:20:00