程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 數據結構與算法——散列表類的C++實現(探測散列表)

數據結構與算法——散列表類的C++實現(探測散列表)

編輯：C++入門知識

數據結構與算法——散列表類的C++實現(探測散列表)

散列表簡介：

散列表的實現常被稱為散列。散列是一種用於以常數平均時間執行插入、刪除和查找的技術。

散列的基本思想：

理想的散列表數據結構只不過是一個包含一些項的具有固定大小的數組。（表的大小一般為素數）
設該數組的大小為TbaleSize，我們向該散列表中插入數據，首先我們將該數據用一個函數（散列函數）映射一個數值x（位於0到TbaleSize1-1之間）；然後將該數據插入到散列表的第x的單元。(如果有多個數據映射到同一個數值，這個時候就會發生沖突)

散列函數介紹：

為了避免散列函數生成的值不是均勻分布，有一個比較好的散列函數可以使用。
在該散列函數中涉及數據中所有的字符，並且一般可以分布的很好,它計算的是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;
}

散列函數完成之後下面就是解決hash值的沖突問題。

解決沖突的方法主要有：分離鏈接法和開放定址法

分離鏈接法：分離鏈接法

開放定址法：

發生沖突的時候分離鏈接法需要給新的單元分配新的地址空間，這會導致算法導致算法速度減慢。還有另外一種思路可以解決hash值的沖突問題，當發生沖突的時候就嘗試選擇另外一個單元，直到找到空的單元。也就是依次嘗試h0(x), h1(x), h2(x).....,其中hi(x) = (hash(x) + f(i)) % TableSize，且f(0)=0，直到找到一個hi(x)單元是空的。函數f是沖突解決函數。因為此辦法是將所有的元素都放入散列表中，分離鏈接法是將有相同hash值的元素放在一個鏈表裡面，所以該方法要比分離鏈接法需要的散列表大。對於此方法的解決沖突方案需要的散列表的裝填因子應該低於0.5。裝填因子是散列表中的元素個數與散列表的大小的比值。所以該方法需要的散列表的大小應該大於等於元素個數的兩倍。我們稱使用此方法的散列表為探測散列表(probing hash tables).

探測散列表有三種常見的解決沖突的方法：線性探測、平方探測、雙散列。

線性探測：

線性探測中函數f是i的線性函數，一般情況下為f(i) = i。相當於是逐個探測散列表的單元直到查找出空單元。
下圖是一個例子：

在上面的例子中，第一個沖突發生在插入49的時候，h0(49)=9，但是此時第9個位置已經被占用了，所以只能繼續探測，直到找到一個空的位置。下一次探測的位置是h1(49)=0，第0個位置是空的，所有將49插入到第0個位置。插入58的時候探測了三次才找到了一個空位置。其它沖突類似。
經過統計，探測散列表如有多於一半的空間被填滿的時候，那麼線性探測就不是一個好方法了，此時插入和查找需要的探測次數比較多。如果裝填因子是0.5，那麼插入操作平均只需要2.5次探測，並且對於成功的查找平均只需要1.5次探測。
線性探測可能會出現一次聚集的問題，因為散列表被占用的空間會形成一塊連續的區域。這樣的話需要探測的次數就會比較多，因為探測需要經過該連續區域。

平方探測：

平方探測是消除線性探測中一次聚集問題的沖突解決方法。平方探測就是沖突函數f為二次函數。一般f(i） = i*i;
下面是一個和上面一樣的例子，見下圖：

經過證明：如果表的一半是空的，並且表的大小為素數，那麼可以保證總能夠插入一個新的元素。
平方探測雖然排除了一次聚集，但是散列到同一位置上的那些元素將探測相同的備選單元，這稱為二次聚集。該問題可以通過下面的雙散列方法解決。

雙散列：

雙散列一般沖突解決函數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){}
};

其中info有三種取值，{ACTIVE, EMPTY, DELETED};//每個數據單元都有一個info變量，表明該位置是否被占用、空或已刪除。

散列表類的主要成員函數：

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處的是否有元素

主要成員函數介紹：

1、再散列rehash():

當元素的個數大於散列表大小的一半的時候，需要擴大散列表的大小為原來的二倍。先保存原來的數據，再擴大原來的空間，再將原來的數據重新插入到新的散列表中。（此時一定要用insert成員函數，不能直接拷貝，因為涉及到hash值的重新計算）

/****************************************************************
*   函數名稱：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);
    }
}

2、查找元素的位置findPos():

該函數是查找一個元素應該處於散列表中的位置。當要插入元素的時候，首先調用該函數找到了空位置，然後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是要插入的元素
*   返回結果：如果找到空的位置則返回要插入的位置標號
*****************************************************************/
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;
}

3、插入函數insert():

/****************************************************************
*   函數名稱：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;

}

4、刪除函數remove():

remove刪除函數使用的是懶惰刪除，並不把散列表中的元素情況，僅僅是將標識位info設置為Deleted。

/****************************************************************
*   函數名稱：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;
}

定義數據類:

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;
};

將該類的對象插入到散列表中進行測試。在main函數可以看到。

下面是main函數，主要是對散列表類進行測試。

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;
}

下面是該散列表類的源代碼：

/*************************************************************************
	> 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