[リソース構造]TableとHash

Table

格納されたデータがキーと値のペアで構成されるデータ構造をテーブルと呼ぶ.テーブルに鍵が存在しない値を保存できません.また、すべてのキーは重複しません.表は辞書構造や地図(map)と呼ばれることがある.
探索演算はO(1)の時間的複雑さを有する.
ex)マンションのメールアドレス-番号(キー)、メール(値)
辞書(dictionary)-単語(key)、単語の説明または内容(value)

typedef struct_empInfo {
	int empNum; //직원의 고유번호 : key
    	int age; // 직원의 나이 : value
} EmpInfo;

EmpInfo empInfoArr[1000]; // 직원들의 정보를 저장하기 위해 선언된 배열

上の列をテーブルと呼ぶのはちょっと足りません.テーブルがキーを決定した場合、その上で前回データを見つけることができる必要があります.すなわち,テーブルではキー(key)がデータを検索するツールである.

EmpInfo ei;
empInfoArr[ei.empNum] = ei; // 저장
ei = empInfoArr[eNum]; // 탐색

テーブルのキー値empNumは、データをその場所に格納できるようにインデックス値である必要があります.
ここでの問題は、従業員が99999999999999であれば、大きな並びが必要で、どのような問題が発生するのでしょうか.

従業員固有番号の範囲は、配列のインデックス値として使用するのに適していません.

人の従業員の固有の番号範囲を収容するには、非常に大きな配列が必要です.

これらの問題を解決したのはハッシュ関数である.

Hash Table

Hash Tableは、関連配列構造を用いてキーに値を格納するデータ構造である.鍵(key)は、ハッシュ関数によってハッシュに変更され、ハッシュ値と一致してリポジトリに格納される.
関連配列構造(関連配列):1つのキーと1つの値1:1に関連する資料構造.したがって、キーを使用して値をエクスポートできます.

こうぞう

キー(キー):一意の値.ハッシュ関数の入力になります.様々な長さの値を指定できます.この状態で最終リポジトリに保存する場合は、異なる長さのリポジトリを構成する必要があるため、スペース効率を向上させるには、値をハッシュ関数に変換して格納する必要があります.

値(値):最終的にリポジトリ(bucket,slot)に格納される値は、格納、削除、検索、アクセスのために鍵と一致する必要があります.

ハッシュ関数(Hash Function):鍵(キー)をハッシュ(hash)に変換するために使用される.異なる長さの鍵(鍵)を一定の長さのハッシュ(hash)に変更することで、リポジトリの効率的な実行を支援できます.しかし,異なるキーが同じハッシュになるとハッシュ競合(Hash Collision)と呼ばれ,ハッシュ競合を引き起こす確率を最大限に低減する関数を作成することが重要である.

ハッシュ(Hash):ハッシュ関数(Hash Function)の結果は、リポジトリ(bucket,slot)で値(value)と一致して格納されます.

ハッシュ関数の例

typedef struct_empInfo {
	int empNum; //직원의 고유번호 : key
    	int age; // 직원의 나이 : value
} EmpInfo;

int getHashValue(int empNum) {
	return empNum % 100;
}

例えば、上記のコードとは異なり、社員の固有番号は、入社年度の4つの位置と、入社順の4つの位置からなる.いずれ1000人を超えることになるが、現在は100人以上を採用する可能性がある.したがって、アレイの長さを最小限に抑えるために努力していると仮定し、getHashValue関数で解を得ます.
hash関数により広範囲の鍵を小範囲の鍵に変更します.しかし、20210103と2012003の固有番号を持つ職員がいれば、03という値はハッシュ値を持つという問題が生じる.このような状況を衝突と呼ぶ.

挿入

時間複雑度:O(1)
最悪の場合はO(n)になる可能性があります.

削除

時間複雑度:O(1)
最悪の場合はO(n)になる可能性があります.

ブラウズ(Search)

時間複雑度:O(1)
最悪の場合はO(n)になる可能性があります.

ハッシュ競合

競合しない限り、ハッシュ・テーブルは、挿入、削除、およびブラウズの間、平均O(1)時間の複雑さを有する効率的なデータ構造である.

John SmithはSandra Deeのhashと同じです.これをHash Collisionと呼ぶ.ハトの巣の原理によれば、このような状況は必然的に現れる.

鳩の巣の原理:n+1個の鳩の巣がn個の鳩の巣に入り、少なくとも1個以上の鳩の巣が2個以上の鳩の巣がある.

ハッシュ競合の解決方法

クローズドアドレッシングメソッド

Chaining

これは閉鎖アドレス法(closed addressing method)である.閉じたアドレスメソッドは、何が起こっても(衝突が発生しても)、自分の場所に保存されることを意味します.
これを可能にするには、価格を貯蔵するために複数の場所を手配するしかありません.複数の座席を手配する方法には、並べ替えの方法と接続リストの方法があります.
ただし、アレイが競合していない場合は、メモリが大量に消費され、競合の最大回数を決定する必要があるため、リストを使用してスロットを接続する方法は、閉じたアドレス方法を表します.

Sandra Deeの価格は153になります.もう価格があります.既存のJohn Smith値の後に接続します.
すなわち、フィルタリングは、データを格納する際に、リポジトリが競合した場合に、その値を既存の値に関連付ける方法である.
メモリが比較的少ないという利点がありますが、ハッシュ・テーブルのデータが接続され続けると(傾斜現象が発生すると)、検索効率が低下するという欠点があります.

in Java

HashMap vs HashTable

同期がサポートされているかどうかは異なります.

// 해시테이블의 put
public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }
    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }
    addEntry(hash, key, value, index);
    return null;
}

// 해시맵의 put
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

並列処理時にリソース同期を考慮する必要がある場合はハッシュテーブル(HashTable)を使用し、並列処理を行わない場合やリソース同期を考慮しない場合はハッシュテーブル(HashMap)を使用します.

オープンアドレッシングメソッド

競合が発生した場合は、別の場所として保存します.ハッシュを探すルールによって,オープンアドレス方式は3つに分けられる.

1.線形調査法

これは、競合が発生した場合に、その隣の位置が空であるかどうかを確認し、空である場合にその位置に保存する方法です.隣の位置が空でない場合は、もう1つの格子を移動して位置を観察します.すなわち、f(k)+1->f(k)+2->f(k)+3.である.展開しかし,線形調査法の欠点は,衝突回数が増えるにつれてクラスタ現象が現れることである.

2.二次調査法

これは線形調査法の欠点を克服するために設計された方法である.衝突が発生した場合は、遠くから空き地を探す方法です.f(k)+1^2 -> f(k)+2^2 -> f(k)+3^2...順次展開する.

3.ツイストワイヤ

2回目の調査法でも、ハッシュ値が同じであれば、競合が発生したときに空のスロットを見つけるために、アクセス先が常に同じであるという問題があります.線形調査法よりは優れているが,近接しているスロットを中心にクラスタ現象が発生する確率は依然として高い.
二次調査法は遠くで空白を探していますが、空白を選ぶ方法は1マス、4マス、9マス…規則がある.このように不規則に空白空間を探す方法が二重ハッシュ法である.2つのハッシュ関数が書かれているので名前が付けられます.

第1のハッシュ関数:鍵に基づいて記憶位置を決定するために使用される.

2第2のハッシュ関数:競合が発生した場合にいくつかのグリッドの後ろを表示するかを決定するために使用されます.

比較