JavaScriptハッシュ表

ハッシュ表

 ハッシュ関数を使用してkeyを固有インデックスに変換し、値をハッシュテーブルに格納します.ハッシュ関数を使用してindexを作成します.ハッシュ・テーブルには、ハッシュ関数を使用して生成されたインデックスが重複する可能性があるという問題があります.従って,ハッシュ関数は線形プローブ法,二乗プローブ法,二重復号化などのアルゴリズムを用いて問題を解決する必要がある.
 ハッシュ・テーブルは、ハッシュ関数によって作成されたインデックスと値を使用してハッシュ・テーブルに格納されます.したがって、追加または削除する要素のキー(ハッシュ関数からindexに変換)がわかっている場合は、一定の時間的複雑さがあります.
では、なぜこの不安定な「ハッシュ関数」を使うのでしょうか.配列のように直接保存すれば問題はなく、ハッシュ関数で生成されたインデックスが競合する心配もありません.
 ハッシュ関数を使用して配列に直接格納するのではなく、検索結果を検索する場合は、最大キー値を知る必要があります.また,キー値が大きくなるとフルナビゲーションが必要になる可能性があるため,実用的ではない.キー値が固定されていない場合(ex.昇順0,1,2.)キー値は配列に広く分布し、配列のサイズが大きくなり、メモリの無駄になる可能性があります.したがって、ハッシュ関数を使用してデータを追加するユーザーと、データを抽出するユーザーのインデックスを考慮する必要がない場合は、キー値を使用するだけで必要な要素を追加または削除できます.
 ここでは、ハッシュ関数ではなくJavaScriptでハッシュテーブルを実装します.ハッシュテーブルを実装する方法としては,JavaScript配列を用いる方法とオブジェクトを用いる方法,およびMapとSetを用いる方法がある.

配列を使用したハッシュ・テーブルの作成

const hashTableByArray = [];
hashTableByArray["key"] = 100;
hashTableByArray["key2"] = "Hello";
hashTableByArray[1234] = 1234;

console.log(hashTableByArray["key"])
console.log(hashTableByArray["key2"])
console.log(hashTableByArray[1234])

delete hashTableByArray["key"];
console.log(hashTableByArray["key"]);
console.log(hashTableByArray);

 空の配列を作成する(JavaScriptで配列を作成するときにサイズを考慮しない点は、いつでも便利です.)key値に基づいてvalueを格納します.ここで、value 1234は、文字列ではなく数値1234をキー値として格納する.

出力時にはキー値として1234が入力されるが、出力は正常である.これは、1234が文字列に自動的に変換されるためです.同様に、配列内の要素を削除すると、その要素の値は空になりますが、配列のサイズは変わりません.

オブジェクトを使用したハッシュ・テーブルの作成

const hashTableByObject = {};
hashTableByObject["key"] = 100;
hashTableByObject["key2"] = "hello";
hashTableByObject[1234] = 1234;

const obj = { B: 32};
hashTableByObject[obj] = 22;
console.log(hashTableByObject[obj]);

console.log(hashTableByObject["key"]);
console.log(hashTableByObject["key"]);
console.log(hashTableByObject[1234]);

delete hashTableByObject["key"];
console.log(hashTableByObject);

 配列と同様にkeyとvalueを追加します.違いはdeleteを使用する場合、オブジェクトは保持されません.削除配列とオブジェクトの値を出力するとundefinedが出力されますが、配列は空であり、オブジェクトは存在しません.また、オブジェクトはキー値として使用できません.

Mapを使用したハッシュ・テーブルの作成

const map = new Map();
map.set("key", 100);
map.set("key2", "Hello");
map.set(1234, 1234);
console.log("map[]", map["key"]); //undefined
console.log("map[]", map["key2"]); //undefined
console.log("map[]", map[1234]); //undefined
console.log("map.get()", map.get("key"));
console.log("map.get()", map.get("key2"));
console.log("map.get()", map.get(1234));

const obj = { a: 1 };
map.set(obj, "A1");
console.log("map[]", map[obj]); // undefined
console.log("map.get()", map.get(obj)); // object를 key로 사용

console.log(map.keys());
console.log(map.values());

map.delete("key");
map.clear();
console.log(map);

 Mapではset、get、delete、clear関数を使用できます.配列のように[{key}]を使用して値を決定することはできません.getを使用する必要があります.要素を追加する場合もsetを使用します.また、オブジェクトや配列とは異なりobjectをキーとして使用できます.clearを使用してMapオブジェクトを空にします.

Setを使用したハッシュ・テーブルの作成

const set = new Set();
set.add("key");
set.add("key2");
set.add("key3");

console.log(set.has("key"));
console.log(set.has("key3"));
set.delete("key2");
console.log(set.has("key2"));
console.log(set.size);
console.log(set);
set.clear();
console.log(set);

 Setを使用してキー値と同じ値をテーブルに格納します.add関数を使用して追加し、deleteを使用して削除できます.テーブルに要素が存在するかどうかを決定するにはhas関数を使用します.has関数はtrue/falseを返します.Mapとの最大の違いは、Key Valueが同じ値で格納されていることです.

 ハッシュテーブルを実現する最も重要な部分はハッシュ関数を実現することだと思います.安定したハッシュテーブルは、競合しないハッシュ関数を有する場合にのみ達成される.ハッシュ関数を実現する方法は後で勉強します...