5分でハッシュ・テーブルを迅速に実現

ハッシュテーブル(Hash table、ハッシュリストとも呼ばれる)は、キーに基づいて(Key)を使用して、メモリに格納されている場所のデータ構造に直接アクセスします.つまり、キー値に関する関数を計算することで、必要なクエリーのデータをテーブルの1つの場所にマッピングしてレコードにアクセスし、検索速度を速めます.このマッピング関数はハッシュ関数と呼ばれ、レコードを格納する配列はハッシュリストと呼ばれます.--ウィキペディア
いくつかの合理的な仮定の下で,ハッシュテーブルにおけるすべての動作の時間的複雑さはO(1)と簡単に見なすことができる.キーのハッシュ値を計算することによって、ハッシュ・テーブルのキー値の位置を迅速に特定します.良いハッシュテーブルを実現する鍵は、良いハッシュアルゴリズムとハッシュ競合を処理する方法である.一般的な単純ハッシュアルゴリズムはBKDRHAsh,APHash,DJBHash,JSHash,RSHashである.複雑なのはMD 5とSHA 1の流れです.ハッシュアルゴリズムの良し悪しはハッシュテーブルアクセスの効率に直接影響する.ハッシュ競合を処理する方法には、オープンアドレス法とファスナー法がある.次の例ではファスナー法を使用しています
BKDRHAshハッシュアルゴリズム
上記の複数のハッシュアルゴリズムの中でBKDRHAshは効率,平衡,均一分布の面で際立っており,その実現も最も理解と記憶が容易である.次のようになります.

/** 
 * BKDR hash function in clang
 * @param key char*    
 * @return int hashed value, we will get a int value
 */
int bkdrHash( char *key )
{
    uint seed = 131;//i can be 13, 131, 1313,131313 etc
    uint hash = 0;
    while( *key != '
' && *key != 0 )
    {
            hash = hash * seed + ( *key++ );
    }
    return ( hash & 0x7FFFFFFF );
}

ハッシュテーブル
概略図:(画像ソース:http://blog.csdn.net/v_JULY_v...)
上図では、左は配列で、各一方向チェーンテーブルのヘッダポインタが保存されています.実際の値はチェーンテーブルに格納されます
一方向チェーンテーブルのノードのデータ構造と配列定義コード

/**             */
typedef struct _htItem{
        struct _htItem  *next;
        char *key_string;
        uint fid;

} htItem;

/**   Key          */
uint htIndex( char *key, htItem **ht ){
        uint hashedKey = bkdrHash( key );
        uint length = (ht[0]->fid-1);
        return (uint)hashedKey % length+1;
}

/**      */
htItem *item[21]; //       ，         ，        ，          ，       ，       

配列要素の初期化

/**             0      */
void htInit( htItem **ht, uint length ){
    int i;
    for( i=0; ifid = length;
}

データの挿入と更新
まずハッシュ関数でKeyが配列に対応する位置を見つけてチェーンテーブルを巡り、チェーンテーブルで同じkeyが見つかったら、そのノードのデータを直接更新します.そうしないとmalloCのノードが1つ、チェーンテーブルの末尾にノードを置きます.

/** set hashTable element */
uint htSet( char *key, uint fid,  htItem **ht ){
    uint i = htIndex( key, ht );
    htItem *item = ht[i];
    while( item->next )
    {
        if( strcmp(key, item->next->key_string) == 0 ){
            item->next->fid = fid;
            return 0;
        }else{
            item = item->next;
        }
    }
    item->next = (htItem*)malloc(sizeof(htItem));
    item->next->fid = fid;
    item->next->key_string = key;
    return 0;
}

データの取得
まずハッシュ関数でKEYの配列内の位置を特定し、KEY値を順次比較し、ヒットした場合は対応する値を返し、そうでなければ空の値を返します.

/** get hashTable elements */
htItem* htGet( char *key, htItem **ht ){
        uint i = htIndex( key, ht);
        htItem *item = ht[i]->next;
    htItem *tmp = (htItem*)malloc(sizeof(htItem));
    memset(tmp, 0, sizeof(htItem));
        while( item )
        {
                if( strcmp(key, item->key_string) == 0 ){
            printf("hiting %s
", key);
            tmp->fid = item->fid;
            tmp->key_string = item->key_string;
                        return tmp;
                }
        item = item->next;
        }
        return;
}

データの削除

/** delete one element of hashtable */
int htDel(char *key, htItem **ht){
        uint i = htIndex(key, ht);
        htItem *item = ht[i];
        while(item->next){
                if(strcmp(key, item->next->key_string) == 0 ){
                        htItem *tmp = item->next;
                        item->next = tmp->next;
                        free(tmp);
                        return 0;
                }
                item = item->next;
        }
        return -1;
}

完全hashtableの要素を印刷

void print_hashTable( htItem **ht )
{
        uint length = ht[0]->fid;
        uint i;
        htItem *item;
        for( i = 1; i < length; i++ )
        {
                item = ht[i]->next;
                while(item)
                {
                        printf("%s => %d
",item->key_string, item->fid);
                        item = item->next;
                }
        }
}

簡単ないくつかの方法でハッシュテーブルの削除変更を実現した.
使用例

    /**        */
    htItem *item[101]; 
    htInit(item, 101);
    
    /**      */
    htSet("longmon",100,item); 
    htSet("natalie", 1000,item);
    htSet("xiaoqiong",99, item);
    
    /**   ⑴ */
    print_hashTable(item);
    
    /**        */
    htDel("natalie", item);
    
    /**   ⑵ */
    print_hashTable(item);
    
    /**   key longmon   */
    htItem *tmpitem = htGet("longmon", item); 
    
    /**   ⑶ */
    printf("key: %s => val:%d
", tmpitem->key_string, tmpitem->fid);

出力結果

#  ⑴ 
xiaoqiong => 99
natalie => 1000
longmon => 100

#  ⑵ 
xiaoqiong => 99
longmon => 100

#  ⑶ 
Key: longmon => val: 100

完全なコードhttps://github.com/longmon/hashTable_in_c
ハッシュテーブルはPHPコアの基石です.
PHPカーネルのハッシュテーブルは非常に重要なデータ構造であり、PHPの言語特性の大部分はハッシュテーブルに基づいて実現されている.例えば、変数の役割ドメイン、関数テーブル、クラスの属性、方法など、Zendエンジン内部の多くのデータはハッシュテーブルに保存されている.PHPカーネルにおけるハッシュテーブルの競合処理にもファスナー法が用いられる.
拡張読書:

PHPのハッシュテーブルは

を実現する

PHP配列のHash衝突例