30016：开放寻址散列表的删除

题目

在开放寻址、线性探测的字符串集合中加入删除操作。删除不能把槽直接恢复为空，因为后续探测必须越过已删除的槽继续寻找。

解析

槽有三种状态：空、占用和墓碑。查找遇到墓碑时继续探测；插入可以记住第一个墓碑，但必须继续探测到空槽或完整一轮，确认后面没有重复键。

删除本身通常只需把占用槽改成墓碑。若墓碑达到阈值，则必须重建表。为了满足失败不变式，重建时先分配新的槽数组和状态数组，把除目标键外的所有键指针重新放入新表；两次分配和搬移成功后才提交新表。这样重建失败时旧表、集合大小和输出对象仍然保持不变。

答案

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

typedef struct StringSet StringSet;

enum {
    SLOT_EMPTY,
    SLOT_OCCUPIED,
    SLOT_TOMBSTONE
};

struct StringSet {
    char **slots;
    unsigned char *states;
    size_t capacity;
    size_t size;
    size_t tombstones;
};

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(
    const StringSet *set,
    const char *key,
    bool *out_found
) {
    size_t first_tombstone = SIZE_MAX;
    size_t index = hash_string(key) & (set->capacity - 1);
    for (size_t probes = 0; probes < set->capacity; ++probes) {
        if (set->states[index] == SLOT_EMPTY) {
            *out_found = false;
            return first_tombstone == SIZE_MAX
                ? index
                : first_tombstone;
        }
        if (set->states[index] == SLOT_TOMBSTONE) {
            if (first_tombstone == SIZE_MAX) {
                first_tombstone = index;
            }
        } else if (strcmp(set->slots[index], key) == 0) {
            *out_found = true;
            return index;
        }
        index = index + 1 == set->capacity ? 0 : index + 1;
    }
    *out_found = false;
    return first_tombstone;
}

static bool allocate_table(
    size_t capacity,
    char ***out_slots,
    unsigned char **out_states
) {
    if (capacity == 0 || capacity > SIZE_MAX / sizeof(char *)) {
        return false;
    }
    char **slots = calloc(capacity, sizeof *slots);
    unsigned char *states = calloc(capacity, sizeof *states);
    if (slots == NULL || states == NULL) {
        free(slots);
        free(states);
        return false;
    }
    *out_slots = slots;
    *out_states = states;
    return true;
}

static void place_pointer(
    char **slots,
    unsigned char *states,
    size_t capacity,
    char *key
) {
    size_t index = hash_string(key) & (capacity - 1);
    while (states[index] == SLOT_OCCUPIED) {
        index = index + 1 == capacity ? 0 : index + 1;
    }
    slots[index] = key;
    states[index] = SLOT_OCCUPIED;
}

static bool rebuild_without(
    StringSet *set,
    size_t removed_index
) {
    char **slots = NULL;
    unsigned char *states = NULL;
    if (!allocate_table(set->capacity, &slots, &states)) {
        return false;
    }

    for (size_t i = 0; i < set->capacity; ++i) {
        if (set->states[i] == SLOT_OCCUPIED && i != removed_index) {
            place_pointer(slots, states, set->capacity, set->slots[i]);
        }
    }

    char **old_slots = set->slots;
    unsigned char *old_states = set->states;
    char *removed_key = set->slots[removed_index];
    set->slots = slots;
    set->states = states;
    --set->size;
    set->tombstones = 0;
    free(old_slots);
    free(old_states);
    free(removed_key);
    return true;
}

StringSet *string_set_create(void) {
    StringSet *set = malloc(sizeof *set);
    if (set == NULL) {
        return NULL;
    }
    if (!allocate_table(8, &set->slots, &set->states)) {
        free(set);
        return NULL;
    }
    set->capacity = 8;
    set->size = 0;
    set->tombstones = 0;
    return set;
}

void string_set_destroy(StringSet *set) {
    if (set == NULL) {
        return;
    }
    for (size_t i = 0; i < set->capacity; ++i) {
        if (set->states[i] == SLOT_OCCUPIED) {
            free(set->slots[i]);
        }
    }
    free(set->slots);
    free(set->states);
    free(set);
}

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

bool string_set_insert(
    StringSet *set,
    const char *key,
    bool *out_inserted
) {
    if (set == NULL || key == NULL || out_inserted == NULL) {
        return false;
    }
    bool found = false;
    size_t index = find_slot(set, key, &found);
    if (found) {
        *out_inserted = false;
        return true;
    }

    if (set->size + set->tombstones >=
        set->capacity - set->capacity / 4) {
        if (set->capacity > SIZE_MAX / 2) {
            return false;
        }
        char **slots = NULL;
        unsigned char *states = NULL;
        size_t next = set->capacity * 2;
        if (!allocate_table(next, &slots, &states)) {
            return false;
        }
        for (size_t i = 0; i < set->capacity; ++i) {
            if (set->states[i] == SLOT_OCCUPIED) {
                place_pointer(slots, states, next, set->slots[i]);
            }
        }
        free(set->slots);
        free(set->states);
        set->slots = slots;
        set->states = states;
        set->capacity = next;
        set->tombstones = 0;
        index = find_slot(set, key, &found);
    }

    char *copy = malloc(strlen(key) + 1);
    if (copy == NULL) {
        return false;
    }
    strcpy(copy, key);
    set->slots[index] = copy;
    if (set->states[index] == SLOT_TOMBSTONE) {
        --set->tombstones;
    }
    set->states[index] = SLOT_OCCUPIED;
    ++set->size;
    *out_inserted = true;
    return true;
}

bool string_set_remove(
    StringSet *set,
    const char *key,
    bool *out_removed
) {
    if (set == NULL || key == NULL || out_removed == NULL) {
        return false;
    }
    bool found = false;
    size_t index = find_slot(set, key, &found);
    if (!found) {
        *out_removed = false;
        return true;
    }

    size_t threshold = set->capacity / 4;
    if (set->tombstones + 1 >= threshold) {
        if (!rebuild_without(set, index)) {
            return false;
        }
    } else {
        free(set->slots[index]);
        set->slots[index] = NULL;
        set->states[index] = SLOT_TOMBSTONE;
        --set->size;
        ++set->tombstones;
    }
    *out_removed = true;
    return true;
}

这里的重建阈值取容量的四分之一；具体阈值可以调整，但必须在墓碑过多时清理。普通查找、插入和删除的期望复杂度为 $O(1)$，重建的单次成本为 $O(capacity)$。