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