用哈希表实现简单的缓存层-白红宇

用哈希表实现简单的缓存层

阅读量：2339 次

发布时间：2019-05-10

本文共 7353 字，大约阅读时间需要 24 分钟。

用哈希表实现简单的缓存层

问题：

有一个公司，当有新的员工来报道时，要求所有的员工信息录入电脑（id，性别，年龄，住址。。），当输入员工的id时，要求查到该员工的所有信息

要求：不使用数据库，尽量节省内存，速度越快越好------使用哈希表

问题分析

采用数组加链表的方式实现哈希表

建造三各类，Employ{int id,String name},EmployLinkedList{Employ head,增删改除的相关方法}，HashTab{链表型数组，数组规模size，计算hash值的散列函数，操纵链表进行增删改除的相关方法}，

代码实现：

Employ类

public class Employ {
       public int id;    public String name;    public Employ next;    //作为单向链表,必备包含下一个节点的索引信息    public Employ(int id, String name) {
           this.id = id;        this.name = name;    }    public Employ() {
       }    @Override    public String toString() {
           return "Employ{" +                "id=" + id +                ", name='" + name + '\'' +                '}';    }}

EmployLinkedList链表类

public class EmployLinkedList {
       //没有头结点    private Employ head ;    public boolean isEmpty(){
           if (head == null){
               return true;        }else{
               return false;        }    }    //增加元素    public void add(Employ employ){
           if (isEmpty()){
               head = employ;            return;            //即使是没有返回值的语句,也是可以用return增加一个出口            //然后就没有必要再设置else了        }        //不为空,就要找到尾结点,在尾结点处添加        Employ curBoy = head;        while (true) {
               if (curBoy.next == null) {
                   break;            }            curBoy = curBoy.next;        }        curBoy.next = employ;    }    //遍历元素    public void list(){
           //遍历元素,看看是否为空        if (isEmpty()){
               System.out.println("链表为空");            return;        }        Employ curBoy = head;        while (true) {
               System.out.print("id为:" + curBoy.id + "name为:" + curBoy.name + ">>>");            if (curBoy.next == null) {
                   break;            }            curBoy = curBoy.next;        }        System.out.println();    }    //根据id直接查找出对应的雇员    public Employ search(int id){
           //要用到索引,先判定是否为空        if (isEmpty()){
               //System.out.println("链表为空,所查元素不存在");            return head;        }        Employ temp = head;        while (true) {
               //没有固定的序号,明确的次数,不用for            if (temp.id == id) {
                   return temp;            }            if (temp.next == null) {
                   temp = null;                return temp;            }            temp = temp.next;        }        //然后仅仅只有hashtab可以调用,在hashtab中说明相关的方法    }    //删除链表节点    public void delete (int id){
           //删除结点判定是否为空        if (isEmpty()){
               System.out.println("链表为空");        }        //如果不为空,查找待删除的元素        if(search(id) == null){
               System.out.println("所要删除元素不存在");        }else{
               Employ temp = head;            boolean isFLag = false;            while (true){
                   //没有固定的序号,明确的次数,不用for                if (temp.next == null){
                       break;                }                if (temp.next.id == id){
                       isFLag =true;                    break;                }                temp = temp.next;            }            if (isFLag){
                   temp.next = temp.next.next;                System.out.println("成功删除");            }else{
                   if (head.id == id){
                       head = null;                    System.out.println("成功删除");                }else{
                       System.out.println("不存在");                }            }        }    }}

HashTab类以及测试方法

import java.util.Scanner;public class HashTab {
       public static void main(String[] args) {
           HashTab hashTab = new HashTab(10);        //写一个简单的菜单,提示各种信息        String key = "";        Scanner scan = new  Scanner(System.in);        while(true){
               System.out.println("add:添加雇员");            System.out.println("list:遍历雇员");            System.out.println("search:查找雇员");            System.out.println("delete:删除雇员");            System.out.println("exit:退出");            key = scan.next();            switch (key){
                   case "add":                    System.out.println("please input the name");                    String name = scan.next();                    System.out.println("please input the id");                    int id = scan.nextInt();                    hashTab.add(new Employ(id,name));                    break;                case "list":                    hashTab.list();                    break;                case "search":                    System.out.println("please input the id");                    int id2 = scan.nextInt();                    hashTab.search(id2);                    break;                case "delete":                    System.out.println("please input the id");                    int id3 = scan.nextInt();                    hashTab.delete(id3);                    break;                case "exit":                    scan.close();                    System.exit(0);                default:            }        }    }    //创建hashTab管理多条链表    private EmployLinkedList[] employLinkedListsArray;    private int size;    public HashTab(int size) {
           this.size = size;        employLinkedListsArray = new EmployLinkedList[size];        //这里是开辟了一个空间,但是没有给每一个数组的对象进行赋值,默认值都是null        for (int i = 0 ;i < size;i ++){
               employLinkedListsArray[i] = new EmployLinkedList();        }    }    //添加雇员    public void add(Employ employ){
           int employLinkListArrayNo = hasNun(employ.id);        employLinkedListsArray[employLinkListArrayNo].add(employ);    }    //根据雇员的关键值,就是id获取他的hash数值,从而给他进行对应的添加    private int hasNun(int id){
           //取模法获取其对应的hash值        return id % size;    }    //遍历    public void list(){
           for(int i = 0; i < size;i ++){
               System.out.print("第" + i + " 条链表");            employLinkedListsArray[i].list();        }    }    //根据id查找雇员    public void search(int id){
           int emmloyLinkedListNo = hasNun(id);        if (employLinkedListsArray[emmloyLinkedListNo].search(id) == null){
               System.out.println("所查元素不存在");        }else{
               System.out.println("所查元素为:" + employLinkedListsArray[emmloyLinkedListNo].search(id) );        }    }    //删除对应的元素    public void delete(int id){
           int emmloyLinkedListNo = hasNun(id);        employLinkedListsArray[emmloyLinkedListNo].delete(id);    }}

分析与总结：

虽然链表有相关的增删改除方法，但是只有hashTab能够操作数据，所以HashTab要有能够对数据经进行增删该处的方法

就算是没有返回数据类型的参数，也可以return来结束当前的方法，美有必要非得else到方法的末尾，才能结束方法。如下面的两种方法：
用return返回结束程序

public void list(){
           //遍历元素,看看是否为空        if (isEmpty()){
               System.out.println("链表为空");            return;        }        Employ curBoy = head;        while (true) {
               System.out.print("id为:" + curBoy.id + "name为:" + curBoy.name + ">>>");            if (curBoy.next == null) {
                   break;            }            curBoy = curBoy.next;        }        System.out.println();    }

用else嵌套，运行到程序的尽头

public void list() {
           //遍历元素,看看是否为空        if (isEmpty()) {
               System.out.println("链表为空");            return;        } else {
               Employ curBoy = head;            while (true) {
                   System.out.print("id为:" + curBoy.id + "name为:" + curBoy.name + ">>>");                if (curBoy.next == null) {
                       break;                }                curBoy = curBoy.next;            }            System.out.println();        }    }

转载地址：http://dqgpb.baihongyu.com/

你可能感兴趣的文章

Java内存 happens-before原则