![学习数据结构笔记(8) ---[哈希表(Hash table)]](http://www.mshxw.com/aiimages/31/458596.png "学习数据结构笔记(8) ---[哈希表(Hash table)]")
B站学习传送门–>尚硅谷Java数据结构与java算法（Java数据结构与算法）
一般在java程序访问数据库时都会安排从内存的缓存层中取数据;之前的做法是自己写个哈希表,实现对数据的缓存.
哈希表(散列表) 作为一种数据结构,而不是算法
通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
那么该如何实现呢,
通过完成这个案例来实现;领会哈希表的结构
有一个公司,当有新的员工来报道时,要求将该员工的信息加入
(id,性别,年龄,名字,住址…),当输入该员工的id时,要求查找到该员工的
所有信息.
要求:
- 不使用数据库,速度越快越好=>哈希表(散列)
- 添加时，保证按照id从低到高插入
- 1 使用链表来实现哈希表, 该链表不带表头[即: 链表的第一个结点就存放雇员信息]
- 2 思路分析并画出示意图
- 3 代码实现[增删改查(显示所有员工，按id查询)]
首先图解看看;
本次实现考虑使用数组加链表的方式实现;
在链表中存储不同的员工类对象的信息;即使在链表中定义了增删改…方法;那么在整体的哈希表也可以调用这些方法;决定向数组的哪个位置下的链表进行管理操作
(这里实现的话,通过对员工的Id和数组的长度进行取模运算来决定向数组的哪个下标位置进行操作)
具体实现
public class HashTableTest {
//测试使用;
public static void main(String[] args) {
HashTable hashTable = new HashTable(10);
hashTable.addEmp(new Employee(1,"杰克"));
hashTable.addEmp(new Employee(11,"马克"));
hashTable.addEmp(new Employee(12,"阿杰"));
hashTable.addEmp(new Employee(22,"阿杰"));
hashTable.addEmp(new Employee(9,"克烈"));
hashTable.addEmp(new Employee(8,"科斯特"));
//遍历;
hashTable.empList();
//找员工;
hashTable.getEmpById(9);
hashTable.getEmpById(100);
hashTable.getEmpById(12);
}
}
//定义的哈希表;
class HashTable{
//定义数组;
private final Emplinked[] emplinkeds;
// 定义数组的长度;
private final int length;
//初始化哈希表;
public HashTable(int length) {
this.emplinkeds = new Emplinked[length];
this.length = length;
//注意上面只是创建了一个数组,但是链表还为null;
//需要创建链表;
for (int i = 0; i < length; i++) {
emplinkeds[i] = new Emplinked();
}
}
//现根据Id找数组位置;
private int getRightLocation(int id){
return id % length;
}
//添加这个员工到指定位置;
public void addEmp(Employee employee){
//先找到要添加的数组位置;
int location = getRightLocation(employee.id);
System.out.println("----获取要添加到的索引位置"+location);
//然后再放到该数组元素下的链表中;
emplinkeds[location].addEmp(employee);
}
//遍历输出链表;
public void empList(){
for (int i = 0; i < length; i++) {
emplinkeds[i].empList(i);
}
}
//根据Id找员工信息;
public void getEmpById(int id){
//先找到该员工所在的链表位置;
int location = getRightLocation(id);
//找员工信息;
Employee empById = emplinkeds[location].getEmpById(id);
if(empById!=null){
System.out.println("在第"+(location+1)+"条链表找到该员工-> ID:"
+emplinkeds[location].getEmpById(id).id+" 姓名:"+emplinkeds[location].getEmpById(id).empName);
}else {
System.out.println("id为"+id+"的员工不存在");
}
}
}
//存放员工节点的链表;
class Emplinked{
//头结点;
private Employee head;
//添加员工;
public void addEmp(Employee emp){
//若为空链表直接存入;
if(head == null){
head = emp ;
return;
}
//若不是空链表;则先把头结点存入临时节点;
Employee temp = head ;
while (temp.next != null) {
//链表不断后移;
temp = temp.next;
}
//存入员工;
temp.next = emp;
}
//遍历当前的链表;
public void empList(int num){
if(head == null){
System.out.println("当前第"+(num+1)+"条链表为空");
return;
}
System.out.print("第"+(num+1)+"条链表信息为--");
//用临时节点来遍历;
Employee temp = head;
while (true){
System.out.printf("[id::%d enpName::%s]--> ",temp.id,temp.empName);
if(temp.next == null){
break;
}
//遍历链表;
temp = temp.next;
}
System.out.println();
}
//根据Id查找指定的员工信息;
public Employee getEmpById(int id){
if(head == null){
return null;
}
//用临时节点遍历;
Employee temp = head;
while (true){
if(temp.id == id){
break;
}
if(temp.next==null){
//没找到的话,把这个临时节点重置为null空值;
temp = null;
break;
}
//移动;
temp = temp.next;
}
return temp;
}
}
//员工信息类;作为链表中的节点;
class Employee{
//员工的Id与姓名;以及指向下一个员工的指针;
public int id;
public String empName;
public Employee next;
//初始化;
public Employee(int id, String empName) {
this.id = id;
this.empName = empName;
}
}
测试结果
----获取要添加到的索引位置1 ----获取要添加到的索引位置1 ----获取要添加到的索引位置2 ----获取要添加到的索引位置2 ----获取要添加到的索引位置9 ----获取要添加到的索引位置8 当前第1条链表为空 第2条链表信息为--[id::1 enpName::杰克]--> [id::11 enpName::马克]--> 第3条链表信息为--[id::12 enpName::阿杰]--> [id::22 enpName::阿杰]--> 当前第4条链表为空 当前第5条链表为空 当前第6条链表为空 当前第7条链表为空 当前第8条链表为空 第9条链表信息为--[id::8 enpName::科斯特]--> 第10条链表信息为--[id::9 enpName::克烈]--> 在第10条链表找到该员工-> ID:9 姓名:克烈 id为100的员工不存在 在第3条链表找到该员工-> ID:12 姓名:阿杰
