HotRing在Java中对于指针的设计

阅读之前建议先读论文，可能有点本末倒置，不过下一篇我会把论文的原理实现发出来。

这一篇主要是介绍一下如何设计HotRing论文中rehash、occupied、active等字段，在论文中，由于当前计算机基本都是64位的，而它的地址仅仅占用前48位，也就是有12位是可以供我们使用的，对于c++来说很容易操纵这12位的指针，但是Java就很难实现这个动作了，主要有两个原因：

Java屏蔽了指针这个东西，很难直接获取，要么通过Unsafe，要么就是Jni
最重要的是Java的垃圾回收无法认为控制，gc时地址会变

所以Java无法像论文那样把这些标志位存储在指针的那12个bit位上面。

	这个我做过很多论证了，包括

	 System.identityHashCode
	 jni
	 unsafe

发现都很难达到要求，所以只能新增对象来进行存储，但是论文将这些元数据放到指针上面的原因就是压缩内存，无需新增开销，新增对象也可以实现论文，但是如何让开销最小是个问题。最坏的情况就是设计多个对象，每个long类型来存储论文中的这些字段含义

其实好好计算下，论文中 rehash占用1bit，occupied占用1bit，active占用1bit，而totalCounter占用15bit，counter占用14bit，加起来刚好32bit。是不是很熟悉，java的int就是4字节32bit，那么刚好够存储这些字段。

那就是第一个bit存储active，第二个bit存储rehash，第三个bit存储occupied 第4-18bit存储totalCounter，第19-32bit存储counter 相比论文实现多处8字节，32bit的内存消耗，但Java只能这么玩了

其实已经很优化了，我们仅仅对于每个entry新增了一个int，代价不算太大。

那么可能会问如果gc怎么办，这儿其实不用考虑gc，因为这个对象我们不考虑它的地址，仅仅考虑它的值，而现在这个值被分成几个区间来用。只要能读能写就行。

这儿需要涉及到大量的位运算来替我们获取值

首先，需要设置几个变量，代表我们存储的bit位

	// Constants for bit positions
    private static final int ACTIVE_BIT = 0;
    private static final int REHASH_BIT = 1;
    private static final int OCCUPIED_BIT = 2;
    private static final int TOTAL_COUNTER_START_BIT = 3;
    private static final int TOTAL_COUNTER_END_BIT = 18;
    private static final int COUNTER_START_BIT = 19;
    private static final int COUNTER_END_BIT = 32;

	private int meta;

这儿代码就不全贴了，就贴active和totalCounter的举一反三就行

我的存储是小端存储，也就是active存在最低位，counter在最高14位。

先看如何获取active

	public boolean active() {
        return ((meta >> ACTIVE_BIT) & 1) == 0;
    }

是不是很简单，这儿做一个简单的位运算就行。右移一位获取第一个bit，然后判断是否==0，以此作为cas来操作HotRing

active自增

	`public void acquireActive() {
        meta &= ~(1 << ACTIVE_BIT);
        meta |= (1 << ACTIVE_BIT);
    }

先对第一位进行取反得到一个和第一位相反的位掩码，然后通过按位与来消除active的值，再通过按位或操作将其设置为1

重置active

	public void resetActive() {
        meta &= ~(1 << ACTIVE_BIT);
        meta |= (0);
    }

重置和acquireActive一样，只不过写死0，直接将active重置为0就行

上面是active操作，它在第一位，那如果在中间和最后呢，如何进行位运算截取

比如totalCounter就在第3-18位

先看获取totalCounter操作

	public int totalCounter() {
        int mask = ((1 << (TOTAL_COUNTER_END_BIT - TOTAL_COUNTER_START_BIT + 1)) - 1) << TOTAL_COUNTER_START_BIT;
        return (meta & mask) >>> TOTAL_COUNTER_START_BIT;
    }

和之前一样，需要计算一个mask掩码来获取totalCounter的bit区间，原理就是

将1向左移动15 + 1 位
减去1，拿到一个3-18之间的bit为1的二进制
然后这个二进制在左移3bit，移动1到对应的位，这样掩码就可以正确提取3-18之间的位
最后通过按位与将meta和掩码进行位运算，然后>>>3位，这样子就能够获取3-18之间的数据了

这儿估计挺复杂，最好的办法就是写代码自己测试下，光看很难理解估计

然后就是修改totalCounter

	public void incrTotalCounter(int n) {
        int mask = ((1 << (TOTAL_COUNTER_END_BIT - TOTAL_COUNTER_START_BIT + 1)) - 1) << TOTAL_COUNTER_START_BIT;
        // clear the bits in the range
        meta &= ~mask;
        // set the bits to the new value
        meta |= (n << TOTAL_COUNTER_START_BIT);
    }

第一步和获取一样，计算掩码
使用按位与，将掩码所有位清零，方便设置新的值
将传入的n左移3位后的结果与原参数进行按位或操作并赋值回去，这样子就能够修改对应的值

接下来就是重置了，其实可以举一反三了，重置和修改操作一样，直接传入一个0就可以

	public void resetTotalCounter() {
        int mask = ((1 << (TOTAL_COUNTER_END_BIT - TOTAL_COUNTER_START_BIT + 1)) - 1) << TOTAL_COUNTER_START_BIT;
        meta &= ~mask;
        meta |= 0;
    }

这样子就通过位运算完全用一个int类型存储下了5个变量。这是我当前能够发现的最高效的方式了。

项目还有很多使用位运算的地方比如rehash时如何用位运算来定义Hazard Pointers 当然也有我们常见的hash算法，这个就直接贴代码了，想了解的去hashmap源码就行

	default int hash(K key) {
        if (key instanceof String) {
            int hash = 5381;
            for (char c : ((String) key).toCharArray()) {
                hash += (hash << 5) + c;
            }
            // return key[0] << 7 将最高位设置为0，非负数
            return (hash & 0x7FFFFFFF);
        }
        // 否则取地址
        return System.identityHashCode(key);
    }

祝各位秋招加油

#晒一晒我的offer##秋招##Java##java##实习#