hashmapの実装

hashmap: キーと値の組み合わせを保管するためのデータ構造。特定のバケットに割り当て、そのバケットに値を格納する。

2つ以上のキーが同じインデックスにハッシュされる場合、ハッシュ衝突が発生します。この時の解決法は主に2通り。

• チェイン法

  • 同じインデクスに対応する要素を連結リストで繋げる

• オープンアドレス法

  • 別の空いているバケットを見つけるまでハッシュテーブル内を探索する。
    • 探索方法: 線形探索、二次探索、ダブルハッシュ

計算量

operation	average time complexity	worst time complexity
Search	O(1)	O(n)
Insert	O(1)	O(n)
Remove	O(1)	O(n)

チェイン法での実装

class MyHashMap {
public:
    const int array_size = 10002;
    std::vector<std::vector<std::tuple<int, int>>> hashmap;

    MyHashMap() 
        : hashmap(array_size, std::vector<std::tuple<int, int>>()) { // hashmapの初期化
    }

    int convertToIndex(int i) { return i % array_size; }

    void put(int key, int value) {
        int index = convertToIndex(key);
        for (int i = 0; i < hashmap[index].size(); i++){
            auto t = hashmap[index][i];
            auto [k, v] = hashmap[index][i];
            
            if (k == key){ // if there is already a key
                hashmap[index][i] = std::make_tuple(key, value);
                return;
            } 
        }
        tuple<int, int> t = {key, value};
        hashmap[index].push_back(t);
    }

    int get(int key) {
        int index = convertToIndex(key);
        for (int i = 0; i < hashmap[index].size(); i++){
            auto [k, v] = hashmap[index][i];
            
            if (k == key){ // if there is already a key
                return v;
            } 
        }
        return -1;
    }

    void remove(int key) {
        int index = convertToIndex(key);
        for (int i = 0; i < hashmap[index].size(); i++){
            auto t = hashmap[index][i];
            auto [k, v] = hashmap[index][i];
            
            if (k == key){ // if there is already a key
                // 削除
                hashmap[index].erase(hashmap[index].begin() + i);
            } 
        }
    }
};

なんで配列の長さを素数にするといいの？