文章来源(https://github.com/jamesroutley/write-a-hash-table)

介绍

哈希表由一系列桶组成，每个同存储一个key-value键值对，可以看作是一个字典元素。为了找到每个value所在的桶，使用key和hash函数来获取桶所在位置。在文章中key和value的元素都是字符串类型，但如果理解了可以很轻易的转化为其他任何类型。

hash表实现的操作

  • Searc(ht, key): 获取hash表ht中与key关联的value。如果不存在该键值对，返回NULL。
  • Insert(ht, key, value): 往hash表中插入键值对key-value，如果该key已存在hash表中，则value的值会覆盖原value。
  • Delete(ht, key): 删除hash表中键为key的键值对，如果不存在则不进行任何操作。

hash表的结构以及初始化和删除

hash表的结构定义

键值对
1
2
3
4
typedef struct{
    char* key;
    char* value;
}ht_item;
hash表
1
2
3
4
5
typedef struct{
    int size; //hash table最大容量
    int count; //hash table当前大小
    ht_item** items; //数组实现hash table
}ht_hash_table;

初始化

item键值对初始化
1
2
3
4
5
6
7
ht_item* Init_item(const char* key, const char* value)
{
    ht_item temp = (ht_item*)malloc(sizeof(ht_item));
    temp->key = strdup(key);
    temp->value = strdup(key);
    return temp;
}
hash表初始化
1
2
3
4
5
6
7
8
ht_hash_table* ht_table(const int size)
{
    ht_hash_table* ht_table = (ht_hash_table*)malloc(sizeof(ht_hash_table));
    ht_table->size = size;
    ht_table->count = 0;
    ht_table->items = (ht_item**)calloc(size, sizeof(ht_item*));
    return ht_table;
}
删除键值对
1
2
3
4
5
6
void delete_ht_item(it_item ht)
{
    free(ht->key);
    free(ht->value);
    free(ht);
}
删除hash表
1
2
3
4
5
6
7
8
9
10
11
12
13
void delete_ht_table(ht_hash_table* ht)
{
    for(int i = 0; i < ht->size; i++)
    {
        if((ht->items)[i] != NULL)
        {
            delete_ht_item((ht->items)[i]);
            (ht->items)[i] == NULL;
        }
    }
    free(ht->items);
    free(ht);
}

有的时候会出现两个键值对对应的hash表位置相同的情况，这个时候可以使用一些方法来重新获取一个空位置放置这一个键值对。

  1. 顺序放置，即直接往后顺序查找空位置。但是这样查找时的复杂度会比较高。
  2. 双重hash函数，这是比较常用的一种方法，使用两个hash函数，当第一个hash函数求得的位置已经有元素的时候，通过第二个hash函数，获得新的空位置。
1
2
3
4
5
6
7
8
9
10
11
#第一个hash函数
int hash_a(int size, const char* key)
{
    int index_a = 0;
    for(int i = 0; i < strlen(key); i++) #这里是自己定义的hash函数的内容，合理即可
    {
        index_a += prime_1 * key[i];
        index_a %= size;
    }
    return index_a;
}
1
2
3
4
5
6
7
8
9
10
11
#第二个hash函数
int hash_b(int size, const char* key)
{
    int index_b = 0;
    for(int i = 0; i < strlen(key); i++)
    {
        index_b += prime_2 * key[i];
        index_b %= size;
    }
    return index_b;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#调用hash函数
int hash(ht_hash_table* ht, const char* key, int mode)
{
    int size = ht->size;
    int index, index_b ,index_a;
    index_a = hash_a(size, key);
    index_b = hash_b(size, key);
    ht_item** items = ht->items;
    int times = 1;
    index = index_a;
    while(items[index] != NULL)
    {
        if(mode == 0 && items[index] == &DELETED_ITEM)
        {
            return index;
        }
        if(strcmp(items[index]->key, key) == 0)
        {
            return index;
        }
        index += index_b + 1;
        index %= size;
    }
    return index;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#插入键值对
bool Insert(ht_hash_table* ht, const char* key, const char* value)
{
    if(ht->count >= ht->size - 1)
    {
        return false;
    }
    ht_item* temp = ht_new_item(key, value);
    int index = hash(ht, key, 0);
    if(ht->items[index] != NULL && strcmp((ht->items[index])->key, key) == 0)
    {
        delete_ht_item(ht->items[index]);
    }
    ht->items[index] = temp;
    return true;
}
1
2
3
4
5
6
7
8
#搜索键值对
char* Search(ht_hash_table* ht, const char* key)
{
    int index = hash(ht, key, 1);
    if(ht->items[index] == NULL)
    return NULL;
    return (ht->items[index])->value;
}
1
2
3
4
5
6
7
8
9
10
#删除键值对
bool Delete(ht_hash_table* ht, const char* key)
{
    int index = hash(ht, key, 1);
    if(ht->items[index] == NULL)
    return false;
    delete_ht_item(ht->items[index]);
    ht->items[index] = &DELETED_ITEM;
    return true;
}

文章到这里就结束了，写的不是很详细，最近比较忙。