Map源码深入分析
2021-03-14 16:20:45 0 举报AI智能生成
登录查看完整内容
主要描述HashMap和ConcurrentHashMap的原理过程
作者其他创作
大纲/内容
ConcurrentHashMap敬请期待
集合
HashMap（JDK1.8）
重要属性解析
DEFAULT_INITIAL_CAPACITY = 1 << 4
默认的初始容量（容量为HashMap中槽的数目）是16，且实际容量必须是2的整数次幂
MAXIMUM_CAPACITY = 1 << 30
最大容量（必须是2的幂且小于2的30次方，传入容量过大将被这个值替换）
TREEIFY_THRESHOLD = 8
JDK1.8 新加，Entry链表最大长度，当桶中节点数目大于该长度时，会进一步判断数组长度，将链表转成红黑树存储；
UNTREEIFY_THRESHOLD = 6
JDK1.8 新加，当桶中节点数小于该长度，将红黑树转为链表存储；
MIN_TREEIFY_CAPACITY = 64
桶可能被转化为树形结构的最小容量。当哈希表的大小超过这个阈值，才会把链式结构转化成树型结构，否则仅采取扩容来尝试减少冲突。
DEFAULT_LOAD_FACTOR = 0.75f
默认加载因子0.75，如果当前键值对个数 >= HashMap最大容量*装填因子，进行reSize操作
modCount
hashmap结构被修改的次数（add、remove），fail-fast机制
如果你在foreach遍历时，自动调用迭代器的迭代方法，此时在遍历过程中调用了font color=\"#c41230\
使用iterator迭代器的形式，是通过迭代器自身的 remove 或 add 方法从结构上对列表进行修改，两次对比modCount相同，不会报错
table
哈希桶数组，分配的时候，table的长度总是2的幂
size
实际存储的数量，则HashMap的size()方法，实际返回的就是这个值，isEmpty()也是判断该值是否为0
threshold
HashMap的扩容阈值，在HashMap中存储的Node键值对超过这个数量时，自动扩容容量为原来的二倍
loadFactor
HashMap的负加载因子，可计算出当前table长度下的扩容阈值：threshold = loadFactor * table.length
分析
加载因子越大
优点
装载元素越多，空间利用率高
缺点
冲突概率增大，链表变长，查找效率变低
加载因子越小
冲突概率变小，链表小，查找效率高
装载元素少，空间利用率低
频繁扩容，耗费性能
基础位运算
HashMap中涉及很多位运算，需要提前了解一些
数据结构
JDK1.7
数组 + 链表
JDK1.8
数组 + 链表 + 红黑树
引入红黑树的原因
解决链表过长导致的查找效率低问题，时间复杂度O(n)
利用红黑树的快速增删查能力，时间复杂度：O(log(n))
元素
JDK1.6用Entry描述键值对，JDK1.8中用Node代替Entry
数组
实际数组是2幂次，默认初始化16，图缩减一下
链表
红黑树
特性
红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高
核心方法
root：获取红黑树的根
moveRootToFront：确保root是桶中的第一个元素 ，将root移到红黑树中的第一个
find：查找hash为h，key为k的节点
getTreeNode：获取树节点，通过根节点查找
tieBreakOrder：比较2个对象的大小
treeify：将链表转为二叉树
untreeify：将二叉树转为链表
split：分割红黑树
rotateLeft：左旋转
rotateRight：右旋转
balanceDeletion：删除后调整平衡
checkInvariants：检测是否符合红黑树
结构
操作原理
HashMap：构造器
HashMap()
指定的默认初始化容量（16）和默认加载因子DEFAULT_LOAD_FACTOR（0.75）构造一个空HashMap
HashMap(int initialCapacity)
指定的初始化容量initial capacity和默认加载因子DEFAULT_LOAD_FACTOR（0.75）构造一个空HashMap
指定的初始化容量initial capacity 和加载因子load factor构造一个空HashMap
hash：哈希计算
概要
计算key的hash值，为了定位在哈希表（数组）上的位置（下标）
将 键key 转换成 哈希码（hash值）操作 = 使用hashCode() + 4次位运算 + 5次异或运算 =（9次扰动）
将 键key 转换成 哈希码（hash值）操作 = 使用hashCode() + 1次位运算 + 1次异或运算 =（2次扰动）
主要流程
取key的hashCode
key的hashCode高16位异或低16位
将第一步和第二步得到的结果进行取与运算。
核心代码
若是key为null时，hashCode = 0
tableSizeFor：数组大小格式化
先移位再或运算，最终保证返回值是2的整数幂
通俗：n的进制一直向右移动，让n进制的右边全为1，再加上1，则满足2的幂次
先移位，再或运算
重复上一步骤，一直向右移动，为了保持二进制全为1，并且是1、2、4、8、16为阶段，最终保证返回值是2的整数幂
保证n小于最大容量（必须是2的幂且小于2的30次方，传入容量过大将被这个值替换）
getNode：获取节点
据key的哈希值和key获取对应的节点
如果哈希表为空，或key对应的桶为空，返回null
如果桶中的第一个节点就和指定参数hash和key匹配上了，返回这个节点
如果桶中的第一个节点没有匹配上，而且有后续节点
如果当前的桶采用红黑树，则调用红黑树的get方法去获取节点
如果当前的桶不采用红黑树，即桶中节点结构为链式结构，遍历链表，直到key匹配
找到节点返回null，否则返回null
get：获取
返回指定的key映射的value，如果value为null，则返回nul
hash(Object key)
通过hash(Object key)方法计算key的哈希值hash
如果node为null，返回null，否则返回node.value
containsKey：是否存在key
如果map中含有key为指定参数key的键值对，返回true，否则false。主体流程与get方法类似
判断node是否为空NULL，不为空返回true，为空返回false
put：添加元素
将指定参数key和指定参数value插入map中，如果key已经存在，那就替换key对应的value，返回oldValue
通过hash(Object key)方法计算key的哈希值
如果哈希表为空，调用resize()创建一个哈希表
注意：这里说明开始只创建里HashMap对象，第一次调用put才创建哈希表（数组）
JDK1.7在数组为空时，会调用inflateTable初始化
JDK1.8是直接调用resize，在里面做了初始化，oldcap = 0
如果指定参数hash在表中没有对应的桶，即为没有碰撞，直接将键值对插入到哈希表中即可
如果有碰撞，遍历桶，找到key映射的节点
比较链表中第一个元素(数组中的结点)的hash值相等，key相等
遍历链表中无该键值对，且链表是红黑树结构，按照红黑树结构插入
如果不是红黑树，那么就肯定是链表。遍历链表，如果找到了key映射的节点，就记录这个节点，退出循环。如果没有找到，在链表尾部插入节点。插入后，如果链的长度大于等于TREEIFY_THRESHOLD这个临界值，则使用treeifyBin方法把链表转为红黑树。
头插法
在头部插入（数组位置），向下移动行为
出现循环链表的主要原因：并发导致，两个线程都在扩容，链表复制的过程中，一先一后可能导致链表循环，最终影响到get或者put的时候碰到这个循环链表就会可能出现死循环
尾插法
遍历到尾部，是null，则在尾部插入
如果找到了key映射的节点，且节点不为null
记录节点的vlaue
如果参数onlyIfAbsent为false，或者oldValue为null，替换value，否则不替换
返回记录下来的节点的value
如果没有找到key映射的节点，则为插入，插入节点后size会加1，这时要检查size是否大于临界值threshold，大于则进行resize扩容
先扩容，再插入
先插入，再扩容
元素插入
元素插入之后
resize：扩容或初始化
如果对table扩容，因为每次扩容都是翻倍，与原来计算（n-1）&hash的结果相比，节点要么就在原来的位置，要么就被分配到“原位置+旧容量”这个位置
获取原来数组的长度判断是扩容还是初始化
扩容：计算扩容后的容量，临界值
初始化：如果旧容量 <= 0，且旧临界值 <= 0，新容量扩充为默认初始化容量，新临界值为DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY
单独的函数：inflateTable
与扩容集成在一起：resize
将hashMap的临界值修改为扩容后的临界值
根据扩容后的容量新建数组，然后将hashMap的table的引用指向新数组
如果旧table不为空，将旧table中的元素复制到新的table中
遍历旧哈希表的每个桶，将旧哈希表中的桶复制到新的哈希表中
如果旧桶中只有一个node，直接计算新位置，放入元素
如果旧桶中的结构为红黑树，做红黑树的分割，重新定位
关键先理解hash定位 ，这个需要和哈希表（数组定位有关）运算，不管key的hash多长，有效长度只与tab长度有关，定位：原位置 Or 原位置 + 旧容量
按照原先的方式重新计算定位
按照相应的规律进行计算 “原位置 Or 原位置 + 旧容量”
remove：移除元素
删除hashMap中key映射的node，先计算出node，再根据node所在条件删除
通过 hash(Object key)方法计算key的哈希值
通过 removeNode 方法实现功能
如果数组table为空或key映射到的桶为空，返回null
如果key映射到的桶上第一个node的就是要删除的node，记录下来
如果桶内不止一个node，且桶内的结构为红黑树，记录key映射到的node。
桶内的结构不为红黑树，那么桶内的结构就肯定为链表，遍历链表，找到key映射到的node，记录下来
如果被记录下来的node不为null，删除对应类型的node，size-1被删除
返回被删除的node的value
treeifyBin：链表转红黑树
概述
主要功能为符合条件的链表变成双向链表再转为红黑树
如果桶数组table为空，或者桶数组table的长度小于MIN_TREEIFY_CAPACITY = 64，不符合转化为红黑树的条件
不满足会进行扩容resize操作
如果符合转化为红黑树的条件，而且hash对应的桶不为null
遍历链表，替换链表node为树TreeNode，建立双向链表
遍历链表插入每个节点到红黑树
ConcurrentHashMap（JDK1.8）
MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1
help resize的最大线程数 max 65535
MOVED = -1
检查table[i]的节点的hash是否等于MOVED，如果等于，则检测到正在扩容
TREEBIN = -2
标志数组的下标存放的是树结构
RESERVED = -3
临时保留的哈希值
HASH_BITS = 0x7fffffff
哈希的首位置0操作，二进制只有首位为0
NCPU = Runtime.getRuntime().availableProcessors()
可用处理器数量
扩容时用于存放数据的变量，扩容完成后会置为null
transient volatile long baseCount
记录容器的容量大小，通过CAS更新
transient volatile CounterCell[] counterCells
counter cell表，长度总为2的幂次，主要是baseCount的CAS操作失败再用CountCells去加
transient volatile int sizeCtl
正数或0代表hash表还没有被初始化，这个数值表示初始化或下一次进行扩容的大小，类似于扩容阈
它的值始终是当前ConcurrentHashMap容量的0.75倍，这与loadfactor是对应的。实际容量>=sizeCtl，则扩容
JDK1.8的数据结构跟HashMap差不多
JDK1.7数据结构
Unsafe详解
简介
Unsafe在JUC(java.util.concurrent)包中大量使用(主要是CAS)，在netty中方便使用直接内存，还有一些高并发的交易系统为了提高CAS的效率也有可能直接使用到Unsafe
Java无法直接访问到操作系统底层（如系统硬件等)，为此Java使用native方法来扩展Java程序的功能。Unsafe类提供了硬件级别的原子操作，提供了一些绕开JVM的更底层功能，由此提高效率
使用建议
Unsafe有可能在未来的Jdk版本移除或者不允许Java应用代码使用，这一点可能导致使用了Unsafe的应用无法运行在高版本的Jdk。
Unsafe的不少方法中必须提供原始地址(内存地址)和被替换对象的地址，偏移量要自己计算，一旦出现问题就是JVM崩溃级别的异常，会导致整个JVM实例崩溃，表现为应用程序直接crash掉。
Unsafe提供的直接内存访问的方法中使用的内存不受JVM管理(无法被GC)，需要手动管理，一旦出现疏忽很有可能成为内存泄漏的源头。
Unsafe初始化方式
代码
初始化的代码主要包括调用JVM本地方法registerNatives()和sun.reflect.Reflection#registerMethodsToFilter。然后新建一个Unsafe实例命名为theUnsafe，通过静态方法getUnsafe()获取，获取的时候需要做权限判断。由此可见，Unsafe使用了单例设计(可见构造私有化了)。Unsafe类做了限制，如果是普通的调用的话，它会抛出一个SecurityException异常；只有由主类加载器(BootStrap classLoader)加载的类才能调用这个类中的方法。最简单的使用方式是基于反射获取Unsafe实例。
使用详解
类、对象和变量相关方法
getObject
通过给定的Java变量获取引用值。这里实际上是获取一个Java对象o中，获取偏移地址为offset的属性的值，此方法可以突破修饰符的抑制，也就是无视private、protected和default修饰符。类似的方法有getInt、getDouble等等
putObject
将引用值存储到给定的Java变量中。这里实际上是设置一个Java对象o中偏移地址为offset的属性的值为x，此方法可以突破修饰符的抑制，也就是无视private、protected和default修饰符。类似的方法有putInt、putDouble等等
getObjectVolatile
此方法和上面的getObject功能类似，不过附加了'volatile'加载语义，也就是强制从主存中获取属性值。类似的方法有getIntVolatile、getDoubleVolatile等等。这个方法要求被使用的属性被volatile修饰，否则功能和getObject方法相同
putObjectVolatile
此方法和上面的putObject功能类似，不过附加了'volatile'加载语义，也就是设置值的时候强制(JMM会保证获得锁到释放锁之间所有对象的状态更新都会在锁被释放之后)更新到主存，从而保证这些变更对其他线程是可见的。类似的方法有putIntVolatile、putDoubleVolatile等等。这个方法要求被使用的属性被volatile修饰，否则功能和putObject方法相同
putOrderedObject
设置o对象中offset偏移地址offset对应的Object型field的值为指定值x。这是一个有序或者有延迟的putObjectVolatile方法，并且不保证值的改变被其他线程立即看到。只有在field被volatile修饰并且期望被修改的时候使用才会生效。类似的方法有putOrderedInt和putOrderedLong。
staticFieldOffset
返回给定的静态属性在它的类的存储分配中的位置(偏移地址)。不要在这个偏移量上执行任何类型的算术运算，它只是一个被传递给不安全的堆内存访问器的cookie。注意：这个方法仅仅针对静态属性，使用在非静态属性上会抛异常。下面源码中的方法注释估计有误，staticFieldOffset和objectFieldOffset的注释估计是对调了，为什么会出现这个问题无法考究
objectFieldOffset
返回给定的非静态属性在它的类的存储分配中的位置(偏移地址)。不要在这个偏移量上执行任何类型的算术运算，它只是一个被传递给不安全的堆内存访问器的cookie。注意：这个方法仅仅针对非静态属性，使用在静态属性上会抛异常
staticFieldBase
ensureClassInitialized
检测给定的类是否已经初始化。通常需要使用在获取一个类的静态属性的时候(因为一个类如果没初始化，它的静态属性也不会初始化)。
shouldBeInitialized
检测给定的类是否需要初始化。通常需要使用在获取一个类的静态属性的时候(因为一个类如果没初始化，它的静态属性也不会初始化)。 此方法当且仅当ensureClassInitialized方法不生效的时候才返回false
arrayBaseOffset
返回数组类型的第一个元素的偏移地址(基础偏移地址)。如果arrayIndexScale方法返回的比例因子不为0，你可以通过结合基础偏移地址和比例因子访问数组的所有元素。Unsafe中已经初始化了很多类似的常量如ARRAY_BOOLEAN_BASE_OFFSET等
arrayIndexScale
返回数组类型的比例因子(其实就是数据中元素偏移地址的增量，因为数组中的元素的地址是连续的)。此方法不适用于数组类型为\"narrow\"类型的数组，\"narrow\"类型的数组类型使用此方法会返回0(这里narrow应该是狭义的意思，但是具体指哪些类型暂时不明确，笔者查了很多资料也没找到结果)。Unsafe中已经初始化了很多类似的常量如ARRAY_BOOLEAN_INDEX_SCALE等
defineClass
告诉JVM定义一个类，返回类实例，此方法会跳过JVM的所有安全检查。默认情况下，ClassLoader(类加载器)和ProtectionDomain(保护域)实例应该来源于调用者。
defineAnonymousClass
1、VM Anonymous Class可以看作一种模板机制，如果程序要动态生成很多结构相同、只是若干变量不同的类的话，可以先创建出一个包含占位符常量的正常类作为模板，然后利用sun.misc.Unsafe#defineAnonymousClass()方法，传入该类(host class，宿主类或者模板类)以及一个作为\"constant pool path\"的数组来替换指定的常量为任意值，结果得到的就是一个替换了常量的VM Anonymous Class。2、VM Anonymous Class从VM的角度看是真正的\"没有名字\"的，在构造出来之后只能通过Unsafe#defineAnonymousClass()返回出来一个Class实例来进行反射操作。还有其他几点看以自行阅读。这个方法虽然翻译为\"定义匿名类\"，但是它所定义的类和实际的匿名类有点不相同，因此一般情况下我们不会用到此方法。在Jdk中lambda表达式相关的东西用到它，可以看InnerClassLambdaMetafactory这个类
allocateInstance
通过Class对象创建一个类的实例，不需要调用其构造函数、初始化代码、JVM安全检查等等。同时，它抑制修饰符检测，也就是即使构造器是private修饰的也能通过此方法实例化
内存管理
addressSize
获取本地指针的大小(单位是byte)，通常值为4或者8。常量ADDRESS_SIZE就是调用此方法
pageSize
获取本地内存的页数，此值为2的幂次方
allocateMemory
分配一块新的本地内存，通过bytes指定内存块的大小(单位是byte)，返回新开辟的内存的地址。如果内存块的内容不被初始化，那么它们一般会变成内存垃圾。生成的本机指针永远不会为零，并将对所有值类型进行对齐。可以通过freeMemory方法释放内存块，或者通过reallocateMemory方法调整内存块大小。bytes值为负数或者过大会抛出IllegalArgumentException异常，如果系统拒绝分配内存会抛出OutOfMemoryError异常
freeMemory
freeMemory方法释放内存块
reallocateMemory
通过指定的内存地址address重新调整本地内存块的大小，调整后的内存块大小通过bytes指定(单位为byte)。可以通过freeMemory方法释放内存块，或者通过reallocateMemory方法调整内存块大小。bytes值为负数或者过大会抛出IllegalArgumentException异常，如果系统拒绝分配内存会抛出OutOfMemoryError异常
setMemory
多线程同步
monitorEnter
锁定对象，必须通过monitorExit方法才能解锁。此方法经过实验是可以重入的，也就是可以多次调用，然后通过多次调用monitorExit进行解锁
monitorExit
解锁对象，前提是对象必须已经调用monitorEnter进行加锁，否则抛出IllegalMonitorStateException异常
tryMonitorEnter
尝试锁定对象，如果加锁成功返回true，否则返回false。必须通过monitorExit方法才能解锁。
compareAndSwapObject
针对Object对象进行CAS操作。即是对应Java变量引用o，原子性地更新o中偏移地址为offset的属性的值为x，当且仅的偏移地址为offset的属性的当前值为expected才会更新成功返回true，否则返回false。o：目标Java变量引用。offset：目标Java变量中的目标属性的偏移地址。expected：目标Java变量中的目标属性的期望的当前值。x：目标Java变量中的目标属性的目标更新值。类似的方法有compareAndSwapInt和compareAndSwapLong，在Jdk8中基于CAS扩展出来的方法有getAndAddInt、getAndAddLong、getAndSetInt、getAndSetLong、getAndSetObject，它们的作用都是：通过CAS设置新的值，返回旧的值
线程的挂起和恢复
unpark
释放被park创建的在一个线程上的阻塞。这个方法也可以被使用来终止一个先前调用park导致的阻塞。这个操作是不安全的，因此必须保证线程是存活的(thread has not been destroyed)。从Java代码中判断一个线程是否存活的是显而易见的，但是从native代码中这机会是不可能自动完成的
park
阻塞当前线程直到一个unpark方法出现(被调用)、一个用于unpark方法已经出现过(在此park方法调用之前已经调用过)、线程被中断或者time时间到期(也就是阻塞超时)。在time非零的情况下，如果isAbsolute为true，time是相对于新纪元之后的毫秒，否则time表示纳秒。这个方法执行时也可能不合理地返回(没有具体原因)。并发包java.util.concurrent中的框架对线程的挂起操作被封装在LockSupport类中，LockSupport类中有各种版本pack方法，但最终都调用了Unsafe#park()方法
内存屏障
loadFence
在该方法之前的所有读操作，一定在load屏障之前执行完成
storeFence
在该方法之前的所有写操作，一定在store屏障之前执行完成
fullFence
在该方法之前的所有读写操作，一定在full屏障之前执行完成，这个内存屏障相当于上面两个(load屏障和store屏障)的合体功能
其他
getLoadAverage
获取系统的平均负载值，loadavg这个double数组将会存放负载值的结果，nelems决定样本数量，nelems只能取值为1到3，分别代表最近1、5、15分钟内系统的平均负载。如果无法获取系统的负载，此方法返回-1，否则返回获取到的样本数量(loadavg中有效的元素个数)。实验中这个方法一直返回-1，其实完全可以使用JMX中的相关方法替代此方法
throwException
绕过检测机制直接抛出异常
ConcurrentHashMap：构造器
ConcurrentHashMap()
默认构造器
ConcurrentHashMap(int initialCapacity)
指定初始化容量的构造函数
指定初始化容量和加载因子大小的构造函数
创建与给定map具有相同映射的新map
spread：哈希计算
key的哈希值计算，与HashMap类似，多了一步HASH_BITS 与操作
最后再跟HASH_BITS进行取与操作
主要操作为了将左边第一位置为0，0为非负数
tableSizeFor：哈希数组的大小格式化
与HashMap完全一致
tabAt：获取指定节点元素
获得在i位置上的Node节点
算出在i位置上的内存偏移地址：((long) i << ASHIFT) + ABASE
利用Unsafe的原子操作：getObjectVolatile 获取元素
font color=\"#c41230\
casTabAt：利用CAS比较插入元素
利用CAS算法设置i位置上的Node节点（将c和table[i]比较，相同则插入v）
利用Unsafe的CAS原子操作：compareAndSwapObject 插入元素
setTabAt：直接插入元素
利用volatile特性，设置第i个节点的值，强制更新到主内存，可见性、这个操作一定是成功的
利用Unsafe的插入元素：putObjectVolatile
sumCount：获取元素总数
获取集合总大小 = baseCount + counterCells的有效数据
先获取baseCount的大小
再遍历counterCells数组中元素的大小，加一起，得到总数
get：获取元素
根据key在Map中找出其对应的value，如果不存在key，则返回null，其中key不允许为null，否则抛异常对于节点可能在链表或树上的情况，需要分别去查找
spread：算出key的hash值定位，算法为(h ^ (h >>> 16)) & HASH_BITS
根据hash值Unsafe.getObjectVolatile确定节点位置，数组和节点元素存在，则返回null
如果节点Node的hash值eh<0 说明这个节点在树上 直接寻找
否则遍历链表 找到对应的值并返回
containsKey：是否包含key
检查table中是否含有key
直接调用get(int key)方法即可，如果有返回值，则说明是包含key的
containsValue：是否含有value
value 若为null 抛空指针异常
遍历数组，一个个返回，匹配则返回；如果没有，则返回null
putVal：插入元素
将key和value插入map中，两者不能为空，存在key则返回value，不存在插入
检查key/value是否为空，如果为空，则抛异常
获取key的哈希值，两次hash，减少hash冲突，可以均匀分布
检查是否初始化了，如果没有，则初始化
for无限循环，CAS经典写法，不成功无限重试
如果table[i]==null(即该位置的节点为空，没有发生碰撞)，则利用CAS操作直接存储在该位置，如果CAS操作成功则退出死循环，失败则继续循环
检查table[i]的节点的hash是否等于MOVED，如果等于，则检测到正在扩容，则帮助其扩容
table[i]的节点的hash值不等于MOVED，针对首个节点进行加锁操作，而不是segment，进一步减少线程冲突
如果头元素f的哈希值fh>=0，则是链表结构
如果在链表中找到值为key的节点e，直接设置e.val = value即可
如果没有找到值为key的节点，直接新建Node并加入链表即可
插入到链表末尾并跳出循环
如果首节点为TreeBin类型，说明为红黑树结构，执行putTreeVal操作
initTable：初始化哈希表
主要是利用sizeCtl进行初始化的状态维护
判断哈希表是否为空，是否需要进行初始化
若sizeCtl < 0 说明已经正在初始化的，把当前线程让出CPU自旋一下，所以当前线程就先让出CPU时间片，等待下次的系统调度，再次走上面的while判断
将SIZECTL用Unsafe的compareAndSwapInt方法设置为-1，代表正在初始化中
再次判断哈希表是否为空，防止并发情况，还没设置table的值，下一个线程进了位置一，刚刚好又设置位置二，就会有可能进来，需要判断
位置2、计算当前哈希表的阀值，与loadfactor是对应，tab为16，则sizeCtl设置12
addCount：增加计数
主要增加计数，先尝试计数，不成功则其他重试，再判断是否需要扩容
如果并发导致 baseCount CAS 失败了使用 counterCells
如果counterCells CAS 失败了，在 fullAddCount 方法中，会继续死循环操作，直到成功
判断是否是新增，删除是-1
判断是否需要扩容，sizeCtl是扩容阈值
transfer：扩容
主要检查分割哈希表，逐块领取扩容
计算每次任务数量大小：根据哈希表大小(n >>> 3) / NCPU 若小于最小值MIN_TRANSFER_STRIDE 则按照MIN_TRANSFER_STRIDE 16大小去分配每次分配任务大小否则以(n >>> 3) / NCPU 大小去分配这样以便其他线程帮助扩容（在大数据量中）
nextTab == null 说明是第一次 ，刚开始扩容
定义一个ForwardingNode，并把hash变成了MOVED，当线程发现此下标的hash是MOVED，就知道了，这个下标正在扩容，会帮助扩容
领取任务：
说明--i < bound，表示最后一份任务完成了
用CAS去标志TRANSFERINDEX，成功即代表该线程领取任务成功，并把TRANSFERINDEX更新成剩下的区间，最后一份任务是0，帮助扩容也是从这个TRANSFERINDEX获取的任务
执行扩容：
锁住下标的头节点
判断是链表还是红黑树，采取不同的方式扩容
链表：有两个循环主要为了减少new Node的情况
红黑树：与HashMap一致
计算任务数
领取任务
执行扩容
0 条评论
回复 删除
下一页
