[TOC]
哈希表
简介:哈希表(Hash table,散列表),是根据K-V而直接访问的一种数据结构。
两种类型的哈希表:
链式哈希表,通过每个桶附加链表来解决哈希冲突。
**开地址哈希表,**通过探查这个表,直到找到一个可以放置元素的槽。具体方法有线性探查、双散列。
哈希函数:
1,取余,除整取余。
2,处理字符串的哈希函数,ELFhash算法,通过一系列位操作将键强制转换为整数。
int ELFhash(char*key)
{
unsigned long h=0;
while(*key)
{
h = (h << 4) + *key++;
unsigned long g = h & 0xF0000000L;
if(g)
h ^= g >> 24;
h &= ~g;
}
return h % MOD;
}