JDK源码 Hash杂记

最早了解Hash的用法，是一次分表的经历，公司用户表数据有几千万，查询的效率已经比较低了，需要做拆分处理，之前系统中已经有分表的数据，处理方式比较简单，没有使用中间件，按照商家的ID（32位字符串）做Hash然后取模，算出其落在表的编号，然后加上前缀得到最终表名。

最近在了解zk分布式锁时，为了避免一种实现方式的羊群效应，其改进思路类似一致性哈希算法。于是，便看了下Hash相关的知识，并用Java做了简单实现。

哈希简介

哈希算法将任意长度的二进制值映射为较短的固定长度的二进制值，这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母，随后的哈希都将产生不同的值。要找到散列为同一个值的两个不同的输入，在计算上是不可能的，所以数据的哈希值可以检验数据的完整性。一般用于快速查找和加密算法。

简单的Hash应用

类似开头我们的场景，我们根据Hash的特性用代码来模拟下。

/**
 * 表，实际存储
 * Created by childe on 2017/5/14.
 */
public class Table {
    private String name;
    Map<String,Merchant> merchantMap;

    Table(String name) {
        this.name = name;
        merchantMap = new HashMap<>();
    }

    public void insert(Merchant merchant) {
        merchantMap.put(merchant.getId(),merchant);
    }

    public Merchant select(String id) {
        return merchantMap.get(id);
    }
}

/**
 * 商家
 * Created by childe on 2017/5/14.
 */
public class Merchant {
    private String id;

    public Merchant(String id) {
        this.id = id;
    }

    public String getId() {
        return id;
    }

    public void setId(String id) {
        this.id = id;
    }
}

/**
 * 表路由
 * Created by childe on 2017/5/14.
 */
public class TableRoute {
    private static final int TABLE_SIZE_MAX = 512;

    private Table[] tables = new Table[TABLE_SIZE_MAX];

    private int size = 0;

    public void insert(Merchant merchant) {
        //以merchant的ID为key，其不能为空
        if (merchant == null && StringUtils.isEmpty(merchant.getId())) {
            return;
        }

        int index = merchant.getId().hashCode() % size;

        Table table = tables[index];
        table.insert(merchant);
    }

    public Merchant select(String id) {
        if (StringUtils.isEmpty(id)) {
            return null;
        }

        int index = id.hashCode() % size;

        Table table = tables[index];

        return table.select(id);
    }

    public void addTable(Table table) {
        if (table == null) {
            return;
        }
        tables[size++] = table;
    }
}

/**
 * Created by childe on 2017/5/14.
 */
public class Main {

    static int tableNum = 3;
    static int merchantNum = 100;

    public static void main(String[] args) {
        //初始化表
        TableRoute tableRoute = creatTableRoute(tableNum);

        //插入数据
        for (int i = 0; i < merchantNum; i++) {
            Merchant merchant = new Merchant(String.valueOf(i));
            tableRoute.insert(merchant);
        }

        //有效数据统计
        validCount(tableRoute);

        //增加一个表
        tableRoute.addTable(new Table("merchant_100"));

        System.out.println("after add a table");

        //有效数据统计
        validCount(tableRoute);
    }

    private static void validCount(TableRoute tableRoute) {
        int validNum = 0;
        //获取数据
        for (int i = 0; i < merchantNum; i++) {
            Merchant merchant = tableRoute.select(String.valueOf(i));
            if (merchant != null) {
                validNum++;
            }
        }

        System.out.println("vaild merchant : " + validNum + ", total merchant : " + merchantNum);
    }

    public static TableRoute creatTableRoute(int tableNum) {
        TableRoute tableRoute = new TableRoute();
        for (int i = 0; i < tableNum; i++) {
            tableRoute.addTable(new Table("merchant_" + String.valueOf(i)));
        }
        return tableRoute;
    }
}

在上述代码中我们我们模拟了分表插入和查找的过程，最终输出如下：

vaild merchant : 100, total merchant : 100
after add a table
vaild merchant : 24, total merchant : 100

在Main中两次统计了表中有效的数据个数，两次差别还是比较大的，为什么新加入一个表会导致这么多数据实效呢？很简单，因为我们是以分表的个数取模的，当表的数量增加后，当然会造成数据失效。还以开篇的分表为例，如果商家的数据再次很快的增长，那么商家的用户数据当然会更多（商家:用户=1:n），当某个分表记录再次到达千万级别，此时就又面临分表的可能，那么此时就面临数据迁移的问题，否则就会出现我们模拟的状况，从实验上来看，失效的比例还是很高的，迁移就会比较头疼。当然，牵扯到实际问题需要我们对业务的增长有个大概的预测，来计算初次分表的数量。但是大量数据的迁移还是难以避免。

一致性哈希

上面我们看到一旦表的数量增加数据失效比例很高，就需要面临大量的数据迁移，这是难以忍受的。

在应用中还有其他一些类似的场景，比如：缓存（假设我们缓存按照上述方式存放）。本来是为了减轻后方服务的压力，如果缓存的机器挂掉了一台或者我们需要新增加一台，那么，后端服务将面临大量缓存失效而带来的压力，甚至造成雪崩。

一致性哈希很好的解决了这个问题，什么是一致性哈希呢？
一致性哈希将整个哈希值空间组织成一个虚拟的圆环，所有待落到该环上的节点（包括存储节点）均需要按照同一套Hash算法得出落点位置。节点落入到闭环后，按照顺时针的方向存储到离自己最近的一个存储节点。因为存储节点可能比较少，可能会导致存储节点存储数据不均衡，所以需要引入虚拟存储节点。比如：有A、B两台机器提供存储，我们一般使用机器的IP来计算机器的Hash，如果A、B两台机器的hash值比较靠近，数据存储就会出现倾斜，要尽可能保证数据的均匀分布，我们可以再做一层映射，在闭环上放置4个（A#0、A#1、B#0、B#1）或者更多存储节点（使得数据分布约趋于均匀）。

我们简单模拟下一致性哈希的实现：

/**
 * 模拟缓存机器
 * Created by childe on 2017/5/14.
 */
public class Server {
    private String name;
    private Map<String, Entry> entries;

    Server(String name) {
        this.name = name;
        entries = new HashMap<>();
    }

    public void put(Entry e) {
        entries.put(e.getKey(), e);
    }

    public Entry get(String key) {
        return entries.get(key);
    }

    public int hashCode() {
        return name.hashCode();
    }

}

/**
 * 缓存集群
 * Created by childe on 2017/5/14.
 */
public class Cluster {
    private static final int SERVER_SIZE_MAX = 1024;

    private SortedMap<Integer, Server> servers = new TreeMap<>();
    private int size = 0;

    public void put(Entry e) {
        routeServer(e.getKey().hashCode()).put(e);
    }

    public Entry get(String key) {
        return routeServer(key.hashCode()).get(key);
    }

    private Server routeServer(int hash) {
        if (servers.isEmpty()){
            return null;
        }

        /**
         * 顺时针找到离该hash最近的slot（server）
         */
        if (!servers.containsKey(hash)) {
            SortedMap<Integer, Server> tailMap = servers.tailMap(hash);
            hash = tailMap.isEmpty() ? servers.firstKey() : tailMap.firstKey();
        }
        return servers.get(hash);
    }

    public boolean addServer(Server s) {
        if (size >= SERVER_SIZE_MAX) {
            return false;
        }

        servers.put(s.hashCode(), s);

        size++;
        return true;
    }
}

/**
 * 缓存实体
 * Created by childe on 2017/5/14.
 */
public class Entry {
    private String key;

    Entry(String key) {
        this.key = key;
    }

    public String getKey() {
        return key;
    }

    public void setKey(String key) {
        this.key = key;
    }
}

/**
 * Created by childe on 2017/5/5.
 */
public class Main {

    static int entryNum = 100;

    public static void main(String[] args) {
        //创建缓存集群
        Cluster cluster = createCluster();

        //写入缓存实体
        for (int i = 0; i < entryNum; i++) {
            cluster.put(new Entry(String.valueOf(i)));
        }

        //有效数据统计
        validCount(cluster);

        //新增缓存节点
        cluster.addServer(new Server("C"));

        System.out.println("afer add a server");

        //有效数据统计
        validCount(cluster);

    }

    private static Cluster createCluster() {
        Cluster c = new Cluster();
        c.addServer(new Server("A#1"));
        c.addServer(new Server("A#2"));
        c.addServer(new Server("B#1"));
        c.addServer(new Server("B#2"));
        return c;
    }

    private static void validCount(Cluster cluster) {
        int validNum = 0;
        for (int i = 0; i < entryNum; i++) {
            Entry entry = cluster.get(String.valueOf(i));
            if (entry != null) {
                validNum++;
            }
        }
        System.out.println("valid entry : " + validNum + ", total entry : " + entryNum);
    }
}

//输出如下
valid entry : 100, total entry : 100
afer add a server
valid entry : 90, total entry : 100

从输出结果我们看到失效率明显降低。据了解，Memcahce中便采用了一致性哈希的算法。

HashMap

JDK中我们常用的HashMap也是基于哈希实现，JDK1.8以前采用数组和链表来组织数据，1.8中引入了红黑树对链表部分进行了优化。为什么HashMap要采用链表和红黑树呢？因为我们得到某个key的HashCode需要落到具体的桶中，而桶的数量是有限并且固定的，所以难免遇到不同的key却落到相同的桶中，于是就需要链表将这些数据链接起来，这也就是为什么当碰撞比较严重时，HashMap查询变慢的原因，在JDK1.8在处理冲突时采用链表加红黑树，当链表长度大于8时，就将链表转换为红黑树，从而达到加速查找的目的。

JDK1.8中还对HashMap的扩容做了优化，在1.8以前扩容时，需要重新计算每个key的HashCode然后入桶，所以扩容是一个耗时的操作，在1.8中避免了重新计算Hash，加快了扩容操作。

不管是JDK1.7还是1.8我们使用HashMap时最好对需要的容量进行评估，尽量避免扩容操作。JDK1.8对HashMap的优化，想深入了解的可参考美团点评团队的这篇博客

小生不才，以上如有描述有误的地方还望各位不吝赐教 !^_^！

参考：
http://wiki.mbalib.com/wiki/%E5%93%88%E5%B8%8C%E7%AE%97%E6%B3%95
http://www.berlinix.com/