0
0

分享

【校招VIP】Java数据结构-哈希表的实现(hash)

01月14日 收藏 0 评论 0 java开发

【校招VIP】Java数据结构-哈希表的实现(hash)

转载声明：文章来源https://blog.csdn.net/JOElib/article/details/123757897

一、哈希表的阐述:

哈希表,其实是单向链表和数组的结合体,换一种说法呢,就是有一个单向链表数组,里面的每一个元素都是一个单向链表,直观来看,哈希表似乎很难,实际上,哈希表的简单程度与我们的单向链表的难度大抵一致,都非常的简单。

但是,哈希表也引入了新的代码思想,即底层思想和表层思想,具体的解释是,在底层的单向链表中书写各种方法,然后再在哈希表中书写这些方法,用哈希表的方法去调用单向链表的底层方法,这就是哈希表所能带给我们的新事物,这个应用在后面的二叉树,线索化二叉树中经常可以用到,所以非常的重要,一定要掌握!

二、哈希表的创建思路:

1.创建节点类

  • 节点类中应该与单向链表一样有data域和next域
  • 在节点类中提供对应的构造方法,还有重写toString方法,便于输出

2.创建单向链表类

  • 单向链表类应该有head属性,由于哈希表中不需要头节点,所以head被赋值为第一个节点的内存地址
  • 创建增删插查遍历的底层方法

3.创建哈希表类

  • 哈希表类中应该有单向链表数组属性还有数组长度属性
  • 创建对应的构造方法,能指定哈希表的底层数组长度

三、哈希表的代码实现与分析
1.创建节点类 

public class EmpNode {
 
    public int no;
    public String name;
    public EmpNode next;
 
    public EmpNode(int no,String name) {
        this.no = no;
        this.name = name;
    }
 
    public EmpNode() {
 
    }
 
    public String toString() {
        return "该雇员的no[" + no + "] 名字是[" + name + "]";
    }
}

 代码分析:

  • 构造方法的创建不能指定其next域,应该有手动设置
  • toString方法大家可以随便发挥.博主为了好看才这样返回的

2.创建单向链表类

public class EmpLinedList {
    private EmpNode head;
}

代码分析:
head指向的是第一个节点的,不是头节点,哈希表底层的单向链表是无头节点的

3.在单向链表中创建添加节点的方法: 

public void add(EmpNode node) {
        if(head == null) {
            head = node;
            return;
        }
        var cur = head;
        while(cur.next != null)
            cur = cur.next;
        cur.next = node;
    }

代码分析:

  • 首先,校验意识,先判断是否有第一个节点,如果是,则直接将新节点赋值给head
  • 建立一个辅助引用,避免直接去触碰第一个节点,以防底层链表丢失,若能走到这一步,说明head!=null,可以将head给辅助引用
  • 通过循环,就可以找到最后一个节点了,找到之后,直接赋值即可(next不为空,说明不是最后一个节点,需要继续循环跳往下一个节点)

4.在单向链表中创建遍历链表的方法:

public void print(int num) {
        if(head == null) {
            System.out.println("第" + (num + 1) + "个链表为空");
            return;
        }
        var cur = head;
        System.out.print("第" + (num + 1) + "个链表为:");
        while(cur != null){
            System.out.print(cur + "  ");
            cur = cur.next;
        }
        System.out.println();
    }

代码分析:

  • 遍历链表的时候,我们需要先判断一下单向链表是否为空,如果为空,则直接退出,并输出你想要的一句话(校验意识)
  • 建立一个辅助引用,并赋值为head,通过cur!=null,说明当前节点仍然存在,即输出
  • 如果cur=null,说明节点已经遍历完了,应该退出循环,结束遍历
  • 最后的println方法留作悬念,用于哈希表调用时的优化输出

5.在单向链表中创建查找节点的方法:

public boolean findByNo(int no) {
        if(head == null) {
            return false;
        }
        var cur = head;
        while(cur != null && cur.no != no){
            cur = cur.next;
        }
        return cur != null;
    }

 代码分析:

  • 如果第一个节点为空,说明单向链表为空,直接退出,返回false
  • 注意:true表示找得到,false表示找不到
  • cur != null 为了防止空指针异常,而且必须写在前面,充分利用短路与的作用
  • 只要no匹配不上和cur不为空,就进入循环,往后一个节点去跳
  • 当循环结束的时候,有两种情况

 cur为空而出来的,所以最后的结果是cur为空
 找得到出来的,所以最后的结果是cur不为空

  • 根据cur是否为空就可以判断是否找得到

6.在单向链表中创建删除节点的方法:

public boolean del(EmpNode node) {
        if(head == null) {
            return false;
        }else if(head.next == null) {
            if(head.no == node.no) {
                head = null;
                return true;
            }else {
                return false;
            }
        }else {
            if(head.no == node.no) {
                head = head.next;
                return true;
            }
        }
        var cur = head;
        boolean loop = false;
        while (cur.next != null){
            if(cur.next.no == node.no) {
                loop = true;
                break;
            }
            cur = cur.next;
        }
        if(loop) {
            cur.next = cur.next.next;
            return true;
        }
        return false;
    }

代码分析:

  • 开始解释之前,先阐述几种可能出现的情况

是否第一个节点为空
是否只有一个节点,且该节点是否为我们想要删除的节点
是否含有多个节点,且第一个节点是否为我们想要删除的节点
是否含有多个节点,且第一个节点不是我们想要删除的节点

  • 根据这些情况,可列出上述ifelse语句,特别注意的是head = head.next,表示将第一个节点丢掉
  • 下面就是普通单向链表的删除操作,删除节点时,必须要找到待删除节点的上一个节点,因为第一个节点比较特殊,所以要特殊处理

7.在单向链表中创建插入节点的方法:

public void insert(EmpNode node) {
        if(head == null) {
            head = node;
            return;
        }else {
            if(node.no < head.no) {
                node.next = head;
                head = node;
                return;
            }
        }
        boolean loop = false;
        var cur = head;
        while (cur.next != null) {
            if(cur.next.no > node.no) {
                loop = true;
                break;
            }
            cur = cur.next;
        }
        if(loop) {
            node.next = cur.next;
            cur.next = node;
        }
    }

代码分析:

  • 我们先判断一下第一个节点是否为空,若为空,则直接赋值结课
  • 我们需要判断一下特殊情况,就是插入的节点位于第一个节点之前(单向链表一般都是要找待插入节点的上一个节点,第一个节点没有上一个节点,所以要特殊化处理)

    如果满足上述node.no < head.no说明确实要插入第一个节点之前,所以第一步:node.next = head将新节点指向原来的第一个节点,第二步:head = node将node变成第一个节点,原来的第一个节点就会变成第二个节点

  • 接下来按传统的单向链表删除即可,若看不懂可移步至单向链表

底层代码写完了,接下来就是表层了 

8.创建一个哈希表类

public class HashTab {
    public EmpLinedList[] empLinedLists;
    public int size;
 
    public HashTab() {
 
    }
    public HashTab(int size) {
        this.size = size;
        empLinedLists = new EmpLinedList[size];
        for (int i = 0; i < size; i++) {
            empLinedLists[i] = new EmpLinedList();
        }
    }
}

代码分析:

  • 因为哈希表是一个链表数组,所以要有链表数组的属性,还有该数组的大小
  • 需要创建一个有参构造,用于初始化该单向链表数组的大小,即哈希表的大小

     特别特别特别注意的是:要给数组的每一个元素都初始化一个单向链表,否则空指针异常

9.创建一个哈希函数(离散函数)!!!!非常重要

private int hash(int no) {
        return no % size;
    }

代码分析:

  • 该离散函数会根据传进来的no值,通过取模的方式算出其对应的哈希值,即对应的数组下标,让他找到其对应的单向链表

10.创建各种方法,调用底层方法

public void add(EmpNode node) {
        var index = hash(node.no);
        empLinedLists[index].add(node);
    }
    public void print() {
        for (int i = 0; i < size; i++) {
            empLinedLists[i].print(i);
        }
    }
 
    public boolean findByNo(int no) {
        var index = hash(no);
        return empLinedLists[index].findByNo(no);
    }
 
    public boolean del(EmpNode node) {
        var index = hash(node.no);
        return empLinedLists[index].del(node);
    }
 
    public void insert(EmpNode node) {
        var index = hash(node.no);
        empLinedLists[index].insert(node);
    }

代码分析:

这里调用没什么技术含量,主要关注的是对哈希函数(离散函数) 的调用,只有调用了该哈希函数,对应的节点才能找到属于他的单向链表,否则数组下标越界异常或者出现其他运行错误与我们想要的结果不符

完整代码

package datastructure.chapter04.hashtable;
 
/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: asus
 * Date: 2022-03-20
 * Time: 17:03
 */
public class HashTab {
    public EmpLinedList[] empLinedLists;
    public int size;
 
    public HashTab() {
 
    }
 
    public HashTab(int size) {
        this.size = size;
        empLinedLists = new EmpLinedList[size];
        for (int i = 0; i < size; i++) {
            empLinedLists[i] = new EmpLinedList();
        }
    }
 
    public void add(EmpNode node) {
        var index = hash(node.no);
        empLinedLists[index].add(node);
    }
 
    private int hash(int no) {
        return no % size;
    }
 
    public void print() {
        for (int i = 0; i < size; i++) {
            empLinedLists[i].print(i);
        }
    }
 
    public boolean findByNo(int no) {
        var index = hash(no);
        return empLinedLists[index].findByNo(no);
    }
 
    public boolean del(EmpNode node) {
        var index = hash(node.no);
        return empLinedLists[index].del(node);
    }
 
    public void insert(EmpNode node) {
        var index = hash(node.no);
        empLinedLists[index].insert(node);
    }
}
package datastructure.chapter04.hashtable;
 
/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: asus
 * Date: 2022-03-20
 * Time: 17:03
 */
public class EmpLinedList {
    private EmpNode head;
 
    public void add(EmpNode node) {
        if(head == null) {
            head = node;
            return;
        }
        var cur = head;
        while(cur.next != null)
            cur = cur.next;
        cur.next = node;
    }
 
    public void print(int num) {
        if(head == null) {
            System.out.println("第" + (num + 1) + "个链表为空");
            return;
        }
        var cur = head;
        System.out.print("第" + (num + 1) + "个链表为:");
        while(cur != null){
            System.out.print(cur + "  ");
            cur = cur.next;
        }
        System.out.println();
    }
 
    public boolean findByNo(int no) {
        if(head == null) {
            return false;
        }
        var cur = head;
        while(cur != null && cur.no != no){
            cur = cur.next;
        }
        return cur != null;
    }
 
    public boolean del(EmpNode node) {
        if(head == null) {
            return false;
        }else if(head.next == null) {
            if(head.no == node.no) {
                head = null;
                return true;
            }else {
                return false;
            }
        }else {
            if(head.no == node.no) {
                head = head.next;
                return true;
            }
        }
        var cur = head;
        boolean loop = false;
        while (cur.next != null){
            if(cur.next.no == node.no) {
                loop = true;
                break;
            }
            cur = cur.next;
        }
        if(loop) {
            cur.next.next = cur.next;
            return true;
        }
        return false;
    }
 
    public void insert(EmpNode node) {
        if(head == null) {
            head = node;
            return;
        }else {
            if(node.no < head.no) {
                node.next = head;
                head = node;
                return;
            }
        }
        boolean loop = false;
        var cur = head;
        while (cur.next != null) {
            if(cur.next.no > node.no) {
                loop = true;
                break;
            }
            cur = cur.next;
        }
        if(loop) {
            node.next = cur.next;
            cur.next = node;
        }
    }
}
public class EmpNode {
 
    public int no;
    public String name;
    public EmpNode next;
 
    public EmpNode(int no,String name) {
        this.no = no;
        this.name = name;
    }
 
    public EmpNode() {
 
    }
 
    public String toString() {
        return "该雇员的no[" + no + "] 名字是[" + name + "]";
    }
}

四、结论:

哈希表相对来说,在数据结构里还是比较简单的,如果你有单向链表的基础的话,我相信给你一个哈希函数就能把哈希表写出来,这都是后话,我来总结需要注意的几点:

1.底层单向链表对第一个节点的特殊化处理

2.哈希表构造方法初始化单向链表(绝对不要忘)

3.哈希函数的书写与调用

4.底层调用和表层调用的思想

    C 0条回复 评论

    帖子还没人回复快来抢沙发

    热门文章
    【校招VIP】数据库存储过程（全网最全）
    csdn
    86
    【校招VIP】数据库设计的三大范式
    csdn
    85
    课程推荐
    SpingBoot核心注解的分类对比
    938人学习
    ThreadLocal到底用在什么场景？不说要线程池了
    1,072人学习