アルゴリズム学習1週目.亥時

ハッシュ表

亥時の特徴
クイック検索とストレージ
探索と記憶が迅速に行えるのは,キー値が一対として存在し,キー値が配列のインデックスとして存在するため,平均探索/記憶の時間的複雑度はO(1)であるからである.
衝突が発生した場合,最悪の場合,時間複雑度はO(n)である.

長所

リソースが少なくても、大量のデータを効率的に管理できます.
データの取得、挿入、削除が速い

データキャッシュでよく使用されます.

短所

に適合しない順序配列

空間効率が低下した.

ハッシュ関数の依存性は高い.
https://hee96-story.tistory.com/48

ダイレクトアドレステーブル

ハッシュ・テーブルは、最初はアドレス・テーブルというデータ構造から直接開始される.

考えは簡単だ.
同じ配列でも2という数字を探すには、既存の演算が6回(0から6)必要ですが、アドレステーブルをそのまま使うと配列のインデックスがキーになるので、1回の演算で数字を探すことができます.
しかし、ダイレクトアドレステーブルは、格納したい値が大きいほど配列が大きくなるという欠点もあります.

ハッシュ表

直接アドレステーブルの欠点はハッシュテーブルによって補うことができる.

与えられたキーを入力するとhash関数で値が格納されます.
ここではハッシュ関数がどのように動作しているのか疑問に思うかもしれませんが、意外に簡単です.

function hashFunction (key){
  return key%7;
}

上記のコードに示すように,開発者は任意にハッシュ関数を作成して資料を格納することができる.(もちろん、各言語はハッシュ値をサポートしているので、ハッシュ値を書く必要はありません)

ハッシュ表の利点

ハッシュテーブルを使用すると、前述した直接アドレステーブル空間の浪費の欠点を解決することができる.
さらに、ハッシュ関数が分からない限り、鍵と値だけが未知であるため、セキュリティがより高い.

ハッシュ・テーブルの問題

ハッシュ・テーブルの空間は限られているため、ハッシュ関数を回転させることで値を割り当てると、ある瞬間、値を格納する空間で競合が発生します.これをハッシュ競合と呼ぶ.

ハッシュ競合

ハッシュが競合する場合は、この問題を解決するために複数の方法が使用されます.

オープンアドレスほう

リニアナビゲーション

ハッシュが競合する場合は、次の順序の空のbucketに値を入れます.

へいほうこうほう

ハッシュが競合する場合は、現在のbucketアドレスの平方位置に値を配置します.

ダブルハッシュ

ハッシュが競合する場合、別のハッシュ関数に対応するキーを入れて新しいアドレスを取得します.

線形探索は一次クラスタ化問題を生成し,二乗探索は二次クラスタ化問題を生成し,これらの問題は二重ハッシュ値によって解決される.

接続解除(フィルタ)

接続リストとして、競合が発生した場合、bucketに関連付けられたリストを作成します.

テーブル・サイズの再割り当て

テーブルがいっぱいになったり、リストが長すぎたりすると、ナビゲーションに失敗する可能性があります.
したがって、パケットがある程度以上充填されると、리사이징と呼ばれるハッシュテーブルを拡張する必要がある.ほとんどの使用率が70%程度に達すると,ハッシュテーブルを2倍程度に拡張できる.

解散リストアルゴリズム問題

オープンチャットルーム

https://programmers.co.kr/learn/courses/30/lessons/42888

コード#コード#

function solution(record) {
    var answer = [];
    const user = new Map();
    
    record = record.map(el=>el.split(' '))
    
    record.map(el=>{
        if(el[0]==='Enter' || el[0]==='Change') user.set(el[1],el[2])
    })  
    
    record.map(el=>{
        if(el[0]==='Enter'){
            answer.push(`${user.get(el[1])}님이 들어왔습니다.`)
        }else if(el[0]==='Leave'){
            answer.push(`${user.get(el[1])}님이 나갔습니다.`)
        }
    })
    
    return answer;
}

リファレンス

https://overcome-the-limits.tistory.com/9
https://evan-moon.github.io/2019/06/25/hashtable-with-js/
https://keepgoingforever.tistory.com/3