与体验课程有关的问题和对象

HashMap HashMap基于数组+链表，但是jdk1.7和1.8中的特定实现略有不同. 实际上，最明显的优化需求之一是1.7: 当哈希冲突严重时，存储桶上形成的链表会越来越长，查询效率就会越来越低. 时间复杂度为O（N）. 因此，查询效率在1.8中进行了优化. 1.8 HashMapJDK 1.8修改了HashMap: 最大的区别是使用红黑树，该红黑树由数组+链表+红黑树组成. 在JDK 1.7中，搜索元素时，可以根据哈希值快速找到数组的特定索引，但是随后需要遵循链接列表才能找到所需的元素. 时间复杂度取决于链接列表的长度，即O（N）. 为了减少这部分的开销，在JDK 1.8中，当链表中有8个以上元素时，链表将转换为一棵红黑树，并且时间复杂度可以降低为O（logN ）在这些位置进行搜索.

JDK 1.8使用Node（作为入口的1.7）作为链表的数据节点，该链表仍包含键，值，哈希和next属性. 对于红黑树，将使用TreeNode. 根据数组元素中第一个节点的数据类型是Node还是TreeNode，可以确定位置是链表还是红黑树. 核心成员变量类似于1.7，添加了核心变量，如下表所示. 属性描述TREEIFY_THRESHOLD用于确定链接列表的阈值是否需要转换为红黑树. 默认值为8. 放置步骤: 确定当前存储桶是否为空，是否需要对空存储桶进行初始化（调整大小将确定是否初始化）. 根据当前键的哈希码，将其放在特定的存储桶中，并确定其是否为空. 如果为空，则表示没有哈希冲突，您可以直接创建新的存储桶. 如果当前存储桶具有值（哈希冲突），则当前存储桶中的密钥，该密钥的哈希码和已写入的密钥相等. 如果它们相等，则将它们分配给e. 在第8步，将对它们进行分配并统一返回.

如果当前存储桶是一棵红黑树，则以与红黑树相同的方式写入数据. 如果它是一个链表，则需要将当前键和值封装到一个新节点中，并将其写入当前存储区的后面（以形成链表）. 然后判断当前链表的大小是否大于预设的阈值，如果大于则将其转换为红黑树. 如果遍历过程中找到相同的密钥，则遍历将直接退出. 如果是e！ = Null等效于相同的键，您需要覆盖该值. 然后确定是否需要扩展. get方法似乎要简单得多. 散列密钥后，首先找到存储区. 如果存储桶为空，则直接返回null. 否则，判断存储桶的第一位置处的关键字（可能是链接列表或红黑树）是否是查询的关键字. 如果是这样，它将直接返回该值. 如果第一个不匹配，则确定其下一个是红黑树还是链表. 红黑树根据树的搜索方法返回值. 否则，将以链接列表的方式遍历匹配的返回值. 从这两种核心方法（get / put）中可以看出，大型链表在1.8中进行了优化，将查询效率修改为红黑树后直接提高为O（登录）.

但是，HashMap的原始问题也存在. 例如，当在并发方案中使用时，它很容易出现无限循环. 但为什么？简单分析. 阅读以上内容后，我仍然记得当HashMap展开时将调用resize（）方法. 这里的并发操作很容易在存储桶上形成循环链表；这样，当获得不存在的密钥时，计算出的索引正好是圆形的. 链表的索引将以无限循环的形式出现. 如下所示: HashTable HashTable容器使用同步来确保线程安全，但是在激烈的线程竞争中HashTable的效率非常低. 当一个线程访问HashTable的同步方法时，其他线程对HashTable的同步方法的访问可能会进入阻塞或轮询状态. HashTable容器在竞争激烈的并发环境中显示低效率的原因是，访问它的所有线程必须竞争同一锁. 如果容器中有多个锁，则每个锁都用于锁定容器数据的一部分. 这样，当多个线程访问容器中不同数据段中的数据时，线程之间将不会发生锁争用，从而可以有效地提高并发访问效率. 这是ConcurrentHashMap（JDK 1.7）使用的锁定分段技术.

ConcurrentHashMap将数据划分为多个段，然后为每个数据段分配一个锁. 当线程占用锁以访问一个数据段时，其他线程也可以访问其他段中的数据. 一些方法需要跨度段，例如size（）和containsValue（）. 他们可能需要锁定整个表，而不只是一个段. 这要求按顺序锁定所有段. 操作完成后，将按顺序释放所有段的锁. 顺序很重要，否则可能会发生死锁. 在ConcurrentHashMap中，segment数组是final，其成员变量也是final. 但是反复出现您当前的网络存在链路层劫持，仅将数组声明为final并不能保证数组成员也是final. ，需要保证. 这样可以确保不会发生死锁，因为获取锁的顺序是固定的. HashTable迭代器是高度一致的，而ConcurrentHashMap是弱一致的. ConcurrentHashMap的get，clear和iterator方法都是弱一致性的.

满足ConcurrentHashMap并发表示并发，从字面上理解其作用是处理HashMap的并发. 通过先前的学习，我们知道HashMap在多线程并发（例如无限循环）下并不安全. 更一般而言，在多线程并发下，由于堆内存程之间共享，因此HashMap的put方法不是原子操作. 假定Thread1首先放置该值，然后休眠2秒钟（否则系统时间片开关将失去执行权限）. 在2秒内，该值将由Thread2更改. 当Thread1“唤醒”然后获取它时，它不是原始值. 这容易出现问题. 那么如何避免这种多线程错误情况呢？总体思路是锁定HashMap的put方法（已同步），以确保一次只允许一个线程具有对hashmap的写权限. 但是，如果线程1中的操作很耗时，则需要操作哈希图的其他线程需要在门口排队半天，这会严重影响用户体验. HashTable可以做到这一点.

作为生活中的一个例子，除了存款和取款外，许多银行还支持获取贵重物品. 贵重物品放在保险箱中. 将HashMap和HashTable与银行进行比较. 结构: 将线程与人员进行比较，对应的情况如下: 在多线程下使用HashMap的不确定性太大，存在破产的风险，因此无法选择； HashTable不会破产反复出现您当前的网络存在链路层劫持，但是用户体验不好，那么多用户访问又如何不影响他人的价值呢？而且不必排队等候？有人提出了“银行家联合会”. 最好开设更多像HashTable这样的“锁定”银行. 尽可能多的人处理事务，只要开设尽可能多的银行即可. 在此区域，服务很大. 老板，开银行的成本很小，因此成立了“银行家联盟”. 下一种情况是: 例如，用户A和用户B去银行存放自己的项链. 在“银行家联盟”运作之后，然后对用户A说，银行1现在已经没人了，您可以去那里保存. 排队，然后用户A转到银行1存放项链. 银行1将用户A插入门，立即拉开锁，然后将用户A的项链放入第x和第x保险柜. 用户A离开后，重新打开；同样适用于用户B.

这时，无论用户A和B在银行中停留多长时间，他们都不会相互影响. 不用担心他们的项链被盗. 这是ConcurrentHashMap的设计思想. 用图来理解. 从上图可以看出，此时，相应的单个银行被锁定，而不是整个“银行家联合会”被锁定. 分析此设计的特征: 由多个银行组成的“银行家联合会”. 当某人来开展业务时，“银行家联合会”需要确定该人去哪家银行. 当该人去指定银行营业时，银行被锁定，其他人不能同时执行修改操作，直到该人离开并解锁. ConcurrentHashMap源代码分析ConcurrentHashMap也分为1.7版和1.8版，两者的实现略有不同. 首先让我们看一下1.7的实现. 如下: 如图所示，它由Segment数组和HashEntry组成. 像HashMap一样，它仍然是一个数组加上一个链表. 这主要是通过分段锁来实现的. 关于段锁段继承了可重入锁ReentrantLock. 使用锁定功能，每个锁定都控制一个段. 随着每个段越来越大，锁的粒度也变得更大.

分段锁的优点在于，当操作不同的分段映射时，它们可以同时执行. 当操作相同的分段图时，将执行锁定竞争和等待. 与直接在整个地图上进行同步相比，这具有优势. 缺点是将其分成许多段会浪费存储空间（不连续，碎片）. 操作映射时竞争同一段锁的可能性很小，并且段锁将导致长时间等待操作（例如更新）；当段很大时，段锁定的性能将降低. 1.7解决了并发问题，并且可以支持并发N次段，但是1.7版中的HashMap仍然存在问题. 也就是说，通过链表进行查询的效率太低. 因此1.8对数据结构进行了一些调整. 首先看一下底层结构: 实际上，它类似于1.8 HashMap结构. 当链接列表中的节点数超过指定的阈值时，它也会转换为红色和黑色的树. 总体结构是相同的. 那么，JDK 1.8 ConcurrentHashMap如何真正实现线程安全？答: 它放弃了原来的Segment锁，并采用CAS +同步以确保并发安全性.

（cas: 比较和替换）**①基本组成**放弃JDK 1.7中原始的Segment锁，并使用CAS +同步来确保并发安全性. 将JDK 1.7中的HashEntry更改为Node，但是效果是相同的. 让我们看一下ConcurrentHashMap的几个重要属性. 重要组成元素Node: 链接列表中的元素是Node对象. 他是链接列表上的一个节点，该节点存储键，值和对下一个节点的引用. 这样，一系列节点串在一起形成一个链表. ForwardingNode: 扩展时，需要将链接列表迁移到新的哈希表. 执行此操作时，将用ForwardingNode对象替换数组中的头节点. ForwardingNode不存储键和值，仅存储扩展后对哈希表（nextTable）的引用.

要在此时查找对应的节点，您需要在nextTable中搜索. TreeBin: 当链接列表转换为红黑树时，数组中存储的引用为TreeBin. TreeBin不在内部存储键/值. 它保存TreeNode的列表和红黑树的根. TreeNode: 红黑树的节点. **②put方法步骤**存储结构定义了容器的“形状”，那么在容器内部放置了哪些规则？换句话说，密钥在容器的相应位置放置了什么逻辑？我们假设要存储的密钥是​​对象x，其过程如下: 1.通过其hashCode（）方法获取对象x的hashCode； 2.将hashCode映射到数组中的某个位置； 3.将元素存储在链接列表的“位置”中. put方法用于将键值对存储到映射中. 代码如下: 实际调用putVal方法. 第三个参数传递为false，并且在存在控制键的情况下覆盖原始值.

请先阅读代码注释以获得一般理解，然后我们将对其进行更详细的研究: 确定存储的键和值是否为空. 如果它们为空，则引发异常，否则，请转到步骤2. 计算key的哈希值，然后输入旋转. 这种旋转可以确保成功插入数据. 如果表表为空或长度为0，则表表被初始化；否则，表被初始化. 否则，请执行步骤3. 根据密钥的哈希值提取表中的节点元素. 如果提取的节点为空（存储桶为空），则使用CAS将由键，值和哈希值生成的节点放入存储桶中. 否则，请执行步骤4. 如果节点的哈希值为MOVED（-1），则将存储桶中的节点转移；否则，请执行步骤4. 否则，请转到步骤5. 5.桶中的第一个节点（即表表中的节点）被锁定，并且遍历该桶. 存储桶中节点的哈希值和键值以及给定的哈希值和键值Equal，根据标识符选择是否执行更新操作（将节点的值替换为给定值）. 如果在遍历该存储桶后仍未找到该存储桶，则其哈希值和关键值等于该关键值的节点将直接创建一个新节点，并将该值分配给上一个节点之前的下一个节点.

转到步骤6. 如果binCount值达到红黑树转换阈值，则将存储桶中的结构转换为红黑树存储，然后增加binCount值. 如果存储桶中第一个元素的哈希值大于0，表示它是链表结构，则插入或更新链表. 如果存储桶中的第一个元素是TreeBin，则意味着它是一个红黑树结构，并且以红黑树的方式插入或更新了它. 在锁的保护下，插入或更新完成后，如果它是链表结构，则需要确定链表中的元素数是否超过8（默认值）. 一旦超过，您就需要考虑数组扩展或到红黑树的链表. 扩展何时扩展？使用put（）添加元素时会调用AddCount（），并在内部检查sizeCtl以查看是否需要扩展. tryPresize（）被调用. 调用此方法有两个调用点: 当链表变成一棵红黑树（在put（）期间检查）时，如果表容量小于64（MIN_TREEIFY_CAPACITY），它将触发容量扩展.

调用putAll（）并立即添加大量元素将触发容量扩展. addCount（）和addCount（）的实现与tryPresize（）非常相似. 让我们用addCount（）分析扩展逻辑: ** 1.链接到红黑树的列表**首先，我们需要了解为什么需要扩展Map. 这是因为我们使用哈希表存储数据. 当固定大小的哈希表存储越来越多的数据时，链表的长度将变得越来越长，这将导致放置和获取性能下降. 在这一点上，我们希望散列表中有更多的存储桶，以防止链表的累积时间更长. ConcurrentHashMap具有将链接列表变成红黑树以提高搜索速度的操作. 红黑树的时间复杂度为O（logn），而链表为O（n / 2），因此仅当O（logn）

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-156432-1.html