【数据结构与算法】哈希表(散列表)的介绍和程序实现、树的优点和常用术语介绍

1. 哈希表(散列表) 1.1 哈希表的介绍

哈希表(Hash table，也叫散列表)，主要用来提高查询速度

数据的保存过程：一条数据根据key经过映射函数/散列函数(例如进行hash计算然后取模)计算，根据得到的值将数据保存到哈希表(用数组实现)对应的位置

数据的查询过程：查询数据也是指定key，然后将该key经过散列函数计算，再根据得到的值从哈希表(用数组实现)指定的位置获取数据

1.2 哈希表的程序实现

需求：将大量员工的数据进行保存，员工信息包含id、name，添加员工数据时id是递增的；当输入员工id时，要求不使用数据库，使用少量内存且快速的查询该员工信息。可以使用哈希表进行实现

实现思路：使用数组来实现哈希表，数组的元素类型是链表(也可用二叉树实现)，一个链表用来保存相同散列函数结果值的多个员工的数据，链表的head就是第一个添加的员工

程序如下：

public class HashTableDemo {

    public static void main(String[] args) {

        // 创建哈希表
        HashTable hashTable = new HashTable(5);

        // 将多个员工数据添加到哈希表
        Emp emp1 = new Emp(1, "emp1");
        Emp emp2 = new Emp(2, "emp2");
        Emp emp3 = new Emp(6, "emp6");
        hashTable.add(emp1);
        hashTable.add(emp2);
        hashTable.add(emp3);

        // 根据员工id查询员工信息
        hashTable.findEmpById(6);

        // 显示所有员工的信息
        hashTable.show();
    }

}


// 表示一个员工
class Emp {
    public int id;
    public String name;
    // 用来实现链表，默认是null
    public Emp next;

    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }
}


// 链表用来保存相同散列函数结果值的多个员工的数据
class EmpLinkedList {
    // 链表的head就是第一个添加的员工，默认是null
    private Emp head;

    // 添加员工到链表
    // 因为员工的id是递增的，所以直接将新员工添加到链表的最后即可
    public void add(Emp emp) {
        // 第一个员工直接赋值给head
        if (this.head == null) {
            this.head = emp;
            return;
        } else {
            // 找到链表的最后一个节点，然后添加新员工到后面
            Emp currentEmp = this.head;
            while (currentEmp.next != null) {
                currentEmp = currentEmp.next;
            }
            currentEmp.next = emp;
        }
    }

    // 根据员工id查询员工信息
    public Emp findEmpById(int empId) {
        // 如果链表为空，直接返回null
        if (this.head == null) {
            System.out.println("链表为空");
            return null;
        } else {
            Emp currentEmp = this.head;
            while (true) {
                // 如果找到了，则返回当前员工
                if (currentEmp.id == empId) {
                    return currentEmp;
                    // 如果下一个节点为null，则返回null
                } else if (currentEmp.next == null) {
                    return null;
                    // 如果还有下一个节点，则进行下一个节点的查找
                } else {
                    currentEmp = currentEmp.next;
                }

            }
        }

    }

    // 遍历显示链表所有员工的数据。参数为链表在哈希表中的编号
    public void show(int empLinkedListNo) {
        // 如果链表为空
        if (this.head == null) {
            System.out.println("第" + (empLinkedListNo + 1) + "号链表为空");
            return;
        } else {
            System.out.print("第" + (empLinkedListNo + 1) + "号链表的信息为: ");
            Emp currentEmp = this.head; //辅助指针
            // 循环打印所有员工的信息
            while (true) {
                System.out.printf(">>>>>>id=%d, name=%s\t", currentEmp.id, currentEmp.name);
                if (currentEmp.next == null) {
                    break;
                } else {
                    currentEmp = currentEmp.next;
                }
            }
            System.out.println();
        }


    }
}


// 使用数组来实现哈希表，数组的元素类型是链表
class HashTable {
    private EmpLinkedList[] empLinkedListArray;
    // 链表的个数
    private int empLinkedListArraySize;

    public HashTable(int empLinkedListArraySize) {
        this.empLinkedListArraySize = empLinkedListArraySize;
        this.empLinkedListArray = new EmpLinkedList[empLinkedListArraySize];

        // 初始化每个链表
        for (int i = 0; i < this.empLinkedListArraySize; i++) {
            this.empLinkedListArray[i] = new EmpLinkedList();
        }
    }

    // 添加员工
    public void add(Emp emp) {
        // 将员工的id经过散列函数计算, 然后将该员工添加到对应的链表
        int empLinkedListNo = this.hashFunction(emp.id);
        this.empLinkedListArray[empLinkedListNo].add(emp);
    }


    // 根据员工id查找员工信息
    public void findEmpById(int empId) {
        // 将要查找的员工的id经过散列函数计算, 然后从对应的链表进行查询
        int empLinkedListNo = this.hashFunction(empId);
        Emp emp = this.empLinkedListArray[empLinkedListNo].findEmpById(empId);
        if (emp != null) {
            System.out.printf("在第%d号链表中找到id=%d的员工，其name=%s\n", (empLinkedListNo + 1), emp.id, emp.name);
        } else {
            System.out.printf("未找到id=%d的员工的信息\n", empId);
        }
    }

    // 遍历哈希表的所有链表，显示所有员工信息
    public void show() {
        for (int i = 0; i < this.empLinkedListArraySize; i++) {
            this.empLinkedListArray[i].show(i);
        }
    }

    // 散列函数。这里只进行简单的取模
    public int hashFunction(int empId) {
        return empId % this.empLinkedListArraySize;
    }
}

运行程序，结果如下：

在第2号链表中找到id=6的员工，其name=emp6
第1号链表为空
第2号链表的信息为: >>>>>>id=1, name=emp1	>>>>>>id=6, name=emp6	
第3号链表的信息为: >>>>>>id=2, name=emp2	
第4号链表为空
第5号链表为空

2. 树的优点和常用术语介绍 2.1 为什么会有树结构

数组的缺点：按数组的值顺序插入值，或删除值。都要新建一个数组，进行原数组的值拷贝，再进行操作，效率较低。ArrayList的底层也是通过数组来储存数据的 链表的缺点：检索某个值，需要从头节点开始遍历，效率较低

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

2.2 树的常用术语

树的常用术语：

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