化工网站建设/sem是什么意思职业

python通过散列表来实现dict类型。理解python如何实现dict的原理之后，我们就可以自己来实现python的字典了,实现之前， 先了解一下相关的基本概念。

基本概念了解

可散列的数据类型

如果一个对象是可以散列的，那么在这个对象的生命周期内，他的散列值是不变的，而且这个对象实现了__hash__方法。可散列 对象还需要实现了__eq__方法，这样才能和其它的对象进行比较。如果两个可散列对象是相等的，那么他们的散列值一定是相等的。

散列表

散列表其实是一个稀疏数组(总是存在空白元素的数组), 散列表里的单元称作为表元。在dict的散列表中每个键值对占用一个表元 每个表元都有两个部分，一个是对键的引用，一个是对值的引用。

散列表的算法

a[key]获取逻辑

计算hash(key)获取 key的散列值

根据散列值获取偏移量

根据偏移量获取散列表的表元

如果表元为空，抛出keyerror异常。

如果表元不为空，判断表元存的key和获取的key是否相等。

如果相等， 返回表元中存的value。

如果不相等，存在冲突。通过特殊方法获取新的偏移量,重复执行第三步直到结束

a[key]=value的逻辑

计算hash(key)获取key的值散列值

根据散列值获取偏移量

根据偏移量获取散列表的表元 － 如果表元的引用为空，将表元的key设置为a[key]的key, 表元的value设置成 value

如果表元不为空，判断表元中的key和a[key]的key是否相等

如果相等，将表元的value设置成新的value

如果不相等，通过特殊方法获取新的偏移量，重复执行第三步直到结束

del a[key]的逻辑类似，不再赘述。

当散列表过于拥挤的时候，python解释器都可能为字典作出扩容的决定。会产生一个更大的散列表，把已有的数据添加进去。

自定义字典的实现

有了上述的了解之后，我们就可以自己实现了python的字典了。具体代码如下

from typing import Dict

class Node(object):

__slots__ = ("key", "value", "status")

__status_choices__ = ("Active", "Deleted")

def __init__(self, key=None, value=None, status=None):

self.key = key

self.value = value

self.status = status or "Active"

def reset(self):

self.status = "Deleted"

@property

def is_active(self):

return self.status == "Active"

@property

def is_deleted(self):

return self.status == "Deleted"

@is_active.setter

def is_active(self, value):

if value is True:

self.status = "Active"

elif value is False:

self.status = "Deleted"

else:

raise Exception("参数错误")

class CustomDict(object):

nodes_count = 10

used_nodes = 0

def __init__(self, data: Dict = None):

self._array = self._init(self.nodes_count)

if data:

assert isinstance(data, dict)

for key, value in data.items():

self[key] = value

def _init(self, count):

return [Node(status="Deleted") for x in range(count)]

def __setitem__(self, key, value):

hash_str = key

while True:

hash_str = str(self.hash(hash_str))

position = int(hash_str[:self.digit])

node = self._array[position]

if node.key is None or node.key == key or node.is_deleted:

node.key = key

node.value = value

node.is_active = True

self.used_nodes += 1

if self._need_expansion:

print('need expansion')

self._expansion()

break

else:

print("hash conflict")

def __delitem__(self, key):

hash_str = key

while True:

hash_str = str(self.hash(hash_str))

position = int(hash_str[:self.digit])

node = self._array[position]

if node.key is None or (node.key == key and node.is_deleted):

# node为空

raise KeyError(key)

elif node.key == key and node.is_active:

# key相等

self.used_nodes -= 1

node.reset()

break

else:

print("hash conflict")

def __getitem__(self, item):

hash_str = item

while True:

hash_str = str(self.hash(hash_str))

position = int(hash_str[:self.digit])

node = self._array[position]

if node.key is None:

# node为空

raise KeyError(item)

elif node.key == item and node.is_active:

# key相等

return node.value

@property

def digit(self):

return len(str(self.nodes_count // 3))

def hash(self, key):

return abs(hash(key))

@property

def _need_expansion(self):

return self.used_nodes * 2 > self.nodes_count

def _expansion(self):

self.nodes_count *= 10

self._array, old_array = self._init(self.nodes_count), self._array

for node in old_array:

if node.is_active:

print(node.key, node.value)

self[node.key] = node.value

def items(self):

for node in self._array:

if node.is_active:

yield node.key, node.value

def keys(self):

return [x.key for x in self._array if x.is_active]

def values(self):

return [x.value for x in self._array if x.is_active]

def __len__(self):

return len(self.keys())

复制代码

>>> a = CustomDict()

>>> a['name'] = "ethan"

>>> a['name']

ethan

>>> a[111] = 111; a[1111] = 2222

>>> print(a[111], a[1111])

111 2222

>>> a.keys()

['name', 1111, 111]

>>> a.values()

['ethan', 2222, 111]

>>> len(a)

3

复制代码

总结

通过了解python字典的原理，自然而然就能理解字典的一些特点了。

dict为什么是无序的？ 因为dict的key和value作为一个表元存在散列表里面,偏移量并不是根据存入的顺序决定的。所以自然是无序的。

为什么不能在遍历的时候往字典里面添加元素？ 因为在字典里面添加元素的时候，字典随时都可能扩容，导致顺序发生变化。导致遍历变得不可预知。