哈希表¶
哈希函数¶
冲突¶
装填因子：\(\alpha=\) 元素个数 ÷ 哈希表长度
开散列法¶
开散列法在每个存放数据的地方开一个缓冲区，如果有多个 key 索引到同一个地方，就把他们都放到对应位置的缓冲区里
查询的时候遍历缓冲区中元素，比对 key 值找到需要的元素
缓冲区可用静态链表，普通链表，红黑树等数据结构实现
开散列法装填因子一般大于 1
桶式散列（静态链表实现）¶
类似 链式前向星
#define SIZE 1000
#define M 256
struct hash_map{
int head[M],key[SIZE],val[SIZE],next[SIZE],tot=0;
// 0 <= (key % M) < M ，head 范围 [0,M-1]
hash_map(){ // 构造函数
memset(next,-1,SIZE); // -1 模拟空指针
memset(head,-1,M);
}
int hash(int _key){
return key % M; // hash 函数
// return _key & (M-1);
}
int& operator[](int _key){ // 重载 []
for(int i=head[hash(_key)];~i;i=next[i]){
if(key[i]==_key) return val[i];
}
return -1;
}
void add(int _key,int _val){ // 头插法
int h=hash(_key);
key[tot]=_key; // 存的是原始 key 值
val[tot]=_val;
next[tot]=head[h];
head[h]=tot++;
return;
}
};
Note
当哈希函数为 key % M 时，链表的数量 M 最好为 2 的幂，因为此时可以使用位运算 key & (M-1) 代替 key % M
挂链表¶
#define SIZE 1000
#define M 256
struct hash_map{
struct node{
int key,val;
node* next;
node(){
next=nullptr;
}
};
node* head[M];
int& operator[](int _key){
for(node* i=head[hash(_key)];i!=nullptr;i=i->next){
if(i->key==_key) return i->val;
}
return -1;
}
void add(int _key,int _val){
int h=hash(_key);
node* temp=new node();
temp->key=_key;
temp->val=_val;
temp->next=head[h];
head[h]=temp;
}
};
Note
挂链表，插入快，查询慢
挂红黑树¶
Note
挂红黑树，查询快，插入慢
闭散列法（开地址方法）¶
线性探测法¶
有冲突就往后找空地方存，快满了就扩容