哈希表

之前看word2vec和line的实现代码，总会出现哈希表。这里总结一下哈希表的用处。

所谓哈希，其实就是一个映射函数y=f(key)，给定key时，可以得出y的值，希望独特的key对应独特的y。

一般使用的场景如下图：

（怕自己总是搞不清楚，所以干脆画了张图）

但不同关键字可能得到同一散列地址,这种现象称碰撞。处理冲突的方法如下：

• 开放寻址法：线性探测再散列，二次探测再散列，伪随机数再散列
• 再散列法
• 链地址法
• 建立一个公共溢出区

Code

下面是代码实现部分，借鉴了line开源代码的具体实现。

#include<stdlib.h>
#include<string.h>
struct Node {
    double val;
    char *key;
}

const int hash_table_size = 30000000;
int *hash_table;
struct Node *nodes;
unsigned int Hash(char *key) {
    unsigned int seed = 131;
    unsigned int hash = 0;
    while(*key) {
        hash = hash * seed + (*key++);
    }
    return hash % hash_table_size;
}
void InitHashTable() {
    hash_table = (int *)malloc(hash_table_size*sizeof(int));
    for (int k = 0; k != hash_table_size; k++) hash_table[k] = -1;
}
void InsertHashTable(char *key, int value) {
    int addr = Hash(key);
    while(hash_table[addr] != -1) addr = (addr + 1) % hash_table_size;
    hash_table[addr] = value;
}
int SearchHashTable(char *key) {
    int addr = Hash(key);
    while(1){
        if(hash_table[addr] == -1) return -1;
        if(!strcmp(key, node[hash_table[addr]].key)) return hash_table[addr];
        addr = (addr + 1) % hash_table_size;
    }
    return -1;
}