KodikKodik
{}const=>[]async()letfn</>var
開発アルゴリズム

ハッシュテーブル：コードを1000倍速くする秘密兵器

Googleが何十億ものページの中から必要なページを瞬時に見つける方法を考えたことがありますか？または、データベースが1秒に数百万のクエリを処理する方法について？それはハッシュテーブルのおかげです。この記事では、最も強力なデータ構造の1つがどのように機能するかを学び、それをゼロから実装する方法を学び、実際のプロジェクトでどこに適用するかを理解します。

К

Kodik

著者

5分で読める

ハッシュテーブルとは何ですか？なぜ必要ですか？

ハッシュテーブル（ハッシュマップ）は、キーと値のペアを格納し、データへの非常に高速なアクセスを提供するデータ構造です。平均して、検索、挿入、削除の操作は O(1) の定数時間で実行されます。つまり、テーブルに10個の要素が格納されているか1000万個の要素が格納されているかに関係なく、それらのいずれかにアクセスするのにかかる時間はほぼ同じです。

人生の簡単な例：

const userAges = {
    "Alexey": 28,
    "Maria": 25,
    "Dmitry": 32
};

console.log(userAges["Maria"]); // 25  - 即時アクセス！

ほとんどの現代のプログラミング言語では、ハッシュテーブルが組み込まれています。 dict Pythonで、 Map JavaScriptで、 HashMap Javaで、 map行く。

🔥 10万人以上の学生が参加中

理論を読むのに疲れた？
コーディングの時間だ！

Kodik — 実践でプログラミングを学ぶアプリ。AIメンター、インタラクティブなレッスン、実際のプロジェクト。

🤖 AI 24時間
🎓 修了証
💰 無料
🚀 始める
今日参加

ハッシュテーブルの仕組み

ボンネットの下のハッシュテーブルは通常の配列です。魔法は起こります ハッシュ関数キー（文字列、数値、またはオブジェクト）を配列のインデックスに変換します。

作業プロセス：

  1. キーのハッシュ: キー（例：「アレクセイ」）は、数値（例：42）を返すハッシュ関数を介してスキップされます

  2. インデックスの計算：ハッシュ結果は、除算演算の残りを使用して配列インデックスに変換されます： index = hash % array.length

  3. 値を保存する：値はこのインデックスを持つ配列のセルに保存されます

"アレクセイ" → hash ("アレクセイ") → 1892374 → 1892374％10 →インデックス4配列：[_, _, _, _, {key: "アレクセイ", value: 28}, _, _, _, _, _]

ハッシュ関数：システムの心臓部

良いハッシュ関数には、いくつかの特性が必要です。

  • 決定論 - 同じキーは常に同じハッシュを与えます

  • 均一性 — ハッシュは値の範囲全体に均等に分散する必要があります

  • スピード — ハッシュの計算は迅速であるべきです

  • 衝突の最小化 - 異なるキーは異なるハッシュを与える必要があります

文字列の単純なハッシュ関数の例:

function simpleHash(str, tableSize) {
    let hash = 0;
    for (let i = 0; i < str.length; i++) {
        hash = (hash + str.charCodeAt(i) * (i + 1)) % tableSize;
    }
    return hash;
}

console.log(simpleHash("Alexey", 100)); // たとえば、67
console.log(simpleHash("Maria", 100));   // 例：23

実際のシステムでは、MurmurHash、CityHash、またはSHA-256（特別な場合）のような暗号関数など、より複雑な関数が使用されます。

競合：2つのキーが1つの場所を要求する場合

衝突 2つの異なるキーがハッシュ後に同じインデックスを受け取ったときに発生します。これは避けられない問題です。なぜなら、可能なキーの数は通常、配列のサイズよりも大きいからです。

「アレクセイ」→インデックス4「ドミトリー」→インデックス4←衝突！

チェーンメソッド（チェーン）

衝突を解決する最も一般的な方法。配列の各セルには、1 つの値ではなく、同じインデックスを持つすべての値のリスト (チェーン) が格納されます。

class HashTable {
    constructor(size = 50) {
        this.table = new Array(size);
        this.size = size;
    }

    _hash(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash = (hash + key.charCodeAt(i) * (i + 1)) % this.size;
        }
        return hash;
    }

    set(key, value) {
        const index = this._hash(key);
        
        if (!this.table[index]) {
            this.table[index] = [];
        }
        
        // そのようなキーがすでに存在するかどうかを確認します
        for (let item of this.table[index]) {
            if (item[0] === key) {
                item[1] = value; // 値を更新しています
                return;
            }
        }
        
        // 新しいキーと値のペアを追加します
        this.table[index].push([key, value]);
    }

    get(key) {
        const index = this._hash(key);
        const bucket = this.table[index];
        
        if (!bucket) return undefined;
        
        for (let item of bucket) {
            if (item[0] === key) {
                return item[1];
            }
        }
        
        return undefined;
    }

    remove(key) {
        const index = this._hash(key);
        const bucket = this.table[index];
        
        if (!bucket) return false;
        
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                bucket.splice(i, 1);
                return true;
            }
        }
        
        return false;
    }
}

// 使用
const users = new HashTable();
users.set("Alexey", { age: 28, city: "Moscow" });
users.set("Maria", { age: 25, city: "St. Petersburg" });
users.set("Dmitry", { age: 32, city: "Novosibirsk" });

console.log(users.get("Maria")); // { age: 25, city: "サンクトペテルブルク" }users.remove("Alexey");
console.log(users.get("Alexey")); // undefined

オープンアドレス指定（Open Addressing）

衝突が発生した場合、チェーンを作成する代わりに、特定のアルゴリズムに従って配列内の別の空きセルを探します。

線形穿孔 — 次のセルを連続してチェックします。index、index+1、index+2...

class HashTableOpenAddressing {
    constructor(size = 50) {
        this.table = new Array(size);
        this.size = size;
        this.count = 0;
    }

    _hash(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash = (hash + key.charCodeAt(i) * (i + 1)) % this.size;
        }
        return hash;
    }

    set(key, value) {
        if (this.count / this.size > 0.7) {
            this._resize(); // 70%以上の充填時にサイズを拡大します
        }

        let index = this._hash(key);
        let i = 0;

        while (this.table[index] !== undefined && this.table[index].key !== key) {
            i++;
            index = (this._hash(key) + i) % this.size; // 線形穿孔
        }

        if (this.table[index] === undefined) {
            this.count++;
        }

        this.table[index] = { key, value };
    }

    get(key) {
        let index = this._hash(key);
        let i = 0;

        while (this.table[index] !== undefined) {
            if (this.table[index].key === key) {
                return this.table[index].value;
            }
            i++;
            index = (this._hash(key) + i) % this.size;
        }

        return undefined;
    }

    _resize() {
        const oldTable = this.table;
        this.size *= 2;
        this.table = new Array(this.size);
        this.count = 0;

        for (let item of oldTable) {
            if (item !== undefined) {
                this.set(item.key, item.value);
            }
        }
    }
}

二次サンプリング — 確認します： index, index+1², index+2², index+3²...

二重ハッシュ — 2 番目のハッシュ関数を使用してステップを計算します。

生産性と複雑さ

操作

平均的なケース

最悪のケース

挿入

O(1)

O(n)

検索

O(1)

O(n)

削除

O(1)

O(n)

負荷係数 = 要素数/配列サイズ

負荷係数が 0.7 より大きい場合、通常は rehashing — 新しいより大きな配列を作成し、すべての要素を移動します。

実際のユースケース

1. 結果のキャッシュ

class Cache {
    constructor() {
        this.cache = new Map();
    }

    async fetchUser(userId) {
        // キャッシュをチェックしています
        if (this.cache.has(userId)) {
            console.log('Received from cache');
            return this.cache.get(userId);
        }

        // データを読み込んでいます
        const user = await api.getUser(userId);
        
        // キャッシュに保存
        this.cache.set(userId, user);
        
        return user;
    }
}

2. 要素の頻度の計算

function countWords(text) {
    const wordCount = new Map();
    const words = text.toLowerCase().split(/\s+/);

    for (let word of words) {
        wordCount.set(word, (wordCount.get(word) || 0) + 1);
    }

    return wordCount;
}

const text = "JavaScript is a programming language JavaScript is popular";
console.log(countWords(text));
// Map { 'javascript' => 2, 'this' => 1, 'language' => 1, ... }... }

3. 重複の検索

function hasDuplicates(arr) {
    const seen = new Set();
    
    for (let item of arr) {
        if (seen.has(item)) {
            return true;
        }
        seen.add(item);
    }
    
    return false;
}

console.log(hasDuplicates([1, 2, 3, 4, 5])); // false
console.log(hasDuplicates([1, 2, 3, 2, 5])); // true

4. データベースのインデックス作成

データベースは、キーによるレコードの高速検索にハッシュインデックスを使用します。

-- В PostgreSQL
CREATE INDEX users_email_hash ON users USING HASH (email);

-- Теперь поиск по email молниеносный
SELECT * FROM users WHERE email = 'alex@example.com';

5. ユーザーの一意の識別子

class Session {
    constructor() {
        this.sessions = new Map();
    }

    createSession(userId) {
        const sessionId = this.generateSessionId();
        this.sessions.set(sessionId, {
            userId,
            createdAt: Date.now(),
            data: {}
        });
        return sessionId;
    }

    getSession(sessionId) {
        return this.sessions.get(sessionId);
    }

    destroySession(sessionId) {
        this.sessions.delete(sessionId);
    }

    generateSessionId() {
        return Math.random().toString(36).substring(2);
    }
}

6. Webフレームワークでのルーティング

class Router {
    constructor() {
        this.routes = new Map();
    }

    addRoute(path, handler) {
        this.routes.set(path, handler);
    }

    handleRequest(path) {
        const handler = this.routes.get(path);
        
        if (handler) {
            return handler();
        }
        
        return 'Not Found';
    }
}

const router = new Router();
router.addRoute('/home', () => 'Home Page');
router.addRoute('/about', () => 'About Page');

console.log(router.handleRequest('/home')); // Home Page - O(1)!

7.アナグラムと行のグループ化

function groupAnagrams(words) {
    const groups = new Map();

    for (let word of words) {
        // 文字をキーとして並べ替える
        const key = word.split('').sort().join('');
        
        if (!groups.has(key)) {
            groups.set(key, []);
        }
        
        groups.get(key).push(word);
    }

    return Array.from(groups.values());
}

console.log(groupAnagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat']));
// [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

JavaScriptのMap vs Object：どちらを選択しますか？

JavaScript には、ハッシュ テーブルを操作する方法が 2 つあります。

Object:

const obj = {};
obj.name = "Alexey";
obj['age'] = 28;

Map:

const map = new Map();
map.set('name', 'Alexey');
map.set('age', 28);

マップを使用するタイミング：

  • キーは文字列ではありません（オブジェクト、数値、関数）

  • 追加順に反復する必要があります

  • 要素の頻繁な追加/削除

  • 要素の正確な数を知る必要があります（map.size）

Objectを使用するタイミング：

  • キーは常に文字列です

  • JSON.stringify/parseが必要です

  • シンプルな構成

実用的なアドバイス

1. 正しい初期サイズを選択する

// 約1000個の要素があることがわかっている場合
const map = new Map(); // デフォルトは小さいサイズです
// vs
const users = new HashTable(2000); // リハッシュを避ける

2. キーのようなオブジェクトに注意する

const map = new Map();
const key1 = { id: 1 };
const key2 = { id: 1 };

map.set(key1, 'value1');
console.log(map.get(key2)); // 未定義！異なるオブジェクト

3. 使用していないデータをクリーンアップする

// 自動クリアにWeakMapを使用する
const cache = new WeakMap();
let user = { name: 'Alexey' };

cache.set(user, 'some data');
user = null; // データはWeakMapから自動的に削除されます

結論

ハッシュテーブルは、データベースからWebフレームワーク、コンパイラから検索エンジンまで、あらゆる場所で使用される基本的なデータ構造です。そのデザイン、競合解決、パフォーマンスを理解することで、より効率的な開発者になれます。

B コディケ ハッシュテーブルだけでなく、開発者にとって重要な他のテーマも多数解説しています。基本から高度なテクニックまで網羅しています。当社のコースには、実践的な課題と業界の実際のケースが含まれています。

Telegramチャンネルにご参加ください — ここには、フレンドリーな開発者コミュニティ、毎週の役立つ資料、興味深いタスクの分析、質問への回答があります。

一緒に成長しましょう！ 🚀

🎯先延ばしをやめよう

記事は気に入った？
実践の時間だ！

Kodikでは読むだけでなく、すぐにコードを書く。理論 + 実践 = 本当のスキル。

⚡即座に実践
🧠AIがコードを説明
🏆修了証

登録不要 • カード不要