ConcurrentHashMap上的注解译文

    1. 支持检索的完全并发和更新的高预期并发的哈希表。此类遵循与 Hashtable 相同的功能规范，并包含与 Hashtable 的每个方法对应的方法版本。但是，即使所有操作都是线程安全的，检索操作也不需要锁定，并且不支持以阻止所有访问的方式锁定整个表。在依赖线程安全但不依赖同步细节的程序中，此类与 Hashtable 完全可互操作。
    2. 检索操作（包括 get）一般不会阻塞，因此可能与更新操作（包括 put 和 remove）重叠。检索反映了最近完成的更新操作在其开始时保持的结果。 （更正式地说，给定键的更新操作与报告更新值的键的任何（非空）检索具有发生前的关系。）对于诸如 putAll 和 clear 之类的聚合操作，并发检索可能反映插入或删除只有一些条目。类似地，迭代器、拆分器和枚举返回反映哈希表在创建迭代器/枚举时或之后的某个时间点的状态的元素。它们不会抛出 ConcurrentModificationException。但是，迭代器被设计为一次只能由一个线程使用。请记住，包括 size、isEmpty 和 containsValue 在内的聚合状态方法的结果通常仅在地图未在其他线程中进行并发更新时才有用。否则，这些方法的结果反映的瞬态状态可能足以用于监控或估计目的，但不适用于程序控制。
    3. 当有太多冲突时（即，具有不同哈希码但落入以表大小为模的相同槽中的键），表会动态扩展，每个映射保持大约两个 bin 的预期平均效果（对应于 0.75 负载调整大小的因子阈值）。随着映射的添加和删除，这个平均值可能会有很大差异，但总的来说，这保持了哈希表普遍接受的时间/空间折衷。然而，调整这个或任何其他类型的哈希表的大小可能是一个相对缓慢的操作。如果可能，最好将大小估计值作为可选的 initialCapacity 构造函数参数提供。一个额外的可选 loadFactor 构造函数参数通过指定用于计算要为给定数量的元素分配的空间量的表密度来提供自定义初始表容量的进一步方法。此外，为了与此类的先前版本兼容，构造函数可以选择指定预期的 concurrencyLevel 作为内部大小调整的附加提示。请注意，使用具有完全相同 hashCode() 的许多键是降低任何哈希表性能的可靠方法。为了改善影响，当键是 Comparable 时，此类可以使用键之间的比较顺序来帮助打破平局。
    4. 可以创建 ConcurrentHashMap 的 Set 投影（使用 newKeySet() 或 newKeySet(int)），或查看（使用 keySet(Object)，当只有键感兴趣并且映射值（可能暂时）不使用或全部使用时相同的映射值。
    5. 通过使用 java.util.concurrent.atomic.LongAdder 值并通过 computeIfAbsent 进行初始化，ConcurrentHashMap 可以用作可伸缩频率图（直方图或多重集的一种形式）。例如，要将计数添加到 ConcurrentHashMap<String,LongAdder> 频率，您可以使用 freqs.computeIfAbsent(k -> new LongAdder()).increment();
    6. 此类及其视图和迭代器实现了 Map 和 Iterator 接口的所有可选方法。
    7. 与 Hashtable 类似，但与 HashMap 不同，此类不允许将 null 用作键或值。
    8. ConcurrentHashMaps 支持一组顺序和并行的批量操作，与大多数 Stream 方法不同，这些操作被设计为安全且通常明智地应用，即使是由其他线程同时更新的映射；例如，在计算共享注册表中值的快照摘要时。共有三种操作，每种都有四种形式，接受带有键、值、条目和（键，值）参数和/或返回值的函数。因为 ConcurrentHashMap 的元素没有以任何特定方式排序，并且可能在不同的并行执行中以不同的顺序进行处理，所以提供的函数的正确性不应依赖于任何排序，也不依赖于任何其他可能暂时改变的对象或值。计算正在进行中；并且除了 forEach 动作，理想情况下应该没有副作用。 Map.Entry 对象的批量操作不支持方法 setValue。
    9. forEach：对每个元素执行给定的操作。变体形式在执行操作之前对每个元素应用给定的转换。
    10. search：返回对每个元素应用给定函数的第一个可用的非空结果；找到结果时跳过进一步搜索。
    11. reduce：累加每个元素。提供的归约函数不能依赖于排序（更正式地说，它应该是关联的和交换的）。有五种变体：
    12. 简单的削减。 （对于 (key, value) 函数参数，这种方法没有一种形式，因为没有相应的返回类型。）
    13. 累积应用于每个元素的给定函数的结果的映射缩减。
    14. 使用给定的基值减少标量 double、long 和 int。
    15. 这些批量操作接受一个 parallelismThreshold 参数。如果估计当前地图大小小于给定阈值，则方法按顺序进行。使用 Long.MAX_VALUE 的值会抑制所有并行性。使用值 1 通过划分为足够多的子任务以充分利用用于所有并行计算的 ForkJoinPool.commonPool() 来实现最大并行度。通常，您首先会选择这些极端值之一，然后衡量使用折衷开销与吞吐量的中间值的性能。
    16. 批量操作的并发属性遵循 ConcurrentHashMap 的并发属性：从 get(key) 和相关访问方法返回的任何非 null 结果都与关联的插入或更新具有发生前的关系。任何批量操作的结果都反映了这些每个元素关系的组成（但对于整个映射而言不一定是原子的，除非它以某种方式已知是静止的）。相反，因为映射中的键和值永远不会为空，所以 null 可作为当前缺少任何结果的可靠原子指示符。为了保持此属性，null 充当所有非标量归约操作的隐式基础。对于 double、long 和 int 版本，基础应该是与任何其他值组合时返回该其他值的基础（更正式地说，它应该是归约的标识元素）。最常见的归约具有这些属性；例如，计算以 0 为基数的总和或以 MAX_VALUE 为基数的最小值。
    17. 作为参数提供的搜索和转换函数应该类似地返回 null 以指示缺少任何结果（在这种情况下不使用它）。在映射归约的情况下，这也使转换能够充当过滤器，如果不应该组合元素，则返回 null（或者，在原始特化的情况下，返回恒等基础）。在搜索或归约操作中使用它们之前，您可以通过在“null 表示现在没有任何东西”规则下自己组合它们来创建复合转换和过滤。
    18. 接受和/或返回 Entry 参数的方法维护键值关联。例如，在寻找最大价值的关键时，它们可能很有用。请注意，可以使用 new AbstractMap.SimpleEntry(k,v) 提供“普通”条目参数。
    19. 批量操作可能会突然完成，抛出在应用提供的函数时遇到的异常。请记住，在处理此类异常时，其他同时执行的函数也可能引发异常，或者如果没有发生第一个异常，就会这样做。
    20. 与顺序形式相比，并行形式的加速很常见，但不能保证。如果并行计算的基础工作比计算本身更昂贵，则涉及小地图上的简短函数的并行操作可能比顺序形式执行得更慢。同样，如果所有处理器都忙于执行不相关的任务，并行化可能不会导致太多实际的并行性。
    21. 所有任务方法的所有参数都必须为非空。
    22. 此类是 Java 集合框架的成员。
    23. 自从：
    24. 1.5
    25. 作者：
    26. 道格·李
    27. 类型参数：
    28. <K> – 此映射维护的键的类型
    29. <V> – 映射值的类型
    31. /*
    32.      * 概述：
    33.      *
    34.      * 这个哈希表的主要设计目标是维护
    35.      * 并发可读性（通常是方法 get()，但也
    36.      * 迭代器和相关方法）同时最小化更新
    37.      * 争执。次要目标是将空间消耗保持在
    38.      * 与java.util.HashMap相同或更好，并支持高
    39.      * 许多线程在空表上的初始插入率。
    40.      *
    41.      * 此映射通常充当分箱（分桶）哈希表。每个
    42.      * 键值映射保存在一个节点中。大多数节点都是实例
    43.      * 具有 hash、key、value 和 next 的基本 Node 类
    44.      * 字段。但是，存在各种子类： TreeNode 是
    45.      * 排列在平衡树中，而不是列表中。 TreeBins 有根
    46.      * 树节点集。 ForwardingNodes 被放置在头部
    47.      * 调整大小期间的垃圾箱。 ReservationNodes 用作
    48.      * 在 computeIfAbsent 和中建立值时的占位符
    49.      * 相关方法。 TreeBin、ForwardingNode 和
    50.      * ReservationNode 不保存普通的用户键、值或
    51.      * 哈希，并且在搜索等过程中很容易区分
    52.      * 因为它们有负散列字段和空键和值
    53.      * 字段。 （这些特殊节点要么不常见，要么短暂，
    54.      * 所以携带一些未使用的字段的影响是
    55.      * 微不足道。）
    56.      *
    57.      * 该表在
    58.      * 第一次插入。表中的每个 bin 通常包含一个
    59.      * 节点列表（通常，列表只有零个或一个节点）。
    60.      * 表访问需要 volatile/atomic 读取、写入和
    61.      * 案例。因为没有其他方法可以安排这个
    62.      * 添加更多间接，我们使用内在函数
    63.      * (sun.misc.Unsafe) 操作。
    64.      *
    65.      * 我们使用节点哈希字段的顶部（符号）位进行控制
    66.      * 目的——由于寻址，它无论如何都是可用的
    67.      * 约束。具有负哈希字段的节点特别
    68.      * 在地图方法中处理或忽略。
    69.      *
    70.      * 插入（通过 put 或其变体）的第一个节点
    71.      * 空 bin 只需将其 CASing 到 bin 即可。这是
    72.      * 迄今为止最常见的 put 操作情况
    73.      * 密钥/哈希分布。其他更新操作（插入、
    74.      * 删除和替换）需要锁。我们不想浪费
    75.      * 将不同的锁对象与相关联所需的空间
    76.      * 每个 bin，因此使用 bin 列表本身的第一个节点作为
    77.      * 一把锁。对这些锁的锁定支持依赖于内置
    78.      *“同步”监视器。
    79.      *
    80.      * 使用列表的第一个节点作为锁本身不会
    81.      * 足够了：当一个节点被锁定时，任何更新都必须首先
    82.      * 验证它是否仍然是锁定后的第一个节点，并且
    83.      * 如果没有，请重试。因为新节点总是附加到列表中，
    84.      * 一旦一个节点在一个 bin 中的第一个，它会保持在第一个直到被删除
    85.      * 或 bin 失效（在调整大小时）。
    86.      *
    87.      * per-bin 锁的主要缺点是其他更新
    88.      * 对受相同保护的 bin 列表中其他节点的操作
    89.      * 锁可能会停止，例如当用户 equals() 或映射时
    90.      * 函数需要很长时间。然而，在统计上，根据
    91.      * 随机哈希码，这不是常见问题。理想情况下，
    92.      * bin 中节点的频率遵循泊松分布
    93.      * (http://en.wikipedia.org/wiki/Poisson_distribution) 带有
    94.      * 给定调整大小的阈值，参数平均约为 0.5
    95.      * 为 0.75，尽管由于调整大小而存在很大差异
    96.      * 粒度。忽略方差，预期发生
    97.      * 列表大小 k 为 (exp(-0.5) * pow(0.5, k) / factorial(k))。这
    98.      * 第一个值为：
    99.      *
    100.      * 0: 0.60653066
    101.      * 1：0.30326533
    102.      * 2：0.07581633
    103.      * 3：0.01263606
    104.      * 4：0.00157952
    105.      * 5：0.00015795
    106.      * 6: 0.00001316
    107.      * 7: 0.00000094
    108.      * 8: 0.00000006
    109.      * 更多：不到千万分之一
    110.      *
    111.      * 两个线程访问不同的锁竞争概率
    112.      * 随机散列下的元素大约是 1 / (8 * #elements)。
    113.      *
    114.      * 在实践中遇到的实际哈希码分布
    115.      * 有时明显偏离均匀随机性。这
    116.      * 包括 N > (1<<30) 的情况，因此某些键必须发生冲突。
    117.      * 类似地，对于有多个密钥的愚蠢或敌对用法
    118.      * 设计为具有相同的哈希码或仅不同的哈希码
    119.      * 在屏蔽的高位中。所以我们使用次要策略
    120.      * 适用于 bin 中的节点数超过
    121.      * 临界点。这些 TreeBins 使用平衡树来保存节点（a
    122.      * 特殊形式的红黑树），将搜索时间限定为
    123.      * O(log N)。 TreeBin 中的每个搜索步骤至少是两倍
    124.      * 与常规列表一样慢，但考虑到 N 不能超过
    125.      * (1<<64) （在用完地址之前）这个边界搜索
    126.      * 步数，锁定保持时间等，合理的常数（大约
    127.      * 每次操作检查 100 个节点（最坏情况），只要键
    128.      * 是 Comparable（这很常见——String、Long 等）。
    129.      * TreeBin 节点（TreeNodes）也保持相同的“next”
    130.      * 遍历指针作为常规节点，所以可以遍历
    131.      * 迭代器以相同的方式。
    132.      *
    133.      * 当占用率超过百分比时，表格会调整大小
    134.      * 阈值（名义上为 0.75，但见下文）。任何线程
    135.      * 注意到一个过满的垃圾箱可能有助于调整后的大小
    136.      * 启动线程分配并设置替换数组。
    137.      * 但是，这些其他线程可能会继续，而不是停止
    138.      * 插入等。TreeBins 的使用使我们免受
    139.      * 调整大小时过度填充的最坏情况影响
    140.      * 进步。通过一一转移垃圾箱来调整收益的大小，
    141.      * 从表到下一个表。但是，线程声称很小
    142.      * 之前要传输的索引块（通过字段 transferIndex）
    143.      * 这样做，减少争用。田野里的一代印记
    144.      * sizeCtl 确保调整大小不会重叠。因为我们是
    145.      * 使用二次幂展开，每个 bin 中的元素必须
    146.      * 要么保持相同的索引，要么以 2 的幂移动
    147.      * 抵消。我们通过捕获消除不必要的节点创建
    148.      * 旧节点可以重复使用的情况，因为它们的下一个字段
    149.      * 不会改变。平均而言，只有大约六分之一的人需要
    150.      * 表翻倍时克隆。他们替换的节点将是
    151.      * 垃圾一旦不再被引用就可以回收
    152.      * 任何可能在并发中的读者线程
    153.      * 遍历表。转移后，旧表箱包含
    154.      * 只有一个特殊的转发节点（带有哈希字段“MOVED”）
    155.      * 包含下一个表作为其键。在遇到一个
    156.      * 转发节点，访问和更新操作重启，使用
    157.      * 新表。
    158.      *
    159.      * 每个 bin 传输都需要它的 bin 锁，这可能会停顿
    160.      * 调整大小时等待锁。然而，由于其他
    161.      *线程可以加入并帮助调整大小而不是竞争
    162.      * 锁，平均聚合等待随着调整大小而变短
    163.      * 进步。转移操作还必须确保所有
    164.      * 旧表和新表中的可访问垃圾箱可供任何人使用
    165.      * 遍历。这部分是通过从
    166.      * 最后一个 bin (table.length - 1) 向上到第一个。一看到
    167.      * 一个转发节点，遍历（参见 Traverser 类）安排到
    168.      * 移动到新表而不重新访问节点。以确保
    169.      * 即使乱序移动，也不会跳过中间节点，
    170.      * 在第一次遇到
    171.      * 遍历期间的转发节点，如果
    172.      * 稍后处理当前表。需要这些
    173.      * 保存/恢复机制比较少见，但是当一个
    174.      * 遇到转发节点，通常会更多。
    175.      * 所以 Traversers 使用一个简单的缓存方案来避免创建 so
    176.      * 许多新的 TableStack 节点。 （感谢彼得莱瓦特
    177.      * 建议在这里使用堆栈。）
    178.      *
    179.      * 遍历方案也适用于部分遍历
    180.      * 垃圾箱的范围（通过备用的 Traverser 构造函数）
    181.      * 支持分区聚合操作。另外，只读
    182.      * 如果曾经转发到空表，则操作放弃，这
    183.      * 提供对关闭式清除的支持，这也不是
    184.      * 目前已实施。
    185.      *
    186.      * 延迟表初始化最小化占用空间，直到第一次使用，
    187.      * 并且还避免在第一次操作来自
    188.      * putAll，带有映射参数的构造函数，或反序列化。
    189.      * 这些情况试图覆盖初始容量设置，
    190.      * 但在比赛的情况下无害地无法生效。
    191.      *
    192.      * 元素计数是使用专门化的
    193.      * 长加法器。我们需要结合专业化而不是
    194.      * 只需使用 LongAdder 来访问隐式
    195.      * 竞争感知导致创建多个
    196.      *计数器。计数器机制避免争用
    197.      * 更新但如果读取也可能会遇到缓存抖动
    198.      * 在并发访问期间频繁。为了避免经常阅读，
    199.      * 仅在添加到争用时才尝试调整大小
    200.      * bin 已经拥有两个或更多节点。统一哈希下
    201.      *分布，这种情况发生在阈值的概率
    202.      * 约为 13%，这意味着只有大约八分之一的看跌期权
    203.      * 阈值（在调整大小后，这样做的人会更少）。
    204.      *
    205.      * TreeBins 使用一种特殊的比较形式进行搜索和
    206.      * 相关操作（这是我们不能使用的主要原因
    207.      * 现有的集合，例如 TreeMap

    HashMap 的hash算法

    1.  Object key = "23432";
    2.  int h;
    3.  int i = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

    �ConcurrentHashMap的hash算法

    1. static final int HASH_BITS = 0x7fffffff; //正常节点哈希的可用位
    2. int h = key.hashCode()
    3. int i = (h ^ (h >>> 16)) & HASH_BITS; //比HashMap多了 & HASH_BITS