哈希表的基本介绍

忘是亡心i 2021-10-01 09:44 336阅读 0赞

# Hash table 介绍 #

![18721752-ee828b0f6d3e9ab7.png][]

94965625.png

# 练习题 #

![18721752-914c064cdfab9a39.png][]

95031937.png

## notice： ##

hash表的组成：  
数组:维护链表的指针，也就是关键码值 key 可以按照某一规律维护，比如：取模来维护链表的指针。  
链表：用来存值  
取模：  
公式：a mod b = a - b\[a/b\] (\[a/b\]表示整数商)  
取模例子  
简述 商值 取模值

![18721752-9024f3741d2e85a4.png][]

430450453.png

# code #

EmpLinkedList

package com.pl.arithmetic.hash;
 
 import com.pl.arithmetic.dto.HeroNode;
 import lombok.extern.slf4j.Slf4j;
 
 /**
 * 
 *
 * @Description: TODO
 * 
 * @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;
 
 /**
 * 
 *
 * @Description: 哈希表练习
 * 
 * @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;
 
 /**
 * 
 *
 * @Description: TODO
 * 
 * @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);
 }
 }

![18721752-348ffcc3c28faf02.png][]

100629125.png

[18721752-ee828b0f6d3e9ab7.png]: /images/20210918/41bcd19738c64ed0a3c6c3bb3b4cbe24.png
[18721752-914c064cdfab9a39.png]: /images/20210918/3b53f9b59c53495c968630f3c4945a88.png
[18721752-9024f3741d2e85a4.png]: /images/20210918/505ec06f4e11432f9fd34b8b1ee524e8.png
[18721752-348ffcc3c28faf02.png]: /images/20210918/1c2fa5c82e334133830f086afdf09492.png