gpt4 book ai didi

python 字典是指向...什么的指针的 HashMap ?

转载 作者:行者123 更新时间:2023-11-28 18:17:18 25 4
gpt4 key购买 nike

我知道在 python 中,字典是通过对键进行散列并将指针(指向键值对)存储在数组中来实现的,索引由散列确定。

但是键值对本身是如何存储的呢?它们是否存储在一起(即,在内存中的连续位置)?它们是存储为元组还是指针数组,一个指向键,一个指向值?还是完全不同?

谷歌搜索已经找到很多关于散列和开放寻址等的解释,但没有解决这个问题。

最佳答案

粗略地说,有一个函数,我们称它为 F,它计算值数组中的索引 F(h)。所以这些值被存储为一个数组,它们被查找为 F(h)。之所以“粗略地说”,是因为不同对象的哈希值计算方式不同。例如,对于指针,它是p>>3;而对于字符串,哈希是字符串所有字节的摘要。

如果您想查看 C 代码,请搜索 lookdict_index 或直接查看 CPython 源代码中的 dictobject.c 文件。如果您习惯阅读 C 代码,它的可读性非常好。

编辑 1:来自 Python 3.6.1 的 Include/dictobject.h 中的评论:

/* If ma_values is NULL, the table is "combined": keys and values
are stored in ma_keys.

If ma_values is not NULL, the table is splitted:
keys are stored in ma_keys and values are stored in ma_values */

还有来自 dictobject 的解释:

/*
The DictObject can be in one of two forms.

Either:
A combined table:
ma_values == NULL, dk_refcnt == 1.
Values are stored in the me_value field of the PyDictKeysObject.
Or:
A split table:
ma_values != NULL, dk_refcnt >= 1
Values are stored in the ma_values array.
Only string (unicode) keys are allowed.
All dicts sharing same key must have same insertion order.
....
*/

这些值要么存储为一个字符串数组,它跟在一个“键对象”数组之后。或者每个值的指针存储在 PyDictKeyEntryme_value 中。 key 存储在 PyDictKeyEntryme_key 字段中。键数组实际上是 PyDictKeyEntry 结构的数组。

作为引用,PyDictKeyEntry定义为:

   typedef struct {
/* Cached hash code of me_key. */
Py_hash_t me_hash;
PyObject *me_key;
PyObject *me_value; /*This field is only meaningful for combined tables*/
} PyDictKeyEntry;

查看相关文件:Python源码中的Objects/dict-common.h、Objects/dictobject.c、Include/dictobject.h。

Objects/dictobject.c 在文件开头的注释中有详尽的描述,解释了整个方案和历史背景。

关于python 字典是指向...什么的指针的 HashMap ?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47568197/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com