散列表/哈希表（hash table）- C++实现

散列表又称哈希表，查找只需要花费常数时间，查找效率极高，对庞大数据的查找很有作用。

散列表解决冲突的方式有多种，这里采用了分离链接法，除此外还有开放地址法和双散列。

Vocabulary类是用来储存单词的类，用于实现一个离线词典的数据方案，当然这并不是最高效的方法，但是我认为是比较容易理解的方法，对于初学哈希表的人来说还是比较容易接受的。

1 /************************************************************************/
  2 /* 文件说明：
  3 /* 采用分离链接法实现哈希表，采用C++标准库中的vector和list实现 
  4 /* 
  5 /************************************************************************/
  6 #include <vector>
  7 #include <list>
  8 #include <string>
  9 
 10 class Vocabulary;
 11 
 12 int hash(const std::string & key, const int &tableSize);
 13 int hash(const int & key, const int &tableSize);
 14 //int hash(const Vocabulary & e, const int &tableSize);
 15 
 16 namespace stl
 17 {
 18 
 19     template <typename HashedObj>
 20     class HashTable
 21     {
 22     public:
 23         //typedef vector<std::list<HashedObj> >::size_type SIZE;
 24 
 25         HashTable(int size = 101);     //初始化哈希表的大小
 26         ~HashTable(){}
 27         bool contains(const HashedObj & obj);
 28         bool insert(const HashedObj & obj);
 29         bool remove(const HashedObj & obj);
 30     private:
 31         
 32         std::vector<std::list<HashedObj> > theList;   //哈希表
 33         int myhash(const HashedObj & obj) const;   //哈希函数
 34     };
 35 
 36 
 37     //函数定义
 38     template <typename HashedObj>
 39     HashTable<HashedObj>::HashTable(int size /*= 101*/)
 40     {
 41         /*根据哈希表的大小分配vector的空间*/
 42         theList.reserve(size);
 43         theList.resize(size);
 44     }
 45 
 46     template <typename HashedObj>
 47     int HashTable<HashedObj>::myhash(const HashedObj & obj) const
 48     {
 49         //根据object不同调用不同版本的hash重载函数
 50         return hash(obj, theList.size());
 51     }
 52 
 53 /************************************************************************/
 54 /* 函数名称：contains
 55 /* 函数功能：查找指定对象是否在哈希表中
 56 /* 返回值：存在返回true，不存在返回false
 57 /************************************************************************/
 58     template <typename HashedObj>
 59     bool HashTable<HashedObj>::contains(const HashedObj & obj)
 60     {
 61         int iHashValue = myhash(obj);
 62         const std::list<HashedObj> & tempList = theList[iHashValue];
 63 
 64         std::list<HashedObj>::const_iterator it = tempList.cbegin();
 65 
 66         for (; it != tempList.cend() && *it != obj; ++it);
 67         
 68         if(it != tempList.cend())
 69             return true;
 70         else
 71             return false;
 72     }
 73 
 74 /************************************************************************/
 75 /* 函数名称：insert
 76 /* 函数功能：向hash表中插入元素，如果元素已经存在则返回false，不存在则在链表的最前面插入
 77 /* 返回值：成功返回true，失败返回返回false
 78 /************************************************************************/
 79     template <typename HashedObj>
 80     bool HashTable<HashedObj>::insert(const HashedObj & obj)
 81     {
 82         int iHashValue = myhash(obj);
 83 
 84         std::list<HashedObj> & tempList = theList[iHashValue];
 85         if (contains(obj))
 86         {
 87             return false;   //已经存在返回false
 88         }
 89 
 90         tempList.push_back(obj);
 91         return true;
 92     }
 93 
 94     /************************************************************************/
 95     /* 函数名称：remove
 96     /* 函数功能：从哈希表中删除指定元素，如果元素不存在则返回false
 97     /* 返回值：成功返回true，失败返回返回false
 98     /************************************************************************/
 99     template <typename HashedObj>
100     bool HashTable<HashedObj>::remove(const HashedObj & obj)
101     {
102         list<HashedObj> & tempList = theList[myhash(obj)];
103         auto it = find(tempList.begin(), tempList.end(), obj);
104         if (it == tempList.end())
105         {
106             return false;
107         }
108         tempList.erase(it);
109         return true;
110     }
111 }
112 
113 
114 //hash表中存入单词表类，一个对象表示对应一个单词
115 class Vocabulary
116 {
117 public:
118     Vocabulary(){ }
119 
120     ~Vocabulary(){ }
121 
122     void SetWordName(std::string name)
123     {
124         m_sWord = name;
125     }
126 
127     void SetWordExplain(std::string explain)
128     {
129         m_sExplain = explain;
130     }
131 
132     const std::string getName() const
133     {
134         return m_sWord;
135     }
136 
137     Vocabulary(const Vocabulary &vc){
138 
139     }
140 
141     Vocabulary& operator= (const Vocabulary & v)
142     {
143         m_sWord = v.m_sWord;
144         m_sExplain = v.m_sExplain;
145         return *this;
146     }
147 
148 
149 
150 
151 private:
152     std::string m_sWord;
153     std::string m_sExplain;
154 };
155 
156 bool operator== (const Vocabulary & word1, const Vocabulary & word2)
157 {
158     if (word1.getName() == word2.getName())
159     {
160         return true;
161     } 
162     else
163     {
164         return false;
165     }
166 }
167 
168 bool operator!= (const Vocabulary & word1, const Vocabulary & word2) 
169 {
170     return !(word1 == word2);
171 }
172 
173 int hash(const Vocabulary & e,const int &tableSize)
174 {
175     return hash(e.getName(), tableSize);
176 }
177 
178 int hash(const std::string & key, const int &tableSize)
179 {
180     //采用公式：h = (k1*32 + k2) * 32 + k3，将其扩展到n次多项式
181     long long int hashVal = 0;
182     int count = 0;
183     for (auto it = key.begin(); it != key.end(); ++it) 
184     {
185         if (count++ % 2 == 0)
186         {
187             hashVal += (hashVal << 5) + *it;
188         }
189         
190     }
191     return hashVal %= tableSize;
192 }
193 
194 int hash(const int & key, const int &tableSize)
195 {
196     return key % tableSize;
197 }

原文链接: https://www.cnblogs.com/liuteng/p/6426003.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍