Map源码深入分析

加载因子越大

加载因子越小

引入红黑树的原因

若是key为null时，hashCode = 0

通俗：n的进制一直向右移动，让n进制的右边全为1，再加上1，则满足2的幂次

如果当前的桶采用红黑树，则调用红黑树的get方法去获取节点

如果当前的桶不采用红黑树，即桶中节点结构为链式结构，遍历链表，直到key匹配

通过hash(Object key)方法计算key的哈希值hash

通过getNode( int hash, Object key)方法获取node

通过hash(Object key)方法计算key的哈希值hash

通过getNode( int hash, Object key)方法获取node

注意：这里说明开始只创建里HashMap对象，第一次调用put才创建哈希表（数组）

比较链表中第一个元素(数组中的结点)的hash值相等，key相等

遍历链表中无该键值对，且链表是红黑树结构，按照红黑树结构插入

如果不是红黑树，那么就肯定是链表。遍历链表，如果找到了key映射的节点，就记录这个节点，退出循环。如果没有找到，在链表尾部插入节点。插入后，如果链的长度大于等于TREEIFY_THRESHOLD这个临界值，则使用treeifyBin方法把链表转为红黑树。

记录节点的vlaue

如果参数onlyIfAbsent为false，或者oldValue为null，替换value，否则不替换

返回记录下来的节点的value

元素插入之后

扩容：计算扩容后的容量，临界值

初始化：如果旧容量 <= 0，且旧临界值 <= 0，新容量扩充为默认初始化容量，新临界值为DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY

遍历旧哈希表的每个桶，将旧哈希表中的桶复制到新的哈希表中

如果旧桶中只有一个node，直接计算新位置，放入元素

如果旧桶中的结构为红黑树，做红黑树的分割，重新定位

如果旧桶中的结构为链表,链表重排

如果数组table为空或key映射到的桶为空，返回null

如果key映射到的桶上第一个node的就是要删除的node，记录下来

如果桶内不止一个node，且桶内的结构为红黑树，记录key映射到的node。

桶内的结构不为红黑树，那么桶内的结构就肯定为链表，遍历链表，找到key映射到的node，记录下来

如果被记录下来的node不为null，删除对应类型的node，size-1被删除

不满足会进行扩容resize操作

通过给定的Java变量获取引用值。这里实际上是获取一个Java对象o中，获取偏移地址为offset的属性的值，此方法可以突破修饰符的抑制，也就是无视private、protected和default修饰符。类似的方法有getInt、getDouble等等

将引用值存储到给定的Java变量中。这里实际上是设置一个Java对象o中偏移地址为offset的属性的值为x，此方法可以突破修饰符的抑制，也就是无视private、protected和default修饰符。类似的方法有putInt、putDouble等等

此方法和上面的getObject功能类似，不过附加了'volatile'加载语义，也就是强制从主存中获取属性值。类似的方法有getIntVolatile、getDoubleVolatile等等。这个方法要求被使用的属性被volatile修饰，否则功能和getObject方法相同

此方法和上面的putObject功能类似，不过附加了'volatile'加载语义，也就是设置值的时候强制(JMM会保证获得锁到释放锁之间所有对象的状态更新都会在锁被释放之后)更新到主存，从而保证这些变更对其他线程是可见的。类似的方法有putIntVolatile、putDoubleVolatile等等。这个方法要求被使用的属性被volatile修饰，否则功能和putObject方法相同

设置o对象中offset偏移地址offset对应的Object型field的值为指定值x。这是一个有序或者有延迟的putObjectVolatile方法，并且不保证值的改变被其他线程立即看到。只有在field被volatile修饰并且期望被修改的时候使用才会生效。类似的方法有putOrderedInt和putOrderedLong。

返回给定的静态属性在它的类的存储分配中的位置(偏移地址)。不要在这个偏移量上执行任何类型的算术运算，它只是一个被传递给不安全的堆内存访问器的cookie。注意：这个方法仅仅针对静态属性，使用在非静态属性上会抛异常。下面源码中的方法注释估计有误，staticFieldOffset和objectFieldOffset的注释估计是对调了，为什么会出现这个问题无法考究

返回给定的非静态属性在它的类的存储分配中的位置(偏移地址)。不要在这个偏移量上执行任何类型的算术运算，它只是一个被传递给不安全的堆内存访问器的cookie。注意：这个方法仅仅针对非静态属性，使用在静态属性上会抛异常

返回给定的静态属性的位置，配合staticFieldOffset方法使用。实际上，这个方法返回值就是静态属性所在的Class对象的一个内存快照。注释中说到，此方法返回的Object有可能为null，它只是一个'cookie'而不是真实的对象，不要直接使用的它的实例中的获取属性和设置属性的方法，它的作用只是方便调用上面提到的像getInt(Object,long)等等的任意方法

检测给定的类是否已经初始化。通常需要使用在获取一个类的静态属性的时候(因为一个类如果没初始化，它的静态属性也不会初始化)。

检测给定的类是否需要初始化。通常需要使用在获取一个类的静态属性的时候(因为一个类如果没初始化，它的静态属性也不会初始化)。 此方法当且仅当ensureClassInitialized方法不生效的时候才返回false

返回数组类型的第一个元素的偏移地址(基础偏移地址)。如果arrayIndexScale方法返回的比例因子不为0，你可以通过结合基础偏移地址和比例因子访问数组的所有元素。Unsafe中已经初始化了很多类似的常量如ARRAY_BOOLEAN_BASE_OFFSET等

返回数组类型的比例因子(其实就是数据中元素偏移地址的增量，因为数组中的元素的地址是连续的)。此方法不适用于数组类型为"narrow"类型的数组，"narrow"类型的数组类型使用此方法会返回0(这里narrow应该是狭义的意思，但是具体指哪些类型暂时不明确，笔者查了很多资料也没找到结果)。Unsafe中已经初始化了很多类似的常量如ARRAY_BOOLEAN_INDEX_SCALE等

告诉JVM定义一个类，返回类实例，此方法会跳过JVM的所有安全检查。默认情况下，ClassLoader(类加载器)和ProtectionDomain(保护域)实例应该来源于调用者。

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这个类

通过Class对象创建一个类的实例，不需要调用其构造函数、初始化代码、JVM安全检查等等。同时，它抑制修饰符检测，也就是即使构造器是private修饰的也能通过此方法实例化

获取本地指针的大小(单位是byte)，通常值为4或者8。常量ADDRESS_SIZE就是调用此方法

获取本地内存的页数，此值为2的幂次方

分配一块新的本地内存，通过bytes指定内存块的大小(单位是byte)，返回新开辟的内存的地址。如果内存块的内容不被初始化，那么它们一般会变成内存垃圾。生成的本机指针永远不会为零，并将对所有值类型进行对齐。可以通过freeMemory方法释放内存块，或者通过reallocateMemory方法调整内存块大小。bytes值为负数或者过大会抛出IllegalArgumentException异常，如果系统拒绝分配内存会抛出OutOfMemoryError异常

freeMemory方法释放内存块

通过指定的内存地址address重新调整本地内存块的大小，调整后的内存块大小通过bytes指定(单位为byte)。可以通过freeMemory方法释放内存块，或者通过reallocateMemory方法调整内存块大小。bytes值为负数或者过大会抛出IllegalArgumentException异常，如果系统拒绝分配内存会抛出OutOfMemoryError异常

将给定内存块中的所有字节设置为固定值(通常是0)。内存块的地址由对象引用o和偏移地址共同决定，如果对象引用o为null，offset就是绝对地址。第三个参数就是内存块的大小，如果使用allocateMemory进行内存开辟的话，这里的值应该和allocateMemory的参数一致。value就是设置的固定值，一般为0(这里可以参考netty的DirectByteBuffer)。一般而言，o为null，所有有个重载方法是public native void setMemory(long offset, long bytes, byte value);，等效于setMemory(null, long offset, long bytes, byte value);。

锁定对象，必须通过monitorExit方法才能解锁。此方法经过实验是可以重入的，也就是可以多次调用，然后通过多次调用monitorExit进行解锁

解锁对象，前提是对象必须已经调用monitorEnter进行加锁，否则抛出IllegalMonitorStateException异常

尝试锁定对象，如果加锁成功返回true，否则返回false。必须通过monitorExit方法才能解锁。

针对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设置新的值，返回旧的值

释放被park创建的在一个线程上的阻塞。这个方法也可以被使用来终止一个先前调用park导致的阻塞。这个操作是不安全的，因此必须保证线程是存活的(thread has not been destroyed)。从Java代码中判断一个线程是否存活的是显而易见的，但是从native代码中这机会是不可能自动完成的

阻塞当前线程直到一个unpark方法出现(被调用)、一个用于unpark方法已经出现过(在此park方法调用之前已经调用过)、线程被中断或者time时间到期(也就是阻塞超时)。在time非零的情况下，如果isAbsolute为true，time是相对于新纪元之后的毫秒，否则time表示纳秒。这个方法执行时也可能不合理地返回(没有具体原因)。并发包java.util.concurrent中的框架对线程的挂起操作被封装在LockSupport类中，LockSupport类中有各种版本pack方法，但最终都调用了Unsafe#park()方法

在该方法之前的所有读操作，一定在load屏障之前执行完成

在该方法之前的所有写操作，一定在store屏障之前执行完成

在该方法之前的所有读写操作，一定在full屏障之前执行完成，这个内存屏障相当于上面两个(load屏障和store屏障)的合体功能

获取系统的平均负载值，loadavg这个double数组将会存放负载值的结果，nelems决定样本数量，nelems只能取值为1到3，分别代表最近1、5、15分钟内系统的平均负载。如果无法获取系统的负载，此方法返回-1，否则返回获取到的样本数量(loadavg中有效的元素个数)。实验中这个方法一直返回-1，其实完全可以使用JMX中的相关方法替代此方法

绕过检测机制直接抛出异常

主要操作为了将左边第一位置为0，0为非负数

public native void putObjectVolatile(Object o, long offset, Object x);
       此方法和上面的putObject功能类似，不过附加了'volatile'加载语义，也就是设置值的时候强制(JMM会保证获得锁到释放锁之间所有对象的状态更新都会在锁被释放之后)更新到主存，从而保证这些变更对其他线程是可见的。类似的方法有putIntVolatile、putDoubleVolatile等等。这个方法要求被使用的属性被volatile修饰，否则功能和putObject方法相同。

public final native boolean compareAndSwapObject(Object o, long offset, Object expected, Object x);
      针对Object对象进行CAS操作。即是对应Java变量引用o，原子性地更新o中偏移地址为offset的属性的值为x，当且仅的偏移地址为offset的属性的当前值为expected才会更新成功返回true，否则返回false。

1. o：目标Java变量引用。
2. offset：目标Java变量中的目标属性的偏移地址。
3. expected：目标Java变量中的目标属性的期望的当前值。
4. x：目标Java变量中的目标属性的目标更新值。

•  public native void putObjectVolatile(Object o, long offset, Object x);

       此方法和上面的putObject功能类似，不过附加了'volatile'加载语义，也就是设置值的时候强制(JMM会保证获得锁到释放锁之间所有对象的状态更新都会在锁被释放之后)更新到主存，从而保证这些变更对其他线程是可见的。类似的方法有putIntVolatile、putDoubleVolatile等等。这个方法要求被使用的属性被volatile修饰，否则功能和putObject方法相同

binCount ：i处结点标志，0: 未加入新结点, 2: TreeBin或链表结点数, 其它：链表结点数。主要用于每次加入结点后查看是否要由链表转为红黑树

如果头元素f的哈希值fh>=0，则是链表结构

如果首节点为TreeBin类型，说明为红黑树结构，执行putTreeVal操作

判断当前线程领取的任务有没有做完呢,比如说领取了16个,此时的bound为剩余的任务数量
循环每次--去判断，没完成，就直接false跳出这个循环，继续去干活

说明--i < bound，表示最后一份任务完成了

用CAS去标志TRANSFERINDEX，成功即代表该线程领取任务成功，并把TRANSFERINDEX更新成剩下的区间，最后一份任务是0，帮助扩容也是从这个TRANSFERINDEX获取的任务

锁住下标的头节点

判断是链表还是红黑树，采取不同的方式扩容

领取任务