set()是如何实现的？
set()是如何实现的？
提问于 2010-10-16 22:39:01
我见过有人说python中的set对象有O(1)成员资格检查。它们是如何在内部实现的呢？它使用的是哪种数据结构？该实现还具有哪些其他含义？
这里的每一个答案都很有启发性，但我只能接受一个，所以我会选择与我最初的问题最接近的答案。感谢大家提供的信息！
回答 2
Stack Overflow用户
发布于 2010-10-16 22:59:39
我们都可以很容易地访问the source，set_lookkey()前面的注释是这样说的：
/* set object implementation
Written and maintained by Raymond D. Hettinger <python@rcn.com>
Derived from Lib/sets.py and Objects/dictobject.c.
The basic lookup function used by all operations.
This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
The initial probe index is computed as hash mod the table size.
Subsequent probe indices are computed as explained in Objects/dictobject.c.
To improve cache locality, each probe inspects a series of consecutive
nearby entries before moving on to probes elsewhere in memory. This leaves
us with a hybrid of linear probing and open addressing. The linear probing
reduces the cost of hash collisions because consecutive memory accesses
tend to be much cheaper than scattered probes. After LINEAR_PROBES steps,
we then use open addressing with the upper bits from the hash value. This
helps break-up long chains of collisions.
All arithmetic on hash should ignore overflow.
Unlike the dictionary implementation, the lookkey function can return
NULL if the rich comparison returns an error.
*/
...
#ifndef LINEAR_PROBES
#define LINEAR_PROBES 9
#endif
/* This must be >= 1 */
#define PERTURB_SHIFT 5
static setentry *
set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
{
...Stack Overflow用户
发布于 2020-10-23 15:26:01
python中的集合在内部使用哈希表。让我们先来谈谈哈希表。假设有一些您想要存储在哈希表中的元素，并且您在哈希表中有31个位置可以这样做。设元素为: 2.83，8.23，9.38，10.23，25.58，0.42，5.37，28.10，32.14，7.31。当您想要使用哈希表时，首先要确定哈希表中存储这些元素的索引。模函数是确定这些指数的一种流行方法，因此假设我们一次取一个元素，将其乘以100，然后应用模数乘以31。重要的是，在一个元素上的每个这样的操作都会产生一个唯一的数字，因为除非允许链接，否则哈希表中的一个条目只能存储一个元素。以这种方式，每个元素将被存储在由通过模运算获得的索引所管理的位置。现在，如果您想要使用这个哈希表在一个实际上存储元素的集合中搜索一个元素，那么您将在O(1)时间内获得该元素，因为该元素的索引是使用恒定时间内的模运算来计算的。为了阐述模运算，让我也写一些代码：
piles = [2.83, 8.23, 9.38, 10.23, 25.58, 0.42, 5.37, 28.10, 32.14, 7.31]
def hash_function(x):
return int(x*100 % 31)
[hash_function(pile) for pile in piles]输出: 4，17，8，0，16，11，10，20，21，18
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/3949310
复制相关文章
相似问题