构造哈希表常用的方法是:
除留余数法--取关键值被某个不大于散列表长m的数p除后的所得的余数为散列地址。HashKey= Key % P。
直接定址法--取关键字的某个线性函数为散列地址HashKey= Key 或 HashKey= A*Key + BA、B为常数。
我在这里主要使用一下除留余数法Hash(key) =Key%P,(P这里是哈希表的长度)p最好是素数考虑降低哈希冲突的原因,我并没有在这上面过于追究此处哈希表长度10,见线性探测图。
哈希表经常遇到的一个问题就是哈希冲突。
哈希冲突是什么呢?哈希冲突指的是:不同的关键字经过相同的哈希函数映射到相同的的哈希地址处。
在这里,我将线性探测的原理用下图表述:
线性探测
线性探测代码如下:
#define_CRT_SECURE_NO_WARNINGS1 #include<iostream> usingnamespacestd; #include<string> //线性探测的特化处理可以处理自定义类型的数据 enumState { EMPTY,//该位置未存放元素 DELETE,//该位置元素已被删除 EXIST,//该位置存在元素 }; //处理基本类型 template<classK> structDefaultFuncer { size_toperator()(constK&key) { returnkey; } }; //处理自定义类型 template<> structDefaultFuncer<string> { size_tvalue=0; size_toperator()(conststring&str) { for(inti=0;i<str.size();i++) { value+=str[i]; } returnvalue; } }; template<classK,template<class>classHashFuncer=DefaultFuncer> classHashTable { public: HashTable() :_size(0),_capacity(0),_state(NULL),_table(NULL) {} HashTable(size_tsize) :_size(0),_capacity(size),_state(newState[size]),_table(newK[size]) { for(inti=0;i<_capacity;i++)//全部状态初始化成EMPTY { _state[i]=EMPTY; } } //线性探测计算出元素存放位置(假设不哈希冲突) int_HashFunc(constK&key) { HashFuncer<K>hf; returnhf(key)%_capacity; //匿名对象调用operator() /*returnHashFuncer<K>()(key)%_capacity;*/ } voidSwap(HashTable<K>tmp) { swap(_size,tmp._size); swap(_capacity,tmp._capacity); swap(_state,tmp._state); swap(_table,tmp._table); } void_CheckCapacity() { HashTable<K>tmp(2*_capacity); for(inti=0;i<_capacity;i++) { tmp.Insert(_table[i]); } Swap(tmp); } boolInsert(constK&key) { //静态哈希表 /*if(_size==_capacity) { cout<<"HashTableisfull!"<<endl; returnfalse; }*/ //动态哈希表 //高效哈希表的载荷因子大概稳定在0.7-0.8较好 if(10*_size>=7*_capacity) { _CheckCapacity(); } intindex=_HashFunc(key); while(_state[index]==EXIST) { index++; if(index==_capacity) { index=0; } } _table[index]=key; _state[index]=EXIST; _size++; returntrue; } intFind(constK&key) { intindex=_HashFunc(key); while(_state[index]==EXIST||_state[index]==DELETE) //while(_state[index]!=EMPTY)//空状态找不到,非空状态找得到 { if(_table[index]==key&&_state[index]==EXIST) { returnindex; } ++index; if(index==_capacity) { index=0; } } return-1; } boolRemove(constK&key) { intindex=Find(key); if(index!=-1) { _state[index]=DELETE; --_size; returntrue; } returnfalse; } voidPrintTable() { for(inti=0;i<_capacity;i++) { if(_state[i]==EXIST) { cout<<i<<"(EXIST):"<<_table[i]<<endl; } /*我将DELETE状态元素也打印出来,便于观察。 而Insert处理时,DELETE状态下的位置可以插上新的元素*/ elseif(_state[i]==DELETE) { cout<<i<<"(DELETE):"<<_table[i]<<endl; } else { cout<<i<<"(EMPTY):"<<_table[i]<<endl; } } } private: size_t_size;//实际存放元素个数 size_t_capacity;//哈希表长度 State*_state; K*_table; }; //POD(基本类型)的测试用例 voidTestHashTablePOD() { HashTable<int>ht(10); ht.Insert(89); ht.Insert(18); ht.Insert(49); ht.Insert(58); ht.Insert(9); ht.PrintTable(); intret=ht.Find(89); cout<<ret<<endl; ht.Remove(89); ht.PrintTable(); ht.Remove(18); ht.PrintTable(); } //自定义类型的测试用例 voidTestHashTable() { HashTable<string,DefaultFuncer>ht(10); ht.Insert("信息化"); ht.Insert("时代"); ht.Insert("电脑"); ht.Insert("测试工程师"); ht.PrintTable(); intret=ht.Find("测试工程师"); cout<<ret<<endl; ht.Remove("电脑"); ht.PrintTable(); ht.Remove("时代"); ht.PrintTable(); } intmain() { TestHashTable(); system("pause"); return0; }