一致性Hash的简单实现(java demo)

下面使用代码实现一致性hash算法

import org.redisson.connection.CRC16;

import java.security.SecureRandom;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;


public final class HashUtil {

    private static final int MAX_SLOT = 16384; // 取模的值
    private static final SecureRandom RANDOM = new SecureRandom();
    private static final List SERVER_IP = randomIp(4); // 随机生成4个server ip
    // 存放服务器节点(可以理解为服务器Hash后放在环形上)
    private static final TreeMap treeMap = new TreeMap<>();
    private static final int VIRTUAL_SLOT = 50; // 每个真实节点都有50个虚拟节点

    
    public static int hashMold(String key) {
        return CRC16.crc16(key.getBytes()) % MAX_SLOT;
    }

    public static void main(String[] args) {
        consistentHash();
    }

    
    public static void hash() {
        int i = 0;
        for (String ip : SERVER_IP) {
            i++;
            int hashCode = hashMold(ip);
            treeMap.put(hashCode, String.format("服务器节点: %d, real ip=%s", i, ip));
        }

        List clientIpList = randomIp(10000); // 随机生成10000个client ip
        for (String ip : clientIpList) {
            int hash = hashMold(ip);
            Map.Entry entry = treeMap.higherEntry(hash);
            if (entry == null) {
                // 为空表示没有比treeMap更大的key,返回第一个server ip
                System.out.println(ip + " 存入:" + treeMap.firstEntry().getValue());
            } else {
                // 不为空,返回要比hash大,并且是最小的节点
                System.out.println(ip + " 存入:" + entry.getValue());
            }
        }
    }

    
    public static void consistentHash() {
        int i = 0;
        for (String ip : SERVER_IP) {
            i++;
            for (int j = 1; j <= VIRTUAL_SLOT; j++) {
                int hashCode = hashMold(ip + "#" + j);
                treeMap.put(hashCode, String.format("服务器节点%d # real ip=%s # virtual node=%d", i, ip, j));
            }
        }

        List clientIpList = randomIp(10000); // 随机生成10000个client ip
        for (String ip : clientIpList) {
            int hash = hashMold(ip);
            Map.Entry entry = treeMap.higherEntry(hash);
            if (entry == null) {
                // 为空表示没有比treeMap更大的key,返回第一个server ip
                System.out.println(ip + " 存入:" + treeMap.firstEntry().getValue());
            } else {
                // 不为空,返回要比hash大,并且是最小的节点
                System.out.println(ip + " 存入:" + entry.getValue());
            }
        }
    }

    
    public static List randomIp(int num) {
        List list = new ArrayList<>(num);
        for (int i = 0; i < num; i++) {
            String ip = RANDOM.nextInt(256) + 1 + "." + RANDOM.nextInt(256) + "." + RANDOM.nextInt(256) + "." + RANDOM.nextInt(256);
            list.add(ip);
        }
        return list;
    }
}

Hash的特点就是没有规律，随机，没有虚拟节点的实现分布不均匀，生成的四个卡槽也是随机

的，而增加了虚拟节点的hash槽放大了50，节点分布更均匀