Python字典的底层实现

2023-02-26 19:25:02Python06

Python字典的底层实现,第1张

字典是一种可变、无序容器数据结构。元素以键值对存在，键值唯一。它的特点搜索速度很快：数据量增加10000倍，搜索时间增加不到2倍；当数据量很大的时候，字典的搜索速度要比列表快成百上千倍。

在Python中，字典是通过散列表（哈希表）实现的。字典也叫哈希数组或关联数组，所以其本质是数组（如下图），每个 bucket 有两部分：一个是键对象的引用，一个是值对象的引用。所有 bucket 结构和大小一致，我们可以通过偏移量来读取指定 bucket。

定义一个字典 dic = {}，假设其哈希数组长度为8。

Python会根据哈希数组的拥挤程度对其扩容。“扩容”指的是:创造更大的数组，这时候会对已经存在的键值对重新进行哈希取余运算保存到其它位置；一般接近 2/3 时，数组就会扩容。扩容后，偏移量的数字个数增加，如数组长度扩容到16时，可以用最右边4位数字作为偏移量。

计算键对象 name 的哈希值，然后比较哈希数组对应索引内的bucket是否为空，为空返回 None ，否则计算这个bucket的键对象的哈希值，然后与 name 哈希值比较，相等则返回值对象，否则继续左移计算哈希值。

注意：

1.键必须为可哈希的，如数字、元组、字符串；自定义对象需要满足支持hash、支持通过 __eq__() 方法检测相等性、若 a == b 为真，则 hash(a) == hash(b) 也为真。

2.字典的内存开销很大，以空间换时间。

3.键查询速度很快，列表查询是按顺序一个个遍历，字典则是一步到位。

4.往字典里面添加新键可能导致扩容，导致哈希数组中键的次序变化。因此，不要在遍历字典的同时进行字典的修改。

变量是保存存储值的内存位置。也就是说，当创建一个变量时，可以在内存中保留一些空间。

基于变量的数据类型，解释器分配内存并决定可以存储在保留的存储器中的内容。因此，通过为变量分配不同的数据类型，可以在这些变量中存储的数据类型为整数，小数或字符等等。

将值分配给变量

在Python中，变量不需要明确的声明类型来保留内存空间。当向变量分配值时，Python会自动发出声明。等号(=)用于为变量赋值。

=运算符左侧的操作数是变量的名称，而=运算符右侧的操作数是将在存储在变量中的值。例如 -

#!/usr/bin/python3counter = 100 # 一个整型数miles = 999.99 # 一个浮点数name = "Maxsu" # 一个字符串site_url = "http://www.yiibai.com" # 一个字符串print (counter)print (miles)print (name)print (site_url)Python

这里，100,999.99和“Maxsu”分别是分配给counter，miles和name变量的值。执行上面代码将产生以下结果 -

100

999.99

Maxsu

http://www.yiibai.comShell

多重赋值

Python允许同时为多个变量分配单个值。

例如 -

a = b = c = 1Python

这里，创建一个整数对象，其值为1，并且所有三个变量都分配给相同的内存位置。还可以将多个对象分配给多个变量。例如 -

a, b, c = 10, 20, "maxsu"Python

这里，将两个值为10和20的整数对象分别分配给变量a和b，并将一个值为“maxsu”的字符串对象分配给变量c。

标准数据类型

存储在内存中的数据可以是多种类型。例如，一个人的年龄可存储为一个数字值，他的地址被存储为字母数字字符串。 Python具有各种标准数据类型，用于定义可能的操作以及每个标准数据类型的存储方法。

Python有五种标准数据类型 -

1.数字

2.字符串

3.列表

4.元组

5.字典

1.Python数字

数字数据类型存储数字值。当为其分配值时，将创建数字对象。例如 -

var1 = 10var2 = 20Python

可以使用del语句删除对数字对象的引用。 del语句的语法是 -

del var1[,var2[,var3[....,varN]]]]Python

可以使用del语句删除单个对象或多个对象。

例如 -

del vardel var_a, var_bPython

Python支持三种不同的数值类型 -

int(有符号整数)

float(浮点实值)

complex(复数)

Python3中的所有整数都表示为长整数。因此，长整数没有单独的数字类型。

例子

以下是一些数字示例 -

int

float

complex

10 0.0 3.14j

100 15.20 45.j

-786 -21.9 9.322e-36j

080 32.3+e18 .876j

-0490 -90. -.6545+0J

-0x260 -32.54e100 3e+26J

0x69 70.2-E12 4.53e-7j

复数是由x + yj表示的有序对的实数浮点数组成，其中x和y是实数，j是虚数单位。

2.Python字符串

Python中的字符串被标识为在引号中表示的连续字符集。Python允许双引号或双引号。可以使用片段运算符([]和[:])来获取字符串的子集(子字符串)，其索引从字符串开始处的索引0开始，并且以-1表示字符串中的最后一个字符。

加号(+)是字符串连接运算符，星号(*)是重复运算符。例如 -

#!/usr/bin/python3#coding=utf-8# save file: variable_types_str1.pystr = 'yiibai.com'print ('str = ', str) # Prints complete stringprint ('str[0] = ',str[0]) # Prints first character of the stringprint ('str[2:5] = ',str[2:5]) # Prints characters starting from 3rd to 5thprint ('str[2:] = ',str[2:]) # Prints string starting from 3rd characterprint ('str[-1] = ',str[-1]) # 最后一个字符，结果为：'!'print ('str * 2 = ',str * 2) # Prints string two timesprint ('str + "TEST" = ',str + "TEST") # Prints concatenated stringPython

将上面代码保存到 variable_types_str1.py 文件中，执行将产生以下结果 -

F:\worksp\python>python variable_types_str1.py

str = yiibai.com

str[0] = y

str[2:5] = iba

str[2:] = ibai.com

str[-1] = m

str * 2 = yiibai.comyiibai.com

str + "TEST" = yiibai.comTEST

F:\worksp\python>Shell

2.Python列表

列表是Python复合数据类型中最多功能的。一个列表包含用逗号分隔并括在方括号([])中的项目。在某种程度上，列表类似于C语言中的数组。它们之间的区别之一是Python列表的所有项可以是不同的数据类型，而C语言中的数组只能是同种类型。

存储在列表中的值可以使用切片运算符([]和[])来访问，索引从列表开头的0开始，并且以-1表示列表中的最后一个项目。加号(+)是列表连接运算符，星号(*)是重复运算符。例如 -

#!/usr/bin/python3#coding=utf-8# save file: variable_types_str1.pylist = [ 'yes', 'no', 786 , 2.23, 'minsu', 70.2 ]tinylist = [100, 'maxsu']print ('list = ', list) # Prints complete listprint ('list[0] = ',list[0]) # Prints first element of the listprint ('list[1:3] = ',list[1:3]) # Prints elements starting from 2nd till 3rd print ('list[2:] = ',list[2:]) # Prints elements starting from 3rd elementprint ('list[-3:-1] = ',list[-3:-1]) print ('tinylist * 2 = ',tinylist * 2) # Prints list two timesprint ('list + tinylist = ', list + tinylist) # Prints concatenated listsPython

将上面代码保存到 variable_types_str1.py 文件中，执行将产生以下结果 -

F:\worksp\python>python variable_types_list.py

list = ['yes', 'no', 786, 2.23, 'minsu', 70.2]

list[0] = yes

list[1:3] = ['no', 786]

list[2:] = [786, 2.23, 'minsu', 70.2]

list[-3:-1] = [2.23, 'minsu']

tinylist * 2 = [100, 'maxsu', 100, 'maxsu']

list + tinylist = ['yes', 'no', 786, 2.23, 'minsu', 70.2, 100, 'maxsu']

F:\worksp\python>Shell

3.Python元组

元组是与列表非常类似的另一个序列数据类型。元组是由多个值以逗号分隔。然而，与列表不同，元组被括在小括号内(())。

列表和元组之间的主要区别是 - 列表括在括号([])中，列表中的元素和大小可以更改，而元组括在括号(())中，无法更新。元组可以被认为是只读列表。例如 -

#!/usr/bin/python3#coding=utf-8# save file : variable_types_tuple.pytuple = ( 'maxsu', 786 , 2.23, 'yiibai', 70.2 )tinytuple = (999.0, 'maxsu')# tuple[1] = 'new item value' 不能这样赋值print ('tuple = ', tuple) # Prints complete tupleprint ('tuple[0] = ', tuple[0]) # Prints first element of the tupleprint ('tuple[1:3] = ', tuple[1:3]) # Prints elements starting from 2nd till 3rd print ('tuple[-3:-1] = ', tuple[-3:-1]) # 输出结果是什么？print ('tuple[2:] = ', tuple[2:]) # Prints elements starting from 3rd elementprint ('tinytuple * 2 = ',tinytuple * 2) # Prints tuple two timesprint ('tuple + tinytuple = ', tuple + tinytuple) # Prints concatenated tuplePython

将上面代码保存到 variable_types_tuple.py 文件中，执行将产生以下结果 -

F:\worksp\python>python variable_types_tuple.py

tuple = ('maxsu', 786, 2.23, 'yiibai', 70.2)

tuple[0] = maxsu

tuple[1:3] = (786, 2.23)

tuple[-3:-1] = (2.23, 'yiibai')

tuple[2:] = (2.23, 'yiibai', 70.2)

tinytuple * 2 = (999.0, 'maxsu', 999.0, 'maxsu')

tuple + tinytuple = ('maxsu', 786, 2.23, 'yiibai', 70.2, 999.0, 'maxsu')

F:\worksp\python>Shell

以下代码对于元组无效，因为尝试更新元组，但是元组是不允许更新的。类似的情况可能与列表 -

#!/usr/bin/python3tuple = ( 'abcd', 786 , 2.23, 'john', 70.2 )list = [ 'abcd', 786 , 2.23, 'john', 70.2 ]tuple[2] = 1000 # 无法更新值，程序出错list[2] = 1000 # 有效的更新，合法Python

Python字典

Python的字典是一种哈希表类型。它们像Perl中发现的关联数组或散列一样工作，由键值对组成。字典键几乎可以是任何Python数据类型，但通常为了方便使用数字或字符串。另一方面，值可以是任意任意的Python对象。

字典由大括号({})括起来，可以使用方括号([])分配和访问值。例如 -

#!/usr/bin/python3#coding=utf-8# save file : variable_types_dict.pydict = {}dict['one'] = "This is one"dict[2] = "This is my"tinydict = {'name': 'maxsu', 'code' : 1024, 'dept':'IT Dev'}print ("dict['one'] = ", dict['one']) # Prints value for 'one' keyprint ('dict[2] = ', dict[2]) # Prints value for 2 keyprint ('tinydict = ', tinydict) # Prints complete dictionaryprint ('tinydict.keys() = ', tinydict.keys()) # Prints all the keysprint ('tinydict.values() = ', tinydict.values()) # Prints all the valuesPython

将上面代码保存到 variable_types_dict.py 文件中，执行将产生以下结果 -

F:\worksp\python>python variable_types_dict.py

dict['one'] = This is one

dict[2] = This is my

tinydict = {'name': 'maxsu', 'code': 1024, 'dept': 'IT Dev'}

tinydict.keys() = dict_keys(['name', 'code', 'dept'])

tinydict.values() = dict_values(['maxsu', 1024, 'IT Dev'])Shell

字典中的元素没有顺序的概念。但是说这些元素是“乱序”是不正确的它们是无序的。

数据类型转换

有时，可能需要在内置类型之间执行转换。要在类型之间进行转换，只需使用类型名称作为函数即可。

有以下几种内置函数用于执行从一种数据类型到另一种数据类型的转换。这些函数返回一个表示转换值的新对象。它们分别如下所示 -

编号