Java中的哈希表實現

哈希表是一種非常重要的數據結構，它將關鍵字映射為值，實現快速的查找、插入、刪除等操作。在Java中，哈希表也被廣泛地應用於各種場景中。在本文中，我們將從多個方面對Java中的哈希表實現進行詳細的闡述，包括哈希函數、衝突解決、擴容等方面。

一、哈希函數

哈希函數是哈希表的關鍵，它將一個關鍵字映射為一個整型值，作為該關鍵字在哈希表中的下標。一般情況下，哈希函數需要具有以下特點：

1、映射的值應該儘可能的均勻分布在哈希表的各個位置上，避免衝突。

2、計算哈希值的時間複雜度應該儘可能低，以保證哈希表的高效性。

在Java中，可以使用Object類中的hashCode()方法來計算hash值，但是這種方法並不能滿足上述的特點。因此，我們需要自定義哈希函數。通常，一個好的哈希函數應該是通過將關鍵字的各個部分進行合理的運算得出的，如下面這個簡單的例子：

public int hash(String key) {
    int hash = 0;
    for (int i = 0; i < key.length(); i++) {
        hash = 31 * hash + key.charAt(i);
    }
    return hash;
}

這個哈希函數將字元串key中的每個字元轉化為一個整型值，並使用31這個質數作為係數進行加權求和，最終得到一個整型的哈希值。這種哈希函數的好處在於，它可以確保哈希值的均勻分布，且計算時間複雜度較低，是一種比較實用的哈希函數。

二、衝突解決

在實際應用中，由於哈希函數的不完美性，不同的關鍵字可能會映射到同一個下標位置上，這就產生了哈希衝突。如果不進行衝突解決，就會導致數據丟失、查找失敗等問題。

解決哈希衝突的方法有很多種，常見的有鏈地址法和開放地址法兩種。

1、鏈地址法：

這種方法使用鏈表來存儲哈希衝突的關鍵字，每個哈希桶中存儲的是一條鏈表。當發生哈希衝突時，只需要將新的關鍵字插入到對應的鏈表中即可。這種方法簡單易懂，但是在高並發的情況下，可能會導致鏈表長度過長，影響哈希表的查找效率。

public class HashTable {

    private static final int DEFAULT_CAPACITY = 16;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    private LinkedList<Entry>[] buckets;
    private int size;
    private int capacity;
    private float loadFactor;

    public HashTable() {
        this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    public HashTable(int capacity, float loadFactor) {
        this.capacity = capacity;
        this.loadFactor = loadFactor;
        this.buckets = new LinkedList[capacity];
    }

    public void put(K key, V value) {
        int bucketIndex = hash(key) % capacity;
        if (buckets[bucketIndex] == null) {
            buckets[bucketIndex] = new LinkedList();
        }
        for (Entry entry : buckets[bucketIndex]) {
            if (entry.key.equals(key)) {
                entry.value = value;
                return;
            }
        }
        buckets[bucketIndex].add(new Entry(key, value));
        size++;
        resizeIfNeeded();
    }

    public V get(K key) {
        int bucketIndex = hash(key) % capacity;
        if (buckets[bucketIndex] == null) {
            return null;
        }
        for (Entry entry : buckets[bucketIndex]) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
        }
        return null;
    }

    private int hash(K key) {
        return key.hashCode();
    }

    private void resizeIfNeeded() {
        if ((float) size / capacity >= loadFactor) {
            capacity *= 2;
            LinkedList<Entry>[] newBuckets = new LinkedList[capacity];
            for (LinkedList<Entry> bucket : buckets) {
                if (bucket == null) {
                    continue;
                }
                for (Entry entry : bucket) {
                    int bucketIndex = hash(entry.key) % capacity;
                    if (newBuckets[bucketIndex] == null) {
                        newBuckets[bucketIndex] = new LinkedList();
                    }
                    newBuckets[bucketIndex].add(entry);
                }
            }
            this.buckets = newBuckets;
        }
    }

    private static class Entry {

        public final K key;
        public V value;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}

2、開放地址法：

這種方法使用哈希表中的其他位置存儲衝突的數據。當發生哈希衝突時，不斷尋找下一個空閑位置，直到找到能夠存儲數據的位置。這種方法對內存空間的利用率較高，但是需要解決多種衝突的情況，同時還需要考慮如何刪除數據。

三、擴容機制

哈希表的擴容也是一個重要的問題。當哈希表中的元素過多時，可能會導致哈希衝突的概率過高，影響哈希表的效率。此時，我們需要對哈希表進行擴容，即新建一個更大的哈希表，將原哈希表中的元素逐個插入到新的哈希表中。

在Java中，一般情況下，哈希表的負載因子為0.75。當哈希表的元素個數達到容量的75%時，就應該開始考慮擴容了。一般情況下，哈希表的容量應該是2的冪次方，以確保哈希函數計算的下標值均勻。

private void resizeIfNeeded() {
    if ((float) size / capacity >= loadFactor) {
        capacity *= 2;
        LinkedList<Entry>[] newBuckets = new LinkedList[capacity];
        for (LinkedList<Entry> bucket : buckets) {
            if (bucket == null) {
                continue;
            }
            for (Entry entry : bucket) {
                int bucketIndex = hash(entry.key) % capacity;
                if (newBuckets[bucketIndex] == null) {
                    newBuckets[bucketIndex] = new LinkedList();
                }
                newBuckets[bucketIndex].add(entry);
            }
        }
        this.buckets = newBuckets;
    }
}

以上是一個簡單的哈希表實現，使用鏈地址法來解決哈希衝突，當哈希表的負載因子達到0.75時，自動進行擴容，以保證哈希表的高效性。