哈希表
一、基本概念
散列表（Hash table，也叫哈希表），是根据关键码值 (Key value) 而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表 M，存在函数 f(key)，对任意给定的关键字值 key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表 M 为哈希 (Hash）表，函数 f(key) 为哈希 (Hash) 函数。
-
结构
哈希表的结构可以使用数组 + 链表实现，也可以使用数组 + 二叉树来实现，因为前面我们还未接触到树这部分内容，所以这里我们就使用数组 + 链表来实现。这样一个哈希表的结构如下：
我们可以看到，哈希表其实就是一个存放着链表的数组构成的，可以理解为就是一个数组，而这个数组中的元素又是一个链表。
-
存储
下面我们来看看哈希表的存储。
哈希表是根据关键码值 (Key value) 而直接进行访问的，通过一个散列函数来将码、键进行映射。简单来说，就是我们提前编写一个规则，即函数 y=f(key)，在存储或访问时，我们通过 k 进行计算，得到一个位置来进行存储或访问。
简单举个例子，现有以下一个哈希表，我们给出一个散列函数 y=f(key)=key%5（取模）。
假设我们要进行存储的数据关键码值为（1，张三），那么经过散列函数计算：y=1%5=1，那么这个数据将被存放到数组下标为 1 的位置：
同样我们再随便存储几个数据（2，李四）（6，王五）（49，小明）
为了举例简单，我们这里的散列函数也比较简单，在实际中，有时我们可能需要为了避免冲突而专门设计一个比较复杂的散列函数。
二、代码实现
背景：利用哈希表来存储员工信息（id,name), 并可以通过 id 来查找员工
- 首先创建一个员工类
//表示一个员工
class Emp {
public int id;
public String name;
public Emp next;//默认为空
public Emp(int id, String name) {
this.id = id;
this.name = name;
}
}
- 接下来我们创建哈希表中每个数组中存储的链表结构，包括基本的添加（add）、遍历（list）、查找（findEmpById)
//创建EmpLinkedList,表示链表
class EmpLinkedList {
private Emp head;//头指针，默认为空
//添加员工到链表,假设id是自增长的
public void add(Emp emp) {
if (head == null) {//如果是第一个员工
head = emp;
return;
}
//如果不是第一个员工
Emp temp = head;
while (true) {
if (temp.next == null) {
break;
}
temp = temp.next;
}
temp.next = emp;
}
//遍历链表
public void list(int no) {
if (head == null) {//链表为空
System.out.println("第" + (no + 1) + "条链表为空！");
return;
}
System.out.print("第" + (no + 1) + "条链表的信息为：");
Emp temp = head;
while (true) {
System.out.printf("=> id=%d name=%s\t",temp.id,temp.name);
if (temp.next == null) {
break;
}
temp = temp.next;
}
System.out.println();
}
//根据id查找员工
public Emp findEmpById(int id) {
if (head == null) {
System.out.println("链表空");
return null;
}
Emp temp = head;
while (true) {
if (temp.id == id) {//找到员工
break;
}
if (temp.next == null) {//没有找到员工
temp = null;
break;
}
temp = temp.next;
}
return temp;
}
- 然后来创建一个哈希表结构
//创建hashtable管理多条链表
class HashTable {
private EmpLinkedList[] empLinkedLists;
private int size;//表示共有多少条链表
//空参构造器，数组默认初始化为5
public HashTable() {
this.size = 5;
empLinkedLists = new EmpLinkedList[size];
//分别初始化每一个链表
for (int i = 0; i < size; i++) {
empLinkedLists[i] = new EmpLinkedList();
}
}
//带参构造器
public HashTable(int size) {
//初始化
this.size = size;
empLinkedLists = new EmpLinkedList[size];
//分别初始化每一个链表
for (int i = 0; i < size; i++) {
empLinkedLists[i] = new EmpLinkedList();
}
}
//添加员工
public void add(Emp emp) {
//根据员工id，得到该员工要插入到哪条链表
int empLinkedListNum = hashFun(emp.id);
//将emp添加到对应的链表中
empLinkedLists[empLinkedListNum].add(emp);
}
//遍历所有链表，遍历哈希表
public void list() {
for (int i = 0; i < size; i++) {
empLinkedLists[i].list(i);
}
}
//根据id查找员工
public void findEmpById(int id) {
//使用散列函数确定到哪条链表中查找
int empLinkedListNum = hashFun(id);
Emp emp = empLinkedLists[empLinkedListNum].findEmpById(id);
if (emp != null) {//找到了
System.out.printf("在第%d条链表中找到员工 id=%d\n",(empLinkedListNum+1),id);
} else {
System.out.println("未找到该员工");
}
}
//编写一个简单的散列函数
public int hashFun(int id) {
return id % size;
}
}
- 最后写一个简单的 Demo 来测试
public static void main(String[] args) {
//创建一个哈希表
HashTable hashTable = new HashTable(5);
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.print("请输入员工id：");
int id = scanner.nextInt();
System.out.print("请输入员工name：");
String name = scanner.next();
Emp emp = new Emp(id, name);
hashTable.add(emp);
break;
case "list":
System.out.println("员工信息如下：");
hashTable.list();
break;
case "find":
System.out.print("请输入要查找的员工id：");
id = scanner.nextInt();
hashTable.findEmpById(id);
break;
case "exit":
scanner.close();
System.exit(0);
default:
break;
}
}
}
我们按照上面举例的数据进行存储
根据 id 查找员工
