哈希表
前言
哈希表(Hash Table)也叫做散列表，是根据键值对(Key Value)而直接访问的数据结构。它通过将关键码值Key映射到表的一个位置来直接访问，以此加快查找的速度。这个映射函数叫做散列函数，存放记录的数值叫做散列表。
实现思路
哈希表底层通过数组和链表组成，数组中的每一个值就是链表。
HashMap就是用哈希表实现，当我们使用put(key,value)方法时，哈希表中调用key.hashCode()%size，计算得出的值就是数组的下标，因不同key算出的来下标值可能相同，即使相同不同的key也可用使用链表连接起来，由此组成如下图所示的哈希表。
代码实现
-
节点Node
class Node { /** * 模拟key-value键值对 */ public Integer key; public String value; /** * 下一节点的引用 */ public Node next; public Node(Integer key, String value) { this.key = key; this.value = value; } public Node() { } } -
链表LinkedList
class LinkedList { //头节点 不存放数据 private Node head; public LinkedList() { //初始化头节点 this.head = new Node(); } /** * 添加数据,key值必须唯一,否则对value值进行覆盖 * @param key 键 * @param value 值 */ public void add(int key,String value) { Node node = new Node(key, value); Node temp = head; while (temp.next != null) { //对value值进行覆盖 if (temp.next.key == key) { temp.next.value = value; return; } //指针后移 temp = temp.next; } //没有重复key值 向链表末尾添加节点 temp.next = node; } public boolean delete(int key) { if (isEmpty()) { System.out.println("链表为空...."); return false; } Node temp = head; while (temp.next != null) { //找到对应key值 if (temp.next.key == key) { //删除key所对应节点 temp.next = temp.next.next; return true; } temp = temp.next; } return false; } public void list(int num) { if (isEmpty()) { System.out.printf("链表[%d]为空,无法展示数据....\n",(num+1)); return; } Node temp = head.next; System.out.printf("链表[%d] -> ",(num+1)); while (temp != null) { System.out.printf("{key:%d,value:%s} -> ",temp.key,temp.value); temp = temp.next; } System.out.print("NULL\n"); } public String getValue(int key) { if (isEmpty()) { System.out.println("链表为空,无法获取数据...."); return null; } Node temp = head.next; while (temp != null) { if (temp.key == key) { return temp.value; } temp = temp.next; } return null; } public boolean isEmpty() { return head.next == null; } } -
哈希表HashTable
class HashTable { private LinkedList[] array; private int size; public HashTable(int size) { this.size = size; array = new LinkedList[size]; //为每个链表进行初始化 for (int i = 0; i < size; i++) { array[i] = new LinkedList(); } } /** * 空参时默认size为8 */ public HashTable() { this.size = 8; array = new LinkedList[size]; //为每个链表进行初始化 for (int i = 0; i < size; i++) { array[i] = new LinkedList(); } } public void add(int key,String value) { if (value == null || value == "") { System.out.println("Value值不能为空"); return; } int index = hashCode(key); array[index].add(key,value); } public void list() { for (int i = 0; i < size; i++) { array[i].list(i); } } public String getValue(int key) { int index = hashCode(key); return array[index].getValue(key); } public void delete(int key) { int index = hashCode(key); array[index].delete(key); } public int hashCode(Integer key) { return key.hashCode() % size; } } -
测试
/** * @Author: 又蠢又笨的懒羊羊程序猿 * @CreateTime: 2021年08月15日 09:51:17 */ public class HashTableDemo { public static void main(String[] args) { //创建哈希表 HashTable hashTable = new HashTable(); //菜单 String select = ""; Scanner scanner = new Scanner(System.in); while (true) { System.out.println("add:添加节点"); System.out.println("list:显示节点"); System.out.println("find:查找节点"); System.out.println("del:删除节点"); System.out.println("exit:退出"); select = scanner.next(); switch (select) { case "add": System.out.println("输入Key:"); int key = scanner.nextInt(); System.out.println("输入Value:"); String value = scanner.next(); hashTable.add(key, value); break; case "list": hashTable.list(); break; case "find": System.out.println("请输入要查找的Key:"); key = scanner.nextInt(); System.out.printf("key-value->{%d:%s}\n",key,hashTable.getValue(key)); break; case "del": System.out.println("请输入要删除的key:"); key = scanner.nextInt(); hashTable.delete(key); break; case "exit": scanner.close(); System.out.println("退出...."); System.exit(0); } } } } //以下是测试结果 add:添加节点 list:显示节点 find:查找节点 del:删除节点 exit:退出 输入选择:add 输入Key: 1 输入Value: Tom add:添加节点 list:显示节点 find:查找节点 del:删除节点 exit:退出 输入选择:add 输入Key: 1 输入Value: Smith add:添加节点 list:显示节点 find:查找节点 del:删除节点 exit:退出 输入选择:list 链表[1]为空,无法展示数据.... 链表[2] -> {key:1,value:Smith} -> NULL //此时第一次添加的节点已经被覆盖 链表[3]为空,无法展示数据.... 链表[4]为空,无法展示数据.... 链表[5]为空,无法展示数据.... 链表[6]为空,无法展示数据.... 链表[7]为空,无法展示数据.... 链表[8]为空,无法展示数据.... add:添加节点 list:显示节点 find:查找节点 del:删除节点 exit:退出 输入选择:add 输入Key: 9 输入Value: TaylorSwift add:添加节点 list:显示节点 find:查找节点 del:删除节点 exit:退出 输入选择:list 链表[1]为空,无法展示数据.... 链表[2] -> {key:1,value:Smith} -> {key:9,value:TaylorSwift} -> NULL 链表[3]为空,无法展示数据.... 链表[4]为空,无法展示数据.... 链表[5]为空,无法展示数据.... 链表[6]为空,无法展示数据.... 链表[7]为空,无法展示数据.... 链表[8]为空,无法展示数据.... add:添加节点 list:显示节点 find:查找节点 del:删除节点 exit:退出 输入选择:find 请输入要查找的Key: 9 key-value->{9:TaylorSwift} //通过key查询value值 add:添加节点 list:显示节点 find:查找节点 del:删除节点 exit:退出 输入选择:del 请输入要删除的key: 1 //通过key删除节点 add:添加节点 list:显示节点 find:查找节点 del:删除节点 exit:退出 输入选择:list 链表[1]为空,无法展示数据.... 链表[2] -> {key:9,value:TaylorSwift} -> NULL 链表[3]为空,无法展示数据.... 链表[4]为空,无法展示数据.... 链表[5]为空,无法展示数据.... 链表[6]为空,无法展示数据.... 链表[7]为空,无法展示数据.... 链表[8]为空,无法展示数据.... add:添加节点 list:显示节点 find:查找节点 del:删除节点 exit:退出 输入选择:exit 退出.... 进程已结束，退出代码为 0
以上。
如有不足或者错误欢迎评论区指正。