哈希表

底层数据结构

哈希表底层数据结构为数组＋链表或者数组+红黑树。

节点类

static class Entry {
    int hash;
    Object key;
    Object value;
    Entry next;

    public Entry(int hash, Object key, Object value) {
        this.hash = hash;
        this.key = key;
        this.value = value;
    }
}

位运算代替求模运算

前提：数组长度为2的幂
hash % 数组长度 <==>（等价于） hash & (数组长度 - 1)

哈希表扩容

若数组大小固定，元素过多，导致链表过长，效率降低。

负载因子（load factor）

当 size / length >= 负载因子，进行自动扩容

扩容规律

链表最多拆分成两个链表

hash & length == 0 为一组
hash & length != 0 为一组

规律分析

前提：数组大小为 2 的幂
扩容时，新数组大小为 2 * 旧数组大小，那么只看第n位的值即可，若第n位的值为 0 ，则在新数组中位置不变，若为 1，反之。这就是为什么拆分成两个链表。

哈希算法

MD5
SHA1
SHA256
SHA512
CRC32

String的hash算法

遍历每个字符，取ascii码，再根据字符位置设置不同的权重累加。

murmurhash

murmurhash具有以下优点：

快速计算
低碰撞率
随机性强

总之，murmurhash是一种高效、优秀的哈希函数，被广泛应用于哈希表、布隆过滤器、哈希集合等数据结构中。

murmurhash使用

导入guava

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>33.2.1-jre</version>
</dependency>

Hashing类使用

private int hash(Object key) {
    if (key instanceof String k)
        return Hashing.murmur3_32_fixed().hashString(k, StandardCharsets.UTF_8).asInt();

    int hashCode = key.hashCode();
    // 高位与低位异或运算，让高位参与求模，减少冲突
    return hashCode ^ hashCode >> 16;
}

自定义HashTable，完整代码

import com.google.common.hash.Hashing;

import java.nio.charset.StandardCharsets;

public class HashTable {
    private Entry[] arr;
    private int size;

    public HashTable(){
        this(16);
    }

    public HashTable(int size){
        arr = new Entry[size];
    }

    public void put(Object key, Object value) {
        if (key == null || value == null)
            return;

        put(hash(key), key, value);
    }

    public Object get(Object key) {
        if (key == null)
            return null;

        return get(hash(key), key);
    }

    public Object remove(Object key) {
        if (key == null) {
            return null;
        }

        return remove(hash(key), key);
    }

    // 根据 hash码 获取 value
    private Object get(int hash, Object key) {
        int idx = hash & (arr.length - 1);
        Entry entry = arr[idx];

        if (entry == null)
            return null;

        while (entry != null){
            if (entry.key.equals(key))
                return entry.value;

            entry = entry.next;
        }

        return null;
    }

    // 插入或更新
    private void put(int hash, Object key, Object value) {
        int idx = hash & (arr.length - 1);
        Entry entry = arr[idx];

        if (entry == null){
            arr[idx] = new Entry(hash, key, value);
            size++;
            checkExpand();
            return;
        }

        Entry prev = null;
        while (entry != null) {
            if (entry.key.equals(key)){
                entry.value = value;
                return;
            }

            prev = entry;
            entry = entry.next;
        }

        prev.next = new Entry(hash, key, value);
        size++;
        checkExpand();
    }

    private Object remove(int hash, Object key) {
        int idx = hash & (arr.length - 1);
        Entry entry = arr[idx];

        if (entry == null)
            return null;

        Entry prev = null;
        while (entry != null){
            if (entry.key.equals(key)){
                Object re = entry.value;

                if (prev != null)
                    prev.next = entry.next;
                else
                    arr[idx] = entry.next;

                size--;
                return re;
            }

            prev = entry;
            entry = entry.next;
        }

        return null;
    }

    private int hash(Object key) {
        if (key instanceof String k)
            return Hashing.murmur3_32_fixed().hashString(k, StandardCharsets.UTF_8).asInt();

        int hashCode = key.hashCode();
        return hashCode ^ hashCode >> 16;
    }

    private void checkExpand(){
        float f1 = 0.75f;
        if ((float) size / arr.length < f1){
            return;
        }

        Entry[] newEntries = new Entry[arr.length << 1];

        for (int i = 0; i < arr.length; i++) {
            Entry p = arr[i];
            if (p == null)
                continue;

            Entry f = new Entry(-1, null, null);
            Entry sentinelF = f;
            Entry s = new Entry(-1, null, null);
            Entry sentinelS = s;
            while (p != null){
                if ((p.hash & arr.length) == 0) {
                    f.next = p;
                    f = f.next;
                } else {
                    s.next = p;
                    s = s.next;
                }

                p = p.next;
            }

            f.next = s.next = null;
            newEntries[i] = sentinelF.next;
            newEntries[i + arr.length] = sentinelS.next;
        }

        this.arr = newEntries;
    }

    static class Entry {
        int hash;
        Object key;
        Object value;
        Entry next;

        public Entry(int hash, Object key, Object value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }
}