散列表（Hash表）

1、散列查找的基本思想

散列技术是在记录的存储位置和它的关键字之间的一个确定的对应关系f，使得每一个关键字key对应的一个存储位置f(key)。这里我们把这种对应关系f称为散列表函数，又称为哈希函数。采用存储在一块连续的空间中，这块连续存储空间称为散列表或哈希表（Hash table）。

2、散列表的查找步骤

  • 当查找存储记录时，通过散列表函数计算出记录的散列地址

  • 当查找记录时，我们通过同样的是散列函数计算记录的散列地址，并按照此散列地址访问该记录。

3、散列表函数的设计

3.1、直接定址法

直接定值法是关键码的线性函数：

1
H(key)=a*key+b(a、b为常数)

直接定值法的特点是不会产生冲突，但实际使用这种散列函数的情况很少

3.2、保留余数法

保留余数法的思想是选择某个正整数p以关键码除以p的余数作为散列表地址即:

1
H(key)=key mod p

这个办法的关键在于选取合适的p，否则容易产生同义词。一般情况下，若散列表表长为m通常以选取p为小于或等于m的最大素数或不包括小于20质因子的合数。

3.3、平方取中法

平方取中法是对关键码平方后，按散列表大小，取中间的若干位作为散列表的地址，其原理是一个是平方后，中间的若干位作为散列表，其原理是一个数平方后，中间的几位分布较均匀，从而冲突发生的概率较为小，例如对于关键码1234，假设散列表地址是2，由于1234的平方等于1522756，选取的中间的2位作为散列地址，可以选22页可以选27.

4、处理冲突的方法

4.1、开放定值法

线性探测法处理冲突：

image-20210922222740123

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<iostream>
using namespace std;
#define NIL 0        /* 用NIL作为空闲单元的标志 */
#define DelNIL -1        /* 用DelNIL作为已删除单元的标志 */
#define m 13
#define n 20
typedef struct {
    int key;
} LHashTable;
/* 初始化哈希表 */
void HashListInit(LHashTable HT[n]) {
    int i;
    for (i = 0; i < n; i++)
        HT[i].key = NIL;
}
/* 清空哈希表 */
void HashListClear(LHashTable HT[]) {
    int i;
    for (i = 0; i < n; i++)
        HT[i].key = NIL;
}
/* 定义哈希函数 */
int Hash(int k) {
    return (k % m);
}
/* 在哈希表中查找元素 */
int HashListSearch(LHashTable HT[n], int k) {
    int d, temp;
    d = Hash(k);                       /* 计算k的哈希地址 */
    temp = d;                      /* temp暂存k的哈希地址 */
    while (HT[d].key != NIL) {
         if (HT[d].key == k) {
            return d;
        }//TODO  在哈希表中查找到元素k 
        

        else
        {
            d = (d + 1) % m;
        }
         /* TODO 没找到进行线性探测法继续查找 */


        /* 哈希中没有待查元素k */
        if (d == temp)
            return -1;     
    }
    return -1;
}
/* 在哈希表中插入一个元素 */
void HashListInsert(LHashTable HT[n], int k) {
    int d, temp;
    d = Hash(k);                        /* 计算k的哈希地址 */
    temp = d;                           /* temp暂存k的哈希地址 */
    while (HT[d].key != NIL && HT[d].key != DelNIL)   /* 当前位置已有元素 */
    {   
        d++;
        /* TODO 进行线性探测 */
        if (d == temp) {
           cout << "哈希表无空间" << endl;  /* 哈希表已满 */
            return;//exit(1);
        }
    }
       HT[d].key = k;/* TODO 插入k */
}
/* 从哈希表中删除元素 */
void HashListDelete(LHashTable HT[n], int k) {
    int d, temp;
    d = Hash(k);
    temp = d;
    while (HT[d].key != NIL) {
        /* TODO 找到k，写上删除标志 */
        if (HT[d].key == k) {
             HT[d].key = DelNIL;
            return;
        }
        else
        {
             d = (d + 1) % m;
        }
           /* 当前位置没找到k，进行线性探测 */
        if (d == temp)
            break;
    }
    cout << "哈希表中无待删除元素" << k << endl;
    //exit(1);
}
/* 输出哈希表中所有元素 */
void PrintHashList(LHashTable HT[n]) {
    int i;
    for (i = 0; i < n; i++)
        cout << i << " ";
    cout << endl;
    for (i = 0; i < n; i++)
        cout << HT[i].key << " ";
}
int main() {
    int k;
    LHashTable HT[n];
    HashListInit(HT);
    cout << "请输入要插入到哈希表中的关键字,以0结束:";
    cin >> k;
    while (k != 0) {
        HashListInsert(HT, k);
        cin >> k;
    }
    cout << "所建立的哈希表长为20,哈希函数为H(key)=key%13" << endl;
    PrintHashList(HT);
    cout << "\n请输入要查找的关键字:";
    cin >> k;
    k = HashListSearch(HT, k);
    if (k == -1)
        cout << "哈希表中无此元素" << endl;
    else
        cout << "查找的关键字位置为:" << k << endl;
    cout << "请输入要删除的关键字:";
    cin >> k;
    HashListDelete(HT, k);
    cout << "删除成功后的哈希表为";
    PrintHashList(HT);
}

二次探测法构造的闭散列表进行查找：

image-20210922223749757

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
using namespace std;
typedef int DataType;
struct Node {
    DataType data;
    Node* next;
};
const int MaxSize = 11;
class HashTable2 {
public:
    HashTable2(); //构造函数，初始化开散列表
    ~HashTable2(); //析构函数，释放同义词子表结点
    int Insert(int k); //插入
    bool Delete(int k); //删除
    Node* Search(int k); //查找
    void Print();
private:
    int hashCode(int k); //散列函数
    Node* hashTable[MaxSize]; //开散列表
};
HashTable2::HashTable2() {
    for (int i = 0; i < MaxSize; i++) {
        hashTable[i] = NULL;
    }
}
HashTable2::~HashTable2() {
    Node* p = NULL, * q = NULL;
    for (int i = 0; i < MaxSize; i++) {
        p = q = hashTable[i];
        while (p != NULL) {
            p = p->next;
            delete q;
            q = p;
        }
    }
}
int HashTable2::hashCode(int k) {
    return k % 11;
}
void HashTable2::Print() {
    Node* p = NULL;
    for (int i = 0; i < MaxSize; i++) {
        p = hashTable[i];
        cout << i << " ";
        while (p != NULL) {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
    }

}
Node* HashTable2::Search(int k) {
    int j = hashCode(k); //计算散列地址
    Node* p = hashTable[j]; //工作指针p初始化
    while (p != NULL) {
        //TODO 查找元素 找到则返回指针p
        if (p->data == k) {
            return p;
        }
        p = p->next;
    }
    return NULL; //查找失败
}
int HashTable2::Insert(int k) {
    int j = hashCode(k); //计算散列地址
    Node* p = Search(k);
    if (p != NULL) {
        return -1; //已存在元素k，无法插入
    }
    else {
        //TODO 头插法 插入元素
        p = new Node;
        p->data = k;
        p->next = hashTable[j];
        hashTable[j] = p;
        return 1; //插入成功标志
    }
}
bool HashTable2::Delete(int k) {
    int j = hashCode(k);
    Node* p = hashTable[j];
    Node* last = p;
    // 头节点即为目标元素
    if (p->data == k) {
        hashTable[j] = p->next;
        return true;
    }
    else {
        p = p->next;
    }
    // TDOO 其他情况删除元素成功则返回true
    return false;
}
int main() {
    HashTable2 HT;
    int k = 0;
    cin >> k;
    while (k) {
        HT.Insert(k);
        cin >> k;
    }
    HT.Print();
    cin >> k;
    bool sign = HT.Delete(k);
    if (sign)
        HT.Print();
    else
        cout << "未找到此元素" << endl;
    return 0;
}