本文献给：

已经掌握基础查找算法，渴望进一步探索高效查找技术的C语言开发者。若你期望知晓如何在庞大数据集中执行迅速的查找，理解现代查找数据结构的工作机制与实现——本文将揭示哈希表、二叉搜索树和跳表的奥秘。

你将学到：

• 熟悉哈希表的运作原理、冲突解决方案和实施策略
• 了解二叉搜索树的基础功能和平衡技术
• 掌握跳表的随机平衡理念和高效查找机制

让我们一同探索高效查找技术的迷人领域！

目录

1. 哈希表原理与实现
2. 二叉搜索树查找
3. 跳表查找简介
4. 三种技术对比与选择
5. 总结
6. 常见问题解答

第一部分：哈希表原理与实现

1. 哈希表核心概念
2. 哈希函数设计
3. 冲突解决方式
4. 动态扩展与效能提升

第二部分：二叉搜索树查找

1. 二叉搜索树基本理论
2. BST基础操作
3. BST的遍历与检索
4. 平衡二叉搜索树概述

第三部分：跳表查找简介

1. 跳表核心概念
2. 跳表的基础操作

第四部分：三种技术对比与选择

1. 性能特点比较
2. 算法选择指导

第五部分：总结

核心要点汇总

第六部分：常见问题解答

第一部分：哈希表原理与实现

1. 哈希表核心概念

哈希表（Hash Table）借助哈希函数将键值映射至数组的指定位置，达成平均O(1)时间复杂度的查找操作。

哈希表三大组成部分：

• 哈希函数：将任意键值转换成固定范围内的整数值
• 冲突解决：应对不同键值映射到相同位置的情形
• 扩展机制：动态调节表尺寸以保持性能

哈希表运作原理：

键 → 哈希函数 → 数组索引 → 存储/查找值

// 哈希表基础架构

typedef struct {
    char* key;
    int value;
    int is_occupied;  // 标记该位置是否已被占用
} HashEntry;

typedef struct {
    HashEntry* entries;
    int capacity;     // 哈希表容量
    int size;         // 当前元素数目
    float load_factor; // 负载因子阈值
} HashTable;

2. 哈希函数设计

优质的哈希函数需具备：

• 计算速度快捷
• 分布均匀
• 冲突几率低

常用哈希函数实现：

// 字符串哈希函数 - DJB2算法
unsigned long djb2_hash(const char* str) {
    unsigned long hash = 5381;
    int c;
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c;  // hash * 33 + c
    }
    return hash;
}

// 整数哈希函数 - 乘法哈希
unsigned int multiplication_hash(int key, int table_size) {
    const double A = 0.6180339887;  // 黄金比例的小数部分
    double product = key * A;
    double fractional = product - (int)product;
    return (unsigned int)(table_size * fractional);
}

// 通用对象哈希函数
unsigned int universal_hash(const void* key, int key_size, int table_size) {
    const unsigned int prime = 16777619;  // FNV质数
    unsigned int hash = 2166136261u;      // FNV偏移基数
    const unsigned char* bytes = (const unsigned char*)key;
    for (int i = 0; i < key_size; i++) {
        hash ^= bytes[i];
        hash *= prime;
    }
    return hash % table_size;
}

3. 冲突解决方式

3.1 链地址法（Separate Chaining）

// 链地址法哈希表节点
typedef struct HashNode {
    char* key;
    int value;
    struct HashNode* next;
} HashNode;

typedef struct {
    HashNode** buckets;  // 桶数组
    int capacity;
    int size;
} ChainedHashTable;

// 链地址法查找
int chained_hash_get(ChainedHashTable* table, const char* key) {
    unsigned int index = djb2_hash(key) % table->capacity;
    HashNode* current = table->buckets[index];
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
```
return current->value;
}
current = current->next;
}
return -1;  // 未找到
}
// 链地址法插入
void chained_hash_put(ChainedHashTable* table, const char* key, int value) {
unsigned int index = djb2_hash(key) % table->capacity;
HashNode* current = table->buckets[index];
// 核查键是否已存在
while (current != NULL) {
if (strcmp(current->key, key) == 0) {
current->value = value;  // 更新数值
return;
}
current = current->next;
}
// 创建新节点并添加到链表前端
HashNode* new_node = (HashNode*)malloc(sizeof(HashNode));
new_node->key = strdup(key);
new_node->value = value;
new_node->next = table->buckets[index];
table->buckets[index] = new_node;
table->size++;
}
3.2 开放地址法（Open Addressing）
// 线性探测
int linear_probe(HashEntry* entries, int capacity, const char* key,
int* found_index, int for_insert) {
unsigned int hash = djb2_hash(key);
int index = hash % capacity;
int start_index = index;
do {
if (!entries[index].is_occupied) {
if (for_insert) {
*found_index = index;
return 1;  // 发现空位
}
return 0;  // 查找时遇到空位，键不存在
}
if (strcmp(entries[index].key, key) == 0) {
*found_index = index;
return 1;  // 发现键
}
index = (index + 1) % capacity;  // 线性探测
} while (index != start_index);
return 0;  // 表已满
}
// 二次探测
int quadratic_probe(HashEntry* entries, int capacity, const char* key,
int* found_index, int for_insert) {
unsigned int hash = djb2_hash(key);
int index = hash % capacity;
int start_index = index;
for (int i = 0; i < capacity; i++) {
int probe_index = (index + i * i) % capacity;
if (!entries[probe_index].is_occupied) {
if (for_insert) {
*found_index = probe_index;
return 1;
}
return 0;
}
if (strcmp(entries[probe_index].key, key) == 0) {
*found_index = probe_index;
return 1;
}
}
return 0;  // 表已满或未发现
}
4. 动态扩容与性能优化
// 哈希表扩容
void hash_table_resize(HashTable* table, int new_capacity) {
HashEntry* old_entries = table->entries;
int old_capacity = table->capacity;
// 创建新数组
table->entries = (HashEntry*)calloc(new_capacity, sizeof(HashEntry));
table->capacity = new_capacity;
table->size = 0;
// 重新插入所有元素
for (int i = 0; i < old_capacity; i++) {
    
if (old_entries[i].is_occupied) {

hash_table_put(table, old_entries[i].key, old_entries[i].value);

free(old_entries[i].key);

}

}

free(old_entries);

}

// 检查并执行扩容

void check_and_resize(HashTable* table) {

float load_factor = (float)table->size / table->capacity;

if (load_factor > table->load_factor) {

int new_capacity = table->capacity * 2;

hash_table_resize(table, new_capacity);

}

}
第二部分：二叉搜索树查找
1. 二叉搜索树基本原理
二叉搜索树（Binary Search Tree, BST）是一种基于二叉树的有序数据结构，满足：

左子树所有节点的值小于根节点

右子树所有节点的值大于根节点

左右子树也都是二叉搜索树
// BST节点结构

typedef struct BSTNode {

int key;

void* data;

struct BSTNode* left;

struct BSTNode* right;

} BSTNode;

typedef struct {

BSTNode* root;

int size;

} BinarySearchTree;
2. BST基本操作
2.1 查找操作
// 递归查找

BSTNode* bst_search_recursive(BSTNode* root, int key) {

if (root == NULL || root->key == key) {

return root;

}

if (key < root->key) {

return bst_search_recursive(root->left, key);

} else {

return bst_search_recursive(root->right, key);

}

}
// 迭代查找

BSTNode* bst_search_iterative(BSTNode* root, int key) {

BSTNode* current = root;

while (current != NULL && current->key != key) {

if (key < current->key) {

current = current->left;

} else {

current = current->right;

}

}

return current;

}
2.2 插入操作
// BST插入

BSTNode* bst_insert(BSTNode* root, int key, void* data) {

if (root == NULL) {

BSTNode* new_node = (BSTNode*)malloc(sizeof(BSTNode));

new_node->key = key;

new_node->data = data;

new_node->left = new_node->right = NULL;

return new_node;

}

if (key < root->key) {

root->left = bst_insert(root->left, key, data);

} else if (key > root->key) {

root->right = bst_insert(root->right, key, data);

}

// 如果key相等，可以根据需求处理（更新数据或忽略）

return root;

}
2.3 删除操作
// 查找最小节点（用于删除操作）

BSTNode* find_min(BSTNode* root) {

while (root != NULL && root->left != NULL) {

root = root->left;

}

return root;

}
// BST删除

BSTNode* bst_delete(BSTNode* root, int key) {

if (root == NULL) return NULL;

if (key < root->key) {

root->left = bst_delete(root->left, key);

} else if (key > root->key) {

root->right = bst_delete(root->right, key);

} else {

// 定位需移除的节点

if (root->left == NULL) {

BSTNode* temp = root->right;

free(root);

return temp;

} else if (root->right == NULL) {

BSTNode* temp = root->left;

free(root);

return temp;

} else {

// 拥有两个子节点：采用右侧子树的最小节点替代

BSTNode* temp = find_min(root->right);

root->key = temp->key;

root->data = temp->data;

root->right = bst_delete(root->right, temp->key);

}

}

return root;

}
3. BST的遍历与查询
// 中序遍历（顺序输出）

void bst_inorder_traversal(BSTNode* root) {

if (root != NULL) {

bst_inorder_traversal(root->left);

printf("%d ", root->key);

bst_inorder_traversal(root->right);

}

}
// 寻找前驱节点

BSTNode* bst_predecessor(BSTNode* root, int key) {

BSTNode* current = bst_search_iterative(root, key);

if (current == NULL) return NULL;

// 若存在左侧子树，前驱为左侧子树的最大节点

if (current->left != NULL) {

return find_max(current->left);

}

// 否则，前驱是最接近的祖先，且当前节点位于其右侧子树内

BSTNode* predecessor = NULL;

BSTNode* ancestor = root;

while (ancestor != current) {

if (current->key > ancestor->key) {

predecessor = ancestor;

ancestor = ancestor->right;

} else {

ancestor = ancestor->left;

}

}

return predecessor;

}
// 区间查询

void bst_range_query(BSTNode* root, int low, int high) {

if (root == NULL) return;

if (low < root->key) {

bst_range_query(root->left, low, high);

}

if (low <= root->key && root->key <= high) {

printf("%d ", root->key);

}

if (high > root->key) {

bst_range_query(root->right, low, high);

}

}
4. 平衡二叉搜索树简介
普通BST在最差情形下可能退化成链表，平衡BST通过旋转操作保持树的平衡状态。

AVL树旋转实例：

// 左旋操作

BSTNode* left_rotate(BSTNode* x) {

BSTNode* y = x->right;

BSTNode* T2 = y->left;

y->left = x;

x->right = T2;

return y;

}

// 右旋操作

BSTNode* right_rotate(BSTNode* y) {

BSTNode* x = y->left;

BSTNode* T2 = x->right;

x->right = y;

y->left = T2;

return x;

}
第三部分：跳表查找简介
1. 跳表核心理念
跳表（Skip List）是一种基于概率的有序数据结构，通过多层索引实现O(log n)的时间复杂度查找，作为平衡树的简易替代方案。

跳表的特性：

实现简便，代码量显著少于平衡树

平均时间复杂度O(log n)

支持高效的区间查询

基于概率的平衡策略

// 跳表节点结构

#define MAX_LEVEL 16  // 最高层级
typedef struct SkipNode {
int key;
void* value;
struct SkipNode** forward;  // 前进指针数组
} SkipNode;
typedef struct {
SkipNode* header;
int level;          // 当前最高层级
int size;           // 元素数目
} SkipList;
2. 跳表的基础操作
2.1 初始化与随机层级
// 随机生成层级（概率性质）
int random_level() {
int level = 1;
while ((rand() % 2) == 0 && level < MAX_LEVEL) {
level++;
}
return level;
}
// 跳表初始化
SkipList* skip_list_create() {
SkipList* list = (SkipList*)malloc(sizeof(SkipList));
list->header = (SkipNode*)malloc(sizeof(SkipNode));
list->header->key = INT_MIN;
list->header->forward = (SkipNode**)calloc(MAX_LEVEL, sizeof(SkipNode*));
list->level = 1;
list->size = 0;
return list;
}
2.2 查询操作
// 跳表查询
SkipNode* skip_list_search(SkipList* list, int key) {
SkipNode* current = list->header;
// 从顶层开始搜索
for (int i = list->level - 1; i >= 0; i--) {
while (current->forward[i] != NULL &&
current->forward[i]->key < key) {
current = current->forward[i];
}
}
// 核查最下层
current = current->forward[0];
if (current != NULL && current->key == key) {
return current;
}
return NULL;
}
2.3 插入操作
// 跳表插入
void skip_list_insert(SkipList* list, int key, void* value) {
SkipNode* update[MAX_LEVEL];
SkipNode* current = list->header;
// 记录每层需更新的节点
for (int i = list->level - 1; i >= 0; i--) {
while (current->forward[i] != NULL &&
current->forward[i]->key < key) {
current = current->forward[i];
}
update[i] = current;
}
current = current->forward[0];
// 若键已存在，更新其值
if (current != NULL && current->key == key) {
current->value = value;
return;
}
// 创建新节点
int new_level = random_level();
SkipNode* new_node = (SkipNode*)malloc(sizeof(SkipNode));
new_node->key = key;
new_node->value = value;
new_node->forward = (SkipNode**)calloc(new_level, sizeof(SkipNode*));
// 更新跳表的层级
if (new_level > list->level) {
for (int i = list->level; i < new_level; i++) {
update[i] = list->header;
}
list->level = new_level;
}
// 将新节点插入各层
for (int i = 0; i < new_level; i++) {
    
new_node->forward[i] = update[i]->forward[i];
update[i]->forward[i] = new_node;
}
list->size++;
}
2.4 范围查询
// 跳表范围查询
void skip_list_range_query(SkipList* list, int start_key, int end_key) {
SkipNode* current = list->header;
// 寻找起始位置
for (int i = list->level - 1; i >= 0; i--) {
while (current->forward[i] != NULL &&
current->forward[i]->key < start_key) {
current = current->forward[i];
}
}
current = current->forward[0];
// 遍历指定范围内的节点
printf("范围查询 [%d, %d]: ", start_key, end_key);
while (current != NULL && current->key <= end_key) {
printf("%d ", current->key);
current = current->forward[0];
}
printf("\n");
}
第四部分：三种技术对比与选择
1. 性能特征对比
特性
哈希表
二叉搜索树
跳表
平均查找时间
O(1)
O(log n)
O(log n)
最坏查找时间
O(n)
O(n)
O(n)
插入时间复杂度
O(1)
O(log n)
O(log n)
删除时间复杂度
O(1)
O(log n)
O(log n)
范围查询
不支持
支持
支持
有序遍历
不支持
支持（中序）
支持
内存开销
中等
较小
较大
实现复杂度
中等
简易
简易
2. 算法选择指南
选择哈希表当：
需要极快的查找速度（平均O(1)时间）
无需有序遍历或范围查询
数据量大且内存充足
可以容忍最坏情况性能
选择二叉搜索树当：
需保持数据的有序性
需范围查询或有序遍历
数据量适中，插入删除操作平衡
实现简易性是重要因素
选择跳表当：
需平衡树的性能但希望更简易的实现
需高效的范围查询
可以接受概率性的性能保障
并发环境下的查找（跳表易实现并发版本）
第五部分：总结
核心要点总结
哈希表：
基于键值映射的快速查找结构
平均O(1)时间复杂度，最坏O(n)
需处理冲突和动态扩容
适用于不需要有序访问的场景
二叉搜索树：
基于二叉树的有序数据结构
平均O(log n)时间复杂度
支持范围查询和有序遍历
可能退化成链表，需平衡机制
跳表：
基于多级索引的概率性有序结构
平均O(log n)时间复杂度
实现简易，支持高效范围查询
内存开销大，性能具概率性
第六部分：常见问题解答
Q1：哈希表在何种情况下会退化为O(n)查找？
A1：当哈希函数质量差导致大量冲突，或负载因子过高导致链表过长时，哈希表的查找性能会退化为O(n)。通过设计优良的哈希函数和合理的扩容策略可以避免这种情况。
Q2：二叉搜索树在何种情况下会退化为链表？
A2：当插入有序或近乎有序的数据时，BST会退化为链表。例如按升序插入1,2,3,4,5，树将变成仅有右子节点的链表。使用平衡BST（AVL、红黑树）可以解决这个问题。
Q3：为何认为跳表是概率性的数据结构？
A3：因为跳表的层数是随机生成的，其平衡性基于概率。尽管平均性能优秀，但理论上可能存在最坏情况。然而，在实际应用中，出现性能问题的概率极低。
Q4：如何解决哈希表的线程安全问题？
A4：有几种方法：1）使用读写锁；2）使用分段锁（如ConcurrentHashMap）；3）使用无锁编程技术。在C语言中，通常使用读写锁或自行实现分段锁机制。
Q5：何时应选择平衡BST而非普通BST？
A5：当数据插入顺序不可预测，或数据量大且操作频繁时，应选择平衡BST。如果数据量小或插入顺序相对随机，普通BST可能就足够了。
觉得文章有帮助？别忘了：
???? 点赞 ????
- 给我一点鼓励
? 收藏 ?
- 方便以后查看
???? 关注 ????
- 获取更新通知
标签：
#C语言算法
#高级查找
#哈希表
#二叉搜索树
#跳表