1 哈希表的基本介绍
1.1 用于存储的数据结构
在计算机中，数组和链表都可以用于数据的存储，既然有数据存储，那么必然要有数据的查询，因此我们在将数据存储进数组和链表中之后，必然要对它们进行查询操作。一个链表的查询时间复杂度为O(n)，而一个无序数组的查询时间复杂度也是O(n)，对于数组的查询时间，我们尚有讨论的余地，但是链表的查询时间肯定是更长的，因为链表是不连续的空间，它只能一个接一个的遍历查询，不管链表是否有序。但是数组的查询时间，是可以进行改进的，当数组中数据是有序的，我们就可以使用二分查找的方式查找数组中的数据，进而能大量节省查询时间，对于二分查找，并不是一个困难的问题，因为二分法每次都能甩掉一般的数据，因此其时间复杂度肯定比O(n)低很多，它的时间复杂度是O(logn)，随着查询次数的增长，其时间复杂度会明显比O(n)低很多。
因此对于数组而言，我们的研究方向便不再是如何找更优的查找方案，而是如何将其更快的排序，因此引出了排序算法，目前主流的排序算法有八种，实际上大家比较认可的排序方法还有更多，值得学习的排序方法至少有十种。现实告诉我们，矛盾很难消除，它只会转移，有了二分查找的数组，查询时间长的矛盾并不能直接消除，因为排序算法也是耗费时间的，查询的时间跑到了排序的时间里去了。对于排序的时间复杂度，最低的为O(nlogn)，看上去也不是特别的少，这也就直接导致了两个算法加起来的时间复杂度，比直接无序状态查还耗费时间。
基于这个问题，有人创造性的提出了一种新的思想，那就是：在存储数据的时候，不再来数就存，而是使用一种巧妙的分类方法，将数据们进行分类，进而达到像二分查找一样的大规模缩减查询范围的效果，这就是哈希存储。
1.2 哈希表
哈希表的物理结构多种多样，在基数排序中用到的桶结构，实际上就是一种哈希表，哈希表通常是基于某种分类规则，为存储的数据进行分类，然后将他们存储在不同的索引下，这样我们在查询一个数据的时候，先拿到索引，然后找到哈希表中索引吻合的数据存储表，然后直接在这个表中查询即可，而不用再遍历所有数据，这就是哈希表的好处。为了助记哈希表，我将使用一个例子来生动的阐述哈希表：在一个图书馆中，存放着很多各种类别的书，有小说，字典，杂志，专业书籍等若干本。在早期，图书管理员并不怎么好好打理这些书籍，它将这些书籍完全无序的堆放在一起，来了借阅的人，就要直接挨个翻找，直到找到自己想要看的书籍为止。在之后的某一天，来了一个新的图书管理员，这个图书管理员为这些书籍进行了分类，他按照这四种类别将这些书放到了不同的区域中，之后，来了借阅的人，首先会报出书名，然后图书管理员按照书名判断这本书的类别，如来了一个人想借阅《人民文学》，图书管理员就会告诉这名读者：该书籍属于杂志，请去杂志区寻找，这名读者就会直接步行至杂志区，这样就他就不用再对整堆书进行翻找，很大程度上的节省了时间。哈希表的工作原理，实际上就是这样的一种过程。其使用到的主要思想，就是索引存储，它按照某一种规则，为数据分类，然后将这些数据放入不同的类别下，这些类别会有相应的索引值，在我们进行查询的时候，首先会查询索引值，查询到索引值之后，便直接将这个数据与索引值对应的存储结构中进行查询，这样就直接缩减了查询范围，缩小了查询规模。
1.3 什么是哈希表
散列表（Hash table，也叫哈希表），是根据关键码值（key value）而直接进行访问的数据结构。也就是说，它通过把关键吗值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
2 应用实例
有一个公司，当新员工来报到时，要求将该员工的信息加入（id，性别，年龄，名字，住址…），当输入该员工的id时，要求查找到该员工所有信息。
要求：
不使用数据库，速度越快越好 => 哈希表
添加时，保证按照 id 从低到高插入。
（1）使用链表来实现哈希表，该链表不带表头【即：链表的第一个节点就存放雇员信息】
（2）思路分析
（3）代码实现
代码实现：
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");
int no = scanner.nextInt();
hashTab.findEmpById(no);
break;
case "exit":
scanner.close();
System.out.println("退出系统");
System.exit(0);
default:
break;
}
}
}
}
// 创建 hashtable 管理多条链表
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);
}
}
// 编写散列函数
public int hashFun(int id) {
return id % size;
}
// 根据输入的 id查找雇员
public void findEmpById(int id){
// 使用散列函数确定到哪条链表查找
int i = hashFun(id);
Emp emp = empLinkedListArray[i].findEmpById(id);
if(emp != null){
System.out.printf("在第%d条链表中找到雇员 id=%d name=%s\n", i, emp.id, emp.name);
}else{
System.out.println("没有找到该雇员");
}
}
}
// 表示一个雇员
class Emp {
public int id;
public String name;
public Emp next;
public Emp(int id, String name) {
this.id = id;
this.name = name;
}
}
// 创建EmpLinkedList，表示链表
class EmpLinkedList {
// 头指针，执行第一个Emp，因此我们这个链表的 head 是直接指向第一个 Emp
// 默认为 null
private Emp head;
// 添加雇员到链表
// 说明：
// 1. 假定当添加雇员时，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("第" + no + "条链表的信息为");
Emp curEmp = head;
while (true) {
System.out.printf("=> id=%d name =%s \t", curEmp.id, curEmp.name);
// 说明 curEmp 已经是最后节点
if (curEmp.next == null) {
break;
}
// 后移
curEmp = curEmp.next;
}
System.out.println();
}
// 根据id查找链表
// 如果找到，返回Emp
public 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){
curEmp = null;
break;
}
curEmp = curEmp.next;
}
return curEmp;
}
}