数据结构与算法——散列表类的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