package ext.geek.hash;
public interface IHash {
	int genHash(String key);	}
class FVHash implements IHash {
    static final int p = (2 << 23) + (2 << 7) + 0x93;    static final long hashConst = 2166136261L;
    @Override    public int genHash(String key) {        int hash = (int) hashConst;        for (int i = 0; i < key.length(); i++) {            hash = (hash ^ key.charAt(i)) * p;        }        hash += hash << 13;        hash ^= hash >> 7;        hash += hash << 3;        hash ^= hash >> 17;        hash += hash << 5;
        if (hash < 0)            hash = Math.abs(hash);        return hash;    }}

package ext.geek.hash;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        String hostPre = "test.servers";
        int num_real_server = 4;        int num_virtual_server = 150;
        // TODO: Factory Mode        IHash hasher = new FVHash();
        SortedMap<Integer, Server> serverMap = new TreeMap<Integer, Server>();
        List<Server> rList = new ArrayList<>();        // Init Servers        for (int i = 0; i < num_real_server; i++) {            Server rs = new Server(hostPre + i, 0, 0);            rs.nHash = hasher.genHash(rs.host + ":" + rs.port + ":" + rs.type);            rList.add(rs);            if (serverMap.containsKey(rs.nHash)) {                System.out.println("Already mapped hash");                break;            }            serverMap.put(rs.nHash, rs);            boolean vHashDup = false;            for (int j = 1; j <= num_virtual_server && !vHashDup; j++) {                Server vs = new Server(hostPre + i, j, 1);                vs.nHash = hasher.genHash(vs.host + ":" + vs.port + vs.type);                if (serverMap.containsKey(vs.nHash)) {                    System.out.println("Already mapped hash");                    vHashDup = true;                    break;                }                // Mark for delete vserver                rs.childServers.put(vs.nHash, vs);                serverMap.put(vs.nHash, vs);            }        }
        String[] testSource = {"test.servers0:0:0", "test.servers0:100:0", "test.servers0:15:0"};
        // Request Url        for (int i = 0; i < testSource.length; i++) {            int value = hasher.genHash(testSource[i]);            System.out.println("Hash is:" + value);            // find tree node            Iterator<Integer> serverHashKeys = serverMap.keySet().iterator();            Integer nextKey = null;            while (serverHashKeys.hasNext()) {                int tmp = serverHashKeys.next();                nextKey = value >= tmp ? nextKey = tmp : nextKey;                if (nextKey == null) {                    break;                }            }            System.out.println("Seleted Node: " + serverMap.get(nextKey));        }
        // Delete Servers        Server rServer = rList.get(0);        for (Integer key : rServer.childServers.keySet()) {            serverMap.remove(key);        }        // ReHash        for (int i = 0; i < testSource.length; i++) {            int value = hasher.genHash(testSource[i]);            System.out.println("Hash is:" + value);            // find tree node            Iterator<Integer> serverHashKeys = serverMap.keySet().iterator();            Integer nextKey = null;            while (serverHashKeys.hasNext()) {                int tmp = serverHashKeys.next();                nextKey = value >= tmp ? nextKey = tmp : nextKey;                if (nextKey == null) {                    break;                }            }            System.out.println("Seleted Node: " + serverMap.get(nextKey));        }

    }
    public static class Server {
        String host;        int port;        int nHash;        int type;        Map<Integer, Server> childServers = new HashMap<Integer, Server>();
        public Server(String host, int port, int type) {            this.port = port;            this.host = host;            this.type = type;        }
    }
}