第08课：哈希索引

索引结构 第8课 / 共25课

📖 课程概述

哈希索引提供了O(1)的等值查找性能，是B+树之外另一种重要的索引结构。数据库中哈希索引分为静态哈希和动态哈希(可扩展哈希/线性哈希)。本课深入实现哈希索引，分析哈希冲突解决策略，并探讨PostgreSQL的哈希索引和MySQL的自适应哈希索引。

🔑 哈希索引原理

冲突解决策略

💻 C语言实现：可扩展哈希索引

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

#define BUCKET_SIZE   4
#define MAX_DEPTH     16
#define MAX_KEY       32
#define MAX_VAL       64

typedef struct {
    char keys[BUCKET_SIZE][MAX_KEY];
    char values[BUCKET_SIZE][MAX_VAL];
    int  count;
    int  local_depth;
} Bucket;

typedef struct {
    Bucket** directory;    // 目录数组
    int      dir_size;     // 目录大小 = 2^global_depth
    int      global_depth;
    int      num_buckets;
    int      splits;
} ExtHashTable;

uint32_t hash_func(const char* key) {
    uint32_t h = 5381;
    while (*key) h = h * 33 + (unsigned char)*key++;
    return h;
}

ExtHashTable* ext_hash_create() {
    ExtHashTable* ht = calloc(1, sizeof(ExtHashTable));
    ht->global_depth = 1;
    ht->dir_size = 2;
    ht->directory = calloc(ht->dir_size, sizeof(Bucket*));
    // 初始两个桶
    Bucket* b0 = calloc(1, sizeof(Bucket));
    Bucket* b1 = calloc(1, sizeof(Bucket));
    b0->local_depth = 1;
    b1->local_depth = 1;
    ht->directory[0] = b0;
    ht->directory[1] = b1;
    ht->num_buckets = 2;
    printf("[ExtHash] 创建，全局深度=%d\n", ht->global_depth);
    return ht;
}

int bucket_index(ExtHashTable* ht, const char* key) {
    uint32_t h = hash_func(key);
    return h & ((1 << ht->global_depth) - 1);
}

// 分裂桶
void split_bucket(ExtHashTable* ht, int idx) {
    Bucket* old = ht->directory[idx];
    int old_depth = old->local_depth;
    int new_depth = old_depth + 1;

    // 如果局部深度等于全局深度，需要翻倍目录
    if (old_depth == ht->global_depth) {
        int new_size = ht->dir_size * 2;
        Bucket** new_dir = calloc(new_size, sizeof(Bucket*));
        for (int i = 0; i < ht->dir_size; i++) {
            new_dir[i] = ht->directory[i];
            new_dir[i + ht->dir_size] = ht->directory[i];
        }
        free(ht->directory);
        ht->directory = new_dir;
        ht->dir_size = new_size;
        ht->global_depth++;
        printf("  [ExtHash] 目录翻倍，全局深度→%d\n", ht->global_depth);
    }

    // 创建新桶
    Bucket* new_bucket = calloc(1, sizeof(Bucket));
    new_bucket->local_depth = new_depth;
    old->local_depth = new_depth;
    ht->num_buckets++;
    ht->splits++;

    // 重新分配旧桶的记录
    char temp_keys[BUCKET_SIZE][MAX_KEY];
    char temp_vals[BUCKET_SIZE][MAX_VAL];
    int temp_count = old->count;
    memcpy(temp_keys, old->keys, sizeof(temp_keys));
    memcpy(temp_vals, old->values, sizeof(temp_vals));

    old->count = 0;
    int mask = (1 << new_depth) - 1;
    int old_suffix = idx & mask;

    // 更新目录指针
    for (int i = 0; i < ht->dir_size; i++) {
        if (ht->directory[i] == old) {
            int suffix = i & mask;
            if (suffix != old_suffix) {
                ht->directory[i] = new_bucket;
            }
        }
    }

    // 重新插入旧记录
    for (int i = 0; i < temp_count; i++) {
        uint32_t h = hash_func(temp_keys[i]);
        int bi = h & ((1 << ht->global_depth) - 1);
        Bucket* target = ht->directory[bi];
        if (target->count < BUCKET_SIZE) {
            strcpy(target->keys[target->count], temp_keys[i]);
            strcpy(target->values[target->count], temp_vals[i]);
            target->count++;
        }
    }
    printf("  [ExtHash] 桶分裂，新局部深度=%d\n", new_depth);
}

// 插入
void ext_hash_insert(ExtHashTable* ht, const char* key, const char* val) {
    int idx = bucket_index(ht, key);
    Bucket* bucket = ht->directory[idx];

    // 检查重复
    for (int i = 0; i < bucket->count; i++) {
        if (strcmp(bucket->keys[i], key) == 0) {
            strcpy(bucket->values[i], val);
            return;
        }
    }

    if (bucket->count < BUCKET_SIZE) {
        strcpy(bucket->keys[bucket->count], key);
        strcpy(bucket->values[bucket->count], val);
        bucket->count++;
        return;
    }

    // 桶满，分裂
    split_bucket(ht, idx);
    // 重新计算位置
    idx = bucket_index(ht, key);
    bucket = ht->directory[idx];
    if (bucket->count < BUCKET_SIZE) {
        strcpy(bucket->keys[bucket->count], key);
        strcpy(bucket->values[bucket->count], val);
        bucket->count++;
    } else {
        // 递归分裂(极端情况)
        ext_hash_insert(ht, key, val);
    }
}

// 查找
char* ext_hash_search(ExtHashTable* ht, const char* key) {
    int idx = bucket_index(ht, key);
    Bucket* bucket = ht->directory[idx];
    for (int i = 0; i < bucket->count; i++) {
        if (strcmp(bucket->keys[i], key) == 0) {
            printf("  [ExtHash] 找到: %s→%s\n", key, bucket->values[i]);
            return bucket->values[i];
        }
    }
    printf("  [ExtHash] 未找到: %s\n", key);
    return NULL;
}

// 删除
int ext_hash_delete(ExtHashTable* ht, const char* key) {
    int idx = bucket_index(ht, key);
    Bucket* bucket = ht->directory[idx];
    for (int i = 0; i < bucket->count; i++) {
        if (strcmp(bucket->keys[i], key) == 0) {
            // 用最后一个元素替换
            strcpy(bucket->keys[i], bucket->keys[bucket->count - 1]);
            strcpy(bucket->values[i], bucket->values[bucket->count - 1]);
            bucket->count--;
            printf("  [ExtHash] 删除: %s\n", key);
            return 0;
        }
    }
    return -1;
}

void ext_hash_stats(ExtHashTable* ht) {
    printf("\n=== 可扩展哈希统计 ===\n");
    printf("全局深度: %d  目录大小: %d  桶数: %d  分裂次数: %d\n",
           ht->global_depth, ht->dir_size, ht->num_buckets, ht->splits);
    // 统计桶利用率
    int total = 0, used = 0;
    for (int i = 0; i < ht->dir_size; i++) {
        if (i == 0 || ht->directory[i] != ht->directory[i-1]) {
            total += BUCKET_SIZE;
            used += ht->directory[i]->count;
        }
    }
    printf("桶利用率: %.1f%%\n", (double)used / total * 100);
}

int main() {
    printf("╔══════════════════════════════════════╗\n");
    printf("║   可扩展哈希索引                     ║\n");
    printf("╚══════════════════════════════════════╝\n\n");

    ExtHashTable* ht = ext_hash_create();
    const char* data[][2] = {
        {"alice","Beijing"}, {"bob","Shanghai"}, {"charlie","Shenzhen"},
        {"diana","Hangzhou"}, {"eve","Chengdu"}, {"frank","Wuhan"},
        {"grace","Nanjing"}, {"henry","Xi'an"}, {"ivy","Qingdao"},
        {"jack","Xiamen"}, {"kate","Suzhou"}, {"leo","Dalian"},
        {"mia","Changsha"}, {"noah","Zhengzhou"}, {"olivia","Tianjin"},
        {"peter","Harbin"}, {"quinn","Kunming"}, {"rose","Guiyang"},
    };

    printf("--- 插入 ---\n");
    for (int i = 0; i < 18; i++) {
        printf("Insert %s→%s\n", data[i][0], data[i][1]);
        ext_hash_insert(ht, data[i][0], data[i][1]);
    }

    ext_hash_stats(ht);

    printf("\n--- 查找 ---\n");
    ext_hash_search(ht, "alice");
    ext_hash_search(ht, "frank");
    ext_hash_search(ht, "xyz");

    printf("\n--- 删除 ---\n");
    ext_hash_delete(ht, "bob");
    ext_hash_search(ht, "bob");

    printf("\n✅ 可扩展哈希索引运行完成\n");
    return 0;
}

🐍 Python实现：线性哈希

"""
线性哈希(Linear Hashing)实现
与可扩展哈希不同，线性哈希按轮次分裂，不需要目录
"""
import hashlib

class LinearHashTable:
    def __init__(self, bucket_size=4, load_factor=0.75):
        self.bucket_size = bucket_size
        self.load_factor = load_factor
        self.buckets = [[] for _ in range(4)]  # 初始4个桶
        self.level = 0        # 当前轮次
        self.split_ptr = 0    # 分裂指针
        self.num_records = 0
        self.next_split = len(self.buckets)  # 2^level * 2

    def _hash(self, key, level=None):
        if level is None: level = self.level
        h = int(hashlib.md5(key.encode()).hexdigest(), 16)
        n = 2 ** (level + 2)  # 当前桶数基数
        idx = h % n
        if idx < self.split_ptr:
            n = 2 ** (level + 3)  # 已分裂，用下一级
            idx = h % n
        return idx

    def _should_split(self):
        return self.num_records > len(self.buckets) * self.bucket_size * self.load_factor

    def _split_bucket(self):
        old_idx = self.split_ptr
        old_bucket = self.buckets[old_idx]
        # 创建新桶
        new_idx = len(self.buckets)
        self.buckets.append([])

        # 重新分配旧桶记录
        entries = old_bucket[:]
        self.buckets[old_idx] = []
        self.level_changed = False

        for k, v in entries:
            new_pos = self._hash(k, self.level + 1)
            self.buckets[new_pos].append((k, v))

        self.split_ptr += 1
        if self.split_ptr >= 2 ** (self.level + 2):
            self.level += 1
            self.split_ptr = 0
            self.level_changed = True

        print(f"  [LinHash] 分裂桶{old_idx}→新桶{new_idx}, split_ptr={self.split_ptr}, level={self.level}")

    def put(self, key, value):
        idx = self._hash(key)
        bucket = self.buckets[idx]
        # 检查更新
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self.num_records += 1
        if self._should_split():
            self._split_bucket()

    def get(self, key):
        idx = self._hash(key)
        for k, v in self.buckets[idx]:
            if k == key: return v
        return None

    def delete(self, key):
        idx = self._hash(key)
        bucket = self.buckets[idx]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.num_records -= 1
                return True
        return False

    def stats(self):
        max_len = max(len(b) for b in self.buckets)
        min_len = min(len(b) for b in self.buckets)
        avg_len = self.num_records / len(self.buckets)
        return {
            "buckets": len(self.buckets), "records": self.num_records,
            "level": self.level, "split_ptr": self.split_ptr,
            "max_bucket": max_len, "min_bucket": min_len,
            "avg_bucket": f"{avg_len:.1f}",
            "utilization": f"{self.num_records / (len(self.buckets) * self.bucket_size) * 100:.1f}%"
        }

# 测试
lh = LinearHashTable(bucket_size=4)
names = ["alice","bob","charlie","diana","eve","frank","grace","henry",
         "ivy","jack","kate","leo","mia","noah","olivia","peter",
         "quinn","rose","sam","tina","uma","vera","will","xena"]

for name in names:
    lh.put(name, f"city_{hash(name) % 10}")

print("=== 线性哈希统计 ===")
s = lh.stats()
for k, v in s.items(): print(f"  {k}: {v}")

# 查找
print("\n--- 查找测试 ---")
for name in ["alice", "frank", "xyz"]:
    val = lh.get(name)
    print(f"  {name} → {val}")

# 删除
lh.delete("bob")
print(f"\n删除bob后: {lh.stats()}")
print("✅ 线性哈希实现完成")

🔑 关键概念总结