はじめに: ハッシュテーブルは「名前で素早く取り出す」仕組み
これまで、配列、探索、計算量、ハッシュ関数などを見てきました。今回扱うハッシュテーブルは、それらの知識がつながるデータ構造です。
ハッシュテーブルは、キーと値を対応させて保存し、キーを使って値を素早く取り出す仕組みです。たとえば、ユーザーIDからユーザー情報を取り出す、商品コードから商品名を取り出す、設定名から設定値を取り出す、といった場面で使われます。
配列を先頭から順番に探す場合、データが多いほど時間がかかります。一方、ハッシュテーブルでは、キーから保存場所を計算することで、目的の値へ直接近づけます。
JavaScriptでは、実務でハッシュテーブルを一から書くことは多くありません。多くの場合は Map やオブジェクトを使います。それでも、裏側の考え方を知っておくと、なぜキーで素早く取り出せるのかが見えやすくなります。
ハッシュテーブルは、キーから値を素早く取り出すためのデータ構造です。
ハッシュテーブルの基本: キーと値を対応させる
ハッシュテーブルでは、データをキーと値の組み合わせで保存します。
キー: "user:1"
値: "田中さん"配列では、array[0] や array[1] のように数値の添字で値を取り出します。ハッシュテーブルでは、"user:1" のようなキーを使って値を取り出します。
JavaScriptの Map を使うと、キーと値の対応を簡単に表せます。
const users = new Map();
users.set("user:1", "田中さん");
users.set("user:2", "佐藤さん");
console.log(users.get("user:1"));このコードでは、"user:1" というキーに "田中さん" という値を対応させています。あとから同じキーを指定すれば、対応する値を取り出せます。
ハッシュテーブルの重要な点は、「何番目に入っているか」ではなく「どのキーに対応しているか」でデータを扱うことです。
ハッシュテーブルでは、キーと値を対応させることで、意味のある名前やIDからデータを取り出せます。
ハッシュ関数で保存場所を決める
ハッシュテーブルでは、キーをそのまま配列の添字として使うわけではありません。文字列のキーを、配列の位置として使える数値に変換する必要があります。
この変換を行うのがハッシュ関数です。ハッシュ関数は、キーを受け取り、ハッシュ値と呼ばれる数値を返します。
たとえば、かなり単純化すると、文字コードを合計して数値にするような関数を考えられます。
function hash(key, size) {
let total = 0;
for (const char of key) {
total += char.charCodeAt(0);
}
return total % size;
}
console.log(hash("apple", 10));charCodeAt(0) は、文字に対応する文字コードを返します。合計した値を配列サイズで割った余りにすれば、0 から size - 1 までのインデックスにできます。
このインデックスが、ハッシュテーブル内の保存場所になります。保存場所のことをバケットと呼ぶこともあります。
実際のハッシュ関数は、もっと偏りが少なくなるように工夫されています。ここでは、仕組みを理解するために単純な例を使っています。
ハッシュ関数は、キーを配列の保存場所として使える数値に変換する役割を持ちます。
JavaScriptで小さなハッシュテーブルを作る
学習用に、小さなハッシュテーブルを実装してみます。まずは衝突を深く考えず、キーからインデックスを計算して値を保存する流れを見ます。
class SimpleHashTable {
constructor(size = 10) {
this.buckets = new Array(size);
}
hash(key) {
let total = 0;
for (const char of key) {
total += char.charCodeAt(0);
}
return total % this.buckets.length;
}
set(key, value) {
const index = this.hash(key);
this.buckets[index] = value;
}
get(key) {
const index = this.hash(key);
return this.buckets[index];
}
}
const table = new SimpleHashTable();
table.set("apple", "りんご");
table.set("banana", "バナナ");
console.log(table.get("apple"));set() では、キーからインデックスを計算し、その場所に値を保存しています。get() でも同じキーから同じインデックスを計算し、その場所の値を取り出しています。
このように、同じキーを同じハッシュ関数に通せば、同じ保存場所を計算できます。これが、ハッシュテーブルで値を取り出せる基本の仕組みです。
ただし、この実装には大きな問題があります。違うキーでも、同じインデックスになることがあるからです。
ハッシュテーブルでは、保存するときも取り出すときも、同じハッシュ関数でキーから保存場所を計算します。
衝突が起きたらどうするか
違うキーなのに同じ保存場所になってしまうことを、衝突と呼びます。
たとえば、"apple" と "melon" が同じインデックスになったとします。先ほどの単純な実装では、あとから保存した値が前の値を上書きしてしまいます。これでは、正しくデータを取り出せません。
衝突への対応方法はいくつかあります。ここでは、同じバケットに複数のキーと値のペアを入れる方法を見ます。この方法はチェイン法と呼ばれます。
class HashTable {
constructor(size = 10) {
this.buckets = Array.from({ length: size }, () => []);
}
hash(key) {
let total = 0;
for (const char of key) {
total += char.charCodeAt(0);
}
return total % this.buckets.length;
}
set(key, value) {
const index = this.hash(key);
const bucket = this.buckets[index];
for (const pair of bucket) {
if (pair.key === key) {
pair.value = value;
return;
}
}
bucket.push({ key, value });
}
get(key) {
const index = this.hash(key);
const bucket = this.buckets[index];
for (const pair of bucket) {
if (pair.key === key) {
return pair.value;
}
}
return undefined;
}
}この実装では、各バケットを配列にしています。同じインデックスになったキーと値のペアは、同じバケット内に追加されます。取り出すときは、バケットの中から目的のキーを探します。
衝突が少なければ、バケット内の探索は短く済みます。しかし衝突が多くなると、結局バケットの中を順番に探す時間が増えます。そのため、ハッシュ関数の偏りやバケット数が重要になります。
ハッシュテーブルでは、違うキーが同じ保存場所になる衝突に対応する必要があります。
JavaScriptの Map とオブジェクトとの関係
実務では、ハッシュテーブルを自分で実装するより、JavaScriptの Map やオブジェクトを使うことがほとんどです。
const cache = new Map();
cache.set("article:100", { title: "ハッシュテーブル入門" });
console.log(cache.get("article:100"));Map は、キーと値の対応を扱うための標準的な仕組みです。キーには文字列だけでなく、オブジェクトなども使えます。
オブジェクトも、文字列のキーから値を取り出す形でよく使われます。
const labels = {
draft: "下書き",
published: "公開済み",
};
console.log(labels.published);厳密な内部実装は処理系によって異なりますが、キーから値を効率よく取り出すという考え方は、ハッシュテーブルの理解とつながります。
JavaScriptの Map やオブジェクトは、キーと値を対応させて扱う身近な仕組みです。
試験ではどう問われるか
基本情報技術者試験では、ハッシュ表、ハッシュ関数、衝突、探索効率が問われることがあります。
ハッシュテーブルのポイントは、キーから保存場所を計算することです。配列を先頭から順番に探す線形探索とは違い、うまく分散できていれば目的の値へ素早く近づけます。
一方で、衝突が増えると効率が落ちます。チェイン法では、同じバケットに多くのデータが集まると、そのバケット内を順番に探す必要があります。
試験では、「平均的には高速に探索できるが、衝突への対応が必要」という理解が大切です。
ハッシュテーブルは平均的には高速に検索できますが、衝突が増えると効率が落ちます。
実務ではどう使われるか
Web開発では、ハッシュテーブル的な考え方が多くの場面に出てきます。
たとえば、IDからユーザー情報を取り出す、商品コードから商品データを取り出す、設定名から設定値を取り出す、といった処理です。配列を毎回先頭から探すより、キーで直接取り出せる形にしておくと、コードも読みやすくなります。
また、一度取得したデータを一時的に保存するキャッシュでも、キーと値の対応はよく使われます。
const userCache = new Map();
userCache.set("user:1", { name: "田中さん" });
if (userCache.has("user:1")) {
console.log(userCache.get("user:1"));
}大量のデータを扱うときは、どのデータ構造を使うかで処理の見通しが変わります。ハッシュテーブルを理解していると、配列で探すべき場面と、キーで取り出す形にしたほうがよい場面を判断しやすくなります。
Web開発では、IDや名前などのキーからデータを取り出す場面でハッシュテーブルの考え方が役立ちます。
まとめ: ハッシュテーブルは高速な検索の土台
ハッシュテーブルは、キーと値を対応させて保存するデータ構造です。キーをハッシュ関数に通して保存場所を計算することで、目的の値へ素早く近づけます。
ただし、違うキーが同じ保存場所になる衝突が起きることがあります。衝突に対応するために、同じバケットに複数のペアを入れるチェイン法などの考え方があります。
実務では、JavaScriptの Map やオブジェクトを使うことが多いです。それでも、ハッシュテーブルの仕組みを知っておくと、キーで値を取り出す処理や、データ構造の選び方を理解しやすくなります。
ハッシュテーブルを理解すると、探索、配列、ハッシュ関数、計算量の知識が実務のデータ処理につながります。
コメント