手赚网 类似网站怎么建设,订阅号 小程序,广州做网站需要多少钱,赣州专业网站推广多少钱数据结构 散列表
哈希表(Hash Table): 通过哈希函数将键#xff08;key#xff09;映射到存储位置#xff0c;从而实现快速的插入、删除和查找操作。 哈希表是现代编程中最重要的数据结构之一#xff0c;几乎所有编程语言都提供了内置实现。 计数
#include stdio.hkey映射到存储位置从而实现快速的插入、删除和查找操作。 哈希表是现代编程中最重要的数据结构之一几乎所有编程语言都提供了内置实现。 计数
#include stdio.h
#include stdlib.h
#include string.h#define TABLE_SIZE 100 // 哈希表大小// 哈希表节点结构
typedef struct Node {int key; // 存储的元素值int count; // 出现次数struct Node* next; // 链表指针处理冲突
} Node;// 创建新节点
Node* createNode(int key) {Node* newNode (Node*)malloc(sizeof(Node));newNode-key key;newNode-count 1;newNode-next NULL;return newNode;
}// 简单哈希函数
unsigned int hash(int key) {return key % TABLE_SIZE;
}// 插入元素到哈希表
void insert(Node* hashTable[], int key) {unsigned int index hash(key);// 检查是否已存在Node* current hashTable[index];while (current ! NULL) {if (current-key key) {current-count; // 已存在计数增加return;}current current-next;}// 不存在创建新节点Node* newNode createNode(key);newNode-next hashTable[index];hashTable[index] newNode;
}// 打印哈希表内容
void printHashTable(Node* hashTable[]) {for (int i 0; i TABLE_SIZE; i) {Node* current hashTable[i];while (current ! NULL) {printf(元素 %d 出现次数: %d\n, current-key, current-count);current current-next;}}
}// 释放哈希表内存
void freeHashTable(Node* hashTable[]) {for (int i 0; i TABLE_SIZE; i) {Node* current hashTable[i];while (current ! NULL) {Node* temp current;current current-next;free(temp);}}
}int main() {Node* hashTable[TABLE_SIZE] {NULL}; // 初始化哈希表int nums[] {1, 2, 3, 2, 1, 3, 3, 4, 5, 4, 4, 4};int size sizeof(nums) / sizeof(nums[0]);// 统计每个元素的出现次数for (int i 0; i size; i) {insert(hashTable, nums[i]);}// 打印统计结果printHashTable(hashTable);// 释放内存freeHashTable(hashTable);return 0;
}
哈希函数:将任意大小的数据映射到固定大小的值哈希值
#include stdio.h
#include string.h// 简单哈希函数 - 适用于字符串
unsigned int simple_hash(const char* str) {unsigned int hash 0;while (*str) {hash (hash * 31) *str; // 31是个常用质数str;}return hash;
}// 测试
int main() {const char* str1 hello;const char* str2 world;printf(%s 的哈希值: %u\n, str1, simple_hash(str1));printf(%s 的哈希值: %u\n, str2, simple_hash(str2));return 0;
}
桶Bucket存储数据的容器通常是一个数组
冲突Collision不同键映射到相同哈希值的情况
滚动哈希:一种高效处理字符串/数组子串哈希的技术常用于字符串匹配、重复子串检测等场景
#include stdio.h
#include string.h#define BASE 256 // 基数通常选择质数
#define MOD 101 // 模数通常选择大质数// 计算初始哈希值
unsigned long initial_hash(const char* str, int len) {unsigned long hash 0;for (int i 0; i len; i) {hash (hash * BASE str[i]) % MOD;}return hash;
}// 滚动哈希计算下一个哈希值
unsigned long roll_hash(unsigned long prev_hash, char left_char, char right_char, int len, unsigned long power) {prev_hash (prev_hash MOD - (left_char * power) % MOD) % MOD;return (prev_hash * BASE right_char) % MOD;
}// 查找模式串在文本中的位置
void rabin_karp(const char* text, const char* pattern) {int n strlen(text);int m strlen(pattern);if (m 0 || n m) return;// 计算BASE^(m-1) % MODunsigned long power 1;for (int i 0; i m - 1; i) {power (power * BASE) % MOD;}unsigned long pattern_hash initial_hash(pattern, m);unsigned long text_hash initial_hash(text, m);for (int i 0; i n - m; i) {if (text_hash pattern_hash) {// 哈希匹配验证实际字符串是否匹配if (strncmp(text i, pattern, m) 0) {printf(在位置 %d 找到匹配\n, i);}}// 滚动到下一个位置if (i n - m) {text_hash roll_hash(text_hash, text[i], text[i m], m, power);}}
}int main() {const char* text ABABDABACDABABCABAB;const char* pattern ABABCABAB;rabin_karp(text, pattern);return 0;
}
哈希工作原理
插入数据时 计算哈希值 确定储存位置
查找数据时 计算哈希值 直接访问对应位置
处理冲突时 链接地址法 每个桶使用链表 储存多个元素 开放寻址法 寻找下一个可用位置
应用场景 数据库索引 缓存实现如Redis 语言中的字典/映射结构如Python的dictJava的HashMap 唯一性检查
优缺点
优点 平均情况下操作非常快 实现简单直接
缺点 哈希函数设计影响性能 冲突处理增加复杂度 不支持有序遍历除非使用特殊实现
