一、先談談數(shù)組與鏈表
?經(jīng)常寫代碼的小伙伴應該不陌生，在編程過程中常常面臨著兩個問題：存儲和查找，存儲和查找的效率往往決定了整個程序的效率。
?實際上，數(shù)據(jù)結構的存儲方式只有兩種：數(shù)組（順序存儲）和鏈表（鏈式存儲）【一種是連續(xù)的存儲結構，一種是不連續(xù)的存儲結構】。
?數(shù)組的隨機訪問性強，查找速度快（連續(xù)內存空間導致的）；但是插入和刪除效率低【每次必須搬移后面的所有數(shù)據(jù)以保持連續(xù)，時間復雜度 O(N)】。但正因為連續(xù)存儲，內存空間必須一次性分配夠，可能浪費內存。數(shù)組大小固定，不能動態(tài)拓展。如果要擴容，需要重新分配一塊更大的空間，再把數(shù)據(jù)全部復制過去，時間復雜度 O(N)；按序號查找時，數(shù)組可以隨機訪問，時間復雜度為O(1)。按值查找時，若數(shù)組無序，時間復雜度為O(n)；但是當數(shù)組有序時，可以采用折半查找將時間復雜度降為O(logn)；
?鏈表插入刪除速度快，內存利用率高，不會浪費內存。大小沒有固定，拓展很靈活【每一個數(shù)據(jù)存儲了下一個數(shù)據(jù)的地址，增刪效率高，時間復雜度O(1)】。但是正因為存儲空間不連續(xù)，不能隨機查找，必須從第一個開始遍歷，查找效率低，平均需要O(n)。
二、什么是哈希表
?數(shù)據(jù)結構種類很多，甚至你也可以發(fā)明自己的數(shù)據(jù)結構，但是底層存儲無非數(shù)組或者鏈表。像堆棧、隊列、樹、圖等數(shù)據(jù)結構，數(shù)組和鏈表才是「結構基礎」。
?但是，上述這些數(shù)據(jù)結構，并不能折衷一下數(shù)組和鏈表的優(yōu)缺點。為了滿足數(shù)據(jù)的查找和修改很容易，同時又不占用很多空間，于是就有了所謂的哈希表【Hash table，散列表】，一種不同于堆棧、隊列、樹、圖的數(shù)據(jù)結構，可以說是數(shù)組和鏈表的結合體吧【結合了數(shù)組的快速查詢的優(yōu)點又能融合鏈表方便快捷的增加刪除元素的優(yōu)勢，不是指一定要同時使用到數(shù)組和鏈表兩種存儲結構】。
?那究竟什么是哈希表呢？
?其實所謂的哈希表，是一種根據(jù)<key—value>【也就是關鍵碼值】進行數(shù)據(jù)訪問的數(shù)據(jù)結構。乍一聽挺難理解，但并不復雜。
?核心思想：
?1、內部是一個數(shù)組
?2、關鍵碼key經(jīng)過變換(hash函數(shù))得到int類型的值
?3、int類型的值變成一個合法的下標
?4、把值value放到數(shù)組這個合法的下標的位置
?所以有：
?記錄的存儲位置=hashfunction(關鍵字)
?當向該結構中：
?1、插入元素
?根據(jù)待插入元素的關鍵碼，以此函數(shù)計算出該元素的存儲位置并按此位置進行存放。
?2、搜索元素
?對元素的關鍵碼進行同樣的計算，把求得的函數(shù)值當做元素的存儲位置，在結構中按此位置取元素比較，若關鍵碼相等，則搜索成功。
?該方式即為哈希(散列)方法，哈希方法中使用的轉換函數(shù)稱為哈希(散列)函數(shù)，構造出來的結構稱為哈希表(HashTable)(或者稱散列表)。
?所以說，散列技術既是一種存儲方法，也是一種查找方法。然而它與線性表、 樹、圖等結構不同的是，前面幾種結構，數(shù)據(jù)元素之間都存在某種邏輯關系，可以用連線圖示表示出來，而散列技術的記錄之間不存在什么邏輯關系，它只與關鍵字有關聯(lián)。因此，散列主要是面向査找的存儲結構。
三、哈希沖突以及負載系數(shù)
?在理想的情況下，每一個關鍵字key，通過散列函數(shù)計算出來的地址都是不一樣的，可現(xiàn)實中，這只是一個理想。
?我們時常會碰到兩個關鍵字key1 ≠ key2，但卻有f (key1) = f (key2)，這種現(xiàn)象稱為沖突（collision)，并把key1和 key2稱為這個散列函數(shù)的同義詞（synonym）。
?出現(xiàn)了沖突當然非常糟糕，那將造成數(shù)據(jù)査找錯誤。盡管我們可以通過精心設計的散列函數(shù)讓沖突盡可能的少，但是不能完全避免。于是如何處理沖突就成了一個很重要的課題，這在我們后面也需要詳細講解。
?處理哈希沖突是個大坑……需要深入了解的東西很多。當然，小編文章后半部分會來詳細解釋下。
?那什么又是哈希表的負載系數(shù)(Load Factor)呢？
?其實，負載系數(shù)的公式是 =
?其中N是哈希表的尺寸,n是哈希表中已存在元素個數(shù)。
?（1）α<1即表中有常有可用的空間，允許我們向當前哈希表插入其他元素
?（2）α=1即表中空間已經(jīng)被填滿,此時需要擴容
?（3）α>1即n>N已經(jīng)溢出，這種情況在具體的代碼實現(xiàn)中是要避免的。
?α我們也稱之為裝填因子。
?后面兩種情況，就要求我們對現(xiàn)在的哈希表的向操作系統(tǒng)申請更多的內容空間(更多存儲桶)，哈希表的這種操作就叫重散列(Rehashing)。
?至于什么是重散列，后續(xù)會講到。
四、哈希表的常用構造方法
1、直接定址法
?直接定址法使用下面的公式：
?比如統(tǒng)計出生年份，那么就可以使用f(key)=key-1990來計算存儲的位置，也就是散列地址。
#include <iostream>
#include <vector>
using namespace std;
//哈希表插入的每個數(shù)據(jù)節(jié)點
template <typename K, typename V>
class HashNode
{
public:
HashNode(const K& key = K(), const V& value = V())//加上K()和V()，可缺省構造
{
key_ = key;
value_ = value;
}
K key_;
V value_;
bool initialized_ = false;
};
template <typename K, typename V>
class HashTable
{
public:
HashTable(int size)
{
count=0;
node_num_ = size;// 存儲容量
nodes_.resize(size);//分配哈希表空間
}
//直接定址法
int hashFunction(const K& key)
{
return hash(key)-1990;
}
//根據(jù)關鍵碼查找鍵值
V find(const K& key)
{
int index = hashFunction(key);
if(nodes_[index].key_ == key)
{
return nodes_[index].value_;
}
}
//哈希表數(shù)據(jù)的插入
void insert(const K& key, const V& value)
{
if(whetherfull()){
int index = hashFunction(key);
count++;
nodes_[index].key_ = key;
nodes_[index].value_ = value;
nodes_[index].initialized_ = true;
}
}
//del()方法是刪除哈希表中某個數(shù)據(jù)。該方法接收一個參數(shù) key
void del(const K& key)
{
int index = hashFunction(key);
if(nodes_[index].initialized_)
{
count--;
nodes_[index].initialized_ = false;
cout<<"成功刪除"<<endl;
}else{
cout<<"哈希表中無該數(shù)據(jù)"<<endl;
}
}
int hash(const K& key)
{
return key;
}
bool whetherfull()
{
if(count<=node_num_){
return true;
}else{
cout<<"表已經(jīng)滿了，無法繼續(xù)插入數(shù)據(jù)"<<endl;
return false;
}
}
private:
vector<HashNode<K, V> > nodes_;
int node_num_;//存儲容量
int count;//當前存儲數(shù)據(jù)數(shù)
};
int main(int argc, char** argv)
{
HashTable<int, int> table(20);
table.insert(1991, 1281);
table.insert(1992, 1283);
table.insert(1993, 1834);
cout<<table.find(1993)<<endl;
table.del(1993);
return 0;
}
?這樣的散列函數(shù)優(yōu)點就是簡單、均勻，也不會產(chǎn)生沖突【不存在f (key1) = f (key2)的情況】，但問題是這需要事先知道關鍵字的分布情況，適合査找表較小且連續(xù)的情況。由于這樣的限制，在現(xiàn)實應用中，直接定址法雖然簡單，但卻并不常用。
2、除留余數(shù)法
?除留余數(shù)法此方法為最常用的構造散列函數(shù)方法。對于散列表長為m的散列函數(shù)公式為：
?mod是取模（求余數(shù)）的意思。
?很顯然，本方法的關鍵就在于選擇合適的p, p如果選得不好，就可能會容易產(chǎn)生同義詞。下面我們來舉個例子看看：
?最終得到的存儲結果如下：
#include <iostream>
#include <vector>
using namespace std;
//哈希表插入的每個數(shù)據(jù)節(jié)點
template <typename K, typename V>
class HashNode
{
public:
HashNode(const K& key = K(), const V& value = V())//加上K()和V()，可缺省構造
{
key_ = key;
value_ = value;
}
K key_;
V value_;
bool initialized_ = false;
};
template <typename K, typename V>
class HashTable
{
public:
HashTable(int size)
{
count=0;
node_num_ = size;// 存儲容量
nodes_.resize(size);//分配哈希表空間
}
//除留余數(shù)法
int hashFunction(const K& key)
{
return hash(key)%node_num_;
}
//根據(jù)關鍵碼查找鍵值
V find(const K& key)
{
int index = hashFunction(key);
if(nodes_[index].key_ == key)
{
return nodes_[index].value_;
}
}
//哈希表數(shù)據(jù)的插入
void insert(const K& key, const V& value)
{
if(whetherfull()){
int index = hashFunction(key);
count++;
nodes_[index].key_ = key;
nodes_[index].value_ = value;
nodes_[index].initialized_ = true;
}
}
//del()方法是刪除哈希表中某個數(shù)據(jù)。該方法接收一個參數(shù) key
void del(const K& key)
{
int index = hashFunction(key);
if(nodes_[index].initialized_)
{
count--;
nodes_[index].initialized_ = false;
cout<<"成功刪除"<<endl;
}else{
cout<<"哈希表中無該數(shù)據(jù)"<<endl;
}
}
int hash(const K& key)
{
return key;
}
bool whetherfull()
{
if(count<=node_num_){
return true;
}else{
cout<<"表已經(jīng)滿了，無法繼續(xù)插入數(shù)據(jù)"<<endl;
return false;
}
}
private:
vector<HashNode<K, V> > nodes_;
int node_num_;//存儲容量
int count;//當前存儲數(shù)據(jù)數(shù)
};
int main(int argc, char** argv)
{
HashTable<int, string> table(12);
table.insert(12, "喬丹");
table.insert(25, "魔術師");
//table.insert(1993, 1834);
cout<<table.find(12)<<endl;
//table.del(1993);
return 0;
}
?上述給的例子過于簡單且沒有出現(xiàn)沖突的情況，一旦出現(xiàn)沖突，小編上面的代碼可就不對勁了。因為這種求余數(shù)作為下標的出現(xiàn)沖突的機率還是常有的，我舉個極端的例子，如下所示：
?但是我們如果不選用p=12來做除留余數(shù)法，而選用p=11，大家計算下可以發(fā)現(xiàn)沖突減少了，只有兩個沖突。所以合理選取p值也能一定程度減少沖突。
?至于解決沖突有哪些方法，代碼該怎么補充修改，小編接下來也會講到的。
3、數(shù)字分析法
?數(shù)字分析法通常適合處理關鍵字位數(shù)比較大的情況，例如我們現(xiàn)在要存儲某家公司員工登記表，如用手機號作為關鍵字，那么我們發(fā)現(xiàn)抽樣后面的四位數(shù)字作為散列地址是不錯的選擇。
?我們來看個例子，看看使用哈希表怎么來進行存儲，如下圖所示：
?atoi這個函數(shù)這里小編就不詳細解釋了。
?具體代碼這里不再展示，只是更改下上述代碼的哈希函數(shù)而已。
?除了上述介紹的三種哈希表的構造方法之外，還有：
4、平方取中法
?取關鍵字平方之后的中間極為作為哈希地址，一個數(shù)平方之后中間幾位數(shù)字與數(shù)的每一位都相關，取得位數(shù)由表長決定。比如：表長為512,=2^9,可以取平方之后中間9位二進制數(shù)作為哈希地址。一個簡單的小例子：
5、折疊法
?關鍵字位數(shù)很多，而且關鍵字中每一位上的數(shù)字分布大致均勻的時候，把關鍵詞分割成位數(shù)相同的幾個部分，然后疊加。
五、哈希表的沖突解決算法
?hash沖突是不可能完全避免的，那么我們要考慮的還有就是當產(chǎn)生哈希沖突的時候，我們如何來解決。比較常見的hash沖突的解決方法有：開放定址法、鏈地址法。
?接下來，小編就來聊一聊這兩種沖突的解決辦法。
1、開放定址法
?其實，開放地址法很好理解。它的實現(xiàn)是在插入一個元素的時候，先通過哈希函數(shù)進行判斷，若是發(fā)生哈希沖突，就以當前地址為基準，根據(jù)再尋址的方法（探查序列），去尋找下一個地址，若發(fā)生沖突再去尋找，直至找到一個為空的地址為止，再將數(shù)值填充進去。所以這種方法又稱為再散列法。
?公式為：??其實，開放地址法包括三小種分別是 線性探測、平方探測、雙散列。下面依次介紹各種方法。
1.1線性探測法
?線性探測法的地址增量di = 1, 2, ... , tablesize-1，其中，i為探測次數(shù)。該方法一次探測下一個地址，知道有空的地址后插入，若整個空間都找不到空余的地址，則產(chǎn)生溢出。
?舉個例子，現(xiàn)在我們的關鍵字集合如下：
?當計算前5個數(shù){12,67,56,16,25}時，都是沒有沖突的散列地址，直接存入，得到：
?于是我們應用上面的公式f1(37) = (f(37)+1) mod 12 = 2。于是將37存入下標為2的位置。這其實就是房子被人買了于是買下一間的作法：
?我們把這種解決沖突的開放定址法稱為線性探測。
?可以發(fā)現(xiàn)，我們探測了多少次，di的最終值就為多少，是一個公差為1的遞增序列。
?所以呢，在插入、查找、刪除數(shù)據(jù)的時候，代碼要進一步的修改，代碼設計如下：
#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;
//哈希表插入的每個數(shù)據(jù)節(jié)點
template <typename K, typename V>
class HashNode
{
public:
HashNode(const K& key = K(), const V& value = V())//加上K()和V()，可缺省構造
{
key_ = key;
value_ = value;
}
K key_;
V value_;
int collision=0; //沖突次數(shù)
bool initialized_ = false;
};
template <typename K, typename V>
class HashTable
{
public:
HashTable(int size)
{
count=0;
node_num_ = size;// 存儲容量
nodes_.resize(size);//分配哈希表空間
}
//除留余數(shù)法
int hashFunction(const K& key)
{
return hash(key)%node_num_;
}
//根據(jù)關鍵碼查找鍵值
V find(const K& key)
{
int index = hashFunction(key);
int countnum=0;
while(nodes_[index].initialized_)//判斷該位置是否有值
{
if(countnum>=node_num_){
string s="哈希表中無該數(shù)據(jù)";
return s;
}
if(nodes_[index].key_==key)//判斷該位置的值的關鍵字是否相等
{
return nodes_[index].value_;
}
index++;
countnum++;
index=index%node_num_;
}
}
//哈希表數(shù)據(jù)的插入
void insert(const K& key, const V& value)
{
if(!whetherfull()){
return;
}
int index = hashFunction(key);
int collision=0;
count++;
//線性探測
//發(fā)生沖突，尋找下一個位置存放
while(nodes_[index].initialized_)
{
collision++;
index++;
if(index == node_num_)
{
index = 0;
}
}
nodes_[index].key_ = key;
nodes_[index].value_ = value;
nodes_[index].initialized_ = true;
nodes_[index].collision=collision;
}
//del()方法是刪除哈希表中某個數(shù)據(jù)。該方法接收一個參數(shù) key
void del(const K& key)
{
int index = hashFunction(key);
int countnum=0;
while(nodes_[index].initialized_ )
{
if(countnum-node_num_>=12)
{
cout<<"哈希表中無該數(shù)據(jù)"<<endl;
return ;
}
if(nodes_[index].key==key)
{
count--;
nodes_[index].initialized_ = false;
cout<<"成功刪除"<<endl;
return ;
}
index++;
index=index%node_num_;
}
}
int hash(const K& key)
{
return key;
}
void PrintHashTable()
{
for (int i = 0; i<node_num_; i++)
{
if(nodes_[i].initialized_){
cout<<"key: "<<nodes_[i].key_<<"--value: " <<nodes_[i].value_<<endl;
}else{
cout<<"key: [ ]--value: [ ]" <<endl;
}
}
}
bool whetherfull()
{
if(count<=node_num_){
return true;
}else{
cout<<"表已經(jīng)滿了，無法繼續(xù)插入數(shù)據(jù)"<<endl;
return false;
}
}
private:
vector<HashNode<K, V> > nodes_;
int node_num_;//存儲容量
int count;//當前存儲數(shù)據(jù)數(shù)
};
int main(int argc, char** argv)
{
HashTable<int, string> table(12);
table.insert(12, "喬丹");
table.insert(67, "科比");
table.insert(56, "魔術師");
table.insert(16, "庫里");
table.insert(25, "詹姆斯");
table.insert(37, "鄧肯");
table.insert(22, "格林");
table.insert(29, "杜蘭特");
table.insert(15, "奧尼爾");
table.insert(47, "姚明");
table.insert(48, "卡特");
table.insert(34, "歐文");
//table.insert(1993, 1834);
//cout<<table.find(12)<<endl;
cout<<table.find(64)<<endl;
table.PrintHashTable();
return 0;
}
?我們還是看剛才那個例子，可以發(fā)現(xiàn)我們在解決沖突的時候，為了處理沖突就會占用下一個位置，而如果沖突較多時，就會出現(xiàn)數(shù)據(jù)都聚集在一塊區(qū)域。例如48和37這種本來都不是同義詞卻需要爭奪一個地址的情況，我們稱這種現(xiàn)象為堆積【如果沖突較多時，就會出現(xiàn)數(shù)據(jù)都聚集在一塊區(qū)域】。很顯然，堆積的出現(xiàn)，使得我們需要不斷處理沖突，無論是存入還是査找效率都會大大降低。
1.2平方探測法
看例子
?我們看我們上述的例子，可以發(fā)現(xiàn)當最后一個key=34，f(key)=10,與22所在的位置沖突，可是22后面沒有空位置了，反而它的前面有一個空位置，盡管可以不斷地求余數(shù)后得到結果，但效率很差【從后到前】。
?因此我們可以改進di = 12, -12, 22, -22,……, q2, -q2 (q <= tablesize/2),這樣就等于是可以雙向尋找到可能的空位置。
?我們還是用上述的例子來進行闡述。關鍵字集合如下：
?當計算前5個數(shù){12,67,56,16,25}時，都是沒有沖突的散列地址，直接存入，得到：
代碼設計關鍵點之一
?下面，我們來分析下代碼設計中比較關鍵的地方。舉個例子，(-1) mod 12的余數(shù)正常為11，但是如果在C++編譯器中，這么去計算負數(shù)除以某個正整數(shù)的余數(shù)，如下代碼所示：
#include<iostream>
using namespace std;
int main()
{
int a=-1;
int c=a%12;
cout<<c<<endl;
return 0;
}
?程序運行后，發(fā)現(xiàn)輸出的結果為-1。這明顯不太對，因此我們需要做點小改進，有兩種方法。
#include<iostream>
using namespace std;
int main()
{
int a;//負整數(shù)
int b; //正整數(shù)
int c;
cin>>a>>b;
//第一種寫法
if(a%b<0){
c=a%b+b;
}else{
c=a%b;
}
//第二種 寫法
//c=（a%b+b)%b
cout<<c<<endl;
return 0;
}
上述解決方法真的對嗎
?上述問題是非常關鍵的，如果沒采取這種分類求余數(shù)方法，得到的結果還發(fā)生錯誤，導致地址探測出現(xiàn)問題。
?但是，如果我們用上述表長為12的哈希表去存儲其他數(shù)據(jù)，有可能會出現(xiàn)一些問題【一般情況下我們是把表長設置為質數(shù)/素數(shù)的】，接著往下看。
?對于線性探測，讓散列表近乎填滿元素是個壞主意，因為此時表的性能會降低。對于平方探測，情況更糟：一旦表被填滿超過一半，若表的大小不是素數(shù)，那么甚至在表被填滿一半之前，就不能保證找到空的單元了。這是因為最多只有表的一半可以用做解決沖突的備選位置。
?這又是為什么，小編簡單做個證明如下：
?證明：
?令表的大小tablesize是一個大于3的素數(shù)（質數(shù))，我們證明，前[tablesize / 2]個備選位置是互異的。
?可以得知(f(x)+i2) mod tablesize 和(f(x)+j2) mod tablesize 是這些位置中的兩個，其中0 < i, j <= [tablesize / 2]。為推出矛盾，假設這兩個位置相同，但i != j，于是:
?1) f(x) + i^2 ^= f(x) + j2 (mod tablesize)
?2) i2 - j2 = 0
?3) (i + j)(i - j) = 0
?所以i = -j或者i = j，因為i != j，且i,j都大于0,所以前[tablesize / 2]個備選位置是互異的。
?由于要被插入的元素，若無任何沖突發(fā)生，也可以放到經(jīng)散列得到的單元，因此任何元素都有[tablesize / 2]個可能被放到的位置，如果最多有[tablesize / 2]個位置可以使用，那么空單元總能夠找到。哪怕表有比一半多一個的位置被填滿，那么插入都有可能失敗。表的大小是素數(shù)也非常重要，如果表的大小不是素數(shù)，則備選單元的個數(shù)也可能銳減。
?開放定址散列表中，標準的刪除操作不能實行。因為相應的單元可能已經(jīng)引起過沖突，元素繞過了它存在了別處。因此，開放定址散列表需要懶惰刪除。
?定理1：如果使用平方探測，且表的大小是素數(shù)，那么當表至少有一半是空的時候，總能夠插入一個新的元素。
?接下來，我們來舉一個簡單的例子。
?將4個關鍵字分別為10,6,4,15的元素插入到大小為5的散列表中。
?hash函數(shù)f(x)=key mod 5。
?插入key=5時，f(10)=10 mod 5=0，插入，有：
?插入key=15時，f(15)=15 mod 5=0，發(fā)生沖突，探測下一個地址，有：f1(15)=(f(15)+12) mod 5=1，該位置已有數(shù)據(jù)繼續(xù)沖突，繼續(xù)探尋下一個地址；f2(15)=(f(15)-12) mod 5=4，該位置已有數(shù)據(jù)發(fā)生沖突，繼續(xù)探測下一個可用地址，有f3(x)=(f(15)+22) mod 5 =4,該位置已有數(shù)據(jù)發(fā)生沖突，繼續(xù)探測下一個可用地址，有f4(x)=(f(15)-22) mod 5 =1，該位置已有數(shù)據(jù)發(fā)生沖突。進行下一次探測時，q=3>tablesize/2【5/2】，因此探測結束。
?可以發(fā)現(xiàn)此時key=15這個元素使用平方探測法無法插入哈希表，但此時表中還有空位置。
?定理2：哈希表的長度為4k+3（k為整數(shù)）形式的素數(shù)，平方探測法可以探測到整個哈希表空間。
?了解完對應的知識后，我們可以來對代碼做下改進，如下：
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <math.h>
#include <cmath>
using namespace std;
//哈希表插入的每個數(shù)據(jù)節(jié)點
template <typename K, typename V>
class HashNode
{
public:
HashNode(const K& key = K(), const V& value = V())//加上K()和V()，可缺省構造
{
key_ = key;
value_ = value;
}
K key_;
V value_;
int collision=0; //沖突次數(shù)
bool initialized_ = false;
};
template <typename K, typename V>
class HashTable
{
public:
HashTable(int size)
{
count=0;
collision=0;
tablesize = nextPrime(size);// 存儲容量
nodes_.resize(tablesize);//分配哈希表空間
}
//找到下一個質數(shù)
int nextPrime(int n)
{
while(!isprime(n) ){
n++;
}
return n;
}
//判斷是否質數(shù)
bool isprime(int x)
{
//判斷質數(shù)
if(x==0||x==1){
return false;
}
for(int i=2;i<=(int)sqrt(x)+1;i++)
{
if(x%i==0){
return false;
}
}
return true;
}
//除留余數(shù)法
int hashFunction(const K& key)
{
return key%tablesize;
}
//找到空位置
int findpos(const K& key)
{
int index = hashFunction(key);
int indextemp=index;
int i=0,j=1;
collision=0;
//發(fā)生沖突，尋找下一個位置存放 【平方探測】
while(nodes_[index].initialized_ )//判斷該位置是否有值
{
if(nodes_[index].key_==key){
return index;
}
if(j>tablesize/2){
return tablesize;
}
collision++;
index=indextemp+pow(-1,i)*pow(j,2);//按照增量序列進行設計
if(hashFunction(index)<0){
index=hashFunction(index)+tablesize;
}else{
index=hashFunction(index);
}
i++;
if(i%2){
j++;
}
}
return index;
}
//根據(jù)關鍵碼查找鍵值
V find(const K& key)
{
int index=findpos(key);
if(nodes_[index].initialized_){
return nodes_[index].value_;
}else{
cout<<"查找不到"<<endl;
}
}
//哈希表數(shù)據(jù)的插入
void insert(const K& key, const V& value)
{
int index = findpos(key);
if(nodes_[index].initialized_){
cout<<"鍵值重復，無法插入"<<endl;
return;
}
if(index==tablesize){
cout<<"增量已經(jīng)大于tablesize/2，無法插入"<<endl;
return;
}
nodes_[index].key_ = key;
nodes_[index].value_ = value;
nodes_[index].initialized_ = true;
nodes_[index].collision=collision;
count++;
}
//del()方法是刪除哈希表中某個數(shù)據(jù)。該方法接收一個參數(shù) key
void del(const K& key)
{
int index = findpos(key);
if(nodes_[index].initialized_){
nodes_[index].initialized_ = false;
}else{
cout<<"表中沒有該數(shù)據(jù)"<<endl;
return ;
}
}
void PrintHashTable()
{
for (int i = 0; i<tablesize; i++)
{
if(nodes_[i].initialized_){
cout<<"key: "<<nodes_[i].key_<<"--value: " <<nodes_[i].value_<<endl;
}else{
cout<<"key: [ ]--value: [ ]" <<endl;
}
}
}
private:
vector<HashNode<K, V> > nodes_;
int tablesize;//存儲容量
int count;//當前存儲數(shù)據(jù)數(shù)
int collision;//臨時存儲沖突次數(shù)
};
int main(int argc, char** argv)
{
HashTable<int, string> table(4);
table.insert(10, "喬丹");
table.insert(6, "科比");
table.insert(4, "魔術師");
table.insert(15, "庫里");
/*table.insert(25, "詹姆斯");
table.insert(37, "鄧肯");
table.insert(22, "格林");
table.insert(29, "杜蘭特");
table.insert(15, "奧尼爾");
table.insert(47, "姚明");
table.insert(48, "卡特");
table.insert(34, "歐文");
//table.insert(1993, 1834);*/
//table.del(10);
//cout<<table.find(15)<<endl;
//table.rehash();
table.PrintHashTable();
return 0;
}
?上述代碼后續(xù)小編會進行適當優(yōu)化。
表空間不夠怎么辦
?對于使用平方探測法的閉散列里，如果元素填的太滿的話后續(xù)插入將耗費過長的時間，甚至可能insert失敗，因為這里面會有太多的移動和插入混合操作。怎么辦呢？一種解決方法是建立另外一個大約兩倍大的表，再用一個新的散列函數(shù)，掃描整個原始表然后按照新的映射插入到新的表里。上述有說過，這種操作叫做重散列【再散列】。
?我們舉一個最簡單的例子，有一個長度為3的哈希表，現(xiàn)在需要插入的鍵值對是(6,"Mosa")，(7,"Kally")，(8"Berry")，且哈系表的散列函數(shù)是 hash(k)=k mod N,當前N=3。
?這三個鍵值對插入表后的狀態(tài)，如下圖，當前N=3，n=3,那么α=1，此時，就需要執(zhí)行重散列的操作,以滿足后續(xù)插入元素有可用的存儲桶可用。
?那問題來了，究竟需要擴容至多大的尺寸才適合呢？首先實現(xiàn)哈希表的底層基本數(shù)據(jù)結構就是順序表，更貼切地說是數(shù)組,按照慣例就是新的內存空間是原來內存空間的2倍。
?這樣的話，擴容后的尺寸不就是N=2x3=6嗎？但是，我們前面剛分析過，若N是非素數(shù)的話，那么多個不同的鍵值對出現(xiàn)散列沖突的概率會比使用素數(shù)高出許多，也就是說新哈希表的尺寸N不可能是2的倍數(shù)。
?因此更準確地說，重散列的最終效果就是為哈希列表擴容提供更多的可用的存儲位置，我們擴容后的哈希表尺寸可以靠近2N附近的素數(shù)。在本例來說,因為2N=2x3=6，那么6附近的素數(shù)可以是5和7,或者遠點11,13都可以，當然按照我們這里的約定，當然7是完美的選擇。
?（1）只要表有一半滿了就做
?（2）只有當插入失敗時才做（這種比較極端）
?（3）途中策略：當表到達某個裝填因子時再做
?隨著裝填因子的增加，表的性能會有所下降，所以第三個方法或許是最好的。
?接下來貼上改進的代碼，如下：
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <math.h>
#include <cmath>
using namespace std;
//哈希表插入的每個數(shù)據(jù)節(jié)點
template <typename K, typename V>
class HashNode
{
public:
HashNode(const K& key = K(), const V& value = V())//加上K()和V()，可缺省構造
{
key_ = key;
value_ = value;
}
K key_;
V value_;
int collision=0; //沖突次數(shù)
bool initialized_ = false;
};
template <typename K, typename V>
class HashTable
{
public:
HashTable(int size)
{
count=0;
collision=0;
tablesize = nextPrime(size);// 存儲容量
nodes_.resize(tablesize);//分配哈希表空間
}
//找到下一個質數(shù)
int nextPrime(int n)
{
while(!isprime(n) ){
n++;
}
return n;
}
//判斷是否質數(shù)
bool isprime(int x)
{
//判斷質數(shù)
if(x==0||x==1){
return false;
}
for(int i=2;i<=(int)sqrt(x)+1;i++)
{
if(x%i==0){
return false;
}
}
return true;
}
//除留余數(shù)法
int hashFunction(const K& key)
{
return key%tablesize;
}
//找到空位置
int findpos(const K& key)
{
int index = hashFunction(key);
int indextemp=index;
int i=0,j=1;
collision=0;
//發(fā)生沖突，尋找下一個位置存放 【平方探測】
while(nodes_[index].initialized_ )//判斷該位置是否有值
{
if(nodes_[index].key_==key){
return index;
}
collision++;
index=indextemp+pow(-1,i)*pow(j,2);//按照增量序列進行設計
if(hashFunction(index)<0){
index=hashFunction(index)+tablesize;
}else{
index=hashFunction(index);
}
i++;
if(i%2){
j++;
}
}
return index;
}
//根據(jù)關鍵碼查找鍵值
V find(const K& key)
{
int index=findpos(key);
if(nodes_[index].initialized_){
return nodes_[index].value_;
}else{
cout<<"查找不到"<<endl;
}
}
//哈希表數(shù)據(jù)的插入
void insert(const K& key, const V& value)
{
int index = findpos(key);
if(nodes_[index].initialized_){
cout<<"鍵值重復，無法插入"<<endl;
return;
}
nodes_[index].key_ = key;
nodes_[index].value_ = value;
nodes_[index].initialized_ = true;
nodes_[index].collision=collision;
count++;
if(count>tablesize/2)
{
rehash();
}
}
//del()方法是刪除哈希表中某個數(shù)據(jù)。該方法接收一個參數(shù) key
void del(const K& key)
{
int index = findpos(key);
if(nodes_[index].initialized_){
nodes_[index].initialized_ = false;
}else{
cout<<"表中沒有該數(shù)據(jù)"<<endl;
return ;
}
}
//重散列
void rehash()
{
int oldTableSize = tablesize;
count=0;
vector<HashNode<K, V> > oldnodes_;
oldnodes_.assign(nodes_.begin(), nodes_.end());
tablesize=nextPrime(2*oldTableSize);
nodes_.clear();
nodes_.resize(tablesize);//分配哈希表空間
for( int i=0; i<oldTableSize; i++ )
{
if(oldnodes_[i].initialized_)
{
insert(oldnodes_[i].key_,oldnodes_[i].value_);
}
}
oldnodes_.clear();
}
void PrintHashTable()
{
for (int i = 0; i<tablesize; i++)
{
if(nodes_[i].initialized_){
cout<<"key: "<<nodes_[i].key_<<"--value: " <<nodes_[i].value_<<endl;
}else{
cout<<"key: [ ]--value: [ ]" <<endl;
}
}
}
private:
vector<HashNode<K, V> > nodes_;
int tablesize;//存儲容量
int count;//當前存儲數(shù)據(jù)數(shù)
int collision;//臨時存儲沖突次數(shù)
};
int main(int argc, char** argv)
{
HashTable<int, string> table(4);
table.insert(10, "喬丹");
table.insert(6, "科比");
table.insert(4, "魔術師");
table.insert(15, "庫里");
/*table.insert(25, "詹姆斯");
table.insert(37, "鄧肯");
table.insert(22, "格林");
table.insert(29, "杜蘭特");
table.insert(15, "奧尼爾");
table.insert(47, "姚明");
table.insert(48, "卡特");
table.insert(34, "歐文");
//table.insert(1993, 1834);*/
//table.del(10);
cout<<table.find(15)<<endl;
//table.rehash();
table.PrintHashTable();
return 0;
}
?重散列是一種非常昂貴的操作；其運行時間為O(N)，因為有N個元素要再散列而且表的大小約為2N，不過這并不經(jīng)常發(fā)生，所以實際效果并沒有這么差。本程序中只要表滿到一半就再散列。
1.3 雙散列
?雙重散列是線性開型尋址散列（開放尋址法）中的沖突解決技術。雙重散列使用在發(fā)生沖突時將第二個散列函數(shù)應用于鍵。
?此算法使用：(hash1(key) + i * hash2(key)) % tablesize
?hash1() 和 hash2() 是哈希函數(shù)，而 tablesize 是哈希表的大小。當發(fā)生碰撞時，我們通過重復增加 步長i 來尋找鍵。
?第一個hash函數(shù)：hash1(key) = key ％ tablesize。
?第二個hash函數(shù)是：hash2(key) = PRIME – (key ％ PRIME)，其中 PRIME 是小于tablesize的質數(shù)。
?當然，第二個Hash函數(shù)表現(xiàn)好的特征包括：
?（1）不會產(chǎn)生 0 索引
?（2）能在整個HashTable 循環(huán)探測
?（3）計算會快點
?（4）與第一個Hash函數(shù)互相獨立
?（5）PRIME 與 tablesize 是相對質數(shù)
?hash2( key )作為關鍵，必須要合理選取，否則會引起災難性的后果——各種撞車。這個策略暫時不做過多分析了。所以小編也不做解釋了。
2、鏈地址法
?前面我們談到了散列沖突處理的開放定址法，它的思路就是一旦發(fā)生了沖突，就去尋找下一個空的散列地址，這其實是一種治標不治本的沖突解決方法。那么，我們其實可以利用鏈表這一數(shù)據(jù)結構，把同一位置的沖突對象組織在一起，不就解決問題了嗎？哈哈，這種沖突解決方法就叫做鏈地址法。
?將所有關鍵字為同義詞的記錄存儲在一個單鏈表中，我們稱這種表為同義詞子表，在散列表中只存儲所有同義詞子表的頭指針。
舉個簡單的例子：
?對于關鍵字集合{12,67,56,16,25,37, 22,29,15,47,48,34}，我們用前面同樣的12為除數(shù)，進行除留余數(shù)法。得到的最終結果如下：
?此時，已經(jīng)不存在什么沖突換址的問題，無論有多少個沖突，都只是在當前位置給單鏈表增加結點的問題，很不錯的解決思路吧！
鏈地址法概述
?（1）一開始開辟一個tablesize的空間的數(shù)組；
?（2）將要存儲的對象轉換成整數(shù)，用tablesize取模，結果會對應到數(shù)組中的一個索引；如果發(fā)生哈希沖突，取模的結果會指向數(shù)組中同一個索引；
?（3）將產(chǎn)生哈希沖突的對象鏈入其對應索引掛接的對象的后面，形成一條鏈表；
?（4）數(shù)組中的每個索引后都掛有一條鏈表，這就是所謂的鏈地址法（Separate Chain）
?注意下，在拉鏈法中，裝填因子α可以大于 1，但一般均取α≤1。
鏈地址法的優(yōu)勢與缺點
?與開放定址法相比，拉鏈法有如下幾個優(yōu)點：
?（1）鏈地址法處理沖突簡單，且無堆積現(xiàn)象，即非同義詞決不會發(fā)生沖突，因此平均查找長度較短；
?（2）由于鏈地址法中各鏈表上的結點空間是動態(tài)申請的，故它更適合于造表前無法確定表長的情況；
?（3）開放定址法為減少沖突，要求裝填因子α較小，故當結點規(guī)模較大時會浪費很多空間。而鏈地址法中可取α≥1，且結點較大時，拉鏈法中增加的指針域可忽略不計，因此節(jié)省空間；
?（4）在用鏈地址法構造的散列表中，刪除結點的操作易于實現(xiàn)。只要簡單地刪去鏈表上相應的結點即可。而對開放地址法構造的散列表，刪除結點不能簡單地將被刪結 點的空間置為空，否則將截斷在它之后填人散列表的同義詞結點的查找路徑。這是因為各種開放地址法中，空地址單元（即開放地址）都是查找失敗的條件。因此在用開放地址法處理沖突的散列表上執(zhí)行刪除操作，只能在被刪結點上做刪除標記，而不能真正刪除結點。
?鏈地址法的缺點：指針需要額外的空間，故當結點規(guī)模較小時，開放定址法較為節(jié)省空間，而若將節(jié)省的指針空間用來擴大散列表的規(guī)模，可使裝填因子變小，這又減少了開放定址法中的沖突，從而提高平均查找速度。
?至于什么是平均查找長度，后續(xù)做個簡單補充。
貼上代碼
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <math.h>
#include <cmath>
using namespace std;
//哈希表插入的每個數(shù)據(jù)節(jié)點
template <typename K, typename V>
class HashNode
{
public:
HashNode(const K& key = K(), const V& value = V())//加上K()和V()，可缺省構造
{
key_ = key;
value_ = value;
}
K key_;
V value_;
int collision=0; //沖突次數(shù)
bool initialized_ = false;
HashNode<K,V>* NextNode=NULL;
};
template <typename K, typename V>
class HashTable
{
public:
typedef HashNode<K, V> hashnode;
HashTable(int size)
{
count=0;
collision=0;
tablesize = nextPrime(size);// 存儲容量
nodes_.resize(tablesize);//分配哈希表空間
}
//找到下一個質數(shù)
int nextPrime(int n)
{
while(!isprime(n) ){
n++;
}
return n;
}
//判斷是否質數(shù)
bool isprime(int x)
{
//判斷質數(shù)
if(x==0||x==1){
return false;
}
for(int i=2;i<=(int)sqrt(x)+1;i++)
{
if(x%i==0){
return false;
}
}
return true;
}
//除留余數(shù)法
int hashFunction(const K& key)
{
return key%tablesize;
}
//根據(jù)關鍵碼查找鍵值
hashnode* find(const K& key)
{
int index = hashFunction(key);
hashnode* p=nodes_[index].NextNode;
collision=0;
temp=NULL;
while (p && key != p->key_)
{
collision++;
temp=p;
p = p->NextNode;
}
return p;
}
//哈希表數(shù)據(jù)的插入
bool insert(const K& key, const V& value)
{
hashnode* p = find(key);
if (!p)
{
//關鍵詞未找到，可以插入
hashnode* new_cell = new hashnode();
new_cell->key_ = key;
new_cell->value_ = value;
new_cell->collision=collision;
int pos = hashFunction(key);
new_cell->NextNode = nodes_[pos].NextNode;
nodes_[pos].NextNode = new_cell;
return true;
}
else
{
cout << "鍵值已存在！" << endl;
return false;
}
}
//del()方法是刪除哈希表中某個數(shù)據(jù)。該方法接收一個參數(shù) key
void del(const K& key)
{
hashnode* p = find(key);
if(!p)
{
cout<<"無該數(shù)據(jù)"<<endl;
return ;
}
int pos=hashFunction(key);
if(!temp)
{
nodes_[pos].NextNode=p->NextNode;
}else{
temp->NextNode=p->NextNode;
}
cout<<"成功刪除"<<endl;
delete p;
return;
}
void PrintHashTable()
{
hashnode* p;
for (int i = 0; i <tablesize; i++)
{
p = nodes_[i].NextNode;
if(!p)
{
cout<<"key: [ ]--value: [ ]" <<endl;
}else{
while (p)
{
cout<<"key: "<<p->key_<<"--value: " <<p->value_<<"沖突次數(shù)："<<p->collision<<" ";
p = p->NextNode;
}
cout<<endl;
}
}
}
private:
vector<HashNode<K, V> > nodes_;
hashnode* temp;//用于存儲查找關鍵字在鏈表里的前一個數(shù)據(jù)地址
int tablesize;//存儲容量
int count;//當前存儲數(shù)據(jù)數(shù)
int collision;//臨時存儲沖突次數(shù)
};
int main(int argc, char** argv)
{
HashTable<int, string> table(4);
table.insert(10, "喬丹");
table.insert(6, "科比");
table.insert(4, "魔術師");
table.insert(15, "庫里");
/*table.insert(25, "詹姆斯");
table.insert(37, "鄧肯");
table.insert(22, "格林");
table.insert(29, "杜蘭特");
table.insert(15, "奧尼爾");
table.insert(47, "姚明");
table.insert(48, "卡特");
table.insert(34, "歐文");
//table.insert(1993, 1834);*/
// table.del(10);
//cout<<table.find(15)<<endl;
//table.rehash();
table.PrintHashTable();
return 0;
}
?PS：代碼雖然跑的起來，但小編水平有限可能也有需要改正的地方哈！
六、哈希表的查找性能
?我們使用平均查找長度（ASL）來度量查找表的查找效率：成功、不成功。
?這里，我們通過一個簡單例子了解下。
?關鍵字序列：{7、8、30、11、18、9、14}
?散列函數(shù)： H(Key) = (key x 3) MOD 7
?裝載因子： 0.7
?處理沖突：線性探測再散列法
1、查找成功的ASL計算方法：
?因為現(xiàn)在的數(shù)據(jù)是7個，填充因子是0.7。所以數(shù)組大小=7/0.7=10，即寫出來的散列表大小為10，下標從0~9。
?第一個元素7，帶入散列函數(shù)，計算得0。
?第二個元素8，帶入散列函數(shù)，計算得3。
?第三個元素30，帶入散列函數(shù)，計算得6。
?第四個元素11，帶入散列函數(shù)，計算得5。
?第五個元素18，帶入散列函數(shù)，計算得5；和11沖突，使用線性探測法，得7。
?第六個元素9，帶入散列函數(shù)，計算得6；和30沖突，使用線性探測法，得8。
?第七個元素14，帶入散列函數(shù)，計算得0；和7沖突，使用線性探測法，得1。
?所以散列表如下：
?這里的沖突次數(shù)計算不再重復，所謂的查找次數(shù)就是沖突次數(shù)加上1。
?成功平均查找長度(ASLs)=（1+2+1+1+1+3+3）/ 7=12/ 7
2、查找不成功的ASL計算方法：
?（1） 定義什么叫查找不成功
?查找不成功時呢？什么是查找不成功呢？查找不成功就是從查找位置開始直到一個位置為空需要比較的次數(shù)。
?舉個例子來說吧。在已知上面散列表的基礎上，如果要查找key為4的關鍵字。根據(jù)散列函數(shù)可以計算Hash(key)=Hash(4)=5。此時在地址為5的地方取出那個數(shù)字，發(fā)現(xiàn)key=11，不等于4。這就說明在裝填的時候會發(fā)生沖突。根據(jù)沖突處理方法，會繼續(xù)檢測地址為6的值，發(fā)現(xiàn)key=30，依然不等。這個時候到了地址為9，但是依然沒有找到。那么就說明根本就沒有key=4這個關鍵字，說明本次查找不成功，總共查找了5次。
?再舉一個例子。查找key為0的關鍵字，根據(jù)散列函數(shù)Hash(key)=Hash(0)=0。此時在地址為0的地方取出那個數(shù)字，發(fā)現(xiàn)key=7，不等于0。這就說明在裝填的時候會發(fā)生沖突。根據(jù)沖突處理方法，會繼續(xù)檢測地址為1的值，發(fā)現(xiàn)key=14，依然不等。這個時候到了地址為2，發(fā)現(xiàn)為空，依然沒有找到。所以停止查找，本次查找不成功。因為如果key=0這個關鍵字存在的話，依照沖突處理函數(shù)，就一定能找到它?？偛荒軄G了吧。故其查找次數(shù)為3。
?這里要注意下，當前哈希表線性探測地址時，最多會將整個表遍歷一遍，查找失敗則是遇到了空的地址。
?第二個難點，位置7、8、9要不要考慮呢？答案是不需要。一個解釋方式是通過哈希函數(shù)來解釋，哪個數(shù)字經(jīng)過哈希函數(shù)的映射之后能映射到7、8或者9？即哪個數(shù)字對7取模之后能得到7、8或者9？這個數(shù)字是不存在的，也就是說根本就不存在能夠通過哈希函數(shù)映射到7、8或者9的元素，也就不會有查找失敗了。這也是為什么ASL的分母是7的原因：要查找的所有元素的哈希函數(shù)映射都在0~6內。那為什么7、8或者9中存在元素呢？被前面的數(shù)字“推過來”的唄。所以，7、8或者9計入從其他位置開始的比較次數(shù)（分子），但是不從自身開始計算比較次數(shù)，也不計入分母。分母是模長。
?（2）根據(jù)第一點定義的不成功，依次推下去：
?查找地址為0的值所需要的次數(shù)為3；
?查找地址為1的值所需要的次數(shù)為2；
?查找地址為2的值所需要的次數(shù)為1；
?查找地址為3的值所需要的次數(shù)為2；
?查找地址為4的值所需要的次數(shù)為1；
?查找地址為5的值所需要的次數(shù)為5；
?查找地址為6的值所需要的次數(shù)為4
?（3）計算
?查找不成功ASLu=（3+2+1+2+1+5+4）/ 7=18/ 7
?對于其他沖突解決辦法，大抵上也是這么來計算的，比如鏈地址法就是下一個位置為null就代表查不到，其他的小編就不講了。
七、寫在最后
?啰里啰唆寫了一大堆，也算是總結了下知識吧。當然，也存在或多或少的錯誤，還得請小伙伴們多多指正。
?寫完這篇，算是真真正正在簡書寫了10萬以上的雜記了。想想為什么能夠堅持有空寫寫點東西呢，想來也是一種興趣。
