散列表的實現常被稱為散列。散列是一種用於以常數平均時間執行插入、刪除和查找的技術。
為了避免散列函數生成的值不是均勻分布,有一個比較好的散列函數可以使用。
在該散列函數中涉及數據中所有的字符,並且一般可以分布的很好,它計算的是0到KeySize-1進行求和Key[KeySize-i-1]*(37^i);
下面是該散列函數的實現:
/**************************************************************** * 函數名稱:hash(const string & key, int tableSize) * 功能描述: 根據鍵值求個hash值 * 參數列表: key 數據項的鍵值 * tableSize 散列表的大小 * 返回結果:返回hash值 *****************************************************************/ int hash(const string & key, int tableSize) { int hashVal = 0; //用散列函數的那個公式求和 for(int i = 0; i < key.length(); ++i) hashVal = 37*hashVal + key[i]; hashVal %= tableSize;//求得的hash值 if(hashVal < 0) hashVal += tableSize; return hashVal; }
線性探測中函數f是i的線性函數,一般情況下為f(i) = i。相當於是逐個探測散列表的單元直到查找出空單元。
下圖是一個例子:
在上面的例子中,第一個沖突發生在插入49的時候,h0(49)=9,但是此時第9個位置已經被占用了,所以只能繼續探測,直到找到一個空的位置。下一次探測的位置是h1(49)=0,第0個位置是空的,所有將49插入到第0個位置。插入58的時候探測了三次才找到了一個空位置。其它沖突類似。
經過統計,探測散列表如有多於一半的空間被填滿的時候,那麼線性探測就不是一個好方法了,此時插入和查找需要的探測次數比較多。如果裝填因子是0.5,那麼插入操作平均只需要2.5次探測,並且對於成功的查找平均只需要1.5次探測。
線性探測可能會出現一次聚集的問題,因為散列表被占用的空間會形成一塊連續的區域。這樣的話需要探測的次數就會比較多,因為探測需要經過該連續區域。
經過證明:如果表的一半是空的,並且表的大小為素數,那麼可以保證總能夠插入一個新的元素。
平方探測雖然排除了一次聚集,但是散列到同一位置上的那些元素將探測相同的備選單元,這稱為二次聚集。該問題可以通過下面的雙散列方法解決。
雙散列一般沖突解決函數f(i) = i * hash2(x);
這又涉及到第二個散列函數hash2(x)的選擇,一般我們選擇hash2(x) = R - (x % R),其中R是小於TableSize的素數。
下面是一個和上面一樣的例子,見下圖:
我們選擇R=7,因為TableSize=10,一般TableSize為素數,這裡為了簡單,將TableSize設置為10。
//散列表的數據單元結構 struct HashEntry{ HashedObj element;//該散列表存放的數據 EntryType info;//表明該位置的狀態 HashEntry(const HashedObj & e = HashedObj(), EntryType i = EMPTY):element(e), info(i){} };
bool containes(const HashedObj & x);//判斷是否包含數據項x void makeEmpty();//清空散列表 bool isEmpty(); bool insert(const HashedObj & x);//插入項x bool remove(const HashedObj & x);//刪除項x void print();//輸出散列表中的內容 int findPos(const HashedObj & x);//根據名字查找數據項 HashedObj findElement(const HashedObj & x);//根據名字查找數據項,並返回 void rehash();//再散列 int myhash(const HashedObj & x) const;//散列函數 int nextPrime(int n);//求的距離N最近的一個大於N的素數 int prePrime(int n);//求距離N最近的一個小於N的素數 bool isActive(int currentPos) const;//判斷位置currentPos處的是否有元素
/**************************************************************** * 函數名稱:rehash() * 功能描述: 擴大散列表的大小 * 參數列表: 無 * 返回結果:無 *****************************************************************/ templatevoid HashTable ::rehash() { vector oldArray = array; //創建一個新的大小為原來兩倍大小的散列表 array.resize(nextPrime(2 * oldArray.size())); for(int i = 0; i < array.size(); ++i) array[i].info = EMPTY; currentSize = 0; //復制散列表 for(int i = 0; i < oldArray.size(); ++i){ if(oldArray[i].info == ACTIVE) insert(oldArray[i].element); } }
該函數是查找一個元素應該處於散列表中的位置。當要插入元素的時候,首先調用該函數找到了空位置,然後insert函數在該空位置插入元素。如果要插入的元素存在,則也返回該位置,然後insert函數中會判斷是否已經存在該元素,如果已經存在則返回false,否則插入該元素。
該函數有三種解決沖突的方法:線性探測、平方探測、雙散列。也就是實現了三種f(i)函數。
//currentPos += offset;//線性探測
currentPos += 2 * offset -1;//平方探測
//currentPos += prePrime(array.size()) - myhash(x)%prePrime(array.size());//雙散列
本例中使用了平方探測,如果想用其它探測方式,將該方式去除注釋,就把另外兩種方式屏蔽。
/**************************************************************** * 函數名稱:findPos(const HashedObj & x) const * 功能描述: 查找x應該插入的位置 * 參數列表: x是要插入的元素 * 返回結果:如果找到空的位置則返回要插入的位置標號 *****************************************************************/ templateint HashTable ::findPos(const HashedObj & x) { //線性探測f(i) = i; f(i) = f(i-1) + 1;相隔為1 //平方探測f(i) = i*i; f(i) = f(i-1) + 2*i - 1; 相隔為2*i-1 //雙散列,f(i) = i*hash2(x); f(i) = f(i-1)+hash2(x);相隔為hash2(x); //hash2(x) = R-(x%R); R=prePrime(array.size()),R為小於TableSize()的素數 int offset = 1; int currentPos = myhash(x); //如果找到了空的位置則返回位置標號 //如果找到了該元素x,則返回該元素的位置標號 while(array[currentPos].info != EMPTY && array[currentPos].element != x){ //currentPos += offset;//線性探測 currentPos += 2 * offset -1;//平方探測 //currentPos += prePrime(array.size()) - myhash(x)%prePrime(array.size());//雙散列 offset++; if(currentPos >= array.size()) currentPos -= array.size(); } return currentPos; }
/**************************************************************** * 函數名稱:insert(const HashedObj & x) * 功能描述: 在散列表中插入元素x,如果插入項已經存在,則什麼都不做。 * 否則將其放在表的前端 * 參數列表: x數據項 * 返回結果:插入成功返回true, 否則返回false *****************************************************************/ templatebool HashTable ::insert(const HashedObj & x) { int currentPos = findPos(x);//先找到位置 if(isActive(currentPos))//如果該位置處已經存放了該元素,則之間返回false return false; array[currentPos] = HashEntry(x, ACTIVE); //如果當前散列表中元素的個數大於散列表長度的一半,則擴大散列表為原來的2倍 if(++currentSize > array.size()/2) rehash();//擴充表的大小 return true; }
/**************************************************************** * 函數名稱:remove(const HashedObj & x) * 功能描述: 刪除散列表中的值為x的元素 * 參數列表: x數據項 * 返回結果:成功刪除返回true,否則返回false *****************************************************************/ templatebool HashTable ::remove(const HashedObj & x) { int currentPos = findPos(x); if(!isActive(currentPos)) return false; array[currentPos].info = DELETED;//懶惰刪除,僅僅將標識位info設置為Deleted --currentSize; return true; }
class Employee{ public: Employee(){name=""; salary=0.0; seniority=0;}; Employee(const string & n, double sal, int sen):name(n), salary(sal), seniority(sen){} //獲得該類的name成員 const string & getName() const { return name; } //重載==運算符 bool operator==(const Employee & rhs) const { return getName() == rhs.getName(); } //重載!=運算符 bool operator!=(const Employee & rhs) const { return !(*this == rhs); } friend ostream & operator<<(const ostream & os, const Employee & e){ cout << "name: " << e.name << ",\tsalary: " << e.salary << ",\tseniority: " << e.seniority; } private: string name; double salary; int seniority; };
int main() { Employee e1("linux", 101.00, 1); Employee e2("ever", 102.00, 2); Employee e3("peter", 103.00, 3); Employee e4("may", 104.00, 4); Employee e5("usa", 105.00, 5); Employee e6("sal", 106.00, 6); Employee e7("usa", 107.00, 7);//和上面的值重復,所以這個值會被忽略 Employee e8("jan", 108.00, 8); Employee e9("kro", 109.00, 9); Employee e10("bei", 110.00, 10); Employee e12("bbb", 110.00, 10); vectorv; v.push_back(e1); v.push_back(e2); v.push_back(e3); v.push_back(e4); v.push_back(e5); v.push_back(e6); v.push_back(e7); v.push_back(e8); v.push_back(e9); v.push_back(e10); cout << "v: " << endl; for(unsigned i = 0; i < v.size(); ++i) cout << v[i] << endl; cout << endl; HashTable hashTable; for(unsigned i = 0; i < v.size(); ++i) hashTable.insert(v[i]); hashTable.print(); cout << endl; cout << "測試包含函數containes: " << endl; if(hashTable.containes(e10)) cout << "containe e10" << endl; else cout << "not containe e10" << endl; if(hashTable.containes(e12)) cout << "containe e12" << endl; else cout << "not containe e12" << endl; cout << "\n測試findElement(): " << endl; Employee e11 = hashTable.findElement(e8); cout << "e11: " << e11 << endl; cout << endl; cout << "測試isEmpty(): " << endl; if(hashTable.isEmpty()) cout << "hashTable is Empty " << endl; else cout << "hashTable is not Empty " << endl; cout << endl; cout << "測試makeEmpty(): " << endl; hashTable.makeEmpty(); if(hashTable.isEmpty()) cout << "hashTable is Empty " << endl << endl; else cout << "hashTable is not Empty " << endl; return 0; }
/************************************************************************* > File Name: hashTable.cpp > Author: > Mail: > Created Time: 2016年04月12日 星期二 10時35分14秒 ************************************************************************/ #include#include #include #include using namespace std; /**************************************************************** * 數據類名稱:Employee * 內容描述: 作為散列表的數據項目 *****************************************************************/ class Employee{ public: Employee(){name=""; salary=0.0; seniority=0;}; Employee(const string & n, double sal, int sen):name(n), salary(sal), seniority(sen){} //獲得該類的name成員 const string & getName() const { return name; } //重載==運算符 bool operator==(const Employee & rhs) const { return getName() == rhs.getName(); } //重載!=運算符 bool operator!=(const Employee & rhs) const { return !(*this == rhs); } friend ostream & operator<<(const ostream & os, const Employee & e){ cout << "name: " << e.name << ",\tsalary: " << e.salary << ",\tseniority: " << e.seniority; } private: string name; double salary; int seniority; }; /**************************************************************** * 函數名稱:hash(const HashedObj & key) * 功能描述: 根據鍵值求個hash值,這個函數是根據一個特定的數學公式 * 參數列表: key 數據項的鍵值 * 返回結果:返回一個通過散列函數求得的值 *****************************************************************/ int hash(const string & key) { int hashVal = 0; //用散列函數的那個公式求和 for(int i = 0; i < key.length(); ++i) hashVal = 37*hashVal + key[i]; return hashVal; } /**************************************************************** * 函數名稱:hash(const HashedObj & key) * 功能描述: 根據鍵值求個hash值,這個函數是根據一個特定的數學公式 * 參數列表: key 數據項的鍵值 * 返回結果:返回一個通過散列函數求得的值 *****************************************************************/ int hash(const Employee & item) { return hash(item.getName()); } /**************************************************************** * 散列表類名稱:HashTable * 內容描述: 散列表類 *****************************************************************/ template
class HashTable{ public: explicit HashTable(int size = 11):array(nextPrime(size)), currentSize(0){makeEmpty();} ~HashTable(); bool containes(const HashedObj & x);//判斷是否包含數據項x void makeEmpty();//清空散列表 bool isEmpty(); bool insert(const HashedObj & x);//插入項x bool remove(const HashedObj & x);//刪除項x void print();//輸出散列表中的內容 int findPos(const HashedObj & x);//根據名字查找數據項 HashedObj findElement(const HashedObj & x);//根據名字查找數據項,並返回 enum EntryType {ACTIVE, EMPTY, DELETED};//每個數據單元都有一個info變量,表明該位置是否被占用、空或已刪除 private: //散列表的數據單元結構 struct HashEntry{ HashedObj element;//該散列表存放的數據 EntryType info;//表明該位置的狀態 HashEntry(const HashedObj & e = HashedObj(), EntryType i = EMPTY):element(e), info(i){} }; vector array;//散列表 int currentSize;//散列表中當前存放的元素個數 private: void rehash();//再散列 int myhash(const HashedObj & x) const;//散列函數 int nextPrime(int n);//求的距離N最近的一個大於N的素數 int prePrime(int n);//求距離N最近的一個小於N的素數 bool isActive(int currentPos) const;//判斷位置currentPos處的是否有元素 public: friend ostream & operator<<(const ostream & os, const HashEntry & e){ cout << "element: " << e.element << ", info = " << e.info; } }; /**************************************************************** * 函數名稱:findElement(const HashedObj & x) const * 功能描述: 查找x的位置 * 參數列表: x是要查找的元素 * 返回結果:如果找到則返回該元素的引用 *****************************************************************/ template HashedObj HashTable ::findElement(const HashedObj & x) { int currentPos = findPos(x); if(isActive(currentPos))//找了則返回 return array[currentPos].element; else{//沒有找到,返回一個空值 HashedObj obj; return obj; } } /**************************************************************** * 函數名稱:findPos(const HashedObj & x) const * 功能描述: 查找x應該插入的位置 * 參數列表: x是要插入的元素 * 返回結果:如果找到空的位置則返回要插入的位置標號 *****************************************************************/ template int HashTable ::findPos(const HashedObj & x) { //線性探測f(i) = i; f(i) = f(i-1) + 1;相隔為1 //平方探測f(i) = i*i; f(i) = f(i-1) + 2*i - 1; 相隔為2*i-1 //雙散列,f(i) = i*hash2(x); f(i) = f(i-1)+hash2(x);相隔為hash2(x); //hash2(x) = R-(x%R); R=prePrime(array.size()),R為小於TableSize()的素數 int offset = 1; int currentPos = myhash(x); //如果找到了空的位置則返回位置標號 //如果找到了該元素x,則返回該元素的位置標號 while(array[currentPos].info != EMPTY && array[currentPos].element != x){ //currentPos += offset;//線性探測 currentPos += 2 * offset -1;//平方探測 //currentPos += prePrime(array.size()) - myhash(x)%prePrime(array.size());//雙散列 offset++; if(currentPos >= array.size()) currentPos -= array.size(); } return currentPos; } /**************************************************************** * 函數名稱:print() * 功能描述: 輸出散列表中的內容 * 參數列表: 無 * 返回結果:無 *****************************************************************/ template void HashTable ::print() { cout << "輸出散列表中的內容: " << endl; for(unsigned i = 0; i < array.size(); ++i){ if(isActive(i)) cout << i << ": " << endl << array[i] << endl; } } /**************************************************************** * 函數名稱:isEmpty() * 功能描述: 判斷散列表是否為空 * 參數列表: 無 * 返回結果:無 *****************************************************************/ template bool HashTable ::isEmpty() { return currentSize == 0; } /**************************************************************** * 函數名稱:makeEmpty() * 功能描述: 清空散列表 * 參數列表: 無 * 返回結果:無 *****************************************************************/ template void HashTable ::makeEmpty() { for(int i = 0; i < array.size(); ++i) array[i].info = EMPTY; currentSize = 0;//當前元素個數設為0 } /**************************************************************** * 函數名稱:containes(const HashedObj & x) const * 功能描述: 判斷散列表是否包含值為x的元素 * 參數列表: x數據項 * 返回結果:如果包括x則返回true,否則返回false *****************************************************************/ template bool HashTable ::containes(const HashedObj & x) { //findPos(x)返回的位置是ACTIVE的說明存在該元素x return isActive(findPos(x)); } /**************************************************************** * 函數名稱:isActive(int currentPos) const * 功能描述: 判斷位置currentPos處的是否有元素 * 參數列表: currentPos是散列表currentPos處的位置 * 返回結果:如果currentPos處有元素則返回true,否則返回false *****************************************************************/ template bool HashTable ::isActive(int currentPos) const { return array[currentPos].info == ACTIVE; } /**************************************************************** * 函數名稱:remove(const HashedObj & x) * 功能描述: 刪除散列表中的值為x的元素 * 參數列表: x數據項 * 返回結果:成功刪除返回true,否則返回false *****************************************************************/ template bool HashTable ::remove(const HashedObj & x) { int currentPos = findPos(x); if(!isActive(currentPos)) return false; array[currentPos].info = DELETED;//懶惰刪除,僅僅將標識位info設置為Deleted --currentSize; return true; } /**************************************************************** * 函數名稱:insert(const HashedObj & x) * 功能描述: 在散列表中插入元素x,如果插入項已經存在,則什麼都不做。 * 否則將其放在表的前端 * 參數列表: x數據項 * 返回結果:插入成功返回true, 否則返回false *****************************************************************/ template bool HashTable ::insert(const HashedObj & x) { int currentPos = findPos(x);//先找到位置 if(isActive(currentPos))//如果該位置處已經存放了該元素,則之間返回false return false; array[currentPos] = HashEntry(x, ACTIVE); //如果當前散列表中元素的個數大於散列表長度的一半,則擴大散列表為原來的2倍 if(++currentSize > array.size()/2) rehash();//擴充表的大小 return true; } /**************************************************************** * 函數名稱:~HashTable() * 功能描述: 析構函數 * 參數列表: 無 * 返回結果:無 *****************************************************************/ template HashTable ::~HashTable() { } /**************************************************************** * 函數名稱:prePrime(int n) * 功能描述: 獲得距離n最近的一個小於n的素數 * 參數列表: n表示數值 * 返回結果:返回一個素數 *****************************************************************/ template int HashTable ::prePrime(int n) { int i; if(n % 2 == 0) n--; for(; ; n -= 2){ for(i = 3; i*i <= n; i += 2){ if(n % i == 0) goto ContOuter; } return n; ContOuter: ; } } /**************************************************************** * 函數名稱:nextPrime(int n) * 功能描述: 獲得距離n最近的一個大於n的素數 * 參數列表: n表示數值 * 返回結果:返回一個素數 *****************************************************************/ template int HashTable ::nextPrime(int n) { int i; if(n % 2 == 0) n++; for(; ; n += 2){ for(i = 3; i*i <= n; i += 2) if(n % i == 0) goto ContOuter; return n; ContOuter: ; } } /**************************************************************** * 函數名稱:rehash() * 功能描述: 擴大散列表的大小 * 參數列表: 無 * 返回結果:無 *****************************************************************/ template void HashTable ::rehash() { vector oldArray = array; //創建一個新的大小為原來兩倍大小的散列表 array.resize(nextPrime(2 * oldArray.size())); for(int i = 0; i < array.size(); ++i) array[i].info = EMPTY; currentSize = 0; //復制散列表 for(int i = 0; i < oldArray.size(); ++i){ if(oldArray[i].info == ACTIVE) insert(oldArray[i].element); } } /**************************************************************** * 函數名稱:myhash(const HashedObj & key) * 功能描述: 根據鍵值求個hash值 * 參數列表: key 數據項的鍵值 * 返回結果:返回hash值 *****************************************************************/ template int HashTable ::myhash(const HashedObj & key) const { int hashVal = hash(key); hashVal %= array.size(); if(hashVal < 0) hashVal += array.size(); return hashVal; } int main() { Employee e1("linux", 101.00, 1); Employee e2("ever", 102.00, 2); Employee e3("peter", 103.00, 3); Employee e4("may", 104.00, 4); Employee e5("usa", 105.00, 5); Employee e6("sal", 106.00, 6); Employee e7("usa", 107.00, 7);//和上面的值重復,所以這個值會被忽略 Employee e8("jan", 108.00, 8); Employee e9("kro", 109.00, 9); Employee e10("bei", 110.00, 10); Employee e12("bbb", 110.00, 10); vector v; v.push_back(e1); v.push_back(e2); v.push_back(e3); v.push_back(e4); v.push_back(e5); v.push_back(e6); v.push_back(e7); v.push_back(e8); v.push_back(e9); v.push_back(e10); cout << "v: " << endl; for(unsigned i = 0; i < v.size(); ++i) cout << v[i] << endl; cout << endl; HashTable hashTable; for(unsigned i = 0; i < v.size(); ++i) hashTable.insert(v[i]); hashTable.print(); cout << endl; cout << "測試包含函數containes: " << endl; if(hashTable.containes(e10)) cout << "containe e10" << endl; else cout << "not containe e10" << endl; if(hashTable.containes(e12)) cout << "containe e12" << endl; else cout << "not containe e12" << endl; cout << "\n測試findElement(): " << endl; Employee e11 = hashTable.findElement(e8); cout << "e11: " << e11 << endl; cout << endl; cout << "測試isEmpty(): " << endl; if(hashTable.isEmpty()) cout << "hashTable is Empty " << endl; else cout << "hashTable is not Empty " << endl; cout << endl; cout << "測試makeEmpty(): " << endl; hashTable.makeEmpty(); if(hashTable.isEmpty()) cout << "hashTable is Empty " << endl << endl; else cout << "hashTable is not Empty " << endl; return 0; }
v: name: linux, salary: 101, seniority: 1 name: ever, salary: 102, seniority: 2 name: peter, salary: 103, seniority: 3 name: may, salary: 104, seniority: 4 name: usa, salary: 105, seniority: 5 name: sal, salary: 106, seniority: 6 name: usa, salary: 107, seniority: 7 name: jan, salary: 108, seniority: 8 name: kro, salary: 109, seniority: 9 name: bei, salary: 110, seniority: 10 輸出散列表中的內容: 1: element: name: kro, salary: 109, seniority: 9, info = 0 3: element: name: jan, salary: 108, seniority: 8, info = 0 4: element: name: may, salary: 104, seniority: 4, info = 0 5: element: name: bei, salary: 110, seniority: 10, info = 0 6: element: name: usa, salary: 105, seniority: 5, info = 0 17: element: name: ever, salary: 102, seniority: 2, info = 0 18: element: name: sal, salary: 106, seniority: 6, info = 0 21: element: name: peter, salary: 103, seniority: 3, info = 0 22: element: name: linux, salary: 101, seniority: 1, info = 0 測試包含函數containes: containe e10 not containe e12 測試findElement(): e11: name: jan, salary: 108, seniority: 8 測試isEmpty(): hashTable is not Empty 測試makeEmpty(): hashTable is Empty