集合

18 October 2018

集合

集合序列化方式

为什么实现serializable接口，writeObject的代码段

if (obj instanceof String) {
    writeString((String) obj, unshared);
} else if (cl.isArray()) {
    writeArray(obj, desc, unshared);
} else if (obj instanceof Enum) {
    writeEnum((Enum<?>) obj, desc, unshared);
} else if (obj instanceof Serializable) {
    writeOrdinaryObject(obj, desc, unshared);
} else {
    if (extendedDebugInfo) {
        throw new NotSerializableException(
            cl.getName() + "\n" + debugInfoStack.toString());
    } else {
        throw new NotSerializableException(cl.getName());
    }
}

集合的writeObject 和 readObject 方法，在使用ObjectOutputStream的writeObject方法和ObjectInputStream的readObject方法时，会通过反射的方式调用。

HashMap

1.8数据结构

说明

Node可链表可树，双重含义

链表

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

红黑树

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>
static class LinkedHashMap.Entry<K,V> extends HashMap.Node<K,V>
static class Node<K,V> implements Map.Entry<K,V>
1.8插入流程

求hash值的方式不同，但是找下标的方法：(length - 1) & h

h是key的hashcode经过扰动函数处理得到的结果

  • key取hash值，扰动函数(位运算和异或各一次[高低16位异或])
  • 数组如果没有初始化，调用resize方法初始化

  • 数组初始化了，找数组下标[(length - 1) & h]，数组第一个位置是否有数据？

    • 没有，直接插入

  • 有数据，equals比较key相同，value覆盖

  • 有数据，equals比较key不同，判断数据结构

    • 无限循环，如果是红黑树的数据结构，插入红黑树[putTreeVal]
    • 无限循环，链表结构
      • equals比较key一样，跳出循环
      • equals key不一样，e = p.next[p是当前节点]，头插[ p.next = newNode(hash, key, value, null);]，循环比较key次数超过8[也就是链表数据大于8]，树化[treeifyBin(tab, hash)][tab是数组][大于64个数据树化，否则直接扩容]
  • 有数据，上面的循环节点e不为空，value覆盖
  • 判断size是否大于容量*负载因子，是的话，扩容，不是的话，结束流程
1.8扩容

旧负载容量=旧容量*负载因子

扩容后的位置 = 原位置 or 原位置 + 旧容量

  • 初始化数组
  • 扩容数组
    • 超过最大容量不动
    • 没有超过最大容量，定义新容量数组，新负载容量
    • 循环旧负载容量次，往新数组插入数据

      • 数组第一位没有数据，直接插入

      • 红黑树类型[split方法]，找到相同hash落点的树，判断树上面的节点是不是小于6个，如果小于，变成链表[一个树10个元素，扩容后分成两个落点，这个数就变成了链表] [树的结构和链表结构是互通的]

      • 链表结构，构建所有原位置的链表数据，构建所有新位置[原位置 + 旧容量]的链表数据，也就是构建好了扩容后的所有链表数据

设计的好处
  • 扩容后，某个落点的数据，不可能比之前的多，因为位置只会是原位置or原位置+旧容量，以前不在一个落点，扩容后，肯定也不在一个落点，所以在扩容时整理落点的链表数据是不存在树化的情况的。
  • 在插入红黑树的过程中，数组是没有扩容逻辑的，只有插入完数据，才会比较是不是达到了负载容量，如果达到，此时进行扩容。
jdk7和jdk8的区别

  • 增加了红黑树数据结构，时间复杂度从O(n)降到了O(logN)

    • 当链表长度 > 8时，转换成红黑树

  • 根据传入的key计算hash

    • hashCode方法

    • 1.7 扰动处理 =9次扰动 =4次位运算 + 5次异或运算

      static final int hash(int h) {
	h ^= k.hashCode(); 
	h ^= (h >>> 20) ^ (h >>> 12); 
	return h ^ (h >>> 7) ^ (h >>> 4); 
}

    • 1.8扰动处理 =2次扰动 =1次位运算 + 1次异或运算

      static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
  • put的时候插入方式
    • 1.7 链表头插 [为什么不插到后面，因为时间复杂度是o(n)]
    • 1.8 判定数据结构是链表还是红黑树（优先判断），如果不是红黑树，链表尾插

  • 扩容

    • 1.7 不插入新数据
    • 1.8 插入

  • 扩容后存储位置的计算方式

    • 1.8 扩容后的位置 = 原位置 or 原位置 + 旧容量
    • 1.7 hashCode() & length -1
解决hash碰撞

  • hash算法

    • hashCode计算方式
    • 扰动函数优化（扰动次数减少，1.8 高低16位异或）
  • 扩容机制
  • 数据结构
    • 拉链法 ，头插
    • 拉链法，尾插，红黑树
      不安全

  • put的时候数据覆盖

  • resize形成环形链表，当相同的hash落点寻找时，死循环
红黑树
  • TreeNode继承LinkedHashMap.Entry<K,V>
  • 最小树形化阈值，当哈希表中的容量 > 该值时，才允许将链表转换成红黑树，否则桶内元素太多，直接扩容，而不是树形化，为了避免扩容，树形化选择的冲突值不能小于 4 * TREEIFY_THRESHOLD [8]，即不能小于32，每次扩容是2的倍数，所以小于64不树形化
  • 桶的树形化域 == 8
  • 桶的链表还原 == 6 ，resize时，数据重新计算落点，当原有红黑树的数量 < 6，变成链表
迭代器快速失败策略
  • 修改次数modCount，迭代器初始化时将该值赋值给expectModCount变量，迭代时判断两个值是否相同，不同代表有人修改了hashMap
位运算

& 两位都是1，才是1 ，其余都是0

^ 相同为0，不同为1

落点问题
  • 为什么不直接采用hashcode处理的哈希码作为存储数组table的下标位置
  • 数组长度为什么要是2的倍数呢
  • 为什么采用哈希码 & （数组长度 - 1）计算数组下标
  • 为什么在计算数组下标前，需要哈希码进行二次处理：扰动处理？
落点问题解决

根本原因是为了提高K,V的随机性，分布均匀性，尽量避免hash冲突！！！

  • 问题1回答：如果出现哈希码（2^31 -1）与数组大小(2^30)范围不匹配的情况，哈希码可能不在数组大小范围内，所以采用 & （数组长度 - 1）
  • 实际是哈希码 % 数组长度，但是 %的效率低，为了提高运算率，只有长度是2的幂， %才和&（length-1）对等
  • 如果不是length-1,那么最后一位一定是0，hash落点全都落在了偶数位，冲突加大，容量小一半，解决问题1
  • 加大哈希码低位的随机性，减小hash冲突

reference：

https://www.jianshu.com/p/8324a34577a0

https://www.jianshu.com/p/e2f75c8cce01

https://www.jianshu.com/p/7fb0b940556d

CurrentHashMap

结构
  • jdk7：segment数组+hashEntry数组，并发用ReentrantLock
  • jdk8：摒弃segment的概念，Node数组，链表，红黑树，并发用Synchronized和CAS来操作
    • Node（链表）只能查不能改，继续Map.Entry
    • TreeNode（红黑树）继承Node
    • TreeBin是封装TreeNode的容器，提供转换红黑树的条件和锁控制
put
  • jdk7：segment实现了ReentrantLock，对key的hash定位segment的位置，如果segment没有初始化，通过cas操作赋值，然后第二次hash找到HashEntry，插入时，tryLock方法获取锁，如果成功插入尾部，失败自旋获取锁，超过指定次数就挂起，等待被唤醒
size
  • jdk7：并发导致size不准，方案一：不加锁尝试计算size，最多三次，比较前后两次结果，一致认为没有数据插入，准确；方案二：如果方案一不符合，给每个segment加上锁，然后计算size
思考
  • 在粗粒度加锁中ReentrantLock通过Condition来控制各个低粒度的边界，锁粒度降低了，低粒度的加锁方式，synchronized并不比ReentrantLock差
1.8-put逻辑
  • 求hash值，扰动函数相比较hashmap多了一次位运算
HASH_BITS=0x7fffffff;
(h ^ (h >>> 16)) & HASH_BITS;

  • 无限循环

  • 数组如果为空，初始化数组

    cas将sizeCtl设置为-1，代表抢到了锁，可要进行数组的初始化，如果并发[sizeCtl不是负数，调用thread.yield使当前线程从执行状态变成就绪状态，之后所有线程再重新竞争]，设置sizeCtl为负载容量

  • 如果数组不为空，找数组下标：(length - 1) & h，cas操作将新值放入数组头元素，如果，结束循环；失败，下次循环。

  • hash值如果是-1[MOVED]

    helpTransfer

  • 获取数组头结点的监视器锁，上锁[synchronized (f)]

    static final int MOVED     = -1; // hash for forwarding nodes
static final int TREEBIN   = -2; // hash for roots of trees
static final int RESERVED  = -3; // hash for transient reservations
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash

    • 头结点的hash值大于0，说明是链表

      binCount记录链表的长度

      无限循环数组头结点的链表结构

      • equals比较key一样，value覆盖
      • 在无限循环的逻辑中，找到链表的最末端，进行尾插，结束循环

    • 判断头结点是否是红黑树

      把元素插入红黑树

  • 判断在插入链表的时候，插入次数是否大于8，如果是，树化[数组容量小于64，直接扩容；如果不是，锁数组头结点Node，插入树(比1.8的hashmap多了一个上锁逻辑)]，结束无限循环的逻辑

1.8-put逻辑-扩容[tryPresize(int size)]

  • 生成rs时间戳

  • 传递进来的size已经是扩容的了，判断是否超过数组最大限制，超过不出来，没超过size的1.5倍再加1，再往上取最近的2的n次方。

  • 当旧的负载容量[sc]小于0

    • 只有一个线程扩容时，rs左移RESIZE_STAMP_SHIFT位+2，sc就变成了一个负数，此时sc的高16位为时间戳，低16位是扩容线程数

    • 多个线程扩容的时候

      • 比较sc高16位生成的时间戳是不是和rs一样，不一样结束
  • 当前扩容线程数是否超过了最大扩容线程数，结束
    • transferIndex小于等于0或者nextTab是null，结束
    • 其余的情况，cas将sc加1，调用transfer
  • 当旧的负载容量大于0，将sc设置为rs左移RESIZE_STAMP_SHIFT位+2[为一个负数]，调用transfer
1.8-put逻辑-transfer

  • advance：数组一层层推进的标识符

  • 核数
    • 单核[单线程]stride[步数]=数组长度
    • 多核[多线程]stride=n»>3/NCPU，最小是16
  • 如果需要初始化，则初始化[helpTransfer调用时]
  • 无限循环
    • 找到当前线程需要负责的桶区间。
    • 扩容完成，清空临时变量，更新table。
    • 扩容没有完成，但是已经没有可以领取的区间了，当前线程退出，sc减1，表示扩容线程少了一个，如果减完这个数以后，sizeCtl 回归了初始状态，表示没有线程再扩容了，该方法所有的线程扩容结束了。
    • 如果当前位置为空，写进fwd，如果成功，推进。
    • 如果当前位置不为空，hash==-1，代表当前桶已经完成扩容和数据迁移操作。
    • 锁住头结点，判断是链表还是红黑树，分别进行迁移
      • 链表，因为两个落点，分别准备好两个链表放在数组下标下。
      • 红黑树，插入，有可能链表化

reference http://www.importnew.com/28263.html

CopyOnWriteArrayList

写时复制容器，往容器新增元素的时候（上锁），不往容器加，将当前容器复制出来一个新的容器，往新的容器里面加元素，加完之后，将原容器的引用指向新的容器，好处是可以对这个容器进行并发的读，不需要加锁，也是读写分离的一种思想，但是如果读的时候有线程向容器加数据，此时读到的还是旧数据，因为写的时候不会锁住旧的容器。

缺点：新旧容器，如果数据大会产生很多内存垃圾，引起gc，不好

​ 只能保证最终一致性，不能保证数据的实时一致性

队列

  • 阻塞
    • offer：将元素e插入到队列末尾
    • poll：移除并获取队首元素
    • peek：获取队首元素
  • 非阻塞（ArrayBlockingQueue）
    • put：向队列尾部插入元素，满了则等待
    • take：从队首取元素，为空则等待

Lock

reference：https://www.cnblogs.com/takumicx/p/9402021.html

blog comments powered by Disqus