Skip to content

javalib jctools map

wangkaiwu edited this page Feb 9, 2023 · 2 revisions

NonBlockingHashMap

构造

public class NonBlockingHashMap<TypeK, TypeV>
        extends AbstractMap<TypeK, TypeV>
        implements ConcurrentMap<TypeK, TypeV>, Cloneable, Serializable {
    private static final int MIN_SIZE_LOG = 3;
    // 1 << 3 = 8
    private static final int MIN_SIZE = (1 << MIN_SIZE_LOG);

    public NonBlockingHashMap() {
        this(MIN_SIZE);
    }

    public NonBlockingHashMap(final int initial_sz) {
        initialize(initial_sz);
    }
}
public class NonBlockingHashMap<TypeK, TypeV>
        extends AbstractMap<TypeK, TypeV>
        implements ConcurrentMap<TypeK, TypeV>, Cloneable, Serializable {
    private transient long _last_resize_milli;
    private transient Object[] _kvs;

    private final void initialize(int initial_sz) {
        int i;
        // 限制初始大小
        if (initial_sz > 1024 * 1024) initial_sz = 1024 * 1024;
        // i 是 5
        for (i = MIN_SIZE_LOG; (1 << i) < (initial_sz << 2); i++) ;
        // length 66
        _kvs = new Object[((1 << i) << 1) + 2];
        _kvs[0] = new CHM(new ConcurrentAutoTable());
        // length = 32
        _kvs[1] = new int[1 << i];
        _last_resize_milli = System.currentTimeMillis();
    }
}

put 第一个值

public class NonBlockingHashMap<TypeK, TypeV>
        extends AbstractMap<TypeK, TypeV>
        implements ConcurrentMap<TypeK, TypeV>, Cloneable, Serializable {
    public static final Object TOMBSTONE = new Object();
    static volatile int DUMMY_VOLATILE;
    private transient Object[] _kvs;
    @Override
    public TypeV put (TypeK  key,TypeV val) {
        return putIfMatch(key, val, NO_MATCH_OLD); 
    }

    public final TypeV putIfMatch( Object key, Object newVal, Object oldVal ) {
        final Object res = putIfMatch0(this, _kvs, key, newVal, oldVal );
        return res == TOMBSTONE ? null : (TypeV)res;
    }

    private static final Object putIfMatch0(
            final NonBlockingHashMap topmap,
            final Object[] kvs,
            final Object key,
            final Object putval,    // value
            final Object expVal) { // NO_MATCH_OLD
        // key 的 hashCode
        final int fullhash = hash  (key);
        // 长度
        final int len      = len   (kvs);
        // 0 位置
        final CHM chm      = chm   (kvs);
        // 1 位置
        final int[] hashes = hashes(kvs);
        // 期望位置
        int idx = fullhash & (len-1);

        int reprobe_cnt=0;
        Object K=null, V=null;
        Object[] newkvs=null;
        while( true ) {
            V = val(kvs,idx);
            K = key(kvs,idx);
            if( K == null ) {
                // 说明目标位置没有被占用
                if( putval == TOMBSTONE ) return TOMBSTONE;
                if( expVal == MATCH_ANY ) return TOMBSTONE;
                if( CAS_key(kvs,idx, null, key ) ) {
                    chm._slots.add(1);
                    // 将 hash记录在 kvs 的 1 位置的数组中
                    hashes[idx] = fullhash;
                    break;
                }
            }
            // ...........
        }
        while ( true ) {
            if( putval == V ) return V;
            if( newkvs == null && // 为 true
                    ((V == null && chm.tableFull(reprobe_cnt,len)) ||
                            V instanceof Prime) ) {
                // 需要resize
                // ...........
            }
            if( newkvs != null ) {
                // ...........
            }
            if( expVal != NO_MATCH_OLD &&
                    V != expVal &&
                    (expVal != MATCH_ANY || V == TOMBSTONE || V == null) &&
                    !(V==null && expVal == TOMBSTONE) &&
                    (expVal == null || !expVal.equals(V)) ) {
                // ............
            }
            // 尝试 cas 设置 v
            if( CAS_val(kvs, idx, V, putval ) ) break;
            // ...............
        }
        if( expVal != null ) {
            if(  (V == null || V == TOMBSTONE) && putval != TOMBSTONE ) chm._size.add( 1);
            // .............
        }
        // 返回旧值
        return (V==null && expVal!=null) ? TOMBSTONE : V;
    }
    
}

get 值

key & val

public class NonBlockingHashMap<TypeK, TypeV>
        extends AbstractMap<TypeK, TypeV>
        implements ConcurrentMap<TypeK, TypeV>, Cloneable, Serializable {
    private static final Object val(Object[] kvs,int idx) {
        // idx 扩大 2倍后 + 3。 kvs 的前2位被占用了,偶数位是 key,奇数位是 value
        return kvs[(idx<<1)+3]; 
    }

    private static final Object key(Object[] kvs,int idx) { 
        // 偶数位是 key
        return kvs[(idx<<1)+2]; 
    }
}

Clone this wiki locally