[巴金督の実戦アルゴリズム]ハッシュ

14564 ワード
ドックステーション 亥時 コセット コーディングテスト アルゴリズム#アルゴリズム# テキストリンク
情報の一部だけを覚えてマッチングします.
📍 鍵に対応する値を格納するデータ構造
  • 配列を使用すると、O(N)を使用して要素が検索され、ハッシュテーブルのすべての演算(挿入、Erase、Find、Update)はO(1)
    • である.
  • ハッシュ関数:任意の長さのデータを固定長のデータに対応する関数(一部の情報のみ表示!)
    ->配列として使用されるインデックス

    • コンフリクト問題

  • キーが等しい場合は
    • が発生する.
  • の衝突を阻止できない
  • 衝突が発生した場合の回避案
    • がある.

    1）衝突回避1-Chaining

  • 接続リスト
    • を使用
  • 実STLデータ構造使用Chaining
  • は、良好なハッシュ関数
    • を定義する必要がある.

    2）衝突回避2-Open Addressing

  • インデックスを基準として、要素がすでに含まれている場合は、隣に
    • を挿入する.
  • を削除するときは、スペース
    • を避けるために、ゴミの値を対応するセルに入れます.

    STL


    1) unordered_set

    #include <unordered_set>

void unordered_set_example() {
	unordered_set<int> s;
    s.insert(-10);
    s.insert(100);
    s.insert(15);
    s.insert(-10); // 중복 불가
    cout << s.erase(100) << '\n'; // 1 반환
    cout << s.erase(20) << '\n'; // 0 반환
    
    if (s.find(15) != s.end()) // 반환값의 형태는 iterator
    	cout << "15 is in s\n";
    else
    	cout << "15 is not in s\n";
    
    cout << s.size() << '\n'; // 2 반환
    cout << s.count(50) << '\n'; // unordered_set에서는 중복이 허용되지 않으므로 항상 1 또는 0 반환
    
    for (auto e : s) // range-based loop
    	cout << e << ' ';
    
    cout << '\n';
}

    2) unordered_multiset


    ✔｣繰り返し許可
    #include <unordered_set>

void unordered_multiset_example() {
	unordered_multiset<int> ms;
    ms.insert(-10);
    ms.insert(100);
    ms.insert(15);
    ms.insert(-10); // 중복 허용
    ms.insert(15);
    cout << ms.erase(15) << '\n'; // 15가 모두 다 지워짐!
    cout << ms.erase(ms.find(-10)) << '\n'; // 딱 한 개의 -10만 지워짐
    
    if (ms.find(15) != ms.end()) // 반환값의 형태는 iterator
    	cout << "15 is in ms\n";
    else
    	cout << "15 is not in ms\n";
    
    cout << ms.size() << '\n';
    
    for (auto e : ms) // range-based loop
    	cout << e << ' ';
    
    cout << '\n';
}

    3) unordered_map


    STL
  • キーに対応する値を検索
    #include <unordered_map>

void unordered_map_example() {
	unordered_map<string, int> m;
    m["hi"] = 123;
    m["bkd"] = 1000;
    m["gogo"] = 165;
    cout << m.size() << '\n'; // 3 반환
    m["hi"] = -7;
    
    if (m.find("hi") != m.end())
    	cout << "hi in m\n";
    else
    	cout << "hi is not in m\n";
    
    m.erase("bkd"); // ("hi", 123), ("gogo", 165)
    
    for (auto e : m)
    	cout << e.first << ' ' << e.second << '\n';
}
    • DP(Dynamic Programming)
    TypeScriptの型定義ファイルを共有しよう！