[解決済み] なぜ、辞書や集合の順番は任意なのか？

質問

Pythonで辞書や集合をループする際に、どのように「任意の」順序で行うのかがわかりません。

プログラミング言語なんだから、言語のすべてが100％決まっているはずでしょう？Pythonは、辞書や集合のどの部分を選ぶか、1番目、2番目と、なんらかのアルゴリズムで決めているはずです。

何が足りないのでしょうか？

解決方法は？

注意 この回答は dict 型は Python 3.6 で変更されました。この回答にある実装の詳細のほとんどはまだ適用されますが ディクショナリー はハッシュ値で決定されなくなりました。セットの実装は変更されていません。

その順番は任意ではなく、辞書やセットの挿入・削除の履歴や、特定のPythonの実装に依存します。この回答の残りの部分では、「辞書」は「セット」とも読むことができます。セットは、キーだけで値を持たない辞書として実装されています。

キーはハッシュ化され、ハッシュ値は動的なテーブルのスロットに割り当てられます（必要に応じて大きくしたり小さくしたりすることができます）。そして、このマッピング処理は衝突を引き起こす可能性があります。つまり、あるキーがスロットで 次 スロットに存在するものをもとに

内容をリストアップすると、スロットをループするので、キーはその順番でリストアップされます。 現在 に存在する。

キーを取る 'foo' と 'bar' 例えば、テーブルの大きさを8スロットと仮定します。Python 2.7では hash('foo') は -4177197833195190597 , hash('bar') は 327024216814240868 . Modulo 8は、この2つのキーがスロット3と4にスロットされていることを意味します。

>>> hash('foo')
-4177197833195190597
>>> hash('foo') % 8
3
>>> hash('bar')
327024216814240868
>>> hash('bar') % 8
4

これにより、掲載順が通知されます。

>>> {'bar': None, 'foo': None}
{'foo': None, 'bar': None}

3と4を除くすべてのスロットは空で、テーブルをループするとまずスロット3がリストされ、次にスロット4がリストされます、したがって 'foo' の前に表示されます。 'bar' .

bar と baz しかし、ハッシュ値がちょうど8つ離れているため、まったく同じスロットにマッピングされます。 4 :

>>> hash('bar')
327024216814240868
>>> hash('baz')
327024216814240876
>>> hash('bar') % 8
4
>>> hash('baz') % 8
4

2番目のキーは次のスロットに移動させなければなりません。

>>> {'baz': None, 'bar': None}
{'bar': None, 'baz': None}
>>> {'bar': None, 'baz': None}
{'baz': None, 'bar': None}

ここでは、どちらかのキーが先にスロットされたため、テーブルの順序が異なっています。

CPython（最もよく使われているPythonの実装）で使われている基礎となる構造の技術的名称は ハッシュテーブル オープンアドレッシングを採用しているものです。もしあなたが好奇心旺盛で、C言語を十分に理解しているのなら C言語実装 をご覧ください。また、次のようなものもあります。 ブランドン・ローズ氏によるPycon 2010のプレゼンテーション CPythonがどのように dict を手に入れるか、あるいは 美しいコード には、Andrew Kuchlingが書いた実装に関する章が含まれています。

Python 3.3 では、ある種のサービス拒否（攻撃者が大量のハッシュ衝突を引き起こすことによって Python サーバを応答不能にする）を防ぐために、ハッシュの衝突を予測できないように、ランダムなハッシュシードも使用されていることに注意してください。これは、与えられた辞書や集合の順序が、その後 また は、現在のPythonの起動時のランダムハッシュの種に依存します。

他の実装では、辞書のためのドキュメント化されたPythonインターフェースを満たす限り、辞書に別の構造を使うことは自由ですが、これまでのところ、すべての実装はハッシュテーブルのバリエーションを使用していると思います。

CPython 3.6で導入された 新しい dict を実装することで、挿入順序を維持し、より高速でメモリ効率の良い起動を実現しました。各行が保存されたハッシュ値やキーと値のオブジェクトを参照する大きな疎なテーブルを維持するのではなく、新しい実装では、より小さなハッシュ 配列 のインデックスを参照するのみであり、含まれる項目を順番にリストアップするのはこの密なテーブルです。このテーブルの 詳細についてはPython-Devに提案してください。 . Python 3.6 では、これは 実装の詳細 Python-the-languageは、他の実装が順序を保持しなければならないとは指定していません。これは Python 3.7 で変更され、この詳細が に昇格しました。 言語仕様 Python 3.7以降と正しく互換性のある実装を行うには、以下の条件を満たす必要があります。 必須 は、この順序を保持する動作をコピーします。そして、この変更はセットには適用されません。セットはすでに「小さな」ハッシュ構造を持っているからです。

Python 2.7以降では、Pythonが提供する OrderedDict クラス のサブクラスである dict これは、キーの順序を記録するための追加のデータ構造を追加したものです。多少の速度と余分なメモリの代償として、このクラスはキーを挿入した順番を記憶しています。これは、追加の辞書に格納された二重リンクリストを使用して、順序を効率的に最新に保ちます。詳細は Raymond Hettingerによるアイデアの概要の投稿 . OrderedDict オブジェクトの利点は他にもあり、例えば 並べ替え可能 .

順番に並べたかった場合は oset パッケージ ; Python 2.5 以上で動作します。