几种常用的散列算法

最近学习HashMap、ThreadLocal、分库分表等源码，发现采用散列算法都不同。散列算法本质上是将一个极大不定范围的数据缩放到指定范围空间中。那么接下来就来了解不同的散列算法以及对应的使用。

除法散列

通过除法得到余数的方式来进行散列，mod M限制到M范围中。
由于编码架构的问题，速度慢。

在分库分表中使用，因为能够做到任意范围的数据均匀分布。

字符串哈希 || 乘法散列

Java中的HashCode就是一种字符串哈希的实现。

 public int hashCode() {
     int h = hash;
     if (h == 0 && value.length > 0) {
          char val[] = value;
          for (int i = 0; i < value.length; i++) {
              h = 31 * h + val[i];
          }
          hash = h;
      }
      return h;
}

进一步来说在HashMap中使用哈希扰动来优化。

 public static int disturbHashIdx(String key, int size) {
        return (size - 1) & (key.hashCode() ^ (key.hashCode() >>> 16));
 }

这样使得Hash在空间中分布更加均匀。

斐波那契散列

斐波那契散列是一种基于黄金分割比的哈希函数设计方法，旨在减少哈希冲突并实现均匀分布。其核心思想是利用斐波那契数列与黄金分割比例（≈0.618）的数学特性，通过位移和乘法操作将键值映射到哈希表中。

public int index(String word){
    int HASH_INCREMENT = (int) ((null == hashIncrementVal ? size : hashIncrementVal) * (Math.sqrt(5) - 1) / 2);
    int idx = (size - 1) & (word.hashCode() * HASH_INCREMENT + HASH_INCREMENT);
    return idx; 
}

在ThreadLocal中需要为每个线程生成唯一且均匀分布的哈希码，采用斐波拉且散列+线性探测开放寻址，在容量长度为2的N次方时，几乎不出现重复数据。

class ThreadLocal{
    private final int threadLocalHashCode = nextHashCode();

    /**
     * The next hash code to be given out. Updated atomically. Starts at
     * zero.
     */
    private static AtomicInteger nextHashCode =
        new AtomicInteger();

    /**
     * The difference between successively generated hash codes - turns
     * implicit sequential thread-local IDs into near-optimally spread
     * multiplicative hash values for power-of-two-sized tables.
     */
    private static final int HASH_INCREMENT = 0x61c88647;

    /**
     * Returns the next hash code.
     */
    private static int nextHashCode() {
        return nextHashCode.getAndAdd(HASH_INCREMENT);
    }
    
    static class ThreadLocalMap{
         int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1); 
    }
}

缺点：当容量不靠近2的N次方时，会出现大量重复数据。（这个也是为什么分库分表不能使用的原因）
补充一下为什么称为斐波拉且散列？为什么选用0x61c88647？
0x61c88647对应的十进制为1640531527。 斐波那契散列的乘数可以用(long) ((1L << 31) * (Math.sqrt(5) - 1))可以得到2654435769，如果把这个值给转为带符号的int，则会得到-1640531527。

一致性Hash

一致性Hash应该都知道是将数据通过%(2^32 - 1)映射到哈希环上，每次添加一个节点就只需要移动一个节点的信息。而虚拟节点，就是解决真实节点在哈希环中分布不均匀的问题，将一个真实节点映射到多个虚拟节点上。
这里记录一下我遇到疑惑：
1）(2^32 - 1)大概4G，我们真的需要实际开辟这么大的哈希环吗？
不用，只需要使用跳表/ 红黑树来存放实际的位置。
新增节点之后，只需要把插入位置下一个节点的数据迁移到新增节点。
删除节点之后，需要把当前节点的数据迁移到下一个节点中。
2）虚拟节点映射到真实节点，两者是在同一个哈希环中？
是的，虚拟节点是真实节点的逻辑扩展。两者通过映射绑定。
1，数据通过哈希函数映射到环上的某个位置
2. 沿环顺时针找到最近的虚拟节点
3. 通过映射表确定该虚拟节点对应的真实节点

public class ConsistentHash<T> {
    private final TreeMap<Long, T> ring = new TreeMap<>(); 
    private final int virtualNodeCount; 
    private final MessageDigest md;   

    public ConsistentHash(int virtualNodeCount) throws NoSuchAlgorithmException {
        this.virtualNodeCount = virtualNodeCount;
        this.md = MessageDigest.getInstance("MD5");
    }

    public void addNode(T node) {
        for (int i = 0; i < virtualNodeCount; i++) {
            String virtualNode = node.toString() + "#" + i;
            long hash = hash(virtualNode);
            ring.put(hash, node);
        }
    }

    public void removeNode(T node) {
        for (int i = 0; i < virtualNodeCount; i++) {
            String virtualNode = node.toString() + "#" + i;
            long hash = hash(virtualNode);
            ring.remove(hash);
        }
    }

    public T getNode(String key) {
        if (ring.isEmpty()) {
            return null;
        }
        long hash = hash(key);
        Map.Entry<Long, T> entry = ring.ceilingEntry(hash);
        if (entry == null) {
            entry = ring.firstEntry();
        }
        return entry.getValue();
    }

    private long hash(String key) {
        md.reset();
        md.update(key.getBytes());
        byte[] digest = md.digest();
        return ((long) (digest[3] & 0xFF) << 24) |
               ((long) (digest[2] & 0xFF) << 16) |
               ((long) (digest[1] & 0xFF) << 8) |
               ((long) (digest[0] & 0xFF));
    }

    public static void main(String[] args) throws Exception {
        ConsistentHash<String> ch = new ConsistentHash<>(1000); // 每个节点 1000 个虚拟节点

        ch.addNode("Node-A");
        ch.addNode("Node-B");
        ch.addNode("Node-C");

        Map<String, Integer> count = new HashMap<>();
        for (int i = 0; i < 10_000; i++) {
            String node = ch.getNode("key-" + i);
            count.put(node, count.getOrDefault(node, 0) + 1);
        }
        
        System.out.println("数据分布: " + count); 

        ch.removeNode("Node-B");
        count.clear();
        for (int i = 0; i < 10_000; i++) {
            String node = ch.getNode("key-" + i);
            count.put(node, count.getOrDefault(node, 0) + 1);
        }
        System.out.println("移除 Node-B 后分布: " + count);
    }
}