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);
}
}