美文网首页
05-哈希表

05-哈希表

作者: 唔哒喂 | 来源:发表于2021-09-20 11:39 被阅读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

    相关文章

      网友评论

          本文标题:05-哈希表

          本文链接:https://www.haomeiwen.com/subject/yxbmgltx.html