05-哈希表

2021-09-20  本文已影响0人  唔哒喂

根据尚硅谷韩顺平老师教程。
根据学习可知哈希表的结构大致如下


HashTab.png

完整代码见底部

HashTab

可以看出在哈希表中用数组方式存储了(size个)链表的头结点。

class HashTab{
    int size;
    Node[] nodes;
}

每一个node存储在哪条链表中的选择是根据 散列函数:num % size;
size是创建HashTab是确定的数据。而num则来自于node中的属性。
根据所学教程,num来自于node中的id。

public int hashIndex(int id){
        return id % size;
    }

由此在插入node时
可知 node 应插入哪一条链表

public void insertNode(Node node){
        if (node == null)
            return;
        int i = hashIndex(node.getId());
        nodes[i].insertNode(node);
    }

在已知id的情况下获取信息时
可知当前id应存在于哪一条链表,遍历比对即可获取信息。

public Node findNode(int id){
        int i = hashIndex(id);
        return nodes[i].findNode(id);
    }

Node

根据所学所创建的Node中包含
Id,name,next指针

class Node{
    Node next;
    int id;
    String name;
}

在插入数据时,从应插入数据的链表的头结点开始,开始遍历,出现null即在此条链表中插入数据。

public void insertNode(Node node) {
        Node p = this;
        while (p.next != null)
            p = p.next;
        p.next = node;
    }

获取数据类似

public Node findNode(int id) {
        if (this.next == null)
            return null;
        Node p = this.next;
        while (p != null){
            if (p.getId() == id)
                return p;
            p = p.next;
        }
        return null;
    }

完整代码

HashTab

class HashTab{

    int size;
    Node[] nodes;


    public HashTab(int size) {
        this.size = size;
        this.nodes = new Node[size];
//        创建头结点。
        for (int i = 0; i < size; i++) {
            nodes[i] = new Node();
        }

    }
//  插入node
    public void insertNode(Node node){
        if (node == null)
            return;
        int i = hashIndex(node.getId());
        nodes[i].insertNode(node);
    }

//  散列函数
    public int hashIndex(int id){
        return id % size;
    }
//    显示整个表信息
    public void listHashTab(){
        for (int i = 0; i < size; i++) {
            nodes[i].listNodeList(i);
        }
    }
    // 查询node
    public Node findNode(int id){
        int i = hashIndex(id);
        return nodes[i].findNode(id);
    }
}

Node

class Node{
    Node next;
    int id;
    String name;

    public Node(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public Node() {
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{"+"id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    public void insertNode(Node node) {
        Node p = this;
        while (p.next != null)
            p = p.next;
        p.next = node;
    }
//    显示整个表信息
    public void listNodeList(int i) {
        System.out.print(i);
        Node p = this.next;
        while (p != null){
            System.out.print("--->");
            System.out.print(p);
            p = p.next;
        }
        System.out.println();
    }

    public Node findNode(int id) {
        if (this.next == null)
            return null;
        Node p = this.next;
        while (p != null){
            if (p.getId() == id)
                return p;
            p = p.next;
        }
        return null;
    }
}

测试

public class HashReview {
    public static void main(String[] args) {

//        新建hash表 指定hash表的大小
        HashTab hashTab = new HashTab(5);
//        手动新建几个需要插入的节点。
        Node ss = new Node(1, "ss");
        Node cc = new Node(2, "cc");
        Node zz = new Node(3, "zz");
        Node qq = new Node(8, "qq");
        hashTab.insertNode(ss);
        hashTab.insertNode(cc);
        hashTab.insertNode(zz);
        hashTab.insertNode(qq);

//        输出hash表
        hashTab.listHashTab();
        System.out.println(hashTab.findNode(8));

    }
}

测试时输出结果

Test.jpg
上一篇 下一篇

猜你喜欢

热点阅读