Zenn
Open15

JavaScript の Set は挿入順序を維持するのか

JavaScript
ECMAScript
#
set
NotFoundsNotFounds

背景

JavaScript で書かれた同僚のコードレビューをしているときにリストの重複排除のために Set を使ったコードがあり、挿入順序が維持されるのかどうか気になった。

Java の HashSet や C++ の unordered_set など一般に抽象データ型の集合は順序を保証しない。
また、Java の SortedSet や C++ の set は値の比較によってソートされた状態で格納されるため順序自体は存在するが、挿入順序は保持しない。

NotFoundsNotFounds

MDN の説明

MDN では以下のように説明されており、追加した順序によって反復可能とのこと。
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set

You can iterate through the elements of a set in insertion order. The insertion order corresponds to the order in which each element was inserted into the set by the add() method successfully (that is, there wasn't an identical element already in the set when add() was called).

これだけでは実装によってそうなっているのか、仕様として挿入順序を維持するように定められているのかはっきりしない。

NotFoundsNotFounds

ECMA262 を読む

Set object に関する仕様は 24.2 Set Objects | ECMAScript® 2023 Language Specification に書かれている。

特に関係しそうなところは以下の項

NotFoundsNotFounds

24.2.3.1 Set.prototype.add ( value )

この項は Set object に対して値を追加する際の仕様について説明している。
add method の挙動が step ごとに記載されており、その中に以下のような記述がある。

  1. Append value to S.[[\mathrm{SetData}]].

S.[[SetData]] は集合の要素のコレクションを表している。add や put ではなく append となっていることから、ここではコレクションの末尾に要素を追加することを要求している。
つまり、この説明によって挿入順序が考慮されていると考える。

NotFoundsNotFounds

S.[[SetData]] は集合の要素のコレクションを表している。add や put ではなく append となっていることから、ここではコレクションの末尾に要素を追加することを要求している。

ここで [[SetData]] がどのようなデータ構造であるかの説明が少し弱かったので補足する。

24.2.1.1 Set ( [ iterable ] ) に以下のような記述があり、[[SetData]] がリストであることが分かる。

  1. Set set.[[SetData]] to a new empty List.
NotFoundsNotFounds

24.2.3.6 Set.prototype.forEach ( callbackfn [ , thisArg ] )

この項は Set object の forEach method についての仕様を説明している。forEach は格納されている各値に対して一度ずつ callbackfn を呼び出し、具体的な step は以下のように書かれている。

  1. Let numEntries be the number of elements in entries.
  2. Let index be 0.
  3. Repeat, while index < numEntries,
    a. Let e be entries[index].
    b. Set index to index + 1.

entries の 0個目, 1個目と順になめており、追加された順序に基づいて各値を走査していることになる。

また同項の NOTE には以下のような記述があり、forEach が明確に挿入順序を維持して走査することが示されている。

forEach calls callbackfn once for each value present in the Set object, in value insertion order.

NotFoundsNotFounds

24.2.5 Set Iterator Objects

この項は Set object を反復する際の仕様について説明しており、CreateSetIterator ( set, kind ) を扱う。 これは 24.2.3.5 Set.prototype.entries ( ) と 24.2.3.10 Set.prototype.values ( ) で使われている。

forEach と同様に以下のように step が記載されていることから、iterateする際も追加された順序に基づいて値を走査するとわかる。

c. Let numEntries be the number of elements in entries.
d. Repeat, while index < numEntries,
　i. Let e be entries[index].
　ii. Set index to index + 1.

NotFoundsNotFounds

一旦まとめ

  • Set object は add する際に挿入の順序関係を維持する
  • Set.prototype.forEach や Set.prototype.entries、Set.prototype.values は挿入された順序を維持しつつ iterate する
NotFoundsNotFounds

考察

  • 重複する要素を挿入した場合、先に追加した要素と後に追加要素のどちらが優先されるのか
  • 順序を維持することによってどの程度のコストがかかるのか？(以後コレクションの要素数を n とする)
    • 極端な例だと list を使った実装の場合、順序は維持されるが基本的な操作の計算量は O(n)
    • HashTable を使うと平均計算量は定数時間(多分)だが、順序は維持されない
    • 平衡二分木などを使うと平均計算量は O(log n) だが SortedSet になりそう...?
  • 配列の重複を除くために以下のようなコードを書いた。挿入順序(元の配列の順序)が維持されることを仕様から確かめたい
    const array = [2, 1, 3, 2, 4, 5];
const distinctArray1 = Array.from(new Set(array));
const distinctArray2 = [...(new Set(array))];
    • Array.from と Set ( [ iterable ] ) の挙動を追う必要がありそう
NotFoundsNotFounds

重複する要素を挿入した場合、先に追加した要素と後に追加要素のどちらが優先されるのか

優先されるという表現はよくなかったかもしれない。
これは 24.2.3.1 Set.prototype.add ( value ) に書いてある。

  1. For each element e of S.[[\mathrm{SetData}]], do
    a. If e is not EMPTY and \mathrm{SameValueZero}(e, value) is true, then
    　i. Return S.

とある通り、重複した値が見つかった場合は削除して追加する（≒後に追加したものが採用される）のではなく見つかった時点で処理が終わる（≒後に追加した要素は破棄される）。

従って以下の例のようになる。

const s = new Set([2, 1, 3]);
s.add(1);
s.forEach((v) => console.log(v));
/*
2
1
3
*/
NotFoundsNotFounds

順序を維持することによってどの程度のコストがかかるのか？(以後コレクションの要素数を n とする)

実は Set の実装に関しては 24.2 Set Objects に書かれており、以下のような記述がある。

Set objects must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection. The data structure used in this specification is only intended to describe the required observable semantics of Set objects. It is not intended to be a viable implementation model.

HashTable を推奨している(?)っぽいが、平均アクセス時間が劣線形[1]であればよいらしい。
一方でここで言う access とはどのような操作だろう？ has は含まれそうだけど add や forEach などの iteration 操作は含まない？

脚注

  1. ちゃんと理解していないけど線形未満のオーダー O(log n) とかを要求しているという認識 ↩︎

NotFoundsNotFounds

これ以上は実装がどうなっているかを見るしかないと思うので具体的な実装を見に行く。
今回は実装例として v8 を参照する(hash: 8d8889ff725cfa0149ad64da53667cb55657c89d)。

v8 の実装は全くもって詳しくないが雰囲気で読んでいく。ちなみに手元のエディタで読んだ方がエディタの支援を受けられて読みやすいので clone することをおすすめする。

NotFoundsNotFounds

set という単語はどうも検索性が低いので Set.prototype などで検索をかける。

一番最初に見つかるのはこの辺。Set object の add 実装。
ちょうど読みたいところが見つかった。 https://chromium.googlesource.com/v8/v8/+/8d8889ff725cfa0149ad64da53667cb55657c89d/src/builtins/builtins-collections-gen.cc#1931

TF_BUILTIN(SetPrototypeAdd, CollectionsBuiltinsAssembler) {
  const auto receiver = Parameter<Object>(Descriptor::kReceiver);
  auto key = Parameter<Object>(Descriptor::kKey);
  const auto context = Parameter<Context>(Descriptor::kContext);

  ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE, "Set.prototype.add");

  key = NormalizeNumberKey(key);

  GrowCollection<OrderedHashSet> grow = [this, context, receiver]() {
    CallRuntime(Runtime::kSetGrow, context, receiver);
    return LoadObjectField<OrderedHashSet>(CAST(receiver), JSSet::kTableOffset);
  };

  StoreAtEntry<OrderedHashSet> store_at_new_entry =
      [this, key](const TNode<OrderedHashSet> table,
                  const TNode<IntPtrT> entry_start) {
        UnsafeStoreKeyInOrderedHashSetEntry(table, key, entry_start);
      };

  StoreAtEntry<OrderedHashSet> store_at_existing_entry =
      [](const TNode<OrderedHashSet>, const TNode<IntPtrT>) {
        // If the entry was found, there is nothing to do.
      };

  const TNode<OrderedHashSet> table =
      LoadObjectField<OrderedHashSet>(CAST(receiver), JSSet::kTableOffset);
  AddToOrderedHashTable(table, key, grow, store_at_new_entry,
                        store_at_existing_entry);
  Return(receiver);
}

雑に読むと OrderedHashSet というクラスを使っていそうだなということがわかる。

NotFoundsNotFounds

OrderdHashSet、なんとなく想像はつくが聞きなれないデータクラスなので調べてみると OrderdHashMap を継承したクラスが定義されている。
https://chromium.googlesource.com/v8/v8/+/8d8889ff725cfa0149ad64da53667cb55657c89d/src/objects/ordered-hash-table.h#271

また OrderedHashMap に関しては同ファイル上部にコメントで説明が書かれている。

// OrderedHashTable is a HashTable with Object keys that preserves
// insertion order. There are Map and Set interfaces (OrderedHashMap
// and OrderedHashTable, below). It is meant to be used by JSMap/JSSet.
//
// Only Object keys are supported, with Object::SameValueZero() used as the
// equality operator and Object::GetHash() for the hash function.
//
// Based on the "Deterministic Hash Table" as described by Jason Orendorff at
// https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables
// Originally attributed to Tyler Close.

key がソートされるのではなく、挿入順を保つ HashTable のよう。
Deterministic hash tables というらしい。知らなかった...

NotFoundsNotFounds

https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables

Background を読むと、ECMAScript の仕様ありきで挿入順序を維持して決定論的な反復を行う Map/Set の実装のためにつくられたっぽい。

具体的なアルゴリズムはさておき、パフォーマンスに関してみてみる。ここでは fill factor と呼ばれる充填率(?)をもとに定量的に分析している。

This would mean that the CloseTable would be 20% larger on average (27% larger on 64-bit).

通常の hash table と比べて dataTable や chain といったオーバーヘッドがあるためメモリ性能は高くない。

OpenTable が通常の Hash Table 実装で、CloseTable が提案されたもの。
どちらも期待としては定数オーダーで lookup が行えるようで、理論上は平均負荷ケース/低負荷ケースで OpenTable が優勢、高負荷なケースでは CloseTable が優勢っぽい。
一方でハッシュテーブルの再構築には O(N) のコストがかかるので注意。