数据结构5:哈希表

哈希表(散列表)

Hash table 也叫哈希表

需求:不使用数据库,尽量节省内存,速度越快越好

简介

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

在java程序和数据库之间需要一层缓存层,可以使用哈希表来作为这个缓存层,提高效率.,也可以使用数组+链表或者数组+二叉树.

如果一级缓存层不够,可以使用多层缓存

实现思路

使用链表实现哈希表,哈希表中的每一个表项都是一个链表

相当于一个链表数组

通过对对象的哈希值取模来得到对象应该存在数组的哪一项

同一个数组项内的元素会串联为一条链表

哈希表实现雇员管理系统

实现思路

主要分为以下四个类

1,测试类(Test)

装有测试的一些输入和输出模块,所有功能和展示在测试类的主菜单中实现

2,数组类(HashTable)

装有一个数组,用来管理多条链表

3,链表类(EmpLinkedList)

装有一个链表,用来管理多个雇员对象

4,雇员类(Emp)

数据的基本存储单元,每个雇员对象装有一个雇员信息

逻辑传递和代码实现

主要功能分为增删查三个模块,因为只是为了熟悉哈希表底层结构所以功能只做了最基本的,其中哈希值用id替代

代码如下:

主菜单:

public static void main(String[] args) {
        HashTable ht = new HashTable(7);
        String key = "";
        Scanner sc = new Scanner(System.in);
        while (true) {
            System.out.println("add: 添加雇员");
            System.out.println("list: 显示雇员");
            System.out.println("search 查找雇员");
            System.out.println("del 删除雇员");
            System.out.println("exit: 退出系统");
            key = sc.next();
            switch (key) {
                case "add":
                    System.out.println("输入id");
                    int id = sc.nextInt();
                    System.out.println("输入name");
                    String name = sc.next();
                    Emp emp = new Emp(id, name);
                    ht.add(emp);
                    break;
                case "list":
                    ht.check();
                    break;
                case "exit":
                    return;
                case "search":
                    System.out.println("请输入id");
                    Emp search = ht.search(sc.nextInt());
                    if(search == null){
                        System.out.println("没有找到符合条件的雇员");
                    }else{
                        System.out.printf("雇员名字为%s\n",search.name);
                    }
                    break;
                case "del":
                    System.out.println("请输入id");
                    if(ht.remove(sc.nextInt())){
                        System.out.println("删除成功");
                    }else{
                        System.out.println("删除失败");
                    }
                default:
                    break;
            }
        }
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

1,增

当用户输入add后,在main方法中创建一个新的Emp对象,并调用HashTable中的add()方法

public void add(Emp emp){
        int empLinkedListNo = hashFun(emp.id);
        emps[empLinkedListNo].add(emp);
    }
1
2
3
4

hashFun代表哈希函数,通过对得到的id(哈希值)取模可以得到一个对应的值,作为在数组中存放的位置

public int hashFun(int id){
        return id % size;//哈希取模
    }
1
2
3

调用数组中对应元素的add方法,即链表的add()方法

public void add(Emp emp) {//将雇员添加到链表尾部
        Emp temp = head;
        if (head == null) {
            head = emp;
            return;
        } else {
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = emp;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12

遍历链表,将新对象添加到尾部

2,查

当用户输入search和需要查找的id后,调用HashTable中的search()方法

public Emp search(int id){
    int id1 = hashFun(id);
    return emps[id1].search(id);
}
1
2
3
4

通过哈希函数得到值后,调用对应数组元素中的search()方法

public Emp search(int id){
    if(head == null){
        return null;
    }else{
        Emp temp = head;
        while(temp!=null){
            if(temp.id == id){
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.1查看

当用户输入check后,调用HashTable中的check()方法

public void check(){
    try {
        for (int i = 0; i < emps.length; i++) {
            emps[i].check(i);
            System.out.println();
        }
    } catch (NullPointerException e) {
        System.out.println("数组中没有元素");
    }
}
1
2
3
4
5
6
7
8
9
10

调用对应链表中的check()方法查看链表中的元素

public void check(int no) {
    if (head == null) {
        System.out.println("第" + no + "条链表空");
        return;
    }
    System.out.println("第" + no + "条链表信息为");
    Emp temp = head;
    while (temp != null) {
        System.out.printf("name: %s,id: %d  ", temp.name, temp.id);
        temp = temp.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

3,删

当用户输入del和需要删除的id时,调用HashTable中的remove()方法

public boolean remove(int id){
    return emps[hashFun(id)].remove(id);
}
1
2
3

调用对应值的链表中的remove()方法

public boolean remove(int id){
    if(head == null){
        return false;
    }else{
        Emp temp = head;
        while(temp.next!=null){
            if(temp.next.id == id){
                temp.next = temp.next.next;
                return true;
            }
            temp = temp.next;
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

通过哈希表实现了一个简单的系统,对哈希表的底层数据结构有了更深层次的了解,但在jdk8之后,哈希表会在链表长度大于8并且数组长度大于64时变换为数组加红黑树的形式,这种更高级的哈希表留待我之后进行学习.