0

要素の位置はハッシュ関数に依存するため、完全に順序付けられていると思います。したがって、そのオブジェクトが不変である場合、それらをセットに配置した後、それらの位置は変更されません。そして、たとえば、セットを印刷するたびに、まったく同じ要素の順序になります。確かに、ハッシュ関数が計算されるまで、それらの位置を予測することはできませんが、とにかく。

4

4 に答える 4

4

ジェネリック/抽象データ型

Aho、Hopcroft、Ullmannからのセットの定義:「データ構造とアルゴリズム」、Addison-Wesely、1987:

セットは、メンバー (または要素) のコレクションです。[...] . セットのすべてのメンバーは異なります [...]

抽象データ型セットには、順序付きまたは順序なしの特性はありません。セットで動作するいくつかのメソッドが定義されていますが、順序付けとは関係ありません (たとえば、Martin Richardsの「データ構造とアルゴリズム」を参照してください)。

2 つのセットは、一方のセットの各要素が他方のセット内にもあり、追加の要素がない場合、等しいと見なされます。

セット (したがって、セットのすべての要素) を書き留める場合、それらを何らかの順序で書き留める必要があります。これは、適切なセットの単なる表現であることに注意してください。

例: 要素 1、2、および 3 を含む集合は、{1, 2, 3}、{1, 3, 2}、{3, 1, 2} などと書き留めることができます。これらは、同じセットの異なる表現にすぎません。

特定の実装

プログラミング言語が異なれば、セットはさまざまなユースケースを念頭に置いてさまざまな方法で実装されます。

一部の言語 (python、JAVA など) では、標準セットの実装は、それらのインターフェイスで順序付けを公開していません。

一部の言語 (C++ など) では、標準セットの実装により、インターフェイスで順序付けが公開されます。

例 (C++):

内部的には、セット内の要素は、コンテナーの構築に設定された特定の厳密な弱い順序付け基準に従って、常に下位から上位へと並べ替えられます。

template < class Key, class Compare = less, class Allocator = allocator > class set;

( C++ セットを参照)。

于 2012-04-25T06:51:35.587 に答える
2

ハッシュ関数は、(通常) 外部から見える、またはセットの変更可能なパラメーターではありません。さらに、ハッシュ関数が既知で十分に特徴付けられている実装がある場合でも、ハッシュ値が衝突したときの動作を指定することはできません。

これの通常の要約は、セットの実装は順序を課す可能性がありますが、インターフェースは課さないということです。

于 2012-04-25T06:48:50.300 に答える
2

セットのどの定義を参照していますか? 私の理解では、«set» は多数の一意の要素を含み、通常は追加と削除が可能なデータ構造の名前です。他のすべては保証されておらず、実装の対象となる場合があります。

順序がないというわけではありませんが、すべての有効な実装に特定の順序はありません。ハッシュテーブルの使用は一般的ですが、任意のタイプのリストまたはツリーを使用することも可能です。

したがって、順序はハッシュ関数（すでに多くの可能な実装）を介して行われるか、追加の順序に関連するか、または...

于 2012-04-25T07:01:09.977 に答える