JavaScript中級

中級 JavaScriptで学ぶデータ構造｜練習問題編

 

導入

データ構造は、プログラミングの基盤を形成する重要な要素です。特に中級レベルのエンジニアにとって、データ構造の理解は業務において効率的なアルゴリズムを選択し、実装するための必須スキルです。本記事では、JavaScriptを用いて特定のデータ構造の実装を通じて、実務での活用方法を探ります。

教科書レベルの解説（データ構造）

重要な概念の整理

データ構造には様々な種類がありますが、ここでは「ハッシュテーブル」に焦点を当てます。ハッシュテーブルは、キーとバリューのペアを効率的に管理するためのデータ構造で、特に検索や挿入の速度が重要なシナリオで有効です。例えば、ユーザー情報を管理するアプリケーションでは、ユーザーIDをキーとしてハッシュテーブルを利用することで、迅速なデータアクセスが可能になります。

ただし、ハッシュテーブルには「衝突」という問題があります。異なるキーが同じハッシュ値を持つ場合、どのようにデータを管理するかが課題となります。この問題に対処するための手法として、チェイニングやオープンアドレス法などがあります。

コード例（JavaScript）


// シンプルなハッシュテーブルの実装
class HashTable {
    constructor(size) {
        this.table = new Array(size);
    }

    hash(key) {
        let hash = 0;
        for (let char of key) {
            hash += char.charCodeAt(0);
        }
        return hash % this.table.length;
    }

    set(key, value) {
        const index = this.hash(key);
        if (!this.table[index]) {
            this.table[index] = [];
        }
        this.table[index].push([key, value]);
    }

    get(key) {
        const index = this.hash(key);
        if (this.table[index]) {
            for (let pair of this.table[index]) {
                if (pair[0] === key) {
                    return pair;
                }
            }
        }
        return undefined;
    }
}

// 使用例
const myHashTable = new HashTable(50);
myHashTable.set('user1', { name: 'Alice', age: 30 });
console.log(myHashTable.get('user1'));

コードの行ごとの解説

  1. class HashTable { – ハッシュテーブルのクラスを定義。
  2. constructor(size) { – コンストラクタでテーブルのサイズを初期化。
  3. this.table = new Array(size); – 指定されたサイズの配列を生成。
  4. hash(key) { – キーをハッシュ値に変換するメソッド。
  5. let hash = 0; – ハッシュ値を初期化。
  6. for (let char of key) { – キーの各文字を処理。
  7. hash += char.charCodeAt(0); – 各文字のASCIIコードを加算。
  8. return hash % this.table.length; – ハッシュ値をテーブルのサイズで割ってインデックスを取得。
  9. set(key, value) { – キーとバリューをセットするメソッド。
  10. const index = this.hash(key); – キーからインデックスを取得。
  11. if (!this.table[index]) { – インデックスが空なら配列を初期化。
  12. this.table[index].push([key, value]); – キーとバリューのペアを追加。
  13. get(key) { – キーに対応するバリューを取得するメソッド。
  14. if (this.table[index]) { – インデックスが存在するか確認。
  15. for (let pair of this.table[index]) { – ペアをループしてキーを比較。
  16. return pair; – 一致するキーのバリューを返す。
  17. return undefined; – キーが見つからない場合はundefinedを返す。

練習問題編

以下の練習問題に取り組んで、ハッシュテーブルの理解を深めましょう。

  1. 問題1: ハッシュテーブルに衝突が発生した場合、どのようにデータを管理しますか？具体的な手法を2つ挙げてください。

    2. 模範解答: 1. チェイニング：同じインデックスに複数の要素をリストで保持する。2. オープンアドレス法：次の空いているインデックスにデータを保存する。

  2. 問題2: 上記のハッシュテーブルに対して、削除メソッドを追加してください。

    3. 模範解答: 

    
remove(key) {
    const index = this.hash(key);
    if (this.table[index]) {
        this.table[index] = this.table[index].filter(pair => pair[0] !== key);
    }
}

  3. 問題3: ハッシュテーブルのサイズを変更する場合、どのようにデータを再配置しますか？

    4. 模範解答: 新しいサイズのテーブルを作成し、既存のデータをすべて新しいテーブルに再挿入する。

  4. 問題4: ハッシュテーブルのロードファクターとは何ですか？その理想的な値はどれくらいですか？

    5. 模範解答: ロードファクターは、テーブルの要素数とテーブルサイズの比率。理想的な値は0.7程度が推奨される。

まとめ

  • ハッシュテーブルは、データの迅速な検索や挿入を可能にする強力なデータ構造です。
  • 衝突処理の手法を理解することで、ハッシュテーブルの性能を向上させることができます。
  • 実際の業務での使用を想定し、ハッシュテーブルの実装や運用を考慮することが重要です。
RELATED POST