JavaScript上級

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

 

導入

データ構造はプログラミングの基盤を成す重要な要素であり、特に業務においてはその選択がパフォーマンスやメンテナンス性に大きな影響を与えます。ここでは、上級者向けに、特定のシチュエーションでのデータ構造の選択や実装について考察します。実際の業務で遭遇するシナリオを通じて、データ構造の理解を深めることを目指します。

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

重要な概念の整理

データ構造を選ぶ際には、操作の頻度やデータの特性を考慮することが不可欠です。例えば、あるシステムではデータの挿入と削除が頻繁に発生し、検索が比較的少ない場合、リストやスタックが適しているかもしれません。一方、検索が多い場合は、ハッシュテーブルや木構造が有効です。ここでは、特にハッシュテーブルに焦点を当て、その実装と利用方法について詳しく見ていきます。

コード例（JavaScript）


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

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

    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]) return undefined;
        for (let pair of this.table[index]) {
            if (pair[0] === key) return pair;
        }
    }

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

// 使用例
const hashTable = new HashTable(50);
hashTable.set('name', 'John Doe');
console.log(hashTable.get('name')); // 'John Doe'
hashTable.remove('name');
console.log(hashTable.get('name')); // undefined

コードの行ごとの解説

  1. class HashTable {：ハッシュテーブルのクラスを定義します。
  2. constructor(size) {：コンストラクタでサイズを指定し、空の配列を初期化します。
  3. hash(key) {：キーをハッシュ化するメソッドを定義します。
  4. set(key, value) {：キーと値を設定するメソッドです。
  5. get(key) {：キーに基づいて値を取得するメソッドです。
  6. remove(key) {：キーを使ってエントリーを削除するメソッドです。

練習問題編

以下の練習問題に挑戦し、ハッシュテーブルの理解を深めてください。

  1. 問題1：ハッシュテーブルに複数の値を持つキーを設定する方法を考えてください。

    模範解答：キーに対して配列を値として設定し、同じキーで追加する際にはその配列に値を追加します。

  2. 問題2：ハッシュテーブルの衝突を解決する他の方法を提案してください。

    模範解答：オープンアドレス法やチェイニング法を用いることで衝突を解決できます。

  3. 問題3：ハッシュテーブルのサイズを動的に変更する方法を考えてください。

    模範解答：現在のサイズの2倍の新しい配列を作成し、既存のエントリーを再ハッシュして新しい配列に移動します。

  4. 問題4：ハッシュテーブルのパフォーマンスを測定する方法を説明してください。

    模範解答：平均的なケース、最悪のケースでの時間計算量を分析することで、パフォーマンスを評価できます。

まとめ

  • データ構造の選択は、業務でのパフォーマンスに直結します。
  • ハッシュテーブルは、特に検索の頻度が高い場合に有効なデータ構造です。
  • 衝突処理や動的サイズ変更など、実務での応用を考えることが重要です。
RELATED POST