一、需求：哈希表(散列)-Google 上机题

看一个实际需求，google 公司的一个上机题:

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

二、哈希表的基本介绍

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

数据结构-哈希表 - 图1

数据结构-哈希表 - 图2

三、Google 上机题代码实现：

有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,名字,住址..),当输入该员工的 id 时, 要求查找到该员工的 所有信息.

要求:

  1. 不使用数据库,,速度越快越好=>哈希表(散列)
  2. 添加时，保证按照 id 从低到高插入 [课后思考：如果 id 不是从低到高插入，但要求各条链表仍是从低到 高，怎么解决?]
  3. 使用链表来实现哈希表, 该链表不带表头[即: 链表的第一个结点就存放雇员信息]
  • 思路分析示意图
    数据结构-哈希表 - 图3
  • 代码实现： 
  1. public class HashTabDemo {
  2.     public static void main(String[] args) {
  3.         //创建哈希表
  4.         HashTab hashTab = new HashTab(7);
  5.         //写一个简单的菜单
  6.         String key = "";
  7.         Scanner scanner = new Scanner(System.in);
  8.         while(true) {
  9.             System.out.println("add: 添加雇员");
  10.             System.out.println("list: 显示雇员");
  11.             System.out.println("find: 查找雇员");
  12.             System.out.println("exit: 退出系统");
  13.             key = scanner.next();
  14.             switch (key) {
  15.                 case "add":
  16.                     System.out.println("输入 id");
  17.                     int id = scanner.nextInt();
  18.                     System.out.println("输入名字");
  19.                     String name = scanner.next();
  20.                     //创建 雇员
  21.                     Emp emp = new Emp(id, name);
  22.                     hashTab.add(emp);
  23.                     break;
  24.                 case "list":
  25.                     hashTab.list();
  26.                     break;
  27.                 case "find":
  28.                     System.out.println("请输入要查找的 id");
  29.                     id = scanner.nextInt();
  30.                     hashTab.findEmpById(id);
  31.                     break;
  32.                 case "exit":
  33.                     scanner.close();
  34.                     System.exit(0);
  35.                 default:
  36.                     break;
  37.             }
  38.         }
  39.     }
  40. }
  42. //创建 HashTab 管理多条链表
  43. class HashTab {
  44.     private EmpLinkedList[] empLinkedListArray;
  45.     private int size; //表示有多少条链表
  47.     //构造器
  48.     public HashTab(int size) {
  49.         this.size = size;
  50.         //初始化 empLinkedListArray
  51.         empLinkedListArray = new EmpLinkedList[size];
  52.         //？留一个坑, 这时不要分别初始化每个链表
  53.         for(int i = 0; i < size; i++) {
  54.             empLinkedListArray[i] = new EmpLinkedList();
  55.         }
  56.     }
  58.     //添加雇员
  59.     public void add(Emp emp) {
  60.         //根据员工的 id ,得到该员工应当添加到哪条链表
  61.         int empLinkedListNO = hashFun(emp.id);
  62.         //将 emp 添加到对应的链表中
  63.         empLinkedListArray[empLinkedListNO].add(emp);
  64.     }
  66.     //遍历所有的链表,遍历 hashtab
  67.     public void list() {
  68.         for(int i = 0; i < size; i++) {
  69.             empLinkedListArray[i].list(i);
  70.         }
  71.     }
  73.     //根据输入的 id,查找雇员
  74.     public void findEmpById(int id) {
  75.         //使用散列函数确定到哪条链表查找
  76.         int empLinkedListNO = hashFun(id);
  77.         Emp emp = empLinkedListArray[empLinkedListNO].findEmpById(id);
  78.         if(emp != null) {//找到
  79.             System.out.printf("在第%d 条链表中找到 雇员 id = %d\n", (empLinkedListNO + 1), id);
  80.         }else{
  81.             System.out.println("在哈希表中，没有找到该雇员~");
  82.         }
  83.     }
  85.     //编写散列函数, 使用一个简单取模法
  86.     public int hashFun(int id) {
  87.         return id % size;
  88.     }
  89. }
  91. //表示一个雇员
  92. class Emp {
  93.     public int id;
  94.     public String name;
  95.     public Emp next; //next 默认为 null
  96.     public Emp(int id, String name) {
  97.         super();
  98.         this.id = id;
  99.         this.name = name;
  100.     }
  101. }
  103. //创建 EmpLinkedList ,表示链表
  104. class EmpLinkedList {
  105.     //头指针，执行第一个 Emp,因此我们这个链表的 head 是直接指向第一个 Emp
  106.     private Emp head; //默认 null
  108.     //添加雇员到链表
  109.     //说明
  110.     //1. 假定，当添加雇员时，id 是自增长，即 id 的分配总是从小到大
  111.     // 因此我们将该雇员直接加入到本链表的最后即可
  112.     public void add(Emp emp) {
  113.         //如果是添加第一个雇员
  114.         if(head == null) {
  115.             head = emp;
  116.             return;
  117.         }
  118.         //如果不是第一个雇员，则使用一个辅助的指针，帮助定位到最后
  119.         Emp curEmp = head;
  120.         while(true) {
  121.             if(curEmp.next == null) {//说明到链表最后
  122.                 break;
  123.             }
  124.             curEmp = curEmp.next; //后移
  125.         }
  126.         //退出时直接将 emp 加入链表
  127.         curEmp.next = emp;
  128.     }
  130.     //遍历链表的雇员信息
  131.     public void list(int no) {
  132.         if(head == null) { //说明链表为空
  133.             System.out.println("第 "+(no+1)+" 链表为空");
  134.             return;
  135.         }
  136.         System.out.print("第 "+(no+1)+" 链表的信息为");
  137.         Emp curEmp = head; //辅助指针
  138.         while(true) {
  139.             System.out.printf(" => id=%d name=%s\t", curEmp.id, curEmp.name);
  140.             if(curEmp.next == null) {//说明 curEmp 已经是最后结点
  141.                 break;
  142.             }
  143.             curEmp = curEmp.next; //后移，遍历
  144.         }
  145.         System.out.println();
  146.     }
  148.     //根据 id 查找雇员
  149.     //如果查找到，就返回 Emp, 如果没有找到，就返回 null
  150.     public Emp findEmpById(int id) {
  151.         //判断链表是否为空
  152.         if(head == null) {
  153.             System.out.println("链表为空");
  154.             return null;
  155.         }
  156.         //辅助指针
  157.         Emp curEmp = head;
  158.         while(true) {
  159.             if(curEmp.id == id) {//找到
  160.                 break;//这时 curEmp 就指向要查找的雇员
  161.             }
  162.             //退出
  163.             if(curEmp.next == null) {//说明遍历当前链表没有找到该雇员
  164.                 curEmp = null;
  165.                 break;
  166.             }
  167.             curEmp = curEmp.next;//以后
  168.         }
  169.         return curEmp;
  170.     }
  171. }
  • 新需求：添加时，自动按顺序排列，代码实现
public class HashTabDemo {
    public static void main(String[] args) {
        //创建哈希表
        HashTab hashTab = new HashTab(7);
        //写一个简单的菜单
        String key = "";
        Scanner scanner = new Scanner(System.in);
        while(true) {
            System.out.println("add: 添加雇员");
            System.out.println("list: 显示雇员");
            System.out.println("find: 查找雇员");
            System.out.println("exit: 退出系统");
            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);
                    hashTab.add(emp);
                    break;
                case "list":
                    hashTab.list();
                    break;
                case "find":
                    System.out.println("请输入要查找的 id");
                    id = scanner.nextInt();
                    hashTab.findEmpById(id);
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                default:
                    break;
            }
        }
    }
}

//创建 HashTab 管理多条链表
class HashTab {
    private EmpLinkedList[] empLinkedListArray;
    private int size; //表示有多少条链表

    //构造器
    public HashTab(int size) {
        this.size = size;
        //初始化 empLinkedListArray
        empLinkedListArray = new EmpLinkedList[size];
        //？留一个坑, 这时不要分别初始化每个链表
        for(int i = 0; i < size; i++) {
            empLinkedListArray[i] = new EmpLinkedList();
        }
    }

    //添加雇员
    public void add(Emp emp) {
        //根据员工的 id ,得到该员工应当添加到哪条链表
        int empLinkedListNO = hashFun(emp.id);
        //将 emp 添加到对应的链表中
        empLinkedListArray[empLinkedListNO].add(emp);
    }

    //遍历所有的链表,遍历 hashtab
    public void list() {
        for(int i = 0; i < size; i++) {
            empLinkedListArray[i].list(i);
        }
    }

    //根据输入的 id,查找雇员
    public void findEmpById(int id) {
        //使用散列函数确定到哪条链表查找
        int empLinkedListNO = hashFun(id);
        Emp emp = empLinkedListArray[empLinkedListNO].findEmpById(id);
        if(emp != null) {//找到
            System.out.printf("在第%d 条链表中找到 雇员 id = %d\n", (empLinkedListNO + 1), id);
        }else{
            System.out.println("在哈希表中，没有找到该雇员~");
        }
    }

    //编写散列函数, 使用一个简单取模法
    public int hashFun(int id) {
        return id % size;
    }
}

//表示一个雇员
class Emp {
    public int id;
    public String name;
    public Emp next; //next 默认为 null
    public Emp(int id, String name) {
        super();
        this.id = id;
        this.name = name;
    }
}

//创建 EmpLinkedList ,表示链表
class EmpLinkedList {
    //头指针，执行第一个 Emp,因此我们这个链表的 head 是直接指向第一个 Emp
    private Emp head; //默认 null

    //添加雇员到链表
    //说明
    //1. 假定，当添加雇员时，id 是自增长，即 id 的分配总是从小到大
    // 因此我们将该雇员直接加入到本链表的最后即可
    public void add(Emp emp) {
        //如果是添加第一个雇员
        if(head == null) {
            head = emp;
            return;
        }
        //如果不是第一个雇员，则使用一个辅助的指针，帮助定位到最后
        Emp curEmp = head;
        // 如果第一个的id大于要加入的
        if (curEmp.getId() > newEmp.getId()) {
            newEmp.setNext(curEmp);
            this.emp = newEmp;
            return;
        }
        // 从第二个开始遍历查找是否有小于要加入的
        Emp temp = this.emp;
        while (temp != null) {
            // 下一个节点的id大于要加入的 进行替换
            if (temp.getNext() == null) {
                temp.setNext(newEmp);
                break;
            } else if (temp.getNext().getId() > newEmp.getId()) { // 如果下一个节点是null 直接加入
                Emp cru = temp.getNext();
                newEmp.setNext(cru);
                temp.setNext(newEmp);
                break;
            }
            temp = temp.getNext();
        }
    }

    //遍历链表的雇员信息
    public void list(int no) {
        if(head == null) { //说明链表为空
            System.out.println("第 "+(no+1)+" 链表为空");
            return;
        }
        System.out.print("第 "+(no+1)+" 链表的信息为");
        Emp curEmp = head; //辅助指针
        while(true) {
            System.out.printf(" => id=%d name=%s\t", curEmp.id, curEmp.name);
            if(curEmp.next == null) {//说明 curEmp 已经是最后结点
                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;//这时 curEmp 就指向要查找的雇员
            }
            //退出
            if(curEmp.next == null) {//说明遍历当前链表没有找到该雇员
                curEmp = null;
                break;
            }
            curEmp = curEmp.next;//以后
        }
        return curEmp;
    }
}
  • 新需求：增加删除功能，代码实现
    ```java public class HashTabDemo { public static void main(String[] args) {
     //创建哈希表
 HashTab hashTab = new HashTab(7);
 //写一个简单的菜单
 String key = "";
 Scanner scanner = new Scanner(System.in);
 while(true) {
     System.out.println("add: 添加雇员");
     System.out.println("list: 显示雇员");
     System.out.println("find: 查找雇员");
     System.out.println("delete：删除员工");
     System.out.println("exit: 退出系统");
     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);
             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 "exit":
             scanner.close();
             System.exit(0);
         default:
             break;
     }
 }
    } }

//创建 HashTab 管理多条链表 class HashTab { private EmpLinkedList[] empLinkedListArray; private int size; //表示有多少条链表

//构造器
public HashTab(int size) {
    this.size = size;
    //初始化 empLinkedListArray
    empLinkedListArray = new EmpLinkedList[size];
    //？留一个坑, 这时不要分别初始化每个链表
    for(int i = 0; i < size; i++) {
        empLinkedListArray[i] = new EmpLinkedList();
    }
}

// 删除雇员
public void delete(int id) {
    int index = hashFun(id);
    this.empLinkedList[index].delete(id);
}

//添加雇员
public void add(Emp emp) {
    //根据员工的 id ,得到该员工应当添加到哪条链表
    int empLinkedListNO = hashFun(emp.id);
    //将 emp 添加到对应的链表中
    empLinkedListArray[empLinkedListNO].add(emp);
}

//遍历所有的链表,遍历 hashtab
public void list() {
    for(int i = 0; i < size; i++) {
        empLinkedListArray[i].list(i);
    }
}

//根据输入的 id,查找雇员
public void findEmpById(int id) {
    //使用散列函数确定到哪条链表查找
    int empLinkedListNO = hashFun(id);
    Emp emp = empLinkedListArray[empLinkedListNO].findEmpById(id);
    if(emp != null) {//找到
        System.out.printf("在第%d 条链表中找到 雇员 id = %d\n", (empLinkedListNO + 1), id);
    }else{
        System.out.println("在哈希表中，没有找到该雇员~");
    }
}

//编写散列函数, 使用一个简单取模法
public int hashFun(int id) {
    return id % size;
}

}

//表示一个雇员 class Emp { public int id; public String name; public Emp next; //next 默认为 null public Emp(int id, String name) { super(); this.id = id; this.name = name; } }

//创建 EmpLinkedList ,表示链表 class EmpLinkedList { //头指针，执行第一个 Emp,因此我们这个链表的 head 是直接指向第一个 Emp private Emp head; //默认 null

//添加雇员到链表
//说明
//1. 假定，当添加雇员时，id 是自增长，即 id 的分配总是从小到大
// 因此我们将该雇员直接加入到本链表的最后即可
public void add(Emp emp) {
    //如果是添加第一个雇员
    if(head == null) {
        head = emp;
        return;
    }
    //如果不是第一个雇员，则使用一个辅助的指针，帮助定位到最后
    Emp curEmp = head;
    // 如果第一个的id大于要加入的
    if (curEmp.getId() > newEmp.getId()) {
        newEmp.setNext(curEmp);
        this.emp = newEmp;
        return;
    }
    // 从第二个开始遍历查找是否有小于要加入的
    Emp temp = this.emp;
    while (temp != null) {
        // 下一个节点的id大于要加入的 进行替换
        if (temp.getNext() == null) {
            temp.setNext(newEmp);
            break;
        } else if (temp.getNext().getId() > newEmp.getId()) { // 如果下一个节点是null 直接加入
            Emp cru = temp.getNext();
            newEmp.setNext(cru);
            temp.setNext(newEmp);
            break;
        }
        temp = temp.getNext();
    }
}

//遍历链表的雇员信息
public void list(int no) {
    if(head == null) { //说明链表为空
        System.out.println("第 "+(no+1)+" 链表为空");
        return;
    }
    System.out.print("第 "+(no+1)+" 链表的信息为");
    Emp curEmp = head; //辅助指针
    while(true) {
        System.out.printf(" => id=%d name=%s\t", curEmp.id, curEmp.name);
        if(curEmp.next == null) {//说明 curEmp 已经是最后结点
            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;//这时 curEmp 就指向要查找的雇员
        }
        //退出
        if(curEmp.next == null) {//说明遍历当前链表没有找到该雇员
            curEmp = null;
            break;
        }
        curEmp = curEmp.next;//以后
    }
    return curEmp;
}

// 根据id删除
public void delete(int id) {
    if (this.isEmpty()) {
        System.out.println("员工：" + id + "不存在！");
    }

    Emp temp = this.emp;
    // 如果第一个就是
    if (temp.getId() == id) {
        this.emp = temp.getNext();
        return;
    }
    while (temp != null) {
        if (temp.getNext().getId() == id) {
            temp.setNext(temp.getNext().getNext());
            return;
        }
        temp = temp.getNext();
    }
    // 最后都没有找到
    System.out.println("员工：" + id + "不存在！");
}

} ```