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