我们去有道翻译translate一下
因为树节点的大小大约是普通节点的两倍,所以我们 只有当容器中包含足够的节点以保证使用时才使用它们 (见TREEIFY_THRESHOLD)。当它们变得太小的时候 移除或调整大小)它们被转换回普通的箱子。在 使用分布良好的用户哈希码,树箱是 很少使用。理想情况下,在随机哈希码下 箱中的节点遵循泊松分布 () 默认大小调整的参数平均约为0.5 阈值为0.75,虽然由于方差较大 调整粒度。忽略方差,得到期望 列表大小k的出现次数为(exp(-0.5) * pow(0.5, k) / 阶乘(k))。第一个值是: 0:0.60653066 1:0.30326533 2:0.07581633 3:0.01263606 4:0.00157952 5:0.00015795 6:0.00001316 7:0.00000094 8:0.00000006 多于:少于千分之一所以,节点插入遵循泊松分布,因此出现一个桶内8个节点是极小概率事件,所以遇到这种情况我们可以用红黑树加速get操作
ConcurrentHashMap不支持 key为null 也不知支持 value为null
JDK7版本下的 //默认的数组大小16(HashMap里的那个数组) static final int DEFAULT_INITIAL_CAPACITY = 16; //扩容因子0.75 static final float DEFAULT_LOAD_FACTOR = 0.75f; //ConcurrentHashMap中的数组 final Segment<K,V>[] segments //默认并发标准16 static final int DEFAULT_CONCURRENCY_LEVEL = 16; //Segment是ReentrantLock子类,因此拥有锁的操作 static final class Segment<K,V> extends ReentrantLock implements Serializable { //HashMap的那一套,分别是数组、键值对数量、阈值、负载因子 transient volatile HashEntry<K,V>[] table; transient int count; transient int threshold; final float loadFactor; Segment(float lf, int threshold, HashEntry<K,V>[] tab) { this.loadFactor = lf; this.threshold = threshold; this.table = tab; } } //换了马甲还是认识你!!!HashEntry对象,存key、value、hash值以及下一个节点 static final class HashEntry<K,V> { final int hash; final K key; volatile V value; volatile HashEntry<K,V> next; } //segment中HashEntry[]数组最小长度 static final int MIN_SEGMENT_TABLE_CAPACITY = 2; //用于定位在segments数组中的位置,下面介绍 final int segmentMask; final int segmentShift; put函数 public V put(K key, V value) { Segment<K,V> s; //步骤①注意valus不能为空!!! if (value == null) throw new NullPointerException(); //根据key计算hash值,key也不能为null,否则hash(key)报空指针 int hash = hash(key); //步骤②派上用场了,根据hash值计算在segments数组中的位置 int j = (hash >>> segmentShift) & segmentMask; //步骤③查看当前数组中指定位置Segment是否为空 //若为空,先创建初始化Segment再put值,不为空,直接put值。 if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck (segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment s = ensureSegment(j); return s.put(key, hash, value, false); } ensureSegement可以看到JDK7版本下,ConcurrentHashMap的segment也是使用写时复制的,并且使用CAS算法来将副本替换
private Segment<K,V> ensureSegment(int k) { //获取segments final Segment<K,V>[] ss = this.segments; long u = (k << SSHIFT) + SBASE; // raw offset Segment<K,V> seg; if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) { //拷贝一份和segment 0一样的segment Segment<K,V> proto = ss[0]; // use segment 0 as prototype //大小和segment 0一致,为2 int cap = proto.table.length; //负载因子和segment 0一致,为0.75 float lf = proto.loadFactor; //阈值和segment 0一致,为1 int threshold = (int)(cap * lf); //根据大小创建HashEntry数组tab HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap]; //再次检查 if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) { // recheck 根据已有属性创建指定位置的Segment Segment<K,V> s = new Segment<K,V>(lf, threshold, tab); while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) { if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s)) break; } } } return seg; } put value首先lock获取 tab[hash(key)]
然后进行操作