哈希详解与实现1（哈希是什么以及解决哈希冲突）

一、哈希是什么

哈希 == 散列

哈希技术：让数据的存储位置和数据值本身产生某种联系，这种联系用哈希函数来表示，使得每一个关键字都会有一个存储位置

如果数据的关键字和数据的存储位置之间存在一个映射关系，这时如果数据无序且需要查找，则不用一个一个遍历，可以直接使用哈希计算

映射关系 == 哈希函数：f(关键字)=存储地址

如果我们使用哈希存储数据，则会有一个效果：假设我们需要查找一个值X是否存储（数据无序），只需要将X代入到哈希函数f(x)中计算即可，会得到一个地址Y，这时只需要直接去看一下地址Y里面的值是否是X即可，时间复杂度是O(1)
1
2
3
4
5
6
7
8
9

二、哈希冲突

哈希函数是一个压缩映像函数。关键码集合比哈希表地址集合大得多。因此有可能经过哈希函数的计算，把不同的关键码映射到同一个哈希地址上，这就产生了冲突。
f(x1)=y，f(x2)=y
1
2

三、哈希的构造方法：

1. 直接定址法：f(key) = x * key + b;
2. 数字分析法：分析数字，取得关键字
3. 平方取中法：适合于不知道关键字的分布，位数不是很大
4. 折叠法：将大的数据分割为几分，然后再处理，适合于不知道关键字的分布，位数很大
5. 除留余数法：f(key) = key mod p( p<= m);m是存储空间的大小
6. 随机数法：f(key) = randon(key)；

四、哈希冲突的方法：

4.1.开发定址：发生冲突，找下一个空的地址，可能占据其他数据的地址

1.1，线性探测法：fi(key) = (f(key) + di) MOD m ( di = 1,2,3,...,m-1)//从冲突的地方向右探测
1.2，二次探测法：fi(key) = (f(key) + di) MOD m ( di = 1^2,,-1^2,2^2,-2^2,,...,q^2,-q^2)，q<= m/2
//从冲突的地方向左、右两方探测，而且探测的距离越大
1.3，随机探测法:di采用随机函数得到
1
2
3
4

4.2.再散列函数：实现准备多个散列函数，一旦发生冲突，换下一个散列函数

fi(key) = RHi(key) (RHi表示多个散列函数)
1

4.3.链地址法：一旦发生冲突，就将数据链在后面（原地解决，续节点）

4.4.公共区域溢出法：把冲突的数据存储到溢出表里面，溢出表按顺序存放，所以查找也得按顺序查找

基础表哈希，溢出表顺序，并且如果在基础表里面找不到（没有冲突），就不需要在溢出表里面找
1

五.实现（哈希冲突链地址法）

5.1思路

5.2代码

.h文件

#pragma once

#define MAX_SIZE 12

typedef int ELEMTYPE;

typedef struct Node
{
	ELEMTYPE data;
	struct Node* next;
}Node;

typedef struct List_hash
{
	struct Node arr[MAX_SIZE];//存放单链表的头节点
}List_hash,*List_Phash;

//初始化
void Init_List_hash(List_hash* lh);
//插入(头插)
bool Inseert_List_hash(List_hash* lh, ELEMTYPE val);
//删除
bool Del_List_hash(List_hash* lh, ELEMTYPE val);
//查找
Node* Find_List_hash(List_hash* lh, ELEMTYPE val);
//打印
void Show(List_hash* lh);

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

.cpp文件

#include "list_hash.h"
#include 
#include 

using namespace std;
//初始化（有头节点）
void Init_List_hash(List_hash* lh)
{
    for (int i = 0; i < MAX_SIZE; i++)
    {
        lh->arr[i].next = nullptr;
    }
}
//插入(头插)
bool Inseert_List_hash(List_hash* lh, ELEMTYPE val)
{
    assert(lh != nullptr);
    //1.首先利用hash函数计算在哪一个头节点插入
    int index = val % MAX_SIZE;
    //2.插入
    Node* newnode = (Node*)malloc(sizeof(Node));
    assert(newnode != nullptr);

    newnode->data = val;
    newnode->next = lh->arr[index].next;
    lh->arr[index].next = newnode;

    return true;
}
//删除
bool Del_List_hash(List_hash* lh, ELEMTYPE val)
{
    assert(lh != nullptr);
    //1.首先利用hash函数计算在哪一个头节点删除
    int index = val % MAX_SIZE;
    
    //2.判断这个头节点后面有没有有效节点（判断是否为空链表），不空查找，为空退出
    if (lh->arr[index].next == nullptr)
    {
        //为空
        return false;
    }
    Node* p = &(lh->arr[index]);
   
    //找到所要删除的节点(p)
    p = Find_List_hash(lh, val);
    if (p == nullptr)
    {
        return false;
    }
    Node* q = &lh->arr[index];
    //找到所要删除的节点的前一个节点(q)
    for (; q->next != p; q = q->next);
    
    //删除节点
    q->next = p->next;
    free(p); 
    return true;
}
//查找
Node* Find_List_hash(List_hash* lh, ELEMTYPE val)
{
    assert(lh != nullptr);
    //1.首先利用hash函数计算在哪一个头节点删除
    int index = val % MAX_SIZE;

    Node* p = lh->arr[index].next;
    for (; p != nullptr; p = p->next)
    {
        if (p->data == val)
        {
            return p;
        }
    }
    return nullptr;
}
//打印
void Show(List_hash* lh)
{
    for (int i = 0; i < MAX_SIZE; i++)
    {
        cout << "[" << i << "]";
        for (Node* p = lh->arr[i].next;p!=nullptr;p=p->next)
        {
            cout << p->data << "->";
        }
        cout <<"NULL" <<endl;
    }
}

int main()
{
    List_hash head;


    Init_List_hash(&head);
    Inseert_List_hash(&head, 48);
    Inseert_List_hash(&head, 37);
    Inseert_List_hash(&head, 15);
    Inseert_List_hash(&head, 16);
    Inseert_List_hash(&head, 29);
    Inseert_List_hash(&head, 67);
    Inseert_List_hash(&head, 56);
    Inseert_List_hash(&head, 34);
    Inseert_List_hash(&head, 47);
    Inseert_List_hash(&head, 12);
    Inseert_List_hash(&head, 25);
    Inseert_List_hash(&head, 22);
    Show(&head);


    Del_List_hash(&head, 25);
    Del_List_hash(&head, 34);
    Del_List_hash(&head, 12);

    Show(&head);
}
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