検索概要5-ハッシュ・リスト検索(ハッシュ・テーブル)

基本概念

ハッシュ技術は、各キーワードkeyが1つの記憶位置f(key)に対応するように、記録された記憶位置とそのキーワードとの間に特定の関係fを確立するものである.

ここでfをハッシュ関数またはハッシュ関数と呼び、ハッシュ技術は記録を連続した記憶空間に記憶する.この連続した記憶空間をハッシュリストまたはハッシュテーブルと呼び、キーワード対応の記録記憶位置をハッシュアドレスと呼ぶ

ハッシュ処理は2つのステップに分けられる:1、記憶時にf選択アドレスで記憶する;2、検索時にf検索アドレスを利用して検索対比を行う.ストレージ方法であり、検索方法でもある

競合、2つの異なるキーワードが散乱関数で求めたハッシュアドレスが同じであれば競合する.

ハッシュ関数の構築方法
原則
1、ハッシュ・アドレスの計算に要する時間をできるだけ小さくする2、キーワードの長さを考慮する3、ハッシュ・テーブルの大きさを考慮する4、キーワードの分布状況5、検索の頻度を記録する

ダイレクトアドレス法f(key) = a*key + b;

数値解析法:キーワードを解析することにより、算出ハッシュアドレスの入力としてキーワードの一部を抽出する

二乗中法:キーワードの分布を知らず、桁数が大きくない場合に適している

折りたたみ法:987654321=>987+654+321=1962キーワード数が多い場合

除留剰余法f(key) = key mod p (p<=m，m )

乱数法f(key) =random(key)

散乱衝突の処理方法

アドレス法の開発、またはリニアプローブ法と呼ぶ.衝突が見つかった場合fi(key) = (f(key)+di) mod m ,(di = 1,2,3,4,5...m-1)fi(key) = (f(key)+di) mod m ,(di = 1^2,-1^2,2^2,-2^2...q^2,-q^2,q<=m/2)fi(key) = (f(key)+di) mod m ,(di )

再ハッシュ関数法で複数のハッシュ関数を用意し、衝突したら次の関数に置き換えるfi(key) =RHi(key), i = 1,2,3...k

チェーンアドレス法散乱テーブルには、各チェーンテーブルのヘッダポインタのみが格納されており、衝突した場合はチェーンテーブルにノードを1つ追加すればよい

共通オーバーフロー領域法により、すべての競合するキーワードを別のオーバーフローテーブルに格納

ハッシュ検索の実装

struct NODE
{
    int data;
    NODE * next; 
    NODE()
    {
        data = 0;
        next = NULL;
    }
};

class hashTable
{
private: NODE * elem;
         int num;
         int SIZE;
         
public: hashTable(int s):SIZE(s),num(0)
        {
            elem = new NODE[SIZE];
        }
        // 
        int myHash(int key)
        {
            return key%SIZE;
        }
        // 
        bool insertHash(int key)
        {
            NODE * addr = elem+myHash(key);
            while(addr!= NULL)
            {
                if (addr->data == key)
                    return false;
                addr = addr->next;
            }
            NODE *newNode = new NODE();
            newNode->data = key;
            newNode->next = (elem+myHash(key))->next;
            (elem+myHash(key))->next = newNode;
            return true;
        }
        // 
        bool searchHash(int key,NODE * addr)
        {
            addr = elem+myHash(key);
            while (addr != NULL)
            {
                if (addr->data = key)
                    return true;
                addr = addr->next;
            }
            return false;
        }
};

ハッシュ・リストのパフォーマンス分析

ハッシュ関数が均一か

競合の処理方法

ハッシュ表装填因子=表に記入された記録個数/ハッシュ表長.平均検索長さは主に充填因子の大きさに依存し,充填因子が大きいほど衝突の可能性が高く,検索にはより多くの時間がかかる.

reference

大話データ構造