30004：开放寻址字符串集合

题目

使用开放寻址和线性探测实现不透明字符串集合，在装载因子即将超过四分之三时自动扩容。

解析

槽数组以空指针表示空槽，容量始终为 2 的幂。因此散列值可以先与 capacity - 1 做按位与，再通过线性探测寻找相同字符串或第一个空槽。散列值相同并不代表字符串相同，仍须调用 strcmp。

集合复制成功插入的键，并在销毁时统一释放。插入时先查询重复键，再复制字符串，最后尝试扩容；扩容失败时旧槽数组完全不动。重新散列只搬移集合已经拥有的指针，不再次复制字符串。

解析

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

typedef struct StringSet StringSet;

StringSet *string_set_create(void);
void string_set_destroy(StringSet *set);
bool string_set_insert(
    StringSet *set,
    const char *key,
    bool *inserted
);
bool string_set_contains(
    const StringSet *set,
    const char *key
);
size_t string_set_size(const StringSet *set);

struct StringSet {
    char **slots;
    size_t capacity;
    size_t size;
};

enum {
    STRING_SET_INITIAL_CAPACITY = 8
};

static size_t hash_string(const char *key) {
    size_t hash = 5381;
    const unsigned char *cursor =
        (const unsigned char *)key;

    while (*cursor != '\0') {
        hash = (hash * 33) ^ *cursor;
        ++cursor;
    }
    return hash;
}

static size_t find_slot(
    char *const *slots,
    size_t capacity,
    const char *key,
    bool *found
) {
    size_t index = hash_string(key) & (capacity - 1);

    for (;;) {
        if (slots[index] == NULL) {
            *found = false;
            return index;
        }
        if (strcmp(slots[index], key) == 0) {
            *found = true;
            return index;
        }
        index = (index + 1) & (capacity - 1);
    }
}

StringSet *string_set_create(void) {
    StringSet *set = malloc(sizeof *set);
    if (set == NULL) {
        return NULL;
    }

    set->slots = calloc(
        STRING_SET_INITIAL_CAPACITY,
        sizeof *set->slots
    );
    if (set->slots == NULL) {
        free(set);
        return NULL;
    }

    set->capacity = STRING_SET_INITIAL_CAPACITY;
    set->size = 0;
    return set;
}

void string_set_destroy(StringSet *set) {
    if (set == NULL) {
        return;
    }

    for (size_t i = 0; i < set->capacity; ++i) {
        free(set->slots[i]);
    }
    free(set->slots);
    free(set);
}

static bool string_set_grow(StringSet *set) {
    if (set->capacity > SIZE_MAX / 2) {
        return false;
    }

    size_t new_capacity = set->capacity * 2;
    if (new_capacity > SIZE_MAX / sizeof *set->slots) {
        return false;
    }

    char **new_slots = calloc(
        new_capacity,
        sizeof *new_slots
    );
    if (new_slots == NULL) {
        return false;
    }

    for (size_t i = 0; i < set->capacity; ++i) {
        char *key = set->slots[i];
        if (key == NULL) {
            continue;
        }

        bool found = false;
        size_t index = find_slot(
            new_slots,
            new_capacity,
            key,
            &found
        );
        new_slots[index] = key;
    }

    free(set->slots);
    set->slots = new_slots;
    set->capacity = new_capacity;
    return true;
}

static char *copy_string(const char *key) {
    size_t length = strlen(key);
    if (length == SIZE_MAX) {
        return NULL;
    }

    char *copy = malloc(length + 1);
    if (copy == NULL) {
        return NULL;
    }
    memcpy(copy, key, length + 1);
    return copy;
}

bool string_set_insert(
    StringSet *set,
    const char *key,
    bool *inserted
) {
    if (set == NULL || key == NULL || inserted == NULL) {
        return false;
    }

    bool found = false;
    find_slot(set->slots, set->capacity, key, &found);
    if (found) {
        *inserted = false;
        return true;
    }

    char *copy = copy_string(key);
    if (copy == NULL) {
        return false;
    }

    if (set->size >=
        set->capacity - set->capacity / 4) {
        if (!string_set_grow(set)) {
            free(copy);
            return false;
        }
    }

    size_t index = find_slot(
        set->slots,
        set->capacity,
        key,
        &found
    );
    set->slots[index] = copy;
    ++set->size;
    *inserted = true;
    return true;
}

bool string_set_contains(
    const StringSet *set,
    const char *key
) {
    if (set == NULL || key == NULL) {
        return false;
    }

    bool found = false;
    find_slot(set->slots, set->capacity, key, &found);
    return found;
}

size_t string_set_size(const StringSet *set) {
    return set == NULL ? 0 : set->size;
}

来源与改编

题型借鉴 Pat Morin 的 Open Data Structures 中散列表的开放寻址与扩容思路，原作采用 CC BY 2.5 Canada；本题改写为拥有字符串副本的不透明 C 接口。