前言
散列表是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說,它通過把關鍵碼值映射到表中一個位置來訪問記錄,以加快查找的速度。而key的沖突主要通過鏈表的方式來處理,后期鏈表過長情況下可以通過紅黑樹來優化查詢效率。
實現原理
-
散列函數(Hash Function): 散列函數用于將輸入的鍵轉換為表中的索引。理想的散列函數應當將鍵均勻地分布到表的各個位置,以減少沖突。散列函數的一些常見實現包括將鍵的ASCII值進行某種數學運算或使用更復雜的算法,如SHA-256。
-
沖突(Collision): 當兩個不同的鍵通過散列函數映射到相同的位置時,就會發生沖突。處理沖突是散列表實現中的一個關鍵問題。
動畫過程
Open Hashing Visualization
具體代碼實現
import java.util.LinkedList;public class HashTable<K, V> {// Node class to store key-value pairsprivate static class Node<K, V> {K key;V value;Node(K key, V value) {this.key = key;this.value = value;}}// Default size of the hash tableprivate static final int DEFAULT_SIZE = 16;// Array of linked lists to store the chainsprivate LinkedList<Node<K, V>>[] table;// Current size of the hash tableprivate int size;// Constructor to initialize the hash table with default size@SuppressWarnings("unchecked")public HashTable() {table = new LinkedList[DEFAULT_SIZE];size = 0;}// Hash function to compute index for a keyprivate int hash(K key) {return Math.abs(key.hashCode() % table.length);}// Method to insert a key-value pair into the hash tablepublic void insert(K key, V value) {int index = hash(key);if (table[index] == null) {table[index] = new LinkedList<>();}// Check if the key already exists, update value if it doesfor (Node<K, V> node : table[index]) {if (node.key.equals(key)) {node.value = value;return;}}// If key does not exist, add a new node to the chaintable[index].add(new Node<>(key, value));size++;}// Method to retrieve a value by its keypublic V get(K key) {int index = hash(key);if (table[index] == null) {return null;}// Search for the key in the chainfor (Node<K, V> node : table[index]) {if (node.key.equals(key)) {return node.value;}}// If key is not found, return nullreturn null;}// Method to delete a key-value pair from the hash tablepublic boolean delete(K key) {int index = hash(key);if (table[index] == null) {return false;}// Search for the key in the chain and remove itfor (Node<K, V> node : table[index]) {if (node.key.equals(key)) {table[index].remove(node);size--;return true;}}return false;}// Method to get the current size of the hash tablepublic int size() {return size;}// Method to check if the hash table is emptypublic boolean isEmpty() {return size == 0;}// Main method for testingpublic static void main(String[] args) {HashTable<String, Integer> hashTable = new HashTable<>();hashTable.insert("apple", 1);hashTable.insert("banana", 2);hashTable.insert("cherry", 3);System.out.println("Value for 'apple': " + hashTable.get("apple"));System.out.println("Value for 'banana': " + hashTable.get("banana"));System.out.println("Value for 'cherry': " + hashTable.get("cherry"));hashTable.delete("banana");System.out.println("Value for 'banana' after deletion: " + hashTable.get("banana"));System.out.println("Current size: " + hashTable.size());}
}
QA:待定