1. Введение
\
Хеш-таблица — это структура данных, доступ к которой осуществляется напрямую в соответствии со значением ключа.
Доступ к записям путем сопоставления значения ключа с местоположением в таблице для ускорения поиска.
Эта функция отображения называется хеш-функцией, а массив записей называется хеш-таблицей.
\
Чтобы сделать очень неточную аналогию:
NBA2K — это игра, которая пользуется большим спросом у любителей баскетбола. Он имеет боевую ценность каждого игрока НБА, чем выше, тем лучше.
Теперь предположим, что в компьютере размещено 2К значений боя от 1 до 100 (не все из них имеют значение 10, например, может не быть значения 10)
Используя боевое значение в качестве ключевого слова, я хочу найти человека, чье значение 2K равно 1? Следуйте традиционному методу:
Если 2К значений хранятся в компьютере не по порядку, чтобы найти 1, можно только вынуть их по одному и сравнить с 1, и тогда они смогут найти того, кто хранил там 1;
Если значения 2k хранятся в компьютере упорядоченным образом, вы можете найти место, где хранится 1, например, путем деления пополам, поиска и сравнения, а затем найти человека.
\
Есть ли способ узнать, кто тот человек, чье значение 2K равно 1, без больших затрат времени и без необходимости много раз сравнивать и искать?
Ответ — хранилище хеш-таблиц, где ключом является боевое значение, а расположение хранилища известно с учетом боевого значения! !
\
Но хэши иногда конфликтуют, то есть даже если ключевые слова разные, адреса, вычисляемые хеш-функцией, могут совпадать, что на данный момент смущает.
Существует множество способов разрешения конфликтов, таких как метод цепочек адресов (метод застежки-молнии), создание общедоступной области переполнения и т. д. В этой статье в основном используются следующие:
\
Метод открытой адресации: при возникновении коллизии в хеш-таблице формируется последовательность проб (проб) с использованием какой-либо техники проб (также называемой пробой).
Hi=(H(key) + di) MOD m,i=1,2,...,k(k1. di=1,2,3,…,m-1, что называется линейным обнаружением и перехешированием;
2. di=1^2,-1^2,2^2,-2^2, ⑶^2,...,±(k)^2,(k3. di = псевдослучайная числовая последовательность, называемая псевдослучайным обнаружением и повторным хешированием.
Метод повторного хеширования: то есть вычисление другого адреса хеш-функции, когда синоним имеет конфликт адресов, до тех пор, пока конфликт не исчезнет. \
\
\
Две программные реализации
\
Подготовьте тестовые файлы:
Имеется 10 записей, начиная со строки 2, в каждой строке есть два числа, первое число — значение 2K, а второе — связанное лицо.
Например, в строке 2 человека, соответствующего значению 2K 6, называют роскошно богатым.
Все, что нужно сделать сейчас, это знать эту информацию и сохранить ее в компьютере в подходящем месте.
В следующий раз, когда вы спросите, кто тот человек, чье значение 2K равно 6, компьютер сразу же узнает, где взять соответствующую запись.
\
\
\
\
1. Создайте HashTable.h
\
#ifndef HASH.H
#define HASH.H
const int SUCCESS=1;//插入元素成功
const int UNSUCCESS=0;
const int EXIST=-1;//哈希表中有相同关键字元素，不再插入
const int MAX=3;
//hashsize数组存放哈希表需要重建时下一个容量大小
int hashsize[MAX]={11,19,37};
template <typename T>
class HashTable{
private:
T *elem;
int count,length;//数据个数，哈希表容量
int sizeindex;//hashsize[sizeindex]为当前容量
int *random_d;//增量随机数数组指针
int Hash(KeyType key){
return key%length;
}
int Hash2(KeyType key){
return key%(length-1);//双散列函数探测法第二个哈希函数
}
void Random(){//随机探测法中建立伪随机数组
bool *a=new bool[length];
random_d=new int[length];
int i;
for(i=1;i<length;i++)
a[i]=false;
srand(time(0));
for(i=1;i<length;i++){
do{
random_d[i]=rand()%(length-1)+1;//给rando[i]赋值为1到length-1
if(!a[random_d[i]])
a[random_d[i]]=true;
else
random_d[i]=0;
}while(random_d[i]==0);//赋值失败重新赋值
// cout<<"random_d["<<i<<"]="<<random_d[i]<<" ";
}
cout<<endl;
delete []a;
}
int d(int i,KeyType key){//增量序列函数，返回第i次冲突的增量
switch(d_type){
//线性探测法：1，2，3···
case 0:return i;
//二次探测法：1，-1，4，-4，9，-9···
case 1:return ((i+1)/2)*((i+1)/2)*(int)pow(-1,i-1);
//双散列探测法
case 2:return i*Hash2(key);
//随机探测法
case 3:return random_d[i];
//默认线性探测
default: return i;
}
}
void FindAnotherPos(KeyType key,int &p,int i){//开地址法求关键字key的第i次冲突地址p
p=(Hash(key)+d(i,key))%length;
if(p<0)//求余是负，在二次探测可能出现
p=p+length;
}
void RecreateHashTable(){
int i,len=length;//哈希表原容量
T *p=elem;
sizeindex++;//取存储容量为hashsize[]中下一个序列数
if(sizeindex<MAX){
length=hashsize[sizeindex];
elem=new T[length];
assert(elem!=NULL);
for(i=0;i<length;i++)
elem[i].key=EMPTY;//未填有数据
for(i=0;i<len;i++)//将p所指原elem中的数据插入到重建的哈希表中
if(p[i].key!=EMPTY&&p[i].key!=REMOVE)//原哈希表【i】有数据
InsertHash(p[i]);
delete []p;
if(d_type==3)
Random();//重建伪随机增量
}
}
public:
int d_type;//探测法类型
HashTable(){
count=0;
sizeindex=0;
length=hashsize[sizeindex];
elem= new T[length];
assert(elem!=NULL);
for(int i=0;i<length;i++)
elem[i].key=EMPTY;//还没填充元素
cout<<" 依下面提示序号选择冲突时探测法："<<endl;
cout<<"（0：线性；1：二次；2：再散列；3：随机）："<<endl;
cin>>d_type;
switch(d_type){
case 0:cout<<"产生冲突时你选择使用线性探测法解决！"<<endl;break;
case 1:cout<<"产生冲突时你选择使用二次探测法解决！"<<endl;break;
case 2:cout<<"产生冲突时你选择用再散列探测法解决！"<<endl;
if(d_type==3)
Random();
else random_d=NULL;
break;
case 3:cout<<"产生冲突时你选择使用随机探测法解决！"<<endl;break;
default:cout<<endl;
}
}
~HashTable(){
if(elem!=NULL)
delete []elem;
if(d_type==3)
delete []random_d;
}
bool SearchHash(KeyType key,int &p,int &c){
/* 查找关键字为key的元素，若查找成功
p代表待查数据在表中位置，返回success;
否则，p代表插入位置，返回unsuccess;
c冲突次数，初值0，在建表插入时用
*/
int c1,remove=-1;//存放第一个删除地址
p=Hash(key);//求得哈希地址
//该位置被删除或者该位置有数据但不相同
while(elem[p].key==REMOVE||(elem[p].key!=EMPTY)&&(key!=elem[p].key))
{
//该位置数据被删除且是第一个
if(elem[p].key==REMOVE&&remove==-1){
remove=p;//该位置存放在remove中
c1=c;//冲突次数存放在c1中
}
//冲突数加1
c++;
//在哈希表中可能找到插入位置
if(c<=hashsize[sizeindex]/2)
FindAnotherPos(key,p,c);
else
break;
}
if(key==elem[p].key)
return true;
else{
if(remove!=-1){//在查找过程中碰到曾删除位置
p=remove;//设为插入位置
c=c1;//找到此位置时的冲突次数
}
return false;//p指示的是插入位置
}
}
int InsertHash(T e){
int p,c=0;
//先查找，有不插入且p指向查到的位置；没有则P指向该插入的位置
if(SearchHash(e.key,p,c))
return EXIST;
else{
if(c<hashsize[sizeindex]/2){
elem[p]=e;
++count;
return SUCCESS;
}
else{
cout<<"插着插着可能不够，暂停！！"<<endl;
cout<<"哈希地址顺序遍历此时哈希表，准备重建："<<endl;
TraverseHash(Visit);
cout<<"重建哈希表如下："<<endl;
RecreateHashTable();
cout<<endl;
return UNSUCCESS;
}
}
}
bool DeleteHash(KeyType key,T &e){
int p,c;
if(SearchHash(key,p,c)){
e=elem[p];
elem[p].key=REMOVE;//设置删除标志！
--count;
return true;
}
else return false;
}
T GetElem(int i)const{
return elem[i];
}
void TraverseHash(void(*visit)(int ,T *))const{
//按照哈希地址顺序遍历表
int i;
cout<<"哈希地址0~"<<length-1<<endl;
for(i=0;i<length;i++)
if(elem[i].key!=EMPTY&&elem[i].key!=REMOVE)
visit(i,&elem[i]);
cout<<endl;
}
};
#endif
\
\
2. Создайте заголовочный файл func.cpp
\
struct DATA{
KeyType key;//关键字必有
string star;
};
void Visit(int i,DATA *c){
cout<<"["<<i<<"]: "<<'('<<c->key<<", "<<c->star<<"）"<<endl;
}
void Visit(DATA c){
cout<<'('<<c.key<<","<<c.star<<")";
}
void InputFromFile(ifstream &f,DATA &c){
f>>c.key>>c.star;
}
void InputKey(int &k){
cin>>k;
}
\
\
\
\
3. Процедура испытаний
\
#include <iostream>
#include <fstream>
#include <cmath>
#include <string>
#include <ctime>
#include <assert.h>
using namespace std;
const int EMPTY=0;//尚未填充数据标志
const int REMOVE=-1;//数据删除标志
typedef int KeyType;//关键字类型
#include "func.cpp"
#include "HashTable.h"
int main()
{
HashTable<DATA> h;
int i, j, n, p=0;
bool m;
DATA e;
KeyType k;
ifstream fin("test.txt");
fin>>n;
for(i=0; i<n; i++)
{
InputFromFile(fin, e);
j=h.InsertHash(e);
if(j==EXIST)
{
cout<<"有人抢着要（已经有主）的关键字（2K战斗力）："<<e.key<<"，妄图再插入成为: ";
Visit(e);
cout<<endl;
}
if(j==UNSUCCESS)
j=h.InsertHash(e);
}
fin.close();
cout<<endl;
cout<<"按哈希地址的顺序遍历哈希表："<<endl;
h.TraverseHash(Visit);
if(h.d_type==1)
{
cout<<"请输入待删除球星的关键字（2K战斗力）：";
InputKey(k);
m=h.DeleteHash(k, e);
if(m)
{
cout<<"成功删除该元素";
Visit(e);
cout<<endl;
}
}
cout<<"请输入待查找球星的关键字（2K战斗力）：";
InputKey(k);
n=0;
j=h.SearchHash(k, p, n);
if(j==SUCCESS)
{
Visit(h.GetElem(p));
cout<<endl;
}
else
cout<<"未找到"<<endl;
if(h.d_type==1)
{
cout<<"插入球星，请输入待插入球星的关键字（2K战斗力）：";
InputKey(e.key);
cout<<"请输入待插入球星的名字：";
cin>>e.star;
j=h.InsertHash(e);
cout<<j<<endl;
cout<<endl;
cout<<"按哈希地址的顺序遍历哈希表："<<endl;
h.TraverseHash(Visit);
}
return 0;
}
\
\
4. Частичные результаты испытаний
\
\
\
\
\
\
\
\