带你了解Java数据结构和算法之哈希表

前言

哈希表是一种常用的数据结构，它可以高效地存储和查询数据。在计算机科学领域，哈希表广泛用于实现关联数组（Associative Array）和哈希集合（Hash Set）。本文将带领大家深入了解哈希表数据结构及常用算法实现。

哈希表的原理

哈希表是根据关键码值(Key Value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。

哈希表实际上就是一个数组，通过哈希算法将数据映射到数组中的一个固定位置，以此来实现快速查找。哈希算法的关键在于解决哈希冲突问题，即两个不同的数据映射到了同一个数组位置的问题。

常见的哈希冲突解决方法有开放地址法和链表法。开放地址法是指当哈希冲突发生时，顺序地向后寻找空槽来存放数据。而链表法是在哈希表的每个槽位（slot）中，使用链表来存储对应哈希值的元素。

哈希表算法实现

哈希函数

哈希函数是将元素转化为索引的核心部分。由于哈希函数必须非常快，因此经典的哈希函数往往结合了位运算、乘法、异或等操作，如下所示：

public int hash(Object key) {
    int h = key.hashCode();
    return (h ^ (h >>> 16)) & (size - 1);
}

其中 size 表示哈希表的大小，key 是需要哈希的元素。

开放地址法

开放地址法的实现比链表法简单，每次发生冲突时，只需要从当前位置往后依次查看数组中的元素，看是否有空槽。

• 线性探测法

线性探测法是指当哈希冲突发生时，顺序地向后寻找空槽来存放数据。如下所示：

private int putInternal(K key, V value) {
    int index = indexOf(key);
    while (table[index] != null) {
        if (table[index].key.equals(key)) {
            V old = table[index].value;
            table[index].value = value;
            return old;
        }
        index = (index + 1) % table.length;
    }
    table[index] = new Entry<>(key, value);
    size++;
    return null;
}

• 二次探测法

二次探测法是指当哈希冲突发生时，按固定的二次探测序列来寻找下一个存储位置。如下所示：

private int quadraticProbing(K key) {
    int index = hash(key);
    for (int i = 1; table[index] != null; i++) {
        if (table[index].key.equals(key)) return index;
        index = (index + i^2) % table.length;
    }
    return -1;
}

链表法

链表法是指在哈希表的每个槽位中，使用链表来存储对应哈希值的元素。具体实现如下：

class Entry<K, V> {
    K key;
    V value;
    Entry<K, V> next;

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

private void putInternal(K key, V value) {
    int index = hash(key);
    if (table[index] == null) {
        table[index] = new Entry<>(key, value);
        size++;
    } else {
        Entry<K, V> cur = table[index];
        while (cur != null) {
            if (cur.key.equals(key)) {
                cur.value = value;
                return;
            }
            cur = cur.next;
        }
        Entry<K, V> newEntry = new Entry<>(key, value);
        newEntry.next = table[index];
        table[index] = newEntry;
        size++;
    }
}

哈希表的应用

哈希表常用于实现关联数组（Associative Array）和哈希集合（Hash Set）。在 Java 中，HashMap 和 HashSet 就是典型的哈希表实现。

比如我们可以使用哈希表来统计一段文本中每个单词出现的次数，具体实现如下：

public Map<String, Integer> wordCount(String text) {
    Map<String, Integer> map = new HashMap<>();
    String[] words = text.split("\\s+");
    for (String word : words) {
        Integer count = map.get(word);
        if (count == null) {
            map.put(word, 1);
        } else {
            map.put(word, count + 1);
        }
    }
    return map;
}

总结

哈希表是一种高效的数据结构，能够快速地存储和查询数据。它通过哈希算法将数据映射到数组中的一个固定位置，来实现快速查找。常用的哈希算法有线性探测法，二次探测法和链表法。在 Java 中，HashMap 和 HashSet 就是典型的哈希表实现，常用于实现关联数组和哈希集合。