哈希表(模板,参考用)

￡神魔★判官ぃ 2022-05-09 21:12 187阅读 0赞

哈希表又叫做散列表,关键值通过哈希函数映射到数组上,查找时通过关键值直接访问数组

**哈希函数指的是关键值和存储位置建立的对应关系,查找时只要根据这个关系就可以找到目标位置**

哈希表里,可能存在关键字不同但是哈希地址相同的情况,会产生冲突,一般情况下,冲突是不可避免的,因为关键字集合往往比哈希地址集合大很多

**哈希表的构造方法:**

(1)直接寻址法:即取关键字的指或者关键字的某个函数变换值,线性映射到存储地址上

(2)取余数法:我们将关键字对整数p取的余数值直接作为存储地址,整数p一般取小于等于哈希表长度size的最大质数,如果关键字不是整数,比如是一个字符串,我们先将其做个转换,可以先将其做个转换,然后再对p取余

下面例举一个hash变换函数:

int hash(string& value) {   //哈希函数
    		int code = 0;
    		for (size_t i = 0; i < value.length(); ++i) {
    			code = (code * 256 + value[i] + 128) % size;   //产生哈希编码
    		}
    		return code;   
    }

我们知道有字符范围是从-128到127,也就是一共有256种。为了减少冲突,

我们可以使用上述构造方法,为了防止出现负数,我们对value\[i\]加上128,为了防止数据溢出,我们再对其进行取余操作

**冲突的解决**

开放地址法:如果发生冲突,那么就使用某种策略寻找下一存储地址,直到找到一个不冲突的地址或者找到关键字,否则一直按照这种策略继续寻找。如果冲突次数达到了上限则终止程序,表示关键字不在哈希表里

1.线性探测法,如果当前的冲突地址为d,那么接下来几个探测地址为d+1,d+2,d+3等,

2.线性补偿探测法: d+m, d+2\*m, d+3\*m(m和表长size互质;

3.随机探测法

4.二次探测法:形成的探测地址为 d + 1平方 d - 1平方 d + 2平方 d - 2平方算法

**算法的具体实现策略:**

(1)用哈希函数找到字符串S的初始位置,初始化冲突次数

(2)从当前位置从后面进行查找,找到第一个未发生冲突的位置K(当前位置上如果存储的字符串不是S则视为发生冲突) 查找过程中记录发生冲突的次数T,如果T大于等于表长,则结束算法,表示查找失败

(3)如果K上的元素就是查找的字符串,则查找成功,否则查找失败

bool search(string& value, int& pos, int& times) {
    		times = 0;   //查找次数归零
    		pos = hash(value);  //构建哈希值
    		while (elem[pos] != "#" && elem[pos] != value) {  //如果没找到,则继续进行查找
    			times++;
    			if (times < size) {
    				pos = (pos + 1) % size;   //向下一个方向查找
    			}
    			else {
    				return false;   //需要扩容
    			}
    		}
    
    		if (elem[pos] == value) {
    			return true;
    		}
    		else {
    			return false;
    		}
    	}

**哈希表的扩容操作:**

程序执行时,如果当前元素已经存在于哈希表中了,就直接返回一个值结束这次插入操作。

当冲突次数小于表长的一半时,我们就可以把字符串插入到哈希表中,如果大于一半,则需要进行重建哈希表(扩容,防止发生堆聚现象)

哈希表重建操作的算法:

1.  开辟一段和当前哈希表等大的临时空间
2.  将原哈希表中的关键字一一复制到临时数组中
3.  申请一个原空间大小两倍的新空间,释放原空间
4.  将新空间里的存储地址初始化
5.  将关键字从临时数组复制到新的空间,释放临时空间

void recreate() {  //扩容操作
    		string* temp_elem = new string[size];
    		for (int i = 0; i < size; ++i) {
    			temp_elem[i] = elem[i];
    		}
    		
    		int copy_size = size;  //保留原有的大小
    		size = size * 2;       //扩大两倍
    		
    		delete[] elem;
    		elem = new string[size]; //扩容
    		for (int i = 0; i < size; ++i) {  //初始化
    			elem[i] = "#";
    		}
    		//插入到表中
    		for (int i = 0; i < copy_size; ++i) {
    			if (temp_elem[i] != "#") {
    				insert(temp_elem[i]);
    			}
    		}
    		delete[] temp_elem;
    	}
    };

整体代码如下:

#include <iostream>
    #include <string>
    using std::cin;
    using std::cout;
    using std::endl;
    using std::string;
    class HashTable {
    private:
        string *elem;
        int size;
    public:
        HashTable() {
            size = 2000;
            elem = new string[size];
            for (int i = 0; i < size; i++) {
                elem[i] = "#";
            }
        }
        ~HashTable() {
            delete[] elem;
        }
        int hash(string &value) {
            int code = 0;
            for (size_t i = 0; i < value.length(); i++) {
                code = (code * 256 + value[i] + 128) % size;
            }
            return code;
        }
        bool search(string &value, int &pos, int &times) {
            pos = hash(value);
            times = 0;
            while (elem[pos] != "#" && elem[pos] != value) {
                times++;
                if (times < size) {
                    pos = (pos + 1) % size;
                } else {
                    return false;
                }
            }
            if (elem[pos] == value) {
                return true;
            } else {
                return false;
            }
        }
        int insert(string &value) {
            int pos, times;
            if (search(value, pos, times)) {
                return 2;
            } else if (times < size / 2) {
                elem[pos] = value;
                return 1;
            } else {
                recreate();
                insert(value);
                return 0;
            }
        }
        // 请在下面实现重建方法 recreate
        void recreate(){
            string* temp_elem;
            temp_elem = new string[size];
            for(int i = 0; i < size; ++i){
                temp_elem[i] = elem[i];
            }
                int copy_size = size;
                size = size*2;
                delete[] elem;
                elem = new string[size];
            for(int i = 0; i < size; ++i){
                elem[i] = "#";
            }
            for(int i = 0; i < copy_size;i++){
                 if(temp_elem[i] != "#"){
                     insert(temp_elem[i]);
                 }
             }
            delete[] temp_elem;
        }
        
    };
    
    int main() {
        HashTable hashtable;
        string buffer;
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> buffer;
            int ans = hashtable.insert(buffer);
            if (ans == 0) {
                cout << "recreate while insert!" << endl;
            } else if (ans == 1) {
                cout << "insert success!" << endl;
            } else if (ans == 2) {
                cout << "It already exists!" << endl;
            }
        }
        int temp_pos, temp_times;
        cin >> buffer;
        if (hashtable.search(buffer, temp_pos, temp_times)) {
            cout << "search success!" << endl;
        } else {
            cout << "search failed!" << endl;
        }
        return 0;
    }