key に対して value をもつデータ構造です
最近の言語なら標準で使えることも多いですが 使えない環境でそれがほしいことがあったので自分で簡単に実装してみようかなと
単にデータの保持とアクセス方法を key-value 形式にしたいだけだったので パフォーマンスは気にせず配列に key と value を持たせるようにしました
JavaScript で書くとこういう感じでデータを保持しアクセスします
const data = [
{ key: "foo", value: 1 },
{ key: "bar", value: 2 },
]
const value = data.find(x => x.key === "bar")?.value
順番も保持できてますし データ数が少ないなら特に問題もないです
ですが 本来の Map 相当の機能はこんな実装はしないはず
100 万件のデータがあって一番最後のを取得すると 100 万件を探索することになりますし
考えてみるとどう実装してるのでしょうか?
昔 C とか低レイヤー言語を使ってたころにアルゴリズムの説明を薄っすらと読んだような記憶はありますが 具体的なことはおぼえてないです
ハッシュやハッシュマップみたいな呼ばれ方もするデータ構造ですし ハッシュ値を使ってるはずですが どう使ってるのでしたっけ?
key にそのまま使うなら 実装のために Map 相当の機能が必要になって矛盾します
MD5 や SHA みたいな文字列をイメージするから どう使うの?と疑問に思ってましたが本来は数値データのはず
文字なのは 16 進数などわかりやすく表現するからです
ハッシュ値を数値として使えば配列のインデックスアクセスが使えます
アクセスイメージ
const calcHash = (data) => {
return // 0 ~ 99 の数値を返す
}
const arr = Array(100)
arr[calcHash(key)] = value
console.log(arr[calcHash(key)])
これなら実現できそう と思ったものの ハッシュ値が 100 パターン程度しかないと重複しそう
100 万パターンくらいあれば 大抵のケースでは重複しなさそうですが 保存領域も 100 万パターン分確保するので配列の長さが 100 万になります
Map のインスタンス 1 つごとに 100 万もメモリを確保するのは かなりムダがあります
value にアドレスが入って 4 バイトだとしても 4MB ほど
Map インスタンスなんてたくさん作ることがよくあるのに 1000 個作れば 4GB って実用性なさすぎです
それに 100 万パターン用意しても運が悪ければ 数個で異なるデータのハッシュ値が重複することはありえるわけですし
これじゃダメそうですね
せっかくなので bing に聞いてみました
ハッシュ値の数値をインデックスにするところまではあってたようです
重複は避けられないので 大きすぎる領域を確保するのではなく 重複したときも問題なく動くようにするという方法でした
2 種類方法があるようです
○ インデックスアクセスで参照できるデータをリスト型として 同じハッシュ値だったデータを全部まとめて持つ
○ すでにデータが入っていたら再ハッシュして別のハッシュ値を割り当てる
言われてみると聞き覚えがあるような
でも これだとどっちの方法でも 異なるデータで同じハッシュ値になったら 同じなのに元データが異なるってことをどうやって判断するの?と疑問が出てきます
ただこれは key そのものも保持していて key が一致するかを順番にチェックするようです
ハッシュ値が常に 0 だったら 最初に書いたコードみたいなことになります
これをハッシュ値で分散してる分 一致チェックする量が減るということのようです
スクリプト言語など高レイヤーの言語ばかり書いてると低レイヤー部分はけっこう忘れてますね