散列表,英文叫做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 + i2 ) % 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 }
插入0到99的關鍵字,散列到表項大小為13的散列表中,在刪除91和70兩個關鍵值.
運行結果輸出了0到99的散列情況和刪除操作之後的散列情況:
本人原創,轉載請注明出處,謝謝合作!
