哈希

Data Structures Experiment #15 - 使用哈希算法完成MyHash类,实现简单的哈希类。

添加private属性之后,完善相应的public函数。
自选哈希函数,自选解决哈希碰撞的方法。

  • MyHash(int max_element);
    构造函数,构造一个元素最多为max_element的哈希表。
  • ~MyHash();
    析构函数。
  • void setvalue(int key, int value);
    将哈希表中键值为key的元素设定值改为value。(哈希表中没有被setvalue的键值默认值为0
  • int getvalue(int key);
    获得哈希表中键值为key的元素的对应value值。

什么是哈希表?

此处选取哈希函数的构造方法为“除留余数法”,解决哈希碰撞的方法为“链地址法”。

众所周知,数组查找容易,但插入和删除困难;链表查找困难,但插入和删除容易。哈希表作为二者的结合,查找容易,插入和删除也容易。

创建哈希表为一个数组。为加快检索,将key值对某一固定值p取余后余数相同的归为一类(即数论中的“同余类/剩余类”),以链表的形式存放到数组中对应第“余数”个元素处,构成“完全剩余系”。

0x00 数据域封装

将数组的每个元素加上一个头指针,用于指向链表头。链表每个结点包括key值和value值。

1
2
3
4
5
6
7
8
9
10
11
private:
struct node {
int value;
int key;
node* next;
};
struct table {
node* head;
};

table* HashTable;

0x01 构造函数

根据最大元素数为1000,可以定义固定的模p为997(小于1000的最大素数)。

若取模为合数,即存在小于自身的因子,则每个含有此因子的key值都会映射到数组的相同元素,从而造成局部链表加长,这显然不利于我们快速查找。

由于取模为997,则所有key值映射后的范围是0~996,所以数组大小取p-1

1
2
3
4
5
6
7
#define p 997

MyHash::MyHash(int max_element){
HashTable = new table[p - 1];
for (int i = 0; i < p - 1; i++)
HashTable[i].head = NULL;
}

0x02 setValue

插入链表,类似栈的LIFO存储方式。

1
2
3
4
5
6
7
void MyHash::setvalue(int key, int value){
node* newNode = new node;
newNode->key = key;
newNode->value = value;
newNode->next = HashTable[key % p].head;
HashTable[key % p].head = newNode;
}

0x03 getValue

先确定余数的值,即其所在链表位于数组中的位置,然后遍历链表查找。

注意“哈希表中没有被setvalue的键值默认值为0”。

1
2
3
4
5
6
7
8
9
int MyHash::getvalue(int key){
node* temp = HashTable[key % p].head;
while (temp) {
if (temp->key == key)
return temp->value;
temp = temp->next;
}
return 0;
}

0x04 析构函数

逐个链表释放内存。

1
2
3
4
5
6
7
8
9
10
11
MyHash::~MyHash(){
for (int i = 0; i < p - 1; i++) {
node* temp = HashTable[i].head;
while (temp) {
node* q = temp;
temp = temp->next;
delete q;
}
}
delete[] HashTable;
}