06-哈希表算法

实现一个哈希表算法，并分析其时间复杂度和空间复杂度。

public class Hashing<K, V> {
    private static final int DEFAULT_CAPACITY = 16;
    private static final float LOAD_FACTOR = 0.75f;
    private Entry<K, V>[] table;
    private int size;
 
    public Hashing() {
        table = new Entry[DEFAULT_CAPACITY];
    }
 
    public void put(K key, V value) {
        if (key == null) {
            throw new IllegalArgumentException("Key cannot be null");
        }
        int index = hash(key);
        Entry<K, V> entry = table[index];
        while (entry != null) {
            if (entry.getKey().equals(key)) {
                entry.setValue(value);
                return;
            }
            entry = entry.getNext();
        }
        Entry<K, V> newEntry = new Entry<>(key, value, table[index]);
        table[index] = newEntry;
        size++;
        if (size >= LOAD_FACTOR * table.length) {
            resize();
        }
    }
 
    public V get(K key) {
        if (key == null) {
            throw new IllegalArgumentException("Key cannot be null");
        }
        int index = hash(key);
        Entry<K, V> entry = table[index];
        while (entry != null) {
            if (entry.getKey().equals(key)) {
                return entry.getValue();
            }
            entry = entry.getNext();
        }
        return null;
    }
 
    public void remove(K key) {
        if (key == null) {
            throw new IllegalArgumentException("Key cannot be null");
        }
        int index = hash(key);
        Entry<K, V> prev = null;
        Entry<K, V> entry = table[index];
        while (entry != null) {
            if (entry.getKey().equals(key)) {
                if (prev == null) {
                    table[index] = entry.getNext();
                } else {
                    prev.setNext(entry.getNext());
                }
                size--;
                return;
            }
            prev = entry;
            entry = entry.getNext();
        }
    }
 
    public int size() {
        return size;
    }
 
    private int hash(K key) {
        return Math.abs(key.hashCode()) % table.length;
    }
 
    private void resize() {
        Entry<K, V>[] oldTable = table;
        table = new Entry[table.length * 2];
        size = 0;
        for (Entry<K, V> entry : oldTable) {
            while (entry != null) {
                put(entry.getKey(), entry.getValue());
                entry = entry.getNext();
            }
        }
    }
 
    private static class Entry<K, V> {
        private K key;
        private V value;
        private Entry<K, V> next;
 
        private Entry(K key, V value, Entry<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
 
        public K getKey() {
            return key;
        }
 
        public V getValue() {
            return value;
        }
 
        public void setValue(V value) {
            this.value = value;
        }
 
        public Entry<K, V> getNext() {
            return next;
        }
 
        public void setNext(Entry<K, V> next) {
            this.next = next;
        }
    }
}

哈希表是一种数据结构，它使用哈希函数将键映射到存储桶中。在哈希表中查找一个键大多数情况下具有常数时间复杂度O(1)的效率，因此它被广泛应用于需要高效查找的场合。

哈希表主要由两个部分组成：哈希函数和散列表。

• 哈希函数：将输入的键转换为索引或哈希值。
• 散列表：存储键值对，并根据哈希函数返回的索引将它们放入不同的存储桶中。

哈希表的时间复杂度取决于哈希函数的选择和是否出现哈希冲突。

• 均匀哈希函数：如果哈希函数返回的散列值均匀分布，则平均情况下每个操作都需要O(1)时间。因此，在最理想的情况下，哈希表的插入、删除和查找操作的时间复杂度均为O(1)。
• 哈希冲突：当多个键具有相同的哈希值时，会产生哈希冲突。这种情况下，哈希表需要解决冲突。一种常用的解决方法是链地址法，即将具有相同哈希值的键存储在同一个链表中。在这种情况下，查找、插入和删除操作的平均时间复杂度变为O(1+α)，其中α是散列表中填充因子，表示存储桶中已经使用的空间与总空间的比例。
• 最坏情况：最坏情况下，所有键具有相同的哈希值，哈希表退化成一个链表。这种情况下，所有操作的时间复杂度都为O(n)，其中n是键值对的数量。

哈希表的空间复杂度取决于存储桶的数量和键值对的数量。

• 存储桶：哈希表的空间复杂度与存储桶的数量成正比。如果存储桶的数量越多，则散列冲突的可能性就越小，但空间开销也会增加。
• 键值对：哈希表的空间复杂度与键值对的数量成正比。如果键值对的数量越多，则需要更多的存储桶来避免散列冲突，因此空间开销也会增加。

综上所述，哈希表的时间复杂度取决于哈希函数的选择和是否出现哈希冲突，而空间复杂度则取决于存储桶的数量和键值对的数量。