【数据结构】哈希表原理及其实现

一、哈希表介绍

散列表（Hash table也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。

通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表

二、代码实现

package work.rexhao.hashtab;

/**
 * 哈希表
 *
 * @author 王铭颢
 * @Date 2022/7/4 23:12
 */
public class HashTabDemo {
   
    public static void main(String[] args) {
   
        hashTab ht = new hashTab();
        ht.add(new stu(10,"wmh","123123"));
        ht.add(new stu(20,"wc","123123"));
        System.out.println(ht.find(10));
        System.out.println(ht.find(20));
        System.out.println(ht.find(30));
    }
}

/**
 * student的实体类
 */
class stu {
   
    private Integer no;
    private String name;
    private String phone;
    public stu next;

    stu(Integer no, String name, String phone) {
   
        this.no = no;
        this.name = name;
        this.phone = phone;
    }

    @Override
    public String toString() {
   
        return "stu{" + "no=" + no + ", name='" + name + '\'' + ", phone='" + phone + '\'' + '}';
    }

    public Integer getNo() {
   
        return no;
    }


    public String getName() {
   
        return name;
    }

    public String getPhone() {
   
        return phone;
    }

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


    public void setNo(Integer no) {
   
        this.no = no;
    }

    public void setPhone(String phone) {
   
        this.phone = phone;
    }
}

/**
 * hashTab
 */
class hashTab {
   
    // 链表节点头部分
    stu[] head = new stu[10];

    /**
     * 添加节点的方法(尾插法) 将最后的next域指向新的node
     */
    public void add(stu s) {
   
        if (s == null) {
   
            return;
        }
        // 没有头指针，第一次添加需要直接放进head里面
        if(head[s.getNo() % 10] == null){
   
            head[s.getNo() % 10] = s;
            return;
        }
        // 需要一个辅助变量
        stu temp = head[s.getNo() % 10];
        // 遍历单链表
        while (temp.next != null) {
   
            temp = temp.next;
        }
        // 退出循环时，temp指向最后
        temp.next = s;
    }

    /**
     * 查找
     */
    public stu find(int no) {
   
        // 判空
        if (head[no % 10] == null) {
   
            return null;
        }
        // 遍历
        stu temp = head[no % 10];
        while (temp != null) {
   
            if (temp.getNo() == no) {
   
                break;
            }
            temp = temp.next;
        }
        return temp;
    }
}