Hash table 介绍
94965625.png
练习题
95031937.png
notice：
hash表的组成：
数组:维护链表的指针，也就是关键码值 key 可以按照某一规律维护，比如：取模来维护链表的指针。
链表：用来存值
取模：
公式：a mod b = a - b[a/b] ([a/b]表示整数商)
取模例子
简述 商值 取模值
430450453.png
code
EmpLinkedList
package com.pl.arithmetic.hash;
import com.pl.arithmetic.dto.HeroNode;
import lombok.extern.slf4j.Slf4j;
/**
* <p>
*
* @Description: TODO
* </p>
* @ClassName EmpLinkedList
* @Author pl
* @Date 2020/9/20
* @Version V1.0.0
*/
@Slf4j
public class EmpLinkedList {
private HeroNode headNode;
/**
*员工链表添加
*
* @param heroNode
* @return void
* @exception
* @author silenter
* @date 2020/9/20 10:11
*/
public void add(HeroNode heroNode){
//@1 非空判断
if (headNode ==null) {
headNode = heroNode;
return;
}
//@2 查找最后一个节点
//局部变量 线程安全，对象引用，不创建新地址值，指向同一个地址。
HeroNode indexNode = headNode;
while (true){
if (indexNode.next == null){
break;
}
indexNode = indexNode.next;
}
indexNode.next = heroNode;
}
/**
*员工链表遍历
*
* @param arrIndex
* @return void
* @exception
* @author silenter
* @date 2020/9/20 10:11
*/
public void list(int arrIndex){
arrIndex ++;
//@1 链表非空判断 headnode非空
if (headNode == null){
System.out.println("第"+arrIndex+"链表为空");
return;
}
//@2 遍历输出
System.out.print("第"+arrIndex+"链表详情：");
HeroNode indexNode = headNode;
while (true){
System.out.printf("=> id=%d name = %s\t",indexNode.no,indexNode.name);
if (indexNode.next ==null)
break;
indexNode = indexNode.next;
}
System.out.println();
}
/**
* 根据id匹配
* @param id 员工id
* @return com.pl.arithmetic.dto.HeroNode
* @exception
* @author silenter
* @date 2020/9/20 10:09
*/
public HeroNode findById(int id){
//@1 链表非空判断 headnode非空
if (headNode == null){
System.out.println("无此员工");
return null;
}
//@2 遍历匹配
HeroNode indexNode = headNode;
while (true){
if (indexNode.no == id){
break;
}
if (indexNode.next == null){
indexNode = null;
break;
}
indexNode = indexNode.next;
}
return indexNode;
}
}
HashTableTest
package com.pl.arithmetic.hash;
import com.pl.arithmetic.dto.HeroNode;
/**
* <p>
*
* @Description: 哈希表练习
* </p>
* @ClassName HashTableTest
* @Author pl
* @Date 2020/9/20
* @Version V1.0.0
*/
public class HashTableTest {
private EmpLinkedList[] empLinkedLists;
//链表数
private int size;
public HashTableTest(int size){
this.size = size;
this.empLinkedLists = new EmpLinkedList[size];
for (int i = 0; i < empLinkedLists.length; i++) {
empLinkedLists[i] = new EmpLinkedList();
}
}
/**
* 获取链表索引位
*
* @param id
* @return int
* @exception
* @author silenter
* @date 2020/9/20 10:19
*/
public int getLinkedIndex(int id){
return id%size;
}
/**
* hash添加
*
* @param heroNode
* @return void
* @exception
* @author silenter
* @date 2020/9/20 10:21
*/
public void add(HeroNode heroNode){
//@1 先获取算出应添加到哪个链表中
int linkedIndex = getLinkedIndex(heroNode.no);
//@2 在指定的链表中添加
empLinkedLists[linkedIndex].add(heroNode);
}
/**
* 遍历
*
* @param
* @return void
* @exception
* @author silenter
* @date 2020/9/20 10:24
*/
public void list(){
for (int i = 0; i < empLinkedLists.length; i++) {
empLinkedLists[i].list(i);
}
}
/**
* 根据id检索
*
* @param id
* @return com.pl.arithmetic.dto.HeroNode
* @exception
* @author silenter
* @date 2020/9/20 10:27
*/
public void getById(int id){
int linkedIndex = getLinkedIndex(id);
HeroNode heroNode = empLinkedLists[id].findById(id);
if (heroNode!=null){
System.out.println("检索到对象"+heroNode.toString());
}else {
System.out.println("没有检索到对象");
}
}
}
MainTest
package com.pl.arithmetic.hash;
import com.pl.arithmetic.dto.HeroNode;
/**
* <p>
*
* @Description: TODO
* </p>
* @ClassName MainTest
* @Author pl
* @Date 2020/9/20
* @Version V1.0.0
*/
public class MainTest {
public static void main(String[] args) {
HashTableTest hashTableTest = new HashTableTest(7);
hashTableTest.add(new HeroNode(1,"xxx","yyyy"));
hashTableTest.add(new HeroNode(5,"www","qqq"));
hashTableTest.add(new HeroNode(7,"777","rrr"));
hashTableTest.add(new HeroNode(8,"zzz","vvv"));
hashTableTest.list();
System.out.println("查询");
hashTableTest.getById(1);
}
}
100629125.png
网友评论