哈希表的实现-白红宇

哈希表的实现

阅读量：6538 次

发布时间：2019-06-24

本文共 7895 字，大约阅读时间需要 26 分钟。

散列表（Hash table，也叫哈希表），是根据（Key value）而直接访问在内存存储位置的。也就是说，它通过计算一个关于键值的函数，将所需查询的数据到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做，存放记录的数组称做散列表。

应用：

一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名 $x$ 到首字母 $F(x)$ 的一个函数关系），在首字母为W的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”是这个例子中散列函数的函数法则 $F()$ ，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。

基本概念：

若关键字为K，则其值存放在 $f(k)$ 的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系 $f$ 为，按这个思想建立的表为散列表。

对不同的关键字可能得到同一散列地址，即 $k_1 \neq k_2$ ，而 $f(k_1)=f(k_2)$ ，这种现象称为冲突（英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数 $f(k)$ 和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为或，所得的存储位置称。

若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

查找效率：

散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。

查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：

散列函数是否均匀；

处理冲突的方法；

散列表的载荷因子

载荷因子：

散列表的载荷因子定义为： $\alpha$ = 填入表中的元素个数 / 散列表的长度。

$\alpha$ 是散列表装满程度的标志因子。由于表长是定值， $\alpha$ 与“填入表中的元素个数”成正比，所以， $\alpha$ 越大，表明填入表中的元素越多，产生冲突的可能性就越大；反之， $\alpha$ 越小，标明填入表中的元素越少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是载荷因子 $\alpha$ 的函数，只是不同处理冲突的方法有不同的函数。

构造哈希表的几种方法：

直接定址法--取关键字的某个线性函数为散列地址，Hash（Key）= Key 或 Hash（Key）= A*Key + B，A、B为常数。

除留余数法--取关键值被某个不大于散列表长m的数p除后的所得的余数为散列地址。Hash（Key）= Key % P。

平方取中法

折叠法

随机数法

数学分析法

线性探测：

#define  _CRT_SECURE_NO_WARNINGS#include
     
      using namespace std;#include
      
       #include
       
        enum Statue  //标记一个数的存在状态{EXIST,DELETE,EMPTY};template
        
             //定义类型struct HashNode{K _key;V _value;Statue statue;HashNode(const K& key, const V& value):_key(key),_value(value),statue(EXIST){}HashNode():statue(EMPTY){}};template
         
          struct _HashFuncDefault{size_t operator()(const K& key){return key;}};static size_t BKDRHash(const char * str){unsigned int seed = 131; // 31 131 1313 13131 131313unsigned int hash = 0;while (*str){hash = hash * seed + (*str++);}return (hash & 0x7FFFFFFF);}template<>struct _HashFuncDefault
          
           {size_t operator()(const string str){return BKDRHash(str.c_str());}};template
           
            
             >class HashTable{typedef HashNode
             
               Node;public:HashTable():_size(0){for (size_t i = 0; i < _table.size(); i++){_table[i].statue = EMPTY;}}bool Insert(const K& key, const V& value){_CheckCapaciy();size_t index = _HashFunc(key,_table.size());size_t tmp = index;if (_table[index]._key == key)//已经有这个数{return false;}if (_table[index].statue == EXIST){++index;while (index != tmp)  //保证不走过一圈{if (index == _table.size()) //到最后一个就从第一个开始{index = 0;}if (_table[index].statue != EXIST)//找到可以插入的位置{break;}if (_table[index]._key == key)//已经有这个数{return false;}++index;}}_table[index].statue = EXIST;_table[index]._key = key;_table[index]._value = value;++_size;return true;}void Remove(const K& key){size_t index = _HashFunc(key, _table.size());size_t tmp = index;if (_table[index]._key != key){++index;while (index != tmp){if (index == _table.size()){index = 0;}if (_table[index]._key == key){break;}++index;}}if (_table[index]._key == key){_table[index].statue = DELETE;--_size;return;}return;}int Find(const K& key){size_t index = _HashFunc(key, _table.size());size_t tmp = index;if (_table[index]._key == key && _table[index].statue == EXIST){return index;}else{++index;while (index != tmp){if (index == _table.size()){index = 0;}if (_table[index]._key == key && _table[index].statue == EXIST){break;}++index;}}if (_table[index]._key == key && _table[index].statue == EXIST){return index;}return -1;}void Print(){for (size_t i = 0; i < _table.size(); i++){if (_table[i].statue == EXIST){cout << "KEY:" << _table[i]._key << "  " << "VALUE:" << _table[i]._value<< "  " << "STATUE:" << _table[i].statue << endl;}}}protected:size_t _HashFunc(const K& key, size_t capacity){_HashFuncer hf;return hf(key) % capacity;}void _CheckCapaciy(){if (_size * 10 >= _table.size()){const int _PrimeSize = 28;static const unsigned long _PrimeList[_PrimeSize] ={53ul, 97ul, 193ul, 389ul, 769ul,1543ul, 3079ul, 6151ul, 12289ul, 24593ul,49157ul, 98317ul, 196613ul, 393241ul, 786433ul,1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,1610612741ul, 3221225473ul, 4294967291ul};size_t newCapacity = 0;for (size_t i = 0; i < _PrimeSize; i++){if (_table.size() < _PrimeList[i]){newCapacity = _PrimeList[i];break;}}HashTable
              
                tmp;tmp._table.resize(newCapacity);for (size_t i = 0; i < _table.size(); i++){tmp.Insert(_table[i]._key, _table[i]._value);}Swap(tmp);}}void Swap(HashTable
               
                & tem){swap(_table, tem._table);tem._size = _size;}private:vector
                
                  _table;size_t _size;};void test(){HashTable
                 
                   ht;ht.Insert("hello", "你好");ht.Insert("hello", "你好");ht.Insert("change", "改变");ht.Insert("world", "世界");ht.Insert("change", "改变");ht.Insert("xi'an", "西安");ht.Remove("hello");int ret = ht.Find("world");ht.Print();}int main(){test();system("pause");return 0;}

二次探测：

#define  _CRT_SECURE_NO_WARNINGS#include
     
      using namespace std;enum Status{EXIST,DELETE,EMPTY};template
      
       struct KeyValue{K _key;V _value;KeyValue(const K& key = K(), const V& value = V()):_key(key),_value(value){}};template
       
        class HashTable{typedef KeyValue
        
          type;public:HashTable():_table(NULL),_size(0),_capacity(0),_status(EMPTY){}HashTable(const size_t& size):_table(new type[size]),_size(0),_capacity(size),_status(new Status[size]){for (size_t i = 0; i < size; i++){_status[i] = EMPTY;}}bool Insert(const K& key, const V& value);void Print();int Find(const K& key);void Remove(const K& key);~HashTable();protected:void _Swap(HashTable
         
          & tmp);size_t _HashFunc(const K& key, size_t i);private:type* _table;size_t _size;size_t _capacity;Status* _status;};template
          
           bool HashTable
           
            ::Insert(const K& key, const V& value){if (_size * 10 >= _capacity * 8)//负载因子{size_t newcapacity = 2 * _capacity;HashTable
            
              tmp(newcapacity);for (size_t i = 0; i < _capacity; i++){tmp.Insert(_table[i]._key, _table[i]._value);}this->_Swap(tmp);}size_t i = 0;//计数器size_t index = _HashFunc(key, i);//计算下标size_t begin = index;do{if (_status[index] == EMPTY || _status[index] == DELETE)//是空或者已经删除break;if (_status[index] == EXIST && _table[index]._key == key)//已经有这个数return true;index = _HashFunc(key, ++i);if (index == _capacity)index = 0;} while (begin != index);if (_status[index] == EXIST)return false;_table[index]._key = key;_table[index]._value = value;_status[index] = EXIST;++_size;return true;}template
             
              void HashTable
              
               ::_Swap(HashTable
               
                & tmp){swap(_table, tmp._table);swap(_size, tmp._size);swap(_capacity, tmp._capacity);swap(_status, tmp._status);}template
                
                 size_t HashTable
                 
                  ::_HashFunc(const K& key, size_t i){size_t ret = (key + i*i) % _capacity;return ret;}template
                  
                   void HashTable
                   
                    ::Print(){for (size_t i = 0; i < _capacity; i++){printf("第%d个 key: %d  value: %d status: %d \n", i, _table[i]._key, _table[i]._value, _status[i]);}}template
                    
                     int HashTable
                     
                      ::Find(const K& key){int i = 0;size_t index = _HashFunc(key,i);if (_table[index]._key == key && _status[index]==EXIST){return index;}else{int begin = index;++index;while (index != begin){if (_table[index]._key == key && _status[index] == EXIST){return index;}index = _HashFunc(key, ++i);}}return -1;}template
                      
                       void HashTable
                       
                        ::Remove(const K& key){int i = 0;size_t index = _HashFunc(key, i);if (_table[index]._key == key && _status[index] == EXIST){_status[index] = DELETE;return;}else{int begin = index;++index;while (index != begin){if (_table[index]._key == key && _status[index] == EXIST){_status[index] = DELETE;return;}index = _HashFunc(key, ++i);}}}template
                        
                         void HashTable
                         
                          ::~HashTable(){if (_table){delete[] _table;}}void test(){HashTable
                          
                           ha(2);ha.Insert(0, 1);ha.Insert(1, 2);ha.Insert(2, 5);ha.Insert(3, 8);ha.Insert(4, 9);ha.Insert(6, 0);ha.Print();int ret=ha.Find(3);ha.Remove(4);ha.Print();}int main(){test();system("pause");return 0;}

转载于:https://blog.51cto.com/10725723/1774006

你可能感兴趣的文章