[C++]实现散列表的分离链接法的数据结构

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

　　散列表,英文叫做Hash Table,因此也叫哈希表,是一种根据关键字值来确定主存中存储位置的数据结构.通过一个散列函数(关于键值的函数),来确定存储该关键字的位置.

　　主要的方法有:　　1.分离链接法(拉链法)

　　分离链接法的散列函数为 position = key % n. 即关键字的存储位置为关键字的值对表项的数量取模.若表项大小为13,对于关键值为27的项,存储在1(27 % 13 = 1)的表项处.为了减少冲突,n往往取素数.对于同余的关键字,采用队列(链表) 的方式连接在一起,新放入的元素放入队头或者队尾均可.用图描述如下:

　　2.线性探查法

　　　　线性探查法是根据冲突次数,来从目标位置后移冲突次数次位置来避免冲突的,即position_new = (position + i) % n,其中i为冲突次数,n为表项大小.

　　3.平方探查法

　　　　与线性探查法类似,只不过是散列函数的不同,其position_new = (position + i²) % n

　　4. 双散列,再散列等

　　分离链接法的数据结构的数据结构的构造,使用一个名为HashTable的类来封装整个表的操作和属性.用vector<deque<int>>来表示整个数据结构,即整个表是一个由(双端)

队列组成的向量(数组).类中还包含其他的函数,用来访问类中的私有属性.

　　类的声明如下:

 1 class HashTable {
 2     public:
 3         HashTable(int = 11);
 4         ~HashTable() = default;
 5         int getHashItemSize(const int) const;        //获得队列长度
 6         int getHashTableSize() const;        //获得表项的大小
 7         bool insertRecord(int);        //插入一个值
 8         void removeRecord(const int);            //删除一个值
 9         bool isEmpty() const;       //判断哈希表是否为空
10         void print() const;       //打印哈希表
11 
12     private:
13         vector<deque<int>>  HashItem;    //结构定义
14         int HashTableSize = 0;      //哈希表表项数
15 };

构造函数定义:

 1 HashTable::HashTable(int n)     //构造函数定义
 2 {
 3     HashTableSize = n;
 4 
 5     for (int i = 0; i < n; ++i)
 6     {
 7         deque<int> adeque;
 8         HashItem.push_back(adeque);     //向向量中压入足够的空队列
 9     }
10 }

插入记录的函数的定义:

 1 bool HashTable::insertRecord(int data)      //插入一个指定值的记录
 2 {
 3     int position = data % HashTableSize;                //映射规则
 4 
 5     if (position >= HashTableSize || position < 0)    //合法性判断
 6         return false;
 7 
 8     else
 9     {
10         HashItem.at(position).push_front(data);  //根据时间局部性原理,插入到队头
11         return true;
12     }
13 }

删除记录的函数定义

 1 void HashTable::removeRecord(const int aim)     //删除一个指定值的记录
 2 {
 3     int i = 0;
 4     int j = 0;
 5 
 6     for (; i < HashTableSize; ++i)            //遍历表项
 7     {
 8 
 9         for (j = 0; j < static_cast<int>(HashItem.at(i).size()); ++j)                //遍历队列
10         {
11             if (HashItem.at(i).at(j) == aim)
12                 HashItem.at(i).erase(HashItem.at(i).begin() + j);       //删除记录
13         }
14     }
15 
16 }

打印函数:

 1 void HashTable::print() const
 2 {
 3     for (int i = 0; i < getHashTableSize(); ++i)        //遍历表项
 4     {
 5         deque<int> temp = HashItem.at(i);
 6 
 7         for (auto &j : temp)            //遍历队列
 8             cout << j << ' ';
 9 
10         cout << endl;
11     }
12 }

对于主函数,写了一点测试语句来进行测试:

 1 int main()
 2 {
 3     HashTable hashtable(13);
 4 
 5     for (int i = 0; i < 100; ++i)
 6         hashtable.insertRecord(i);
 7 
 8     hashtable.print();
 9 
10     cout << endl;
11 
12     hashtable.removeRecord(91);
13     hashtable.removeRecord(70);
14 
15     hashtable.print();
16 
17     return 0;
18 }