2

PHP で、ソートされた数値をキーとして新しいハッシュ テーブルに要素を挿入すると、結果のハッシュも順序付けられるというのは本当ですか?

では、キーを取得すると、それらは注文され、$a[0], $a[1], $a[2]元の注文にも従うのでしょうか? (確かに、キーはその順序になりますが、値はそうである必要はありません)。

PHPでは、それを当てにできるというのは本当ですか? Perl、Python、または Ruby にそのような動作はありませんか?

4

3 に答える 3

3

Python にはOrderedDict. 他の言語にも同等のものがあります。

dictただし、追加の簿記が必要なため、通常、この動作は基本的なハッシュ タイプ (Python の など) では保証されません。

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 から始まる) を法とするハッシュ値に従って配置されます。
  • 整数のハッシュ値は整数そのものです
  • ハッシュ テーブルの 3 分の 2 がいっぱいになると、4 倍にサイズ変更され (2 倍になると 50,000 まで)、既存のキーと値のペアが再挿入されます。

質問: どのような状況で、ソートされた数値をキーとしてハッシュ テーブルに追加すると、ハッシュが順序付けられると期待できますか?

回答: 並べ替えられた数値キーは、辞書のサイズのモジュロnを取得したときにそれらの値が並べ替えられたままである場合にのみ、通常の辞書で並べ替えられたままになり、要素が追加されるときに作成される小さな辞書のそれぞれについてもその条件が当てはまる場合に限ります。

  • 最初の 5 つの要素 (8 * 2 // 3) は、8 を法として取得した場合にソートする必要があります。
  • 最初の 21 個の要素 (32* 2 // 3) は、32 を法として取得した場合にソートする必要があります。
  • 最初の 85 要素 (128 * 2 // 3) は、モジュール 128 を取得するときに並べ替える必要があります。
  • 等々 ...

コード内:

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 に答える