両端チェーンテーブル実装hash(ハッシュ)

5529 ワード

hashテーブルはハッシュリストとも呼ばれ、jsのオブジェクト、javaのキー値ペア、pythonの辞書、hashは配列とチェーンテーブルの利点を結合し、検索、記憶に大きな利点があります.私の理解では、対応するキーを通じて、対応する値を見つけることができて、配列の長所は速いですね.記憶はチェーンテーブルを採用して、空間を節約して、挿入削除が便利です.今回は整数でシミュレーションして、簡単なhash関数を使って、数字だけを余剰にして、余剰を同じ領域に置いて、つまり、1つのキーは複数の値に対応することができます.
   hash.hファイルの宣言
#ifndef _HASH_H_
#define _HASH_H_

#include "dlist.h"
#include "tools.h"


typedef int (*Hash_func)(const void *key);

//hash      
typedef struct Hash{
    int   bucket_size;    //1.   (  )   
    int element_count;    //2.hash       
    Dlist     **table;    //3.hash        
    
    //free、match、hash_func(         )
    void (*hash_free)(const void *ptr);      
    Boolean (*hash_match)(const void *value1, 
                          const void *value2);
    int (*hash_func)(const void *key);
}Hash;

//  hash  
//        hash

//hash    
Hash    *init_hash(int b_size, Hash_func h_func)  ;    //hash     
void    destroy_hash(Hash **hash)                 ;    //hash    
Boolean hash_insert(Hash *hash, const void *value);    //hash    
Boolean hash_search(Hash *hash, const void *value);    //hash    
Boolean hash_remove(Hash *hash, const void *value);    //hash    
int     get_element_count(const Hash *hash)       ;    //  hash      
void    show_hash_table(const Hash *hash,
                        Print_func print)         ;    //  hash      


#endif

hash.cファイルの実装
#include "hash.h"

//hash    
Hash    *init_hash(int b_size, Hash_func h_func)      //hash     
{
    Hash *hash = (Hash *)Malloc(sizeof(Hash));
    hash->bucket_size = b_size;
    hash->element_count = 0;
    hash->hash_free = NULL;
    hash->hash_match = NULL;
    hash->hash_func = h_func;

    //       b_size  
    hash->table = (Dlist **)Malloc(sizeof(Dlist *) * b_size);
    bzero(hash->table, sizeof(Dlist *) * b_size);
    //                   ,          

    return hash;
}

void    destroy_hash(Hash **hash)                     //hash    
{
    int i = 0;
    int bucket_size = 0;
    Hash *p_hash = NULL;

    if(hash == NULL || *hash == NULL){
        return ;
    }
    //    :
    //  1.         
    p_hash = *hash;
    bucket_size = p_hash->bucket_size;
    for(i = 0; i < bucket_size; ++i){
        destroy_dlist(&(p_hash->table[i]));
    }
    //   2.  hash->table
    free(p_hash->table);
    //   3.  hash    
    free(p_hash);
    *hash = NULL;
}

Boolean hash_insert(Hash *hash, const void *value)    //hash    
{
    int b_index = 0;

    if(hash == NULL || value == NULL
    || hash_search(hash, value)){    
        //           ,          hash ,     
        return FALSE;
    }

    //  hash    value     
    b_index = hash->hash_func(value) % hash->bucket_size;

    if(hash->table[b_index] == NULL){
        hash->table[b_index] = init_dlist();
    }

    // value      (  )
    push_back(hash->table[b_index], (void *)value);
    hash->element_count++;

    return TRUE;
}

Boolean hash_search(Hash *hash, const void *value)    //hash    
{
    int        b_index = 0   ;
    Dlist_node *p_node = NULL;

    if(hash == NULL || value == NULL){
        return FALSE;
    } 

    b_index = hash->hash_func(value) % hash->bucket_size;
    
    //        ,        
    if(hash->table[b_index] == NULL){
        return FALSE;
    }

    //         ,      
    if(hash->hash_match != NULL){
        for(p_node = hash->table[b_index]->head;
        p_node ;
        p_node = p_node->next){
            if(hash->hash_match(p_node->data, value)){
                return TRUE;
            }    
        }
    }else{
        for(p_node = hash->table[b_index]->head;
        p_node ;
        p_node = p_node->next){
            if(p_node->data == value){
                return TRUE;
            }    
        }
    }
   
    return FALSE;
}

Boolean hash_remove(Hash *hash, const void *value)    //hash    
{
    int b_index = 0;
    Dlist_node *p_node = NULL;

    if(hash == NULL || value == NULL || hash->element_count == ZERO){
        return FALSE;
    }

    b_index = hash->hash_func(value) % hash->bucket_size;
    
    if(hash->hash_match != NULL){
        for(p_node = hash->table[b_index]->head;
        p_node ;
        p_node = p_node->next){
            if(hash->hash_match(p_node->data, value)){
                remove_dlist_node(hash->table[b_index], p_node, NULL);
                hash->element_count--;
                return TRUE;
            }    
        }
    }else{
        for(p_node = hash->table[b_index]->head;
        p_node ;
        p_node = p_node->next){
            if(p_node->data == value){
                remove_dlist_node(hash->table[b_index], p_node, NULL);
                hash->element_count--;
                return TRUE;
            }    
        }
    }

    return TRUE;    
}

int     get_element_count(const Hash *hash)           //  hash      
{
    if(hash == NULL){ 
        return -1;
    }
    return hash->element_count;
}

void    show_hash_table(const Hash *hash, Print_func print)             //  hash      
{
    int i = 0;
    int bucket_size = 0;

    if(hash == NULL || hash->element_count == ZERO){ 
        return ;
    }

    // hash                
    bucket_size = hash->bucket_size;
    for(i = 0; i < bucket_size; ++i){
         printf("bucket[%d]:", i);
         show_dlist(hash->table[i], print);
    }
}