散列表实现骨架

[xxleyi]

散列表，是现代编程中不可或缺的一种数据结构，其核心思想还是基于线性数组进行巧妙魔改。

想要体会散列表的巧妙之处，必须借助 C 语言，从较低的抽象层级上去学习和体会，方能得其精髓。

本文给出了一个很粗粒度的实现骨架，参考自 https://craftinginterpreters.com/hash-tables.html

使用的具体技术是开放寻址，核心点是 hash 函数，set 逻辑与 get 逻辑。

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

#define CAPACITY 5

int HashTable[CAPACITY];
char **strs;
int COUNT = 0;

static uint32_t hash(char* key, int length) {
  uint32_t h = 2166136261u;

  for (int i = 0; i < length; i++) {
    h ^= key[i];
    h *= 16777619;
  }

  return h;
}

static bool setHashTable(char* key, int length, int value) {
  if (COUNT == CAPACITY)
    return false;
  int index = hash(key, length) % CAPACITY;
  for (;;) {
    if (HashTable[index] == 0 || strcmp(key, strs[index]) == 0) {
      if (HashTable[index] == 0)
        COUNT++;
      HashTable[index] = value;
      strs[index] = key;
      return true;
    }
    else
    {
      index = (index + 1) % CAPACITY;
    }
  }
}

static int getHashTable(char* key, int length) {
  int index = hash(key, length) % CAPACITY;

  for (;;) {
    if (HashTable[index] == 0)
      return 0;
    if (strcmp(key, strs[index]) == 0) {
      return HashTable[index];
    } else {
      index = (index + 1) % CAPACITY;
    }
  }
}

int main(void) {
  strs = calloc(CAPACITY, sizeof(char *));
  setHashTable("liu", 3, 3);
  setHashTable("xi", 2, 2);
  int v = getHashTable("liu", 3);
  printf("%d\n", v);
  v = getHashTable("xi", 2);
  printf("%d\n", v);
  printf("%d\n", getHashTable("min", 3));
  return 0;
}

可视化计算过程追踪：C tutor