13、数据结构与算法 - 实战：哈希表

1、概念

哈希表，也称为散列表（Hash table），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数（也称为散列函数），存放记录的数组叫做哈希表（也称为散列表）。

2、图解

说白了，哈希表就是数组+链表的结构，定义一个数组，数组每一个元素都是一个链表，链表包含若干个结点。

3、代码实现

3.1 定义结点类

package cn.klb.datastructures.hashtable;

/**
 * @author DDKK.COM 弟弟快看，程序员编程资料站
 * @Description: 链表的结点类
 * @Date: Create in 2023/4/10 13:14
 * @Modified By:
 */
public class Node {
   
     
    public int id;
    public String data;
    public Node next = null;

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

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

3.2 定义链表类

package cn.klb.datastructures.hashtable;

/**
 * @author DDKK.COM 弟弟快看，程序员编程资料站
 * @Description: 链表类
 * @Date: Create in 2023/4/10 13:15
 * @Modified By:
 */
public class LinkedList {
   
     
    private Node head = null;  // 链表的头结点

    /**
     * 链表添加结点
     *
     * @param node
     */
    public void add(Node node) {
   
     
        if (head == null) {
   
     
            head = node;
        } else {
   
     
            Node temp = head;
            while (temp.next != null) {
   
     
                temp = temp.next;
            }
            temp.next = node;
        }
    }

    /**
     * 根据结点id删除结点
     *
     * @param id
     */
    public void remove(int id) {
   
     
        if (head == null) {
   
     
            System.out.println("id =" + id + " 不存在，删除失败！");
            return;
        } else {
   
     
            if (head.id == id) {
   
     
                head = head.next;
            } else {
   
     
                Node temp = head;
                while (true) {
   
     
                    if (temp.next == null) {
   
     
                        System.out.println("找不到id为" + id + "的结点，删除失败！");
                        break;
                    } else if (temp.next.id == id) {
   
     
                        temp.next = temp.next.next;
                        break;
                    }
                    temp = temp.next;
                }
            }
        }
    }

    @Override
    public String toString() {
   
     
        String str = "";
        str += "LinkedList{";
        Node temp = head;
        while (temp != null) {
   
     
            str += temp;
            if (temp.next != null) {
   
     
                str += ",";
            }
            temp = temp.next;
        }
        str += '}';
        return str;
    }
}

3.3 定义哈希表类

package cn.klb.datastructures.hashtable;

import java.util.Arrays;

/**
 * @author DDKK.COM 弟弟快看，程序员编程资料站
 * @Description: 哈希表类
 * @Date: Create in 2023/4/10 13:52
 * @Modified By:
 */
public class HashTable {
   
     
    private LinkedList[] linkedListArray;
    private int size;

    public HashTable(int size) {
   
     
        this.size = size;
        linkedListArray = new LinkedList[size];
        for (int i = 0; i < size; i++) {
   
     
            linkedListArray[i] = new LinkedList();
        }
    }

    /**
     * 添加结点到哈希表
     *
     * @param node
     */
    public void add(Node node) {
   
     
        int hashCode = hashFun(node.id);    // 获取该id对应计算得到的哈希值
        linkedListArray[hashCode].add(node);
    }

    /**
     * 根据id删除哈希表的元素
     *
     * @param id
     */
    public void remove(int id) {
   
     
        int hashCode = hashFun(id);    // 获取该id对应计算得到的哈希值
        linkedListArray[hashCode].remove(id);
    }

    @Override
    public String toString() {
   
     
        String str = "";
        str += "HashTable{";

        for (int i = 0; i < size; i++) {
   
     
            str += linkedListArray[i].toString();
            if (i != size - 1) {
   
     
                str += ",";
            }
        }

        str += '}';
        return str;
    }

    /**
     * 计算哈希值
     *
     * @param id
     * @return
     */
    private int hashFun(int id) {
   
     
        return id % size;
    }
}

4、测试类

package cn.klb.test.datastructurestest;

import cn.klb.datastructures.hashtable.HashTable;
import cn.klb.datastructures.hashtable.LinkedList;
import cn.klb.datastructures.hashtable.Node;
import org.junit.Test;

/**
 * @author DDKK.COM 弟弟快看，程序员编程资料站
 * @Description:
 * @Date: Create in 2023/4/10 14:01
 * @Modified By:
 */
public class testHashTable {
   
     
    @Test
    public void testHashTable(){
   
     
        HashTable hashTable = new HashTable(5);
        hashTable.add(new Node(1, "石鸣鸣"));
        hashTable.add(new Node(2, "石通鸣"));
        hashTable.add(new Node(3, "石围都"));
        System.out.println(hashTable);
        hashTable.remove(4);
        System.out.println(hashTable);
        hashTable.remove(2);
        System.out.println(hashTable);
    }
}