(八):哈希表+二叉树_哈希+树混合算法

1.哈希表

1.1哈希表应用背景

看一个实际需求，google公司的一个上机题:
有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址…),当输入该员工的id时,要求查找到该员工的 所有信息.
要求: 不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列)

1. 2.哈希表的基本介绍

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

1. 3.谷歌公司的上机题

要求:

• 不使用数据库,速度越快越好=>哈希表(散列)
• 添加时，保证按照id从低到高插入 [课后思考：如果id不是从低到高插入，但要求各条链表仍是从低到高，怎么解决?]
  使用链表来实现哈希表, 该链表不带表头[即: 链表的第一个结点就存放雇员信息]
• 思路分析并画出示意图
• 代码实现[增删改查(显示所有员工，按id查询)]
  
  代码如下：

public class HashTableDemo {
    public static void main(String[] args) {
        //创建哈希表
        HashTable hashTable=new HashTable(7);
        String key="";
        Scanner scanner=new Scanner(System.in);
        while (true){
            System.out.println("add:添加雇员");
            System.out.println("list:显示雇员");
            System.out.println("exit:退出系统");
            System.out.println("find:退出系统");
            key=scanner.next();
            switch(key){
                case "add":
                    System.out.println("输入id");
                    int id=scanner.nextInt();
                    System.out.println("输入名字");
                    String name=scanner.next();
                    //创建一个雇员
                    Emp emp=new Emp(id,name);
                    hashTable.add(emp);
                    break;
                case "list":
                    hashTable.list();
                    break;
                case "exit":
                    scanner.close();
                    break;
                case "find":
                    System.out.println("请输入查找的id");
                    id=scanner.nextInt();
                    hashTable.findEmpById(id);
                default:
                    break;
            }
        }
    }
}
//写哈希表
class HashTable{
    private EmpLinkedList[] empLinkedListsArray;
    private int size;
    //有一个构造器
    public HashTable(int size){
        this.size=size;//表示有多少条链表
        //初始化链表
        empLinkedListsArray=new EmpLinkedList[size];
        //?不要忘记分别初始化每个链表
        for (int i=0;i<size;i++){
           empLinkedListsArray[i]=new EmpLinkedList();
        }
    }
    public void add(Emp emp){
        //根据员工的id得到该员工应该加入到哪条链表
        int empLinkedListNo=hashFun(emp.id);
        //将emp添加到对应的链表中
        empLinkedListsArray[empLinkedListNo].add(emp);
    }
    //遍历所有的链表
    public void list(){
        for (int i=0;i<size;i++) {
            empLinkedListsArray[i].list(i);
        }
    }
    //编写一个散列函数，使用简单的取模法
    public int hashFun(int id){
        return id%size;
    }
    //根据输出的id，查找雇员
    public void findEmpById(int id){
        int empLinkListNo=hashFun(id);
        Emp emp=empLinkedListsArray[empLinkListNo].findEmpById(id);
        if (emp!=null){//找到
            System.out.println("在x链表中找到雇员"+emp.name);
        }else {
            System.out.println("没找到该雇员");
        }
    }



}
class Emp{
    public int id;
    public  String name;
    public Emp next;//next默认就是空

    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }
}
//创建一个EmpLinkedList，表示链表
class EmpLinkedList{
    //头指针，就是指向第一个Emp
    private Emp head;//默认就是null
    //添加雇员到链表
    //假定当添加雇员时候，id是自增长的，即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.println("当前链表的信息为：");
        Emp curEmp=head;//辅助指针
        while (true){
            System.out.printf("=>id=%d name=%s",curEmp.id,curEmp.name);
            if (curEmp.next==null){//说明curEmp已经是最后节点
                break;
            }
            curEmp=curEmp.next;
        }

    }
    //查找链表
    //查找到就返回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;//这时curEmp就指向雇员
            }
            if (curEmp.next==null){
                //说明遍历当前链表没有找到该雇员
                curEmp=null;
                break;
            }
            curEmp=curEmp.next;
        }
        return curEmp;
    }
}

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

2.二叉树

2.1为什么需要树这种结构

2.1.1数组存储方式的分析

• 优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。
• 缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低 [示意图]

2.1.2链式存储方式的分析

• 优点：在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可， 删除效率也很好)。
• 缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历)

2.1.3树存储方式的分析

能提高数据存储，读取的效率, 比如利用 二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。

2.2 二叉树介绍

2.2.1树的常用术语(结合示意图理解)

• 节点
• 根节点
• 父节点
• 子节点
• 叶子节点 (没有子节点的节点)
• 节点的权(节点值)
• 路径(从root节点找到该节点的路线)
• 层
• 子树
• 树的高度(最大层数)
• 森林 :多颗子树构成森林

树示意图

2.2.2二叉树的概念

• 树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。
• 二叉树的子节点分为左节点和右节点。

• 如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2^n -1 , n 为层数，则我们称为满二叉树。
• 如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。

2.3二叉树的遍历

前序遍历: 先输出父节点，再遍历左子树和右子树
中序遍历: 先遍历左子树，再输出父节点，再遍历右子树
后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点
小结: 看输出父节点的顺序，就确定是前序，中序还是后序

 //前序遍历
    public void preOrder(){
        if (this.root!=null){
            this.root.preOrder();
        }else {
            System.out.println("当前二叉树为空");
        }
    }
    //中序遍历
    public void infixOrder(){
        if (this.root!=null){
            this.root.infixOrder();
        }else {
            System.out.println("空！");
        }
    }
    //后续遍历
    public void postOrder(){
        if (this.root!=null){
            this.root.postOrder();
        }else {
            System.out.println("空！");
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24