当键是数字时的python字典

法拉兹·莫莱

当键是数字时，我对python中的字典属性有疑问。在我的情况下，当我用数字键打印字典时，打印结果将按键排序，但在其他情况下（键是字符串）字典是无序的。我想在字典中了解此规则。

l = {"one" : "1", "two" : "2", "three" : "3"}

print(l)

l = {1: "one", 2: "two", 3: "three", 4: "four", 5: "five"}

print(l)

l = {2: "two", 3: "three", 4: "four", 1: "one", 5: "five"}

print(l)

结果：

{'three': '3', 'two': '2', 'one': '1'}

{1: 'one', 2: 'two', 3: 'three', 4: 'four', 5: 'five'}

{1: 'one', 2: 'two', 3: 'three', 4: 'four', 5: 'five'}

卡斯拉文

Python使用哈希表存储字典，因此使用哈希函数的字典或其他对象中没有排序。

但是关于哈希对象中项目的索引，python根据以下代码在其中hashtable.c计算索引：

key_hash = ht->hash_func(key);
index = key_hash & (ht->num_buckets - 1);

因此，由于整数的哈希值是整数本身，因此索引基于数字（ht->num_buckets - 1是一个常数），因此索引是按位与和之间(ht->num_buckets - 1)和数字计算的。

考虑以下set使用hash-table的示例：

>>> set([0,1919,2000,3,45,33,333,5])
set([0, 33, 3, 5, 45, 333, 2000, 1919])

对于数量，33我们有：

33 & (ht->num_buckets - 1) = 1

实际上是：

'0b100001' & '0b111'= '0b1' # 1 the index of 33

注意在这种情况下(ht->num_buckets - 1)是8-1=7或0b111。

对于1919：

'0b11101111111' & '0b111' = '0b111' # 7 the index of 1919

对于333：

'0b101001101' & '0b111' = '0b101' # 5 the index of 333

有关python哈希函数的更多详细信息，请阅读python源代码中的以下引号：

未来的主要细节：在模拟随机性的意义上，大多数哈希方案都依赖于具有“良好”的哈希函数。Python并非如此：在最常见的情况下，它最重要的散列函数（用于字符串和整数）非常规则：
>>> map(hash, (0, 1, 2, 3))
  [0, 1, 2, 3]
>>> map(hash, ("namea", "nameb", "namec", "named"))
  [-1658398457, -1658398460, -1658398459, -1658398462]
这不一定是坏事！相反，在大小为2 ** i的表中，以低序i位作为初始表索引非常快，并且对于由连续整数范围索引的字典，根本没有冲突。当键是“连续”字符串时，情况大致相同。因此，这在通常情况下会提供比随机行为更好的行为，这是非常理想的。

OTOH，当发生冲突时，填充哈希表的连续切片的趋势使得良好的冲突解决策略至关重要。仅采用哈希码的最后i位也是容易受到攻击的：例如，将列表[i << 16 for i in range(20000)]视为一组键。由于int是它们自己的哈希码，并且适合大小为2 ** 15的字典，因此每个哈希码的最后15位均为0：它们都映射到相同的表索引。

但是迎合不寻常的情况不应减慢通常的情况，因此无论如何我们都只接受最后的i个信息。剩下的事要靠冲突解决来解决。如果我们通常会在第一次尝试中找到我们要寻找的密钥（事实证明，我们通常会这样做-表负载因数保持在2/3以下，所以我们的优势很明显），那么它就可以了保持初始索引计算的便宜是最好的选择。