学习来源：计蒜客
1.定义哈希表，也叫散列表。根据关键码值(Key value)而直接进行访问的数据结构。
比如你要查a，通过哈希函数f(a) = k就可以得到哈希表b的索引，b[k]即可获取a 对应的value
这个可以用来快速查重吧，就是你给我一个a，a在不在哈希表里呢？大家平时注册的时候，用户大的时候就可以用这个来快速查重了
百度百科：
什么是冲突呢，就是多对一，比如：f(a) = k,同时f(c) = k,f(d) = k
2.解决冲突的方法(下面是复制的，仅作为笔记之用)
开放地址法。如果发生冲突，那么就使用某种策略寻找下一存储地址，直到找到一个不冲突的地址或者找到关键字，否则一直按这种策略继续寻找。如果冲突次数达到了上限则终止程序，表示关键字不存在哈希表里。一般常见的策略有这么几种：
1. 线性探测法，如果当前的冲突位置为 d，那么接下来几个探测地址为 d + 1，d + 2，d + 3 等，也就是从冲突地址往后面一个一个探测；
2. 线性补偿探测法，它形成的探测地址为 d + m，d + 2 * m，d + 3 * m 等，与线性探测法不同，这里的查找单位不是 1，而是 m，为了能遍历到哈希表里所有位置，我们设置m 和表长 size 互质；
3. 随机探测法，这种方法和前两种方法类似，这里的查找单位不是一个固定值，而是一个随机序列。
4. 二次探测法，它形成的探测地址为 d + 1^2，d + (-1)^2，d + 2^2，d + (-2)^2 等，这种方法在冲突位置左右跳跃着寻找探测地址。
开放地址法计算简单快捷，处理起来方便，但是也存在不少缺点。线性探测法容易形成“堆聚”的情况，即很多记录就连在一块，而且一旦形成“堆聚”，记录会越聚越多。另外，开放地址法都有一个缺点，删除操作显得十分复杂，我们不能直接删除关键字所在的记录，否则在查找删除位置后面的元素时，可能会出现找不到的情况，因为删除位置上已经成了空地址，查找到这里时会终止查找。
链地址法。该方法将所有哈希地址相同的结点构成一个单链表，单链表的头结点存在哈希数组里。链地址法常出现在经常插入和删除的情况下。
相比开放地址法，链地址法有以下优点：不会出现“堆聚”现象，哈希地址不同的关键字不会发生冲突；不需要重建哈希表，在开放地址法中，如果哈希表里存满关键字了就需要扩充哈希表然后重建哈希表，而在链地址法里，因为结点都是动态申请的，所以不会出现哈希表里存满关键字的情况；相比开放地址法，关键字删除更方便，只需要找到指定结点，删除该结点即可。
3.实现
#include <iostream>
#include <string>
using namespace std;
//下面说得哈希表就是elem这个储存字符串的指针变量
class HashTable{
private:
//储存字符串的指针
string *elem;
//哈希表容量
int size;
public:
HashTable(int input_size){
size = input_size;
elem = new string[size];
//初始化每个字符串
for (int i = 0; i < size; i++) {
elem[i] = "#";
}
}
~HashTable(){
delete[] elem;
}
//哈希函数，就是我在定义里随便说得f()函数
//简单来说就是计算出你这个字符串要放在我哈希表（数组）的哪个位置
int hash(string& index){
int code = 0;
//这里的变量 i 不能用 int 类型，而应该用 size_t 类型，因为字符串是 string 类型，如果用 int 类型会有警告。
for (size_t i = 0; i < index.length(); i++) {
//有符号的字符范围这（ASCII）是从 -128 到 127，也就是一共有 256 种
//index[i] + 128是将他们都转换成正数
//code * 256估计是为了让差不多的字符相差更远，
//比如字符串转化成ASCII是-128，-127，算出的code=1，即位置为1
//比如字符串转化成ASCII是-127，-126，算出的code=258，即位置为258
//为了防止数据过大导致的数据溢出，相加的结果再对哈希表的长度 size 取余
code = (code * 256 + index[i] + 128) % size;
}
return code;
}
//哈希表的查找函数
//index:我们要查找的字符串
//pos：我们的哈希表中可以插入index这个字符串的位置
//times：冲突的次数
bool search(string &index, int &pos, int ×){
pos = hash(index);
times = 0;
//因为我们初始化elem每个元素为"#"
//elem[pos] != "#" 这说明当前hash表pos位置上有元素
//elem[pos] != index 并且该位置上的值不等于index字符串，说明冲突产生了，（两个以上字符串对应哈希表的同一个位置pos）
while (elem[pos] != "#" && elem[pos] != index) {
//找到冲突，冲突次数+1
times++;
//发生冲突后，我们需要找下一个存储地址，
//首先我们要满足冲突次数 times 要小于哈希表的长度 size，否则我们认为哈希表已经填满关键字了，没有空余的地址可以存储。
if (times < size) {
//利用开放地址法的线性探测解决冲突
pos = (pos + 1) % size;
}else{
//哈希表已经填满关键字,找不到index这个字符串插入哈希表的位置
return false;
}
}
//该位置上的值等于index字符串，说明找到了
if (elem[pos] == index) {
return true;
}else{
//否则找不到
return false;
}
}
//插入字符串到哈希表中
int insert(string &index){
int pos, times;
//插入前看看是否已经在哈希表中
if (search(index, pos, times)) {
return 2;
}else if (times < size/2) {
//若冲突次数少于哈希表长度的一半
//上面的search函数已经找到可以插入的位置pos了，直接赋值就可以了
elem[pos] = index;
return 1;
}else{
//冲突过多，为了提高查找效率，重建哈希表
//因为冲突过多，search的while循环的次数会很多咯
recreate();
return 0;
}
}
//重建哈希表
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 (i = 0; i < size; i++) {
elem[i] = "#";
}
for ( i = 0; i < copy_size; i++) {
if (temp_elem[i] != "#") {
insert(temp_elem[i]);
}
}
delete[] temp_elem;
}
};
int main() {
HashTable hashtable(2000);
string buffer;
//这个是要输入多少个字符串
int n;
cin>>n;
for (int i = 1; i <= n; i++) {
cin>>buffer;
int ans = hashtable.insert(buffer);
if (ans == 0) {
cout<<"insert failed!"<<endl;
}else if (ans == 1) {
cout<<"insert success!"<<endl;
}else if (ans == 2) {
cout<<"It already exists!"<<endl;
}
}
//查找字符串
cout<<"请输入你要查找的字符串";
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;
}
4.运行结果
4.简单应用，筛选重名用户
int main() {
HashTable hashtable(200000);
string buffer;
//这个是要输入多少个字符串
int n;
cin>>n;
for (int i = 1; i <= n; i++) {
cin>>buffer;
//转换为小写
for (int j = 0; j < buffer.length(); j++) {
if (buffer[j] >= 65 && buffer[j] <=90) {
buffer[j] = char(buffer[j]+32);
}
}
int ans = hashtable.insert(buffer);
if (ans == 0) {
cout<<"insert failed!"<<endl;
}else if (ans == 1) {
cout<<"此用户名没在我们的数据中"<<endl;
}else if (ans == 2) {
cout<<"此用户已存在，请发邮件叫他更改用户名"<<endl;
}
}
return 0;
}