Java数据结构与算法(散列表)

前言

散列表是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。而key的冲突主要通过链表的方式来处理，后期链表过长情况下可以通过红黑树来优化查询效率。

实现原理

1. 散列函数（Hash Function）： 散列函数用于将输入的键转换为表中的索引。理想的散列函数应当将键均匀地分布到表的各个位置，以减少冲突。散列函数的一些常见实现包括将键的ASCII值进行某种数学运算或使用更复杂的算法，如SHA-256。

2. 冲突（Collision）： 当两个不同的键通过散列函数映射到相同的位置时，就会发生冲突。处理冲突是散列表实现中的一个关键问题。

动画过程

Open Hashing Visualization

具体代码实现

import java.util.LinkedList;

public class HashTable<K, V> {
    // Node class to store key-value pairs
    private 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 table
    private static final int DEFAULT_SIZE = 16;

    // Array of linked lists to store the chains
    private LinkedList<Node<K, V>>[] table;

    // Current size of the hash table
    private 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 key
    private int hash(K key) {
        return Math.abs(key.hashCode() % table.length);
    }

    // Method to insert a key-value pair into the hash table
    public 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 does
        for (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 chain
        table[index].add(new Node<>(key, value));
        size++;
    }

    // Method to retrieve a value by its key
    public V get(K key) {
        int index = hash(key);
        if (table[index] == null) {
            return null;
        }

        // Search for the key in the chain
        for (Node<K, V> node : table[index]) {
            if (node.key.equals(key)) {
                return node.value;
            }
        }

        // If key is not found, return null
        return null;
    }

    // Method to delete a key-value pair from the hash table
    public boolean delete(K key) {
        int index = hash(key);
        if (table[index] == null) {
            return false;
        }

        // Search for the key in the chain and remove it
        for (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 table
    public int size() {
        return size;
    }

    // Method to check if the hash table is empty
    public boolean isEmpty() {
        return size == 0;
    }

    // Main method for testing
    public 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:待定