数据结构与算法——散列表类的C++实现(探测散列表)

程序员文章站 2022-09-24 11:25:04

散列表简介：散列表的实现常被称为散列。散列是一种用于以常数平均时间执行插入、删除和查找的技术。散列的基本思想：理想的散列表数据结构只不过是一个包含一些项的具有固定大小的数组。（表的大小一般为...

散列表简介：

散列表的实现常被称为散列。散列是一种用于以常数平均时间执行插入、删除和查找的技术。

散列的基本思想：

理想的散列表数据结构只不过是一个包含一些项的具有固定大小的数组。（表的大小一般为素数）
设该数组的大小为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。相当于是逐个探测散列表的单元直到查找出空单元。
下图是一个例子：

数据结构与算法——散列表类的C++实现(探测散列表)

在上面的例子中，第一个冲突发生在插入49的时候，h0(49)=9，但是此时第9个位置已经被占用了，所以只能继续探测，直到找到一个空的位置。下一次探测的位置是h1(49)=0，第0个位置是空的，所有将49插入到第0个位置。插入58的时候探测了三次才找到了一个空位置。其它冲突类似。
经过统计，探测散列表如有多于一半的空间被填满的时候，那么线性探测就不是一个好方法了，此时插入和查找需要的探测次数比较多。如果装填因子是0.5，那么插入操作平均只需要2.5次探测，并且对于成功的查找平均只需要1.5次探测。
线性探测可能会出现一次聚集的问题，因为散列表被占用的空间会形成一块连续的区域。这样的话需要探测的次数就会比较多，因为探测需要经过该连续区域。

平方探测：

平方探测是消除线性探测中一次聚集问题的冲突解决方法。平方探测就是冲突函数f为二次函数。一般f(i） = i*i;

下面是一个和上面一样的例子，见下图：

数据结构与算法——散列表类的C++实现(探测散列表)

经过证明：如果表的一半是空的，并且表的大小为素数，那么可以保证总能够插入一个新的元素。
平方探测虽然排除了一次聚集，但是散列到同一位置上的那些元素将探测相同的备选单元，这称为二次聚集。该问题可以通过下面的双散列方法解决。

双散列：

双散列一般冲突解决函数f(i) = i * hash2(x);
这又涉及到第二个散列函数hash2(x)的选择，一般我们选择hash2(x) = r - (x % r)，其中r是小于tablesize的素数。

下面是一个和上面一样的例子，见下图：
我们选择r=7,因为tablesize=10，一般tablesize为素数，这里为了简单，将tablesize设置为10。

数据结构与算法——散列表类的C++实现(探测散列表)

该探测散列表的成员结构为：

 //散列表的数据单元结构
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

上一篇： netCore HTTP 响应状态码

下一篇：为什么每次跟别人吵完架

数据结构与算法——散列表类的C++实现(探测散列表)

散列表简介：

散列的基本思想：

散列函数介绍：

解决冲突的方法主要有：分离链接法和开放定址法

分离链接法：

开放定址法：

探测散列表有三种常见的解决冲突的方法：线性探测、平方探测、双散列。

线性探测：

平方探测：

双散列：

该探测散列表的成员结构为：

散列表类的主要成员函数：

主要成员函数介绍：

1、再散列rehash():

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

3、插入函数insert():

4、删除函数remove():

定义数据类:

下面是main函数，主要是对散列表类进行测试。

下面是该散列表类的源代码：

程序输出结果：

数据结构与算法——散列表类的C++实现(探测散列表)

数据结构与算法——散列表类的C++实现(分离链接散列表)

散列表的原理与Java实现方法详解

数据结构与算法——优先队列类的C++实现(二叉堆)

JavaScript数据结构——字典和散列表的实现

C++ STL中的map用红黑树实现，搜索效率是O(lgN),为什么不像python一样用散列表从而获得常数级搜索效率呢？

数据结构与算法——散列表类的C++实现(探测散列表)

C++ STL中的map用红黑树实现，搜索效率是O(lgN),为什么不像python一样用散列表从而获得常数级搜索效率呢？

数据结构与算法——优先队列类的C++实现(二叉堆)

数据结构与算法——散列表类的C++实现(分离链接散列表)