对int的HashTable实现

C++实现对以int​为键的hashTable​。

目前值为int​,但可变;

 const int N=1e3; // 设计的hashTable大小
 // assume data range: -intINF~+intINF
 
 struct _hash_data
 {
     int sym,data;
     _hash_data *nxt;
     _hash_data(){
         sym=-1;data=-1;nxt=nullptr;
     }
 };
 
 class hash_table{
     public:
         int& operator[](int key){
             unsigned short idx=(key%MOL+MOL)%MOL;
             _hash_data *result=&data[idx];
             while (result->nxt!=nullptr&&result->sym!=key)
                 result=result->nxt;
             if (result->sym==key) return result->data;
             _hash_data *newData=new _hash_data();
             if (!newData) throw bad_alloc();
             result->nxt=newData;
             newData->sym=key;
             return newData->data;
         }
         ~hash_table(){
             // release all the pointers
             for (int i=0;i<N;i++){
                 _hash_data *current=&data[i];
                 while (current-> nxt!=nullptr){
                     _hash_data *tmp=current;
                     current=current->nxt;
                     if (tmp!=&data[i])
                         delete tmp;
                 }
             }
         }
     private:
         const unsigned short int MOL=997; // 一个接近N的大质数
         _hash_data data[N+10];
 };

解释

哈希表

哈希表又称散列表,一种以「key-value」形式存储数据的数据结构。所谓以「key-value」形式存储数据,是指任意的键值 key 都唯一对应到内存中的某个位置。只需要输入查找的键值,就可以快速地找到其对应的 value。可以把哈希表理解为一种高级的数组,这种数组的下标可以是很大的整数,浮点数,字符串甚至结构体。

哈希函数

要让键值对应到内存中的位置,就要为键值计算索引,也就是计算这个数据应该放到哪里。这个根据键值计算索引的函数就叫做哈希函数,也称散列函数。举个例子,如果键值是一个人的身份证号码,哈希函数就可以是号码的后四位,当然也可以是号码的前四位。生活中常用的「手机尾号」也是一种哈希函数。在实际的应用中,键值可能是更复杂的东西,比如浮点数、字符串、结构体等,这时候就要根据具体情况设计合适的哈希函数。哈希函数应当易于计算,并且尽量使计算出来的索引均匀分布。

冲突解决

类似开散列法

拉链法是在每个存放数据的地方开一个链表,如果有多个键值索引到同一个地方,只用把他们都放到那个位置的链表里就行了。查询的时候需要把对应位置的链表整个扫一遍,对其中的每个数据比较其键值与查询的键值是否一致。如果索引的范围是 $1\ldots M$,哈希表的大小为 N,那么一次插入/查询需要进行期望 $O(\frac{N}{M})$ 次比较。

代码中用指针的形式实现链表。

部分引用自:http://oi-wiki.com/ds/hash//