C语言实现一个简易的Hash table(6)

上一章中，我们实现了 Hash表 中的 插入 、 搜索 和 删除 接口，我们在初始化 hash表 时固定了大小为 53 ，为了方便扩展，本章将介绍如何修改 hash表 的大小。

设置 Hash表 大小

现在，我们的 hash表 是固定大小( 53 )的，当插入越来越多数据时，我们的 hash表 就会被插满，这个问题有两个原因：

1. 哈希表的性能随着高冲突率而降低
2. 我们的'hash表'只能存储固定数量的记录，如果我们存储更多，将无法插入数据

为了减少 hash表 被插满的情况发生，当插入很多数据时，我们可以增大 hash表 的大小， hash表 中的 count 属性代表已经插入的数据条数，在每次插入和删除时，我们计算表的“负载”，或插入的数量和总的大小的比率，如果它高于或低于某些值，我们会减小或扩大 hash表 的大小。

我们定义如下规则：

1. 如果 负载>0.7 ，就 扩大
2. 如果 负载<0.1 ，就 缩小

要调整大小，我们创建一个大约是当前大小的一半或两倍的新哈希表，并将所有未删除的项插入其中。

我们的新 hash表 大小应该是大约是当前大小的两倍或一半的素数，找到新的 hash表 大小并非易事。为了确定 hash表 的大小，我们现设置一个最基本的大小，然后将实际大小定义为大于基本大小的第一个素数。扩大时，我们先将基本大小加倍，找到第一个更大的素数，然后作为 hash表 的大小，缩小时，我们将大小减半并找到下一个更大的素数。

我们先从基本大小 50 开始，我们使用最简单粗暴的方法通过检查每个连续数是否为素数来查找下一个素数。这个简单粗暴的方法看起来不是很理想，但是我们实际需要检查的值很少，并且花费的时间超过了重新散列表中每个项目所花费的时间。

首先，我们先定义一个函数用来找到下一个素数， prime.h 和 prime.c 的内容如下：

// prime.h
int is_prime(const int x);
int next_prime(int x);

// prime.c
#include <math.h>
#include "prime.h"

/*
 * Return whether x is prime or not
 *
 * Returns:
 *   1  - prime
 *   0  - not prime
 *   -1 - undefined (i.e. x < 2)
 */
int is_prime(const int x) {
    if (x < 2) { return -1; }
    if (x < 4) { return 1; }
    if ((x % 2) == 0) { return 0; }
    for (int i = 3; i <= floor(sqrt((double) x)); i += 2) {
        if ((x % i) == 0) {
            return 0;
        }
    }
    return 1;
}

/*
 * Return the next prime after x, or x if x is prime
 */
int next_prime(int x) {
    while (is_prime(x) != 1) {
        x++;
    }
    return x;
}

下一步，我们需要修改 ht_new 函数，使之可以在创建 hash表 时指定大小，为此我们要创建一个新的函数 ht_new_sized ，在 ht_new 中我们调用 ht_new_sized 并给我们的 hash表 一个默认大小：

// hash_table.c
static ht_hash_table* ht_new_sized(const int base_size) {
    ht_hash_table* ht = xmalloc(sizeof(ht_hash_table));
    ht->base_size = base_size;

    ht->size = next_prime(ht->base_size);

    ht->count = 0;
    ht->items = xcalloc((size_t)ht->size, sizeof(ht_item*));
    return ht;
}


ht_hash_table* ht_new() {
    return ht_new_sized(HT_INITIAL_BASE_SIZE);
}

现在一切准备就绪。在我们的设置 hash表 大小函数中，我们需要检查以确保我们没有将哈希表的大小减小到最小值以下，然后，我们初始化一个所需大小的新 hash表 ，原表中所有非 NULL 或者未被删除的都会插入到新 hash表 中，然后我们在删除旧的 hash 表之前将属性赋值给新的 hash表 。

// hash_table.c
static void ht_resize(ht_hash_table* ht, const int base_size) {
    if (base_size < HT_INITIAL_BASE_SIZE) {
        return;
    }
    ht_hash_table* new_ht = ht_new_sized(base_size);
    for (int i = 0; i < ht->size; i++) {
        ht_item* item = ht->items[I];
        if (item != NULL && item != &HT_DELETED_ITEM) {
            ht_insert(new_ht, item->key, item->value);
        }
    }

    ht->base_size = new_ht->base_size;
    ht->count = new_ht->count;

    // To delete new_ht, we give it ht's size and items 
    const int tmp_size = ht->size;
    ht->size = new_ht->size;
    new_ht->size = tmp_size;

    ht_item** tmp_items = ht->items;
    ht->items = new_ht->items;
    new_ht->items = tmp_items;

    ht_del_hash_table(new_ht);
}

为了简化设置大小，我们定义了两个函数：

// hash_table.c
static void ht_resize_up(ht_hash_table* ht) {
    const int new_size = ht->base_size * 2;
    ht_resize(ht, new_size);
}


static void ht_resize_down(ht_hash_table* ht) {
    const int new_size = ht->base_size / 2;
    ht_resize(ht, new_size);
}

要执行调整大小，我们先检查插入和删除时 hash表 上的负载。 如果它高于或低于0.7和0.1的预定义限制，我们分别调高或调低。

为了避免进行浮点运算，我们将计数乘以 100 ，并检查它是高于还是低于 70 或 10 ：

// hash_table.c
void ht_insert(ht_hash_table* ht, const char* key, const char* value) {
    const int load = ht->count * 100 / ht->size;
    if (load > 70) {
        ht_resize_up(ht);
    }
    // ...
}


void ht_delete(ht_hash_table* ht, const char* key) {
    const int load = ht->count * 100 / ht->size;
    if (load < 10) {
        ht_resize_down(ht);
    }
    // ...
}

上一章：实现接口

下一章：附录：替代碰撞处理