哈希表

• 哈希表
  • 应用背景
    • Google上机题
    • 减少数据库查询次数
  • 基本介绍
  • 实现思路
  • 代码实现

应用背景

Google上机题

看一个实际需求，Google公司的一个上机题：

有一个公司，当有新的员工来报道时，要求将该员工的信息加入（id，性别，年龄，住址…），当输入该员工的id时，要求查找到该员工的所有信息.
要求：不使用数据库，尽量节省内存，速度越快越好

这时候就暗示要使用哈希表（散列）

减少数据库查询次数

可用于数据库和业务层（Java程序）之间的缓存层，从而减少数据库查询次数。

基本介绍

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

实现思路

创建一个数组，数组每个元素存放一条链表，使用一种散列函数（如除余），使每个结点分散存放到指定链表。

代码实现

hashTable类，包括测试

public class HashTable {

    // 测试
    public static void main(String[] args) {
        HashTable hashTable = new HashTable(8);
        Emp emp1 = new Emp(1, "Yorick");
        Emp emp2 = new Emp(2, "Jerry");
        Emp emp3 = new Emp(3, "Lily");
        Emp emp4 = new Emp(4, "Tom");
        Emp emp5 = new Emp(4, "Sia");
        Emp emp10 = new Emp(10, "Jim");
        Emp emp11 = new Emp(11, "Merry");
        Emp emp12 = new Emp(12, "Jack");
        Emp emp13 = new Emp(13, "Mike");
        Emp emp23 = new Emp(23, "Smith");
        hashTable.add(emp1);
        hashTable.add(emp2);
        hashTable.add(emp3);
        hashTable.add(emp4);
        hashTable.add(emp5);
        hashTable.add(emp10);
        hashTable.add(emp11);
        hashTable.add(emp12);
        hashTable.add(emp13);
        hashTable.add(emp23);
        hashTable.list();
        hashTable.find(11);
        hashTable.del(3);
        hashTable.list();
    }

    private final int size;
    private final EmpLinkedList[] empLinkedLists;

    public HashTable(int tableLength) {
        this.size = tableLength;
        empLinkedLists = new EmpLinkedList[tableLength];
        for (int i = 0; i < size; i++) {
            empLinkedLists[i] = new EmpLinkedList();
        }
    }

    // 增加
    public void add(Emp emp) {
        getListNo(emp.getId());
        empLinkedLists[emp.getId() % size].add(emp);
    }

    // 遍历
    public void list() {
        for (int i = 0; i < size; i++) {
            System.out.print("第 " + (i + 1) + " 条 ");
            empLinkedLists[i].list();
        }
    }

    // 查找
    public void find(int id) {
        EmpLinkedList empLinkedList = getListNo(id);
        Emp emp = empLinkedList.find(id);
        if (emp == null) {
            System.out.println("未找到ID为 " + id + " 的结点");
        } else {
            System.out.println("此ID对应姓名为：" + emp.getName());
        }
    }

    // 删除
    public void del(int id) {
        empLinkedLists[id % size].del(id);
    }

    // 获取id所在链表
    public EmpLinkedList getListNo(int id) {
        return empLinkedLists[id % size];
    }
}

单链表EmpLinkedList类

public class EmpLinkedList {

    public Emp head = null;

    // 增加结点
    public void add(Emp emp) {
        // 如果链表为空，将第一个插入值作为头结点
        if (isEmpty()) {
            head = emp;
            return;
        }
        // 辅助指针
        Emp helper = head;
        while (helper.next != null && emp.getId() > helper.next.getId()) {
            helper = helper.next;
        }
        Emp temp = helper.next;
        helper.next = emp;
        emp.next = temp;
    }

    // 遍历链表
    public void list() {
        if (isEmpty()) {
            System.out.println("NULL");
            return;
        }
        Emp helper = head;
        while (helper != null) {
            System.out.printf("ID:%d NAME:%s\t", helper.getId(), helper.getName());
            helper = helper.next;
        }
        System.out.println();
    }

    public Emp find(int id) {
        if (isEmpty()) {
            System.out.println("链表为空");
            return null;
        }
        Emp helper = head;
        while (helper != null) {
            if (helper.getId() == id) {
                return helper;
            }
            helper = helper.next;
        }
        return null;
    }

    public void del(int id) {
        if (isEmpty()) {
            System.out.println("链表为空");
            return;
        }
        if (head.getId() == id) {
            head = head.next;
            return;
        }
        Emp helper = head;
        while (helper.next != null) {
            if (helper.next.getId() == id) {
                helper.next = helper.next.next;
                break;
            }
            helper = helper.next;
        }
        System.out.println("未找到ID为 " + id + " 的结点");
    }

    // 判断非空
    public boolean isEmpty() {
        return head == null;
    }
}

节点类Emp

public class Emp {
    private int id;
    private String name;
    public Emp next;

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

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

}