散列表(hash table)是一种仅支持 增，删，查 操作的集合，理想情况下， 查找一个元素的期望时间是\(O(1)\)，因为我们在散列表中通过关键字key查找value， 就好像在数组中通过下标查找对应的值一样。算法导论上说:"散列表是普通数组概念的推广"。

实现一个散列表有两个比较重要的问题： 构造散列函数(hash function) 和 解决碰撞(collision)问题。 理想的散列函数能够让每个关键字都等可能的映射到表中的所有位置，这样数据在表中的分布是均匀的。 不过实际应用中基本不可能做到，只要能近似的满足这个条件就是个好的散列函数。一般情况下， 我们可以直接使用其他人设计的散列函数，我自己的实现 中用的就是BKDRHash，它不仅实现简单(看两遍后， 随手就能自己写出来)，实际性能表现也非常的优秀。因为散列表中的元素数可以大于表的长度， 所以碰撞是不可避免的，解决的方法有链接法，开放寻址法，再散列，我用的是链接法，简单易懂。

接口定义如下，完整的 demo放在Github上，可供参考。 此次单独为每一个节点的key和val指定大小主要是考虑到字符串会方便点，因为字符串的长度可大可小， 不像其他类型有固定大小。

typedef unsigned char BYTE;

typedef struct HashLnkLstNode HashLnkLstNode;
typedef struct Hashtable Hashtable;

struct HashLnkLstNode
{
    BYTE* key;
    BYTE* val;
    size_t key_size;
    size_t val_size;
    HashLnkLstNode* next;
};

struct Hashtable
{
    size_t size; //This is the size of the table, 
                 //which contains all header of the single-linked list;
    size_t elemts_count; // The count can be greater than size;

    HashLnkLstNode** table;
};

//Create a new hashtable with size of specified value;
Hashtable* new_hashtable(size_t size);
//Get the size of a hashtable;
size_t hashtable_size(const Hashtable* table);
//Get the number of elements contained in the hashtable;
size_t hashtable_elemts_count(const Hashtable* table);
//The hash function;
size_t hashtable_hash(const BYTE* key, size_t key_size);
//Determines whether the hashtable contains a specific element;
int hashtable_contains_key(const Hashtable* table, const BYTE* key, size_t key_size);
//Search the hashtable and return the value with specific key;
BYTE* hashtable_getval(const Hashtable* table, const BYTE* key, size_t key_size);
//Add a new element into the hashtable, if the key has exist in the hashtable, do nothing;
void hashtable_add(Hashtable* table, 
                   const BYTE* key, 
                   size_t key_size, 
                   const BYTE* val, 
                   size_t val_size);
//Remove a specific element from the hashtable;
void hashtable_remove(Hashtable* table, const BYTE* key, size_t key_size);
//Dispose the hashtable;
void hashtable_dispose(Hashtable* table);
//Romove all elements of the hashtable;
void hashtable_empty(Hashtable* table);