程式師世界 >> 編程語言 >> 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值的沖突問題。

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

分離鏈接法：

思路是做法是將散列到同一個值的所有元素保留到一個鏈表中，該鏈表可以直接使用STL中的list類實現（該鏈表是雙向鏈表）。
此時散列表的結構為： vector > v;

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

bool containes(const HashedObj & x) const;//判斷是否包含數據項x
void makeEmpty();//清空散列表
bool isEmpty();
bool insert(const HashedObj & x);//插入項x
bool remove(const HashedObj & x);//刪除項x

void print();//輸出散列表中的內容
HashedObj findElement(const HashedObj & x);//根據名字查找數據項
void rehash();//再散列
int myhash(const HashedObj & x) const;//散列函數
int nextPrime(int n);//求的距離N最近的一個素數

主要成員函數介紹：

1、再散列rehash():

如果散列表的大小太小了就要進行再散列，在分離鏈接法中很簡單，就是將散列表的大小擴大原來的兩倍。
然後將原來散列表的內容拷貝到新的散列表中。nextPrime函數是為了求的一個素數，因為一般我們讓散列表的大小為一個素數。

/****************************************************************
*   函數名稱：rehash()
*   功能描述: 擴大散列表的大小
*   參數列表: 無
*   返回結果：無 
*****************************************************************/
template
void HashTable::rehash()
{
    vector > oldLists = theLists;
    
    //創建一個新的大小為原來兩倍大小的散列表
    theLists.resize(nextPrime(2 * theLists.size()));

    for(int i = 0; i < theLists.size(); ++i)
        theLists[i].clear();

    //復制散列表
    for(int i = 0; i < oldLists.size(); ++i){
        typename  list::iterator it = oldLists[i].begin();
        while(it != oldLists[i].end())
            insert(*it++);
    }
}

2、散列函數myhash()

該函數會調用hash(key)，使用了函數重載，目的是將不同類型的數據進行hash計算求hash值

/****************************************************************
*   函數名稱：myhash(const HashedObj & key)
*   功能描述: 根據鍵值求個hash值 
*   參數列表: key 數據項的鍵值 
*   返回結果：返回hash值
*****************************************************************/
template
int HashTable::myhash(const HashedObj & key) const
{
    int hashVal = hash(key);
    
    hashVal %= theLists.size();

    if(hashVal < 0)
        hashVal += theLists.size();

    return hashVal;
}

3、插入函數insert(const HashedObj & x)

/****************************************************************
*   函數名稱：insert(const HashedObj & x)
*   功能描述: 在散列表中插入元素x,如果插入項已經存在，則什麼都不做。
*             否則將其放在表的前端
*   參數列表: x數據項
*   返回結果：插入成功返回true, 否則返回false
*****************************************************************/
template
bool HashTable::insert(const HashedObj & x)
{
    list & whichList = theLists[myhash(x)];

    if(find(whichList.begin(), whichList.end(), x) != whichList.end())
        return false;

    whichList.push_back(x);

    //rehash
    if(++currentSize > theLists.size())
        rehash();//擴充表的大小

    return true;

}

4、刪除函數remove(const HashedObj & x)

/****************************************************************
*   函數名稱：containes(const HashedObj & x) const
*   功能描述: 判斷散列表是否包含值為x的元素 
*   參數列表: x數據項
*   返回結果：如果包括x則返回true,否則返回false
*****************************************************************/
template
bool HashTable::remove(const HashedObj & x)
{
    list & whichList = theLists[myhash(x)];

    typename list::iterator it = find(whichList.begin(), whichList.end(), x);

    if(it == whichList.end())
        return false;

    whichList.erase(it);//刪除元素x
    --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 << endl;
        }
    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];
    cout << endl;

    HashTable hashTable;
    
    for(unsigned i = 0; i < v.size(); ++i)
        hashTable.insert(v[i]);

    hashTable.print();

    cout << endl;
    //測試查找函數findElement
    cout << "測試查找函數findElement: " << endl;
    Employee e11 = hashTable.findElement(e12);
    cout << "e11 = " << e11;
    Employee e13 = hashTable.findElement(e10);
    cout << "e13 = " << e13;
    cout << endl;

    cout << "測試包含函數containes: " << endl; 
    if(hashTable.containes(e10))
        cout << "containe e10" << endl;
    else 
        cout << "not containe e10" << endl;

    if(hashTable.containes(e11))
        cout << "containe e11" << endl;
    else 
        cout << "not containe e11" << endl;
        
    cout << "測試remove()：" << endl;
    hashTable.remove(e10);
    if(hashTable.containes(e10))
        cout << "containe e10" << endl;
    else 
        cout << "not containe e10" << 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;
    cout << 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 << endl;
        }
    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):theLists(size), currentSize(0){}
        ~HashTable();

        bool containes(const HashedObj & x) const;//判斷是否包含數據項x
        void makeEmpty();//清空散列表
        bool isEmpty();
        bool insert(const HashedObj & x);//插入項x
        bool remove(const HashedObj & x);//刪除項x

        void print();//輸出散列表中的內容
        HashedObj findElement(const HashedObj & x);//根據名字查找數據項


    private:
        vector > theLists;//散列表的結構,theLists大小默認初始化為11
        int currentSize;//散列表中當前存放的元素個數
    private:
        void rehash();//再散列
        int myhash(const HashedObj & x) const;//散列函數
        int nextPrime(int n);//求的距離N最近的一個素數
};

/****************************************************************
*   函數名稱：findElement(const HashedObj & x) const
*   功能描述: 查找元素x 
*   參數列表: x是要查找的元素
*   返回結果：如果找到則返回該元素，否則返回一個默認構造的元素值
*****************************************************************/
template
HashedObj HashTable::findElement(const HashedObj & x)
{
    list & whichList = theLists[myhash(x)];
    
    typename list::iterator it = find(whichList.begin(), whichList.end(), x);
    if(it != whichList.end())
        return *it;
    else{
        HashedObj obj;//返回一個成員值為0的對象
        return obj;
    }
}


/****************************************************************
*   函數名稱：print()
*   功能描述: 輸出散列表中的內容
*   參數列表: 無 
*   返回結果：無
*****************************************************************/
template
void HashTable::print()
{
    cout << "輸出散列表中的內容: " << endl;
    for(unsigned i = 0; i < theLists.size(); ++i){
        cout << i << ": " << endl;
        for(typename list::iterator it = theLists[i].begin(); it != theLists[i].end(); ++it){
            cout << *it; 
        }
    }
}

/****************************************************************
*   函數名稱：isEmpty()
*   功能描述: 判斷散列表是否為空
*   參數列表: 無 
*   返回結果：無
*****************************************************************/
template
bool HashTable::isEmpty()
{
    return currentSize == 0;
}

/****************************************************************
*   函數名稱：makeEmpty()
*   功能描述: 清空散列表 
*   參數列表: 無 
*   返回結果：無
*****************************************************************/
template
void HashTable::makeEmpty()
{
    for(int i = 0; i < theLists.size(); ++i)
        theLists[i].clear();

    currentSize = 0;//當前元素個數設為0
}

/****************************************************************
*   函數名稱：containes(const HashedObj & x) const
*   功能描述: 判斷散列表是否包含值為x的元素 
*   參數列表: x數據項
*   返回結果：如果包括x則返回true,否則返回false
*****************************************************************/
template
bool HashTable::containes(const HashedObj & x) const
{
    const list & whichList = theLists[myhash(x)];
    return find(whichList.begin(), whichList.end(), x) != whichList.end();
}


/****************************************************************
*   函數名稱：containes(const HashedObj & x) const
*   功能描述: 判斷散列表是否包含值為x的元素 
*   參數列表: x數據項
*   返回結果：如果包括x則返回true,否則返回false
*****************************************************************/
template
bool HashTable::remove(const HashedObj & x)
{
    list & whichList = theLists[myhash(x)];

    typename list::iterator it = find(whichList.begin(), whichList.end(), x);

    if(it == whichList.end())
        return false;

    whichList.erase(it);//刪除元素x
    --currentSize;
    return true;
}

/****************************************************************
*   函數名稱：insert(const HashedObj & x)
*   功能描述: 在散列表中插入元素x,如果插入項已經存在，則什麼都不做。
*             否則將其放在表的前端
*   參數列表: x數據項
*   返回結果：插入成功返回true, 否則返回false
*****************************************************************/
template
bool HashTable::insert(const HashedObj & x)
{
    list & whichList = theLists[myhash(x)];
    
    if(find(whichList.begin(), whichList.end(), x) != whichList.end())
        return false;

    whichList.push_back(x);

    //rehash
    if(++currentSize > theLists.size())
        rehash();//擴充表的大小

    return true;

}


/****************************************************************
*   函數名稱：~HashTable()
*   功能描述: 析構函數
*   參數列表: 無
*   返回結果：無
*****************************************************************/
template
HashTable::~HashTable()
{
    
}

/****************************************************************
*   函數名稱：nextPrime(int 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 > oldLists = theLists;
    
    //創建一個新的大小為原來兩倍大小的散列表
    theLists.resize(nextPrime(2 * theLists.size()));

    for(int i = 0; i < theLists.size(); ++i)
        theLists[i].clear();

    //復制散列表
    for(int i = 0; i < oldLists.size(); ++i){
        typename  list::iterator it = oldLists[i].begin();
        while(it != oldLists[i].end())
            insert(*it++);
    }
}

/****************************************************************
*   函數名稱：myhash(const HashedObj & key)
*   功能描述: 根據鍵值求個hash值 
*   參數列表: key 數據項的鍵值 
*   返回結果：返回hash值
*****************************************************************/
template
int HashTable::myhash(const HashedObj & key) const
{
    int hashVal = hash(key);
    
    hashVal %= theLists.size();

    if(hashVal < 0)
        hashVal += theLists.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];
    cout << endl;

    HashTable hashTable;
    
    for(unsigned i = 0; i < v.size(); ++i)
        hashTable.insert(v[i]);

    hashTable.print();

    cout << endl;
    //測試查找函數findElement
    cout << "測試查找函數findElement: " << endl;
    Employee e11 = hashTable.findElement(e12);
    cout << "e11 = " << e11;
    Employee e13 = hashTable.findElement(e10);
    cout << "e13 = " << e13;
    cout << endl;

    cout << "測試包含函數containes: " << endl; 
    if(hashTable.containes(e10))
        cout << "containe e10" << endl;
    else 
        cout << "not containe e10" << endl;

    if(hashTable.containes(e11))
        cout << "containe e11" << endl;
    else 
        cout << "not containe e11" << endl;
        
    cout << "測試remove()：" << endl;
    hashTable.remove(e10);
    if(hashTable.containes(e10))
        cout << "containe e10" << endl;
    else 
        cout << "not containe e10" << 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;
    cout << 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

輸出散列表中的內容: 
0: 
name: peter,    salary: 103,    seniority: 3
1: 
2: 
name: kro,      salary: 109,    seniority: 9
3: 
4: 
name: ever,     salary: 102,    seniority: 2
name: sal,      salary: 106,    seniority: 6
5: 
name: jan,      salary: 108,    seniority: 8
6: 
7: 
8: 
9: 
name: linux,    salary: 101,    seniority: 1
name: may,      salary: 104,    seniority: 4
name: usa,      salary: 105,    seniority: 5
name: bei,      salary: 110,    seniority: 10
10: 

測試查找函數findElement: 
e11 = name: ,   salary: 0,      seniority: 0
e13 = name: bei,        salary: 110,    seniority: 10

測試包含函數containes: 
containe e10
not containe e11
測試remove()：
not containe e10

測試isEmpty(): 
hashTable is not Empty 

測試makeEmpty(): 
hashTable is Empty