Apakah prinsip pelaksanaan Dict dalam Python?

1. Pelaksanaan Dict tidak tertib

Dict boleh mencari kunci dengan cepat, berkat strategi ruang untuk masa dan pelaksanaan jadual cincangnya. Apabila membaca dan menulis Kekunci, Kekunci akan dicincang (jadi Kekunci diperlukan sebagai jenis yang tidak boleh diubah. Jika ia adalah jenis pembolehubah, nilai cincangnya tidak boleh dikira), dan kemudian berdasarkan nilai yang dikira , lakukan pengiraan modulo dengan panjang ruang tatasusunan semasa, dan nilai yang diperolehi ialah subskrip Kunci semasa dalam tatasusunan Akhirnya, melalui subskrip, nilai itu boleh dibaca dengan kerumitan masa O(1). adalah Distributed ialah pendekatan biasa, tetapi terdapat juga masalah Apakah yang perlu saya lakukan jika tatasusunan penuh atau mempunyai kunci yang berbeza, tetapi hasil cincangan adalah sama?

Penyelesaian untuk masalah pertama adalah sesuai. Apabila kapasiti dikembangkan, dalam Python, apabila nombor yang diletakkan dalam Dict menyumbang 2/3 daripada kapasiti, Dict akan mula berkembang Jumlah kapasiti selepas pengembangan digandakan sebelum pengembangan ini adalah untuk mengurangkan kekerapan pengembangan, mengakibatkan bilangan migrasi utama meningkat;

Terdapat dua penyelesaian kepada masalah kedua:

Kaedah pautan: Tatasusunan asal menyimpan nilai yang sepadan dengan Key , dan tatasusunan kaedah rantaian menyimpan tatasusunan ini menyimpan tatasusunan yang mengandungi kunci dan nilai yang sepadan, seperti yang ditunjukkan di bawah dengan mengandaikan bahawa hasil cincangan kunci1 dan kunci2 adalah kedua-duanya 0, ia akan dimasukkan di bawah 0 tatasusunan. . Dalam subskrip, key1 berada di kedudukan pertama tatasusunan yang dilanggan pada 0, dan apabila key2 dimasukkan, didapati bahawa key1 sudah wujud Kemudian bandingkan key2 dan key1, dan mendapati bahawa kunci mereka sebenarnya berbeza, kemudian subskrip di 0. Tambah.

array = [
	[
    # 分别为key, hash值， 数值
		('key1', 123, 123),
		('key2', 123, 123)
	],
	[
		('key3', 123, 123)
	]
]

Membangunkan kaedah pengalamatan: Kaedah pengalamatan yang sedang dibangunkan menggunakan idea lain, menerima pakai idea meminjam, jika terdapat konflik, gunakannya digit seterusnya subskrip semasa Jika digit seterusnya masih bercanggah, teruskan menggunakan digit seterusnya Apabila mencari data, kekunci yang sepadan dengan nilai cincang akan dibandingkan. digit seterusnya akan ditemui Sehingga atau sehingga kekosongan ditemui.

Pelaksanaan kedua-dua penyelesaian di atas adalah sangat mudah, dan mudah untuk mengetahui kelebihan dan kekurangannya secara perbandingan:

Kelebihan kaedah senarai terpaut:

• Adalah mudah untuk memadamkan rekod. , anda hanya perlu menanyakan subarray

• Kelemahan kaedah senarai terpaut:

menggunakan penunjuk, yang menghasilkan kelajuan pertanyaan yang lebih perlahan, lebih tinggi penggunaan memori, dan tidak sesuai untuk bersiri Kelebihan dan keburukan kaedah pengalamatan terbuka adalah bertentangan dengan kaedah senarai terpaut Memandangkan segala-galanya dalam Python adalah berdasarkan Dict dan perlu bersiri, kaedah pengalamatan terbuka telah dipilih 🎜>

• dengan perbandingan kedua -dua kaedah senarai yang dipautkan dan kaedah carian terbuka boleh didapati. akan menjadi sangat kecil, dan tidak perlu kerap mengembangkan dan memindahkan data, tetapi ia mengambil banyak ruang Oleh itu, nilai awal pelaksanaan jadual cincang tidak boleh terlalu besar nilai awal Dict dalam

  ialah 8. Selain itu, jadual cincang juga perlu menyimpan ruang yang tidak digunakan dalam tatasusunan yang menyimpan data dalam julat nilai, supaya penggunaan ruang dan kebarangkalian perlanggaran cincang akan kekal. dalam keadaan optimum Walau bagaimanapun, kerana setiap pengembangan menggunakan banyak prestasi, ia tidak boleh dikembangkan setiap kali ia diubah, jadi perlu Tentukan nilai Apabila nisbah yang tidak digunakan/digunakan mencapai nilai ini, kapasiti akan diperluaskan secara automatik . Dalam Dict

  , nilai ini ialah 2/3 Iaitu, apabila 2/3 daripada ruang dalam Dict digunakan, dia akan secara automatik mengembang untuk mencapai keseimbangan optimum yang baru untuk mengurangkan bilangan pemindahan kunci semasa setiap pengembangan, jumlah kapasiti selepas pengembangan mestilah dua kali ganda daripada jumlah kapasiti sebelum pengembangan jadual cincang hanya akan memindahkan separuh daripada kunci adalah bahawa mendapatkan subskrip kunci dalam tatasusunan dicapai dengan mengambil modulo nilai cincang, seperti cincang Kapasiti jadual ialah 8, dan nilai modulo kunci dengan nilai cincang 20 ialah 4. Selepas jadual cincang dikembangkan, panjangnya menjadi 16. Pada masa ini, hasil modulo masih 4. Kunci dengan nilai cincang 11 mempunyai nilai modulo 3, dan selepas pengembangan, nilai modulo ialah 11. Ia boleh dilihat dengan jelas bahawa selepas jadual cincang dikembangkan, kunci yang nilai cincangnya lebih besar daripada kapasiti asal tidak perlu dipindahkan, manakala kunci yang nilai cincangnya kurang daripada kapasiti perlu dipindahkan.

Tetapi jika anda mengikuti pernyataan di atas, masih terdapat masalah dengan kaedah pengalamatan terbuka, seperti tatasusunan berikut:

arrray = [None, None, None, None, True, True, True, True]

以True代表当前数组的位置已经被占用, None代表未被占用, 可以看出当前并未满足使用了数组的2/3空间, 数组还未到扩容阶段。 此时假设要插入一个Key, 刚好落在数组下标4, 那么插入的时候就要一直查询下去, 最后发现只有数组下标0的位置的空的, 才可以真正的插入数据. 对于一个长度只有8的数组, 需要执行5次才能插入数据, 那也太浪费性能了, 所以Python要实现一个算法, 尽量让冲突的数据插在别的地方. 在源码中, Python用到了公式x = ((5*y) + 1) % 2**i来实现跳跃插入冲突数据. 式子中x为数组的下一个坐标, y为当前发生冲突的坐标,i为容量系数, 比如初始化时, i为3, 那么容量就是8了, 第一次插入数据到坐标0冲突时, y = 0, 带入公式后, 求得x 等于1, 第二次插入数据到坐标0时, y = 1, 求得x 等于 6, 通过这样算下去, 可以发现数字生成轨迹是0>1>6>7>4>5>2>3>0一直循环着, 这样跳着插数据就能完美解决上面场景的问题.

2.有序Dict的原理

Python3.6之前说的差不多, 它的数组大概是长这样的, 数组中存了子数组, 第一项为hash值, 第二项为key, 第三项为值.

array = [
	[],
	[123456, "key1", 1],
	[],
	[],
	[],
	[234567, "key2", 2],
	[],
	[]
]

这种实现的空间大小在初始化时就固定了, 直到下次扩容再发送变化, 在遍历字典时, 实际上就是遍历数组, 只是把没有占用的空间进行跳过.可以看出这种遍历的生成的顺序只跟哈希结果相关, 无法跟插入顺序相关, 所以这种方法的实现是无序的(同时由于每次启动程序时， 他们的哈希计算是不一样的， 所以每次遍历的顺序也就各不相同了).

而在Python3.7之后, Python的Dict使用了新的数据结构, 使Python新Dict的内存占用也比老的Dict少了, 同时新的Dict在遍历时是跟插入顺序是一致的, 具体的实现是, 初始化时会生成两个数组, 插入值时, 在数组二追加当前的数据, 并获得当前追加数据所在的下标A, 然后对key进行哈希取模算出下标B, 最后对数组下标B的值更新为A, 简单的演示如下:

# 初始的结构
# -1代表还未插入数据
array_1 = [-1, -1, -1, -1, -1, -1, -1, -1]
array_2 = []


# 插入值后, 他就会变为:
array_1 = [-1, 0, -1, -1, -1, 1, -1, -1]
array_2 = [
	[123456, "key1", 1],
	[234567, "key2", 2],
]

可以看出, 数组2的容量跟当前放入的值相等的, 数组1虽然还会保持1/3的空闲标记位, 但他只保存数组二的下标, 占用空间也不多, 相比之前的方案会节省一些空间, 同时在遍历的时候可以直接遍历数组2, 这样Python的Dict就变为有序的了. 注: 为了保持操作高效, 在删除的时候, 只是把数组1的值设置为-2, 并把数组2对应的值设置为None, 而不去删除它, 在查找时会忽略掉数组1中值为-2的元素， 在遍历时会忽略掉值为None的元素.

3.有序字典的实现

通过上面的了解后, 可以使用Python来写一个新版Dict的实现, 具体说明见注释:

from typing import Any, Iterable, List, Optional, Tuple


class CustomerDict(object):

    def __init__(self):
        self._init_seed: int = 3  # 容量因子
        self._init_length: int = 2 ** self._init_seed  # 初始化数组大小
        self._load_factor: float = 2 / 3  # 扩容因子
        self._index_array: List[int] = [-1 for _ in range(self._init_length)]  # 存放下标的数组
        self._data_array: List[Optional[Tuple[int, Any, Any]]] = []  # 存放数据的数组
        self._used_count: int = 0  # 目前用的量
        self._delete_count: int = 0  # 被标记删除的量

    def _create_new(self):
        """扩容函数"""
        self._init_seed += 1  # 增加容量因子
        self._init_length = 2 ** self._init_seed
        old_data_array: List[Tuple[int, Any, Any]] = self._data_array
        self._index_array: List[int] = [-1 for _ in range(self._init_length)]
        self._data_array: List[Tuple[int, Any, Any]] = []
        self._used_count = 0
        self._delete_count = 0

        # 这里只是简单实现, 实际上只需要搬运一半的数据
        for item in old_data_array:
            if item is not None:
                self.__setitem__(item[1], item[2])

    def _get_next(self, index: int):
        """计算冲突的下一跳，如果下标对应的值冲突了, 需要计算下一跳的下标"""
        return ((5*index) + 1) % self._init_length

    def _core(self, key: Any, default_value: Optional[Any] = None) -> Tuple[int, Any, int]:
        """获取数据或者得到可以放新数据的方法, 返回值是index_array的索引, 数据, data_array的索引"""
        index: int = hash(key) % (self._init_length - 1)
        while True:
            data_index: int = self._index_array[index]
            # 如果是-1则代表没有数据
            if data_index == -1:
                break
            # 如果是-2则代表之前有数据则不过被删除了
            elif data_index == -2:
                index = self._get_next(index)
                continue

            _, new_key, default_value = self._data_array[data_index]
            # 判断是不是对应的key
            if key != new_key:
                index = self._get_next(index)
            else:
                break
        return index, default_value, data_index

    def __getitem__(self, key: Any) -> Any:
        _, value, data_index = self._core(key)
        if data_index == -1:
            raise KeyError(key)
        return value

    def __setitem__(self, key: Any, value: Any) -> None:
        if (self._used_count / self._init_length) > self._load_factor:
            self._create_new()
        index, _, _ = self._core(key)

        self._index_array[index] = self._used_count
        self._data_array.append((hash(key), key, value))
        self._used_count += 1

    def __delitem__(self, key: Any) -> None:
        index, _, data_index = self._core(key)
        if data_index == -1:
            raise KeyError(key)
        self._index_array[index] = -2
        self._data_array[data_index] = None
        self._delete_count += 1

    def __len__(self) -> int:
        return self._used_count - self._delete_count

    def __iter__(self) -> Iterable:
        return iter(self._data_array)
    
    def __str__(self) -> str:
        return str({item[1]: item[2] for item in self._data_array if item is not None})

    def keys(self) -> List[Any]:
        """模拟实现keys方法"""
        return [item[1] for item in self._data_array if item is not None]

    def values(self) -> List[Any]:
        """模拟实现values方法"""
        return [item[2] for item in self._data_array if item is not None]

    def items(self) -> List[Tuple[Any, Any]]:
        """模拟实现items方法"""
        return [(item[1], item[2]) for item in self._data_array if item is not None]


if __name__ == '__main__':
    customer_dict: CustomerDict = CustomerDict()
    customer_dict["demo_1"] = "a"
    customer_dict["demo_2"] = "b"
    assert len(customer_dict) == 2

    del customer_dict["demo_1"]
    del customer_dict["demo_2"]
    assert len(customer_dict) == 0

    for i in range(30):
        customer_dict[i] = i
    assert len(customer_dict) == 30

    customer_dict_value_list: List[Any] = customer_dict.values()
    for i in range(30):
        assert i == customer_dict[i]

    for i in range(30):
        assert customer_dict[i] == i
        del customer_dict[i]
    assert len(customer_dict) == 0

Atas ialah kandungan terperinci Apakah prinsip pelaksanaan Dict dalam Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!