实现一个哈希表

1、哈希表简介

查找序列中某个元素是我们经常会碰见的一种操作，但是在顺序查找表（比如二分查找）和动态查找表（比如二叉搜索树）中，由于记录的存储位置和关键字之间不存在确定的对应关系，在查找时，只能通过一系列的给定值和关键字的比较，该算法均是建立在“比较”的基础上，查找效率依赖于查找过程中给定值和关键字的比较次数。
理想的情况下我们是不经过任何比较，直接得到待查记录的存储位置，查找的期望复杂度是O（1）。这就必须在记录的存储位置和其关键字之间建立一个确定的对应关系，使得每个关键字和唯一的存储位置想对应。我们在查找时只需要根据此对应关系找到给定值映射，如果查找表中存在的该记录，则必定在该映射的位置上，这种查找方法称为哈希方法。

哈希法就是把大数据范围映射到一个小区域内的方法。
离散化是一种非常特殊的哈希法。

关于哈希表的一些基础知识不在赘述，我们直接上代码来实现一个哈希表。

2、代码实现

2.1 实现思考

由于我们不知道要用该哈希表存储什么类型的数据，为了使我们的代码具有通用性，我们采用了c++的模板函数。
对于一个哈希表，我们在算法中一般只进行元素的插入和查找，而不去删除元素。如果删除也只是用个bool变量标记下那个元素的状态。我们使用c++的enum工具来定义一些符号常量标记哈希表中元素的状态。
本文的哈希函数使用除留取余法，冲突函数使用的是线性探测法。

2.2 框架构造

#include<iostream>
using namespace std;

enum FlagType
{	
  	//下面的枚举量都是符号常量
    FLAG_DATA,          //已经有元素
    FLAG_DELETED,       //已经删除
    FLAG_EMPTY,         //没有元素，空
};
template<class KEY>
class HashTable{
private:
    ...

public:
    //构造函数
    HashTable()
    {
        
    }
    //析构函数
    ~HashTable()
    {

    }   
    //哈希函数（除留取余法)
    int Hash(const KEY key)
    {

    }
    //处理冲突函数(线性探测法)
    int LinearProbe()
    {

    }
    //查找元素
    int search_Hash(const KEY key)
    {

    }
    //插入哈希表
    bool Insert_Hash(KEY key)
    {

    }
    //删除元素
    bool Delete_Hash()
    {

    }
    //获取元素的个数
    int GetElementCount()
    {

    }
    //获取哈希表大小
    int GetSize()
    {

    }
    //清空哈希表
    void clear()
    {

    }
    //遍历哈希表
    void Display()
    {

    }
};

void test()
{
  
}

int main()
{
  test();
  return 0;
}

c++的enum工具提供了另一种创建符号常量的方式，这种方式可以代替const。它还允许定义新的类型。结构语法如同上述代码。

2.3 构造函数

分析下该类应该有的成员变量：

存储元素的数组
元素标志指针
哈希表当前元素个数（返回元素个数函数）
哈希表大小（返回哈希表大小函数）
除留取余法需要的那个质数
当前地址，线性再探测用

接下来我们在构造函数中对成员变量初始化：

private:
    KEY* _arr;    //存储元素的数组
    FlagType* _flag;  //元素标志指针
    int _count;      //哈希表当前元素个数
    int _size;      //Hash表大小
    int _prime;     //质数
    int _cur;       //当前地址，线性探测再哈希用

//构造函数
 HashTable(int table_size,int prime) 
    {
        _size = table_size;
        _count = 0;
        _prime = prime;
        _arr = new KEY[_size];
        _flag = new FlagType[_size];

        for (int i = 0; i < _size; i++)
        {
            _flag[i] = FLAG_EMPTY; //标记所有元素为空（相当于初始化）
        }
    }

2.4 析构函数

很简单，只需要释放构造函数中开辟的堆内存即可。

	//析构函数
    ~HashTable()
    {
        delete[] _arr;
        delete[] _flag;
    }

delete [] 释放数组，delete释放指针

2.5 哈希函数（除留取余法）

只需要传过来一个元素，然后我们对其值利用除留取余法进行地址映射即可：

    //哈希函数(除留余数法)
    int Hash(const KEY key)  
    {
         _cur = key % _prime;
         return _cur;
    }

2.6 处理冲突方法（线性探测）

有冲突的时候我们探测下一地址：

    //线性探测再哈希获得下一地址(处理冲突的方法)
    int LinearProbe()         
    {
        _cur = (_cur + 1) % _size;
        return _cur;
    }

2.7 查找元素

传入参数key，在哈希表中查找该元素，如果找到返回其地址，如果未找到返回-1。查找思路：
首先利用哈希函数找到该元素应该映射的位置i。如果位置上为空（没有元素），说明哈希表中没有该元素；如果该位置上有元素，那么利用冲突函数开始找，如果找了一圈（当i等于起始的那个值时）还未找到，说明哈希表中不存在该元素。

    //查找元素
    int Search_Hash(const KEY& key)
    {
        int i = Hash(key);
        int firstIndex = i; //保留起始的映射位置
        while (1) //开始寻找
        {
            if (FLAG_EMPTY == _flag[i]) //位置为空
            {
                return -1;
            }
            if (FLAG_DATA == _flag[i] && key == _arr[i])// 如果找到，并且打印

            {
                cout <<"key = "<<i<< " value = "<< _arr[i] << endl;
                return i;
            }
            i = LinearProbe();
            if (i == firstIndex)
            {
                break;
            }
        }
        return -1;
    }

2.8 插入哈希表

如果插入成功返回true，插入失败返回false。
实现思路：传过来元素key后，先根据哈希函数获得key的初始地址，要保留起始地址，（走一圈还没发现能插入的位置说明表满，插入失败）如果发生了冲突，我们就要利用线性探测函数来找可以插入的位置。如果某位置的标志是空或者删除，就插入该位置。插入后把该位置的标志置为有元素，哈希表的元素个数+1,并返回true。如果转了一圈还没有可以插入的位置就返回false。

    //插入哈希表
    bool Insert_Hash(KEY key)
    {
        int i = Hash(key);//根据key获得初始哈希地址
        int firstIndex = i;

        while (1)
        {
            if (FLAG_EMPTY == _flag[i] || FLAG_DELETED == _flag[i])
            {
                _flag[i] = FLAG_DATA;
                _arr[i] = key;
                _count++;
                return true;
            }
            i = LinearProbe();
            if (i == firstIndex)
            {
                break;
            }
        }
        return false;
    }

2.9 删除元素

删除成功返回true，删除失败返回false。实现思路：传过来参数key后我们先要找到它的位置（调用查找函数），找到后把该位置标志置为空，哈希表元素个数--即可。

    //删除元素
    bool Delete_Hash(const KEY& key)
    {
        int i = Search_Hash(key);
        if (i != -1) //查找成功
        {
            _flag[i] = FLAG_EMPTY;
            _count--;
            return true;
        }
        return false;
    }

其实删除元素的过程就是查找元素，所以一般我们用哈希表不会涉及到删除操作。

2.10 获取元素个数

返回成员变量_count即可。

     //获取元素的个数
    int GetElementCount()
    {
        return _count;
    }

2.11 获取哈希表大小

返回成员变量_size即可：

    //获取哈希表大小
    int GetSize()
    {
        return _size;
    }

2.12 清空哈希表元素

就是将每个位置的标志置空。

	//清空哈希表
    void Clear()
    {
        for (int i = 0; i < _size; i++)
        {
            _flag[i] = FLAG_EMPTY;
        }
        _count = 0;
    }

2.13 遍历哈希表

就是对数组的一次遍历。根据每个位置上不同的标志打印响应的话就可。

    //打印哈希表
    void Display()
    {
        int i = 0;
        int data = 0;
        FlagType flag;

        cout << "HashTable_Length: " << GetSize() <<endl<< "HashTable_Content: " << endl;

        if (0 == GetElementCount())
        {
            cout << "Empty!" << endl << endl;
            return;
        }

        for (int i = 0; i < GetSize(); i++)
        {
            flag = _flag[i];
            if (flag == FLAG_DATA)
            {
                data = _arr[i];
                cout << "arr[" << i << "]=" << data <<" ";
            }
            else
            {
                if (flag == FLAG_DELETED)
                {
                    cout << "arr[" << i << "]=delete  ";
                }
                else
                {
                    cout << "arr[" << i << "]=NULL  ";
                }
            }
            if (4 == (i % 5))
            {
                cout << endl;
            }
        }
        cout << endl;
        return;
    }

2.14 测试

void Test()
{
    HashTable<int> hs(30,11); //哈希表大小30，质数选取11

    hs.Insert_Hash(23);
    hs.Insert_Hash(36);
    hs.Insert_Hash(34);
    hs.Insert_Hash(45);
    hs.Insert_Hash(63);
    hs.Insert_Hash(1);
    hs.Insert_Hash(67);
    hs.Insert_Hash(28);
    hs.Insert_Hash(29);
    hs.Insert_Hash(0);
    hs.Insert_Hash(5);
    hs.Insert_Hash(65);
    hs.Insert_Hash(31);
    hs.Insert_Hash(52);
    hs.Insert_Hash(75);
    hs.Insert_Hash(87);


    hs.Display();
    hs.Search_Hash(34);
    hs.Search_Hash(87);


    hs.Delete_Hash(75);
    hs.Display();

}