10 哈希表（Hashtable）
引入：
有一个公司，当有新的员工来报道时，要求将该员工的信息加入（id，性别，年龄，住址…），当输入该员工的id时，要求查找到该员工的所有信息。
要求：不适用数据结构，尽量节省内存，速度越快越好=>哈希表（散列）
1）基础介绍
哈希表（又叫散列表），是根据关键码值（key value）而直接进行访问的数据结构。
也就是说，它通过关键码直接映射到表中的位置来访问，以加快查找速度
这个映射函数叫做散列函数，存放记录的数组叫散列表
2）哈希表实际应用场景
一个java程序会经常的调动数据库里的数据，为了加快这个调用，程序员在java程序和数据库之间加入一个缓存层，以缓存要调用的数据，依次加快调用速度。
缓存层可以是现有的缓存产品，比如：Redis、Memcache；也可以是自己写出，比如：哈希表。
3）哈希表的结构
1. 有两种形式：
数组+链表数组+二叉树
2.哈希表的内存结构
如图是数组（左）+链表（右）的形式
4）哈希表实现思路图解
google公司的一个上机题
有一个公司，当有新的员工来报道时，要求将该员工的信息加入（id，性别，年龄，住址…），当输入该员工的id时，要求查找到该员工的所有信息。
要求：不适用数据结构，尽量节省内存，速度越快越好=>哈希表（散列）
添加时，保证id从低到高插入
做题流程：
使用链表来实现哈希表，该链表不带头（即：链表的第一个节点就存放雇员信息）思路分析并画示意图 代码实现↓
5）代码实现——增删改查
package DataStructures.Hashtable;import java.util.Scanner;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("find：查找雇员");System.out.println("exit：退出系统");System.out.println("del：删除雇员");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 "find":System.out.println("请输入要查找的id");id = scanner.nextInt();hashTable.findEmpById(id);break;case "del":System.out.println("请输入要删除的id");id = scanner.nextInt();hashTable.delEmp(id);break;case "exit":scanner.close();System.exit(0);break;default:break;}}}}//创建HashTable 管理多条链表class HashTable {private EmpLinkedList empLinkedListArray[];private int size;//构造器public HashTable(int size) {this.size = size;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);}//遍历所有的链表,遍历hashtablpublic 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("在哈希表中没有找到该雇员");}}//删除输入的id对应的雇员信息public void delEmp(int id){int empLinkedListNo = hashFun(id);empLinkedListArray[empLinkedListNo].del(id);}//编写散列函数，使用一个简单的取模法public int hashFun(int id) {return id % size;}}//表示一个雇员class Emp {public int id;public String name;public Emp next;public Emp(int id, String name) {super();this.id = id;this.name = name;}}//创建一个EmpLinkedList，表示链表class EmpLinkedList {//头指针，执行第一个Emp,因此我们这个链表的head是直接指向第一个Empprivate Emp head;//默认为null//添加雇员到链表//说明//1.假定添加雇员就是链表最后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+1)+"条链表为空");return;}System.out.println("第"+(no+1)+"条链表信息为：");Emp curEmp = head;while (true) {System.out.printf(" =>id=%d name=%s\t", curEmp.id, curEmp.name);if (curEmp.next == null) {break;}curEmp = curEmp.next;}System.out.println();}//根据id查找雇员//如果查找到就返回Emp，如果没有就返回nullpublic Emp findEmpById(int id){//判断链表是否为空if(head==null){System.out.println("链表空");return null;}Emp curEmp = head;while (true){if(curEmp.id==id){break;}//退出条件if (curEmp.next==null){//no findcurEmp = null;break;}curEmp = curEmp.next;}return curEmp;}public void del(int id){if(head==null){System.out.println("链表为空，无法删除");return;}if (head.id==id){if(head.next==null){head=null;}else {head = head.next;}return;}Emp curEmp = head;boolean flag = false;while (true){if(curEmp.next==null){break;}if (curEmp.next.id==id){flag=true;break;}curEmp = curEmp.next;}if (flag){curEmp.next = curEmp.next.next;}else {System.out.println("要删除的节点不存在");}}}
注释：首先先监理节点Emp然后建立一个单无头链表EmpLinkedList最后以链表的形式转成哈希表HashTable（即用数组表示的链表）详见上面图解
