2

在 PHP 中，当我们使用排序后的数字作为键将元素插入到新的哈希表中时，是否也会对生成的哈希进行排序？

那么当我们拿到钥匙时，它们会被排序，并且$a[0], $a[1], $a[2]也会遵循原来的顺序吗？（当然，键将是那个顺序，但值不一定是）。

在 PHP 中，我们真的可以指望它吗？Perl、Python 或 Ruby 中没有这种行为吗？

4

3 回答 3

3

Python 有OrderedDict. 其他语言也有等价物。

然而，对于基本的散列类型（例如 Python 的），通常不能保证这种行为，dict因为它需要额外的簿记。

PHP 的数组是一片特殊的雪花；最好不要养成依赖基本哈希排序的习惯，即使您使用的是 PHP。

于 2012-05-02T00:50:19.447 回答
2

Perl 中的行为记录在keys中：

哈希的键以明显随机的顺序返回。实际的随机顺序在 Perl 的未来版本中可能会发生变化，但它保证与值或每个函数产生的顺序相同（假设哈希没有被修改）。从 Perl 5.8.1 开始，出于安全原因，即使在 Perl 的不同运行之间，排序也可能不同（请参阅perlsec 中的算法复杂性攻击）。

您可以使用Tie::IxHash：

这个 Perl 模块实现了 Perl 哈希，它保留了添加哈希元素的顺序。更改与现有键对应的值时，顺序不受影响IxHash。元素也可以设置为任意提供的顺序。熟悉的 Perl 数组操作也可以在IxHash.

于 2012-05-02T01:11:08.083 回答
1

正如 Amber 所指出的，collections.OrderedDict是保证保留插入顺序的 Python 工具。

也就是说，我发现标题中提出的问题很有趣。Python 的一个实现细节是整数的哈希值就是值本身。由于常规字典（通常是无序的）只是哈希表，因此有时可以将已排序的数字添加到字典中，使其保持排序：

>>> from random import sample
>>> dict.fromkeys(range(5)).keys()
[0, 1, 2, 3, 4]
>>> dict.fromkeys(range(25)).keys()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]
>>> dict.fromkeys(range(0,25,2)).keys()
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24]
>>> dict.fromkeys(sorted(sample(range(50), 40))).keys()
[0, 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 15, 16, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 31, 32, 33, 34, 35, 36, 38, 39, 40, 41, 42, 43, 44, 45, 47, 49]

这个结果是脆弱的，不是保证的行为。它依赖于以下属性：

  • 键根据它们的哈希值以字典大小为模（从 8 开始）定位
  • 整数的哈希值是整数本身
  • 当哈希表已满三分之二时，它的大小会向上调整四倍（然后开始加倍时高达 50,000），并且重新插入现有的键/值对。

问题：在什么情况下，如果我们将排序后的数字作为键添加到哈希表中，我们可以期望哈希是有序的？

回答：排序的数字键在常规字典中保持排序当且仅当这些值在对字典的大小取模时保持排序，并且如果该条件对于添加元素时创建的每个较小的字典也成立：

  • 当取模 8 时，前五个元素 (8 * 2 // 3) 必须排序。
  • 当取模 32 时，前 21 个元素 (32* 2 // 3) 必须进行排序。
  • 取模块 128 时，前八十五个元素 (128 * 2 // 3) 必须排序。
  • 等等 ...

在代码中：

def will_remain_sorted(seq):
    i, n = 0, 8
    while i < len(seq):
        i = n * 2 // 3
        if not sorted(seq[:i], key=lambda x: x%n) == seq[:i]:
            return False
        n *= 4 if n < 50000 else 2
    return True
于 2012-05-02T01:06:19.520 回答