哈希表的介绍和内存布局

哈希表基本介绍

散列表(Hash table，也叫哈希表)，是根据关键码值(Key value)直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中的一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数据叫做散列表。

hash

哈希表应用图例

image-20221025102934310

哈希表实现思路图解

哈希表(散列)-Google上机题

有一个公司，当有新的员工来报道时，要求将该员工的信息加入(ID，性别，姓名，住址…)，当输入该员工的ID时，要求查找到该员工的所有信息。

要求：不使用数据库，尽量节省内存，速度越快越好=>哈希表(散列)，添加时，保证按照ID从低到高插入。

  1. 使用链表来实现哈希表，该链表不带表头[即：链表的第一个节点就存放雇员信息]；

  2. 思路分析并画出示意图；

    image-20221025110737389

  3. 实现增删查(显示所有员工，按照ID查询)

思考：如果ID不是从低到高插入，但要求各条链表仍然是从低到高，该如何解决？

哈希表代码实现

代码

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
package com.jokerdig.hashTab;

import java.util.Scanner;

/**
 * @author Joker大雄
 * @data 2022/10/26 - 8:25
 **/
public class HashTabDemo {
    public static void main(String[] args) {
        // 创建哈希表
        HashTab hashTab = new HashTab(7);
        // 写一个菜单测试
        String key = "";
        boolean flag = true;
        Scanner scanner = new Scanner(System.in);
        while (flag){
            System.out.println("==========HashTab雇员信息管理=============");
            System.out.println("add:添加雇员");
            System.out.println("list:显示雇员");
            System.out.println("find:查找雇员");
            System.out.println("delete:删除雇员");
            System.out.println("update:修改雇员");
            System.out.println("exit:退出");
            System.out.print("请输入要测试的功能:");
            key = scanner.next();
            switch (key){
                case "add":
                    System.out.println("请输入ID");
                    int id = scanner.nextInt();
                    System.out.println("请输入性别(1或0)");
                    int sex = scanner.nextInt();
                    System.out.println("请输入姓名");
                    String name = scanner.next();
                    System.out.println("请输入地址");
                    String address = scanner.next();
                    // 创建雇员
                    Emp emp = new Emp(id,sex,name,address);
                    hashTab.add(emp);
                    break;
                case "list":
                    hashTab.list();
                    break;
                case "find":
                    System.out.println("请输入要查找的雇员ID");
                    id = scanner.nextInt();
                    hashTab.findEmpById(id);
                    break;
                case "delete":
                    System.out.println("请输入要删除的雇员ID");
                    id = scanner.nextInt();
                    hashTab.delete(id);
                    break;
                case "update":
                    System.out.println("请输入要修改雇员的ID");
                    id = scanner.nextInt();
                    System.out.println("请输入要修改雇员的性别(1或0)");
                    sex = scanner.nextInt();
                    System.out.println("请输入要修改雇员的姓名");
                    name = scanner.next();
                    System.out.println("请输入要修改雇员的地址");
                    address = scanner.next();
                    // 创建雇员
                    emp = new Emp(id,sex,name,address);
                    hashTab.update(emp);
                    break;
                case "exit":
                    flag = false;
                    scanner.close();
                    break;
                default:
                    break;
            }
        }
    }
}
// 创建HashTab，管理多条链表
class HashTab{
    private EmpLinkedList[] empLinkedList;
    private int size;
    // 构造器
    public HashTab(int size){
        this.size = size;
        // 初始化empLinkedList
        empLinkedList = new EmpLinkedList[size];
        // 初始化empLinkedList之后，不要忘了分别初始化每一条链表
        for (int i = 0; i < size; i++) {
            empLinkedList[i] = new EmpLinkedList();
        }
    }
    // 添加雇员
    public void add(Emp emp){
        // 根据员工id,得到该员工应该添加到哪条链表；
        int empLinkedListNo = hashFun(emp.id);
        // 将emp添加到对应的链表中
        empLinkedList[empLinkedListNo].add(emp);
    }
    // 遍历
    public void list(){
        for (int i = 0; i < size; i++) {
            empLinkedList[i].list(i);
        }
    }
    // 查找雇员
    public void findEmpById(int id){
        // 使用散列函数确定到哪条链表查找
        int empLinkedListNo = hashFun(id);
        // 将emp添加到对应的链表中
        Emp emp = empLinkedList[empLinkedListNo].findEmpById(id);
        if(emp==null){
            System.out.println("没有找到该雇员");
        }else{
            System.out.println("在第"+(++empLinkedListNo)+"条链表中找到该雇员信息");
        }
    }
    // 删除雇员
    public void delete(int id){
        // 使用散列函数确定到哪条链表查找
        int empLinkedListNo = hashFun(id);
        // 调用删除
        boolean back = empLinkedList[empLinkedListNo].delete(id);
        if(back){
            System.out.println("雇员信息删除成功");
        }else{
            System.out.println("雇员信息删除失败");
        }
    }
    // 修改雇员信息
    public void update(Emp emp){
        // 使用散列函数确定到哪条链表查找
        int empLinkedListNo = hashFun(emp.id);
        // 调用修改
        boolean back = empLinkedList[empLinkedListNo].update(emp);
        if(back){
            System.out.println("雇员信息修改成功");
        }else{
            System.out.println("雇员信息修改失败");
        }
    }
    // 编写散列函数，使用一个简单取模法
    public int hashFun(int id){
        return id % size;
    }
}
// 表示雇员
class Emp{
    public int id;
    public int sex; // 1代表男，0代表女
    public String name;
    public String address;
    public Emp next; // 默认为null
    // 构造器
    public Emp(int id, int sex, String name, String address) {
        this.id = id;
        this.sex = sex;
        this.name = name;
        this.address = address;
    }
}
// 创建EmpLinkedList，表示链表
class EmpLinkedList{
    // 头指针，执行第一个Emp，这个链表的head是直接指向第一个Emp
    private Emp head; // 默认为null

    // 添加雇员
    // 添加雇员的时候，id自增；
    // 因此我们将该雇员直接加入到本链表最后
    public void add(Emp emp){
        // 如果是添加第一个雇员
        if(head == null){
            head = emp;
            return;
        }
        // 如果不是添加第一个雇员，则使用一个辅助指针，帮助定位
        Emp curEmp = head;
        while(true){
            if(curEmp.next==null){
                // 到链表最后了
                break;
            }
            curEmp = curEmp.next;// 后移
        }
        // 退出时直接将emp加入链表
        curEmp.next = emp;
    }
    // 遍历雇员链表
    public void list(int no){
        if(head==null){
            System.out.println("第 "+(++no)+" 条链表为空");
            return;
        }
        System.out.print("第 "+(++no)+" 条链表信息为：");
        Emp curEmp = head; //辅助指针
        while (true){
            System.out.printf("=> ID=%d sex=%d name=%s address=%s\t",curEmp.id, curEmp.sex,curEmp.name,curEmp.address);
            if(curEmp.next==null){
                // 到最后节点了
                break;
            }
            curEmp = curEmp.next; // 后移
        }
        System.out.println();
    }
    // 根据ID查找雇员
    // 如果找到就返回Emp，没找到就返回null
    public Emp findEmpById(int id){
        // 判断链表是否为空
        if(head == null){
            System.out.println("链表为空");
            return null;
        }
        // 辅助指针
        Emp curEmp = head;
        while(true){
            if(curEmp.id == id){
                // 找到了
                break;
            }
            // 退出
            if(curEmp.next == null){
                // 遍历结束且没找到该雇员
                curEmp = null;
                break;
            }
            curEmp = curEmp.next; // 后移
        }
        return curEmp;
    }
    // 删除雇员
    public boolean delete(int id){
        boolean flag = false;
        // 判断链表是否为空
        if(head == null){
            System.out.println("链表为空");
            return false;
        }
        // 辅助指针
        Emp curEmp = head;
        while(true){
            if(curEmp.id == id){
                //找到了,通过head删除
                head = curEmp;
                head = null;
                flag = true;
                break;
            }
            // 退出
            if(curEmp.next == null){
                // 遍历结束且没找到该雇员
                break;
            }
            curEmp = curEmp.next;// 后移
        }
        return flag;
    }
    // 修改雇员信息
    public boolean update(Emp emp){
        boolean flag = false;
        // 判断链表是否为空
        if(head == null){
            System.out.println("链表为空");
            return false;
        }
        // 辅助指针
        Emp curEmp = head;
        while(true){
            if(curEmp.id == emp.id){
                //找到了,进行修改
                head = curEmp;
                head = emp;
                flag = true;
                break;
            }
            // 退出
            if(curEmp.next == null){
                // 遍历结束且没找到该雇员
                break;
            }
            curEmp = curEmp.next;// 后移
        }
        return flag;
    }
}

运行结果

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
==========HashTab雇员信息管理=============
add:添加雇员
list:显示雇员
find:查找雇员
delete:删除雇员
update:修改雇员
exit:退出
请输入要测试的功能:add
请输入ID
1
请输入性别(1或0)
1
请输入姓名
张三
请输入地址
北京
==========HashTab雇员信息管理=============
add:添加雇员
list:显示雇员
find:查找雇员
delete:删除雇员
update:修改雇员
exit:退出
请输入要测试的功能:add
请输入ID
2
请输入性别(1或0)
0
请输入姓名
李四
请输入地址
上海
==========HashTab雇员信息管理=============
add:添加雇员
list:显示雇员
find:查找雇员
delete:删除雇员
update:修改雇员
exit:退出
请输入要测试的功能:list
第 1 条链表为空
第 2 条链表信息为：=> ID=1 sex=1 name=张三 address=北京	
第 3 条链表信息为：=> ID=2 sex=0 name=李四 address=上海	
第 4 条链表为空
第 5 条链表为空
第 6 条链表为空
第 7 条链表为空
==========HashTab雇员信息管理=============
add:添加雇员
list:显示雇员
find:查找雇员
delete:删除雇员
update:修改雇员
exit:退出
请输入要测试的功能:delete
请输入要删除的雇员ID
1
雇员信息删除成功
==========HashTab雇员信息管理=============
add:添加雇员
list:显示雇员
find:查找雇员
delete:删除雇员
update:修改雇员
exit:退出
请输入要测试的功能:list
第 1 条链表为空
第 2 条链表为空
第 3 条链表信息为：=> ID=2 sex=0 name=李四 address=上海	
第 4 条链表为空
第 5 条链表为空
第 6 条链表为空
第 7 条链表为空
==========HashTab雇员信息管理=============
add:添加雇员
list:显示雇员
find:查找雇员
delete:删除雇员
update:修改雇员
exit:退出
请输入要测试的功能:update
请输入要修改雇员的ID
2
请输入要修改雇员的性别(1或0)
1
请输入要修改雇员的姓名
王五
请输入要修改雇员的地址
陕西
雇员信息修改成功
==========HashTab雇员信息管理=============
add:添加雇员
list:显示雇员
find:查找雇员
delete:删除雇员
update:修改雇员
exit:退出
请输入要测试的功能:list
第 1 条链表为空
第 2 条链表为空
第 3 条链表信息为：=> ID=2 sex=1 name=王五 address=陕西	
第 4 条链表为空
第 5 条链表为空
第 6 条链表为空
第 7 条链表为空
==========HashTab雇员信息管理=============
add:添加雇员
list:显示雇员
find:查找雇员
delete:删除雇员
update:修改雇员
exit:退出
请输入要测试的功能:exit

Process finished with exit code 0