皮皮网

1.HashMap实现原理一步一步分析(1-put方法源码整体过程)
2.三万字带你认识 Go 底层 map 的析源实现
3.一文捋清 sync.Map的实现原理
4.结合源码探究HashMap初始化容量问题
5.Source Map 原理及源码探索
6.concurrenthashmap1.8源码如何详细解析?

HashMap实现原理一步一步分析(1-put方法源码整体过程)

       本文分享了HashMap内部的实现原理，重点解析了哈希(hash)、源码散列表(hash table)、解析哈希码(hashcode)以及hashCode()方法等基本概念。析源

       哈希(hash)是源码将任意长度的输入通过散列算法转换为固定长度输出的过程，建立一一对应关系。解析手机变监控源码常见算法包括MD5加密和ASCII码表。析源

       散列表(hash table)是源码一种数据结构，通过关键码值映射到表中特定位置进行快速访问。解析

       哈希码(hashcode)是析源散列表中对象的存储位置标识，用于查找效率。源码

       Object类中的解析hashCode()方法用于获取对象的哈希码值，以在散列存储结构中确定对象存储地址。析源

       在存储字母时，源码使用哈希码值对数组大小取模以适应存储范围，解析防止哈希碰撞。

       HashMap在JDK1.7中使用数组+链表结构，而JDK1.8引入了红黑树以优化性能。

       HashMap内部数据结构包含数组和Entry对象，数组用于存储Entry对象，Entry对象用于存储键值对。

       在put方法中，首先判断数组是否为空并初始化，然后计算键的哈希码值对数组长度取模，用于定位存储位置。如果发生哈希碰撞，使用链表解决。

       本文详细介绍了HashMap的存储机制，包括数组+链表的实现方式，以及如何处理哈希碰撞。后续文章将继续深入探讨HashMap的其他特性，如数组长度的优化、多线程环境下的性能优化和红黑树的引入。

三万字带你认识 Go 底层 map 的实现

       map在Go语言中是一种基础数据结构，广泛应用于日常开发。其设计遵循“数组+链表”的通用思路，但Go语言在具体实现上有着独特的设计。本文将带你深入了解Go语言中map的底层实现，包括数据结构设计、性能优化策略以及关键操作的内部实现。

       在Go语言的map中，数据存储在数组形式的桶(bucket)中，每个桶最多容纳8对键值对。哈希值的低位用于选择桶，而高位则用于在独立的桶中区分键。这种设计有助于高效地处理冲突和实现快速访问。

       源码位于src/runtime/map.go，展示了map的内部结构和操作。在该文件中，定义了桶和map的内存模型，桶的魔兽tbc源码内存结构示例如下。每个桶的前7-8位未被使用，用于存储键值对，避免了不必要的内存填充。在桶的末尾，还有一个overflow指针，用于连接超过桶容量的键值对，以构建额外的桶。

       初始化map有两种方式，根据是否指定初始化大小和hint值，调用不同的函数进行分配。对于不指定大小或hint值小于8的情况，使用make_small函数直接在堆上分配。当hint值大于8时，调用makemap函数进行初始化。

       插入操作的核心是找到目标键值对的内存地址，并通过该地址进行赋值。在实现中，没有直接将值写入内存，而是返回值在内存中的对应地址，以便后续进行赋值操作。同时，当桶达到容量上限时，会创建新的溢出桶来容纳多余的数据。

       查询操作通过遍历桶来实现，找到对应的键值对。对于查询逻辑的优化，Go语言提供了不同的函数实现，如mapaccess1、mapaccess2和mapaccessK等，它们在不同场景下提供高效的关键字查找和值获取。

       当map需要扩容时，Go语言会根据装载因子进行决策，以保持性能和内存使用之间的平衡。扩容操作涉及到数据搬移，通过hashGrow()和growWork()函数实现。增量扩容增加桶的数量，而等量扩容则通过重新排列元素提高桶的利用率。

       删除操作在Go语言中同样高效，利用map的内部机制快速完成。迭代map时，可以使用特定的函数遍历键值对，实现对数据的访问和操作。

       通过深入分析Go语言中map的实现，我们可以看到Go开发者在设计时的巧妙和全面考虑，不仅关注内存效率，还考虑到数据结构在不同情况下的复用和性能优化。这种设计思想不仅体现在map自身，也对后续的缓存库等开发产生了深远的影响。

       综上所述，Go语言中map的新浪星座源码底层实现展示了高效、灵活和强大的设计原则，为开发者提供了强大的工具，同时也启发了其他数据结构和库的设计。了解这些细节有助于我们更深入地掌握Go语言的特性，并在实际开发中做出更优的选择。

一文捋清 sync.Map的实现原理

       golang 内置的 map 类型不支持并发操作，若需并发读写，通常需配合锁使用。

       然而，加锁操作较重，golang 官方提供了 sync.Map 类型，专门用于支持并发读写。

       本文基于 go1.. linux/amd 版本的源码对 sync.Map 进行分析，旨在对 sync.Map 的原理及适用场景有更清晰的理解。

       为了提高并发访问效率，通常原则是：尽量减少锁的争用，如使用原子操作替代加锁。

       sync.Map 采用读写分离 + 原子操作的方式，设置了两个 map（dirty map 和 read map），read map 通过原子方式访问，dirty map 的访问需要加锁。

       同步过程分为两类：

       sync.Map 的数据结构定义如下：

       read map 通过原子操作进行读取和写入，实际存的是 readOnly 结构。

       其中字段 m 就是普通的 map，amended 用于标识 read map 的数据是否完整（dirty map 中可能写入了新的数据，此时为 true）。

       read map 和 dirty map 底层的 map 中，存储的 value 都是 entry 结构。

       疑问：为什么这里不直接将 m 定义为 map[any]unsafe.Pointer 类型？

       其实结合下文的 entry.p 的状态可以得出结论，主要是为了并发高效地删除 key。

       删除 key 时从 read map 中删除即可，但是由于 read map 是原子操作的，因此只能整体替换整个 readOnly 结构，或者原子地将 value 中的指针置为 nil，不能直接使用 delete 关键字删除（要加锁）。

       entry.p 字段在不同阶段会有不同的取值，代表不同的状态：

       Store 操作：

       Store 方法用于向 map 中并发安全地修改或新增数据，签名如下：

       下面将源码拆成小段进行详细分析：

       首先查询 read map，如果 read map 中存在该 key，则尝试写入。这里只是进行尝试，是否能写入还需看对应 entry 的状态。

       如果 entry.p == expunged，则不能写入，因为已经经历过 read map 向 dirty map 的同步，read map 接下来会被直接替换掉，即使写入也没用。

       运行到这里，说明要么 read map 中不存在该 key，要么 read map 中存在该 key 但 entry 为 expunged 状态（即将被物理清理）。益智答题源码需要在锁的保护下将数据存到 dirty map 中。

       由于上一次判断到获取锁之间可能会有其他的线程修改了 read map，所以利用了 double check 再次判断 read map 是否有该 key。

       情况一：read map 中存在

       具体执行什么操作依赖于 entry 的状态：

       注意到这里的 entry 和 entry.p 都是指针，说明如果 read map 和 dirty map 中同时存在 entry，那么数据是共享的。

       情况二：read map 中不存在且 dirty 中存在

       这种情况直接原子地将值存到对应的 entry 中。

       情况三：read map 和 dirty map 都不存在

       这种情况涉及到 read map 向 read map 的同步。

       如果 read.amended == true，即 dirty map 中存在独有的 key，那么直接在 dirty map 新增 entry 即可。

       如果 read.amended == false，dirty map 中可能缺失数据（比如刚经历过 dirty map 向 read map 的同步，dirty map 可能为 nil），写入之前需要将 read map 中正常的数据同步过去。这里指的正常的数据即非 nil 状态的 entry。

       Load 操作：

       前面说可以将 read map 视为 dirty map 的快照，由于使用原子操作可以保证并发效率，因此读取时也是优先尝试 read map。

       和 Store 类似，也会有 double check 机制。

       如果 read map 中不存在且 amended == false（dirty map 中没有独有的 key），说明整个 map 中不存在该 key，直接返回 false；

       如果 read map 不存在且 amended == true，key 可能存在于 dirty map，因此加锁从 dirty map 获取。

       由于 read map 未命中，还会将 misses 计数增加 1，如果 misses 计数达到阈值，会将 dirty map 整体替换为 read map，dirty map 置为 nil。

       如果 read map 中存在 entry，则根据 entry 状态返回。nil 状态或 expunged 状态下都说明该 key 被删除，返回 false；正常状态返回 true。

       Delete 操作：

       逻辑总体和 Load 相似：

       Range 操作：

       range 操作用于遍历 sync.Map 中每个元素并执行函数。

       由于 read map 和 dirty map 数据并不完全一致，且都可能有对方不存在的 key，因此需要分情况讨论：

结合源码探究HashMap初始化容量问题

       探究HashMap初始化容量问题

       在深入研究HashMap源码时，有一个问题引人深思：为何在知道需要存储n个键值对时，我们通常会选择初始化容量为capacity = n / 0. + 1？

       本文旨在解答这一疑惑，适合具备一定HashMap基础知识的读者。请在阅读前，思考以下问题：

       让我们通过解答这些问题，逐步展开对HashMap初始化容量的深入探讨。

       源码探究

       让我们从实际代码出发，通过debug逐步解析HashMap的初始化逻辑。

       举例：初始化一个容量为9的HashMap。

       执行代码后，我们发现初始化容量为，表白官方源码且阈值threshold设置为。

       解析

       通过debug，我们首先关注到构造方法中的初始化逻辑。注意到，初始化阈值时，实际调用的是`tabliSizeFor(int n)`方法，它返回第一个大于等于n的2的幂。例如，`tabliSizeFor(9)`返回，`tabliSizeFor()`返回，`tabliSizeFor(8)`返回8。

       继续解析

       在构造方法结束后，我们通过debug继续追踪至`put`方法，直至`putVal`方法。

       在`putVal`方法中，我们发现当第一次调用`put`时，table为null，从而触发初始化逻辑。在初始化过程中，关键在于`resize()`方法中对新容量`newCap`的初始化，即等于构造方法中设置的阈值`threshold`()。

       阈值更新

       在初始化后，我们进一步关注`updateNewThr`的代码逻辑，发现新的阈值被更新为新容量乘以负载因子，即 * 0.。

       案例分析

       举例：初始化一个容量为8的HashMap。

       解答：答案是8，因为`tableSizeFor`方法返回大于等于参数的2的幂，而非严格大于。

       扩容问题

       举例：当初始化容量为时，放入9个不同的entry是否会引发扩容。

       解答：不会，因为扩容条件与阈值有关，当map中存储的键值对数量大于阈值时才触发扩容。根据第一问，初始化容量是，阈值为 * 0. = 9，我们只放了9个，因此不会引起扩容。

       容量选择

       举例：已知需要存储个键值对，如何选择合适的初始化容量。

       解答：初始化容量的目的是减少扩容次数以提高效率并节省空间。选择容量时，应考虑既能防止频繁扩容又能充分利用空间。具体选择取决于实际需求和预期键值对的数量。

       总结

       通过本文的探讨，我们深入了解了HashMap初始化容量背后的逻辑和原因。希望这些解析能够帮助您更深入地理解HashMap的内部工作原理。如果您对此有任何疑问或不同的见解，欢迎在评论区讨论。

       最后，如有帮助，欢迎点赞分享。

Source Map 原理及源码探索

       前端开发中，代码经过转换后发布到线上时，通常会遇到压缩或混淆的问题，这虽然减小了代码体积，降低了网络开销，但同时也给开发者调试代码带来了不便。为解决这一难题，Source Map应运而生，旨在提供一种方式，使得开发者能够在压缩或混淆后的代码上进行源代码级别的调试。

       从Source Map的诞生和演变可以看出，它经历了几个版本的更新，以适应不同场景的需求。最初由Joseph Schorr创建的v1版，旨在让闭包检查器在优化JS代码时进行源代码级别的调试。随着项目规模的扩大，v1版的映射结果变得异常冗长。v2版对此进行了优化，增加了映射文件的灵活性和简便性，减少了映射文件的总体大小，相较于v1版减少了约%至%。然而，v2版仍存在一些问题，因此v3版应运而生，进一步缩减了映射文件的大小，相较于v2版减少了大约%。

       在v3规范格式中，mappings数据遵循一定的规则，其中VLQ（Variable-Length Quantized）编码起到了关键作用。VLQ编码的原理基于简化数字表示，通过使用特殊字符分隔数字，减少不必要的字符，实现数据的紧凑存储。VLQ背后的想法很简单，即根据数字位数调整分隔符，当数字位数减少时，可以省去分隔符，从而减少存储空间。

       VLQ的进制表示和2进制表示展示了其灵活性。进制表示时，通过在数字之间插入分隔符来区分不同数字。二进制表示中，使用由6位组成的二进制组来表示数值，其中第一位作为连续标记位，确定后续字节组是否需要连续表示，最后一位作为符号标记位，指示数值的正负。这种编码方式允许更高效地表示数值，特别是当数值位数减少时，可以显著节省空间。

       在实际应用中，通过Base编码，VLQ编码的数字可以进一步压缩，使得映射文件更加紧凑。在生成映射文件时，通常需要考虑输入文件的行号，但随着内容的增多，映射编码会快速增多，占用大量空间。为解决这一问题，可以采取以下改进措施：

       1. 省略输出文件的行号，使用“;”换行来节省空间。

       2. 名称和输入文件列表按索引引用，提取出两个索引表，减少重复记录。

       3. 使用相对偏移，而不是绝对偏移，减少映射编码的长度，特别是在处理大型文件时。

       4. 通过VLQ+Base编码进一步压缩映射数据。

       5. 省略不必要的字段，优化映射长度，使其更紧凑。

       在源码探索部分，以uglify-js为例，它利用source-map库生成SourceMap。生成过程涉及source-map库中的SourceMapGenerator类，通过调用generator.toJSON()方法输出SourceMap。在实际应用中，通过了解这些源码，开发者可以更深入地理解Source Map的生成机制，并在需要时进行定制或优化。

       最后，以JS压缩为例，通过应用上述改进措施，可以生成紧凑的SourceMap文件。在实际环境中，使用命令行工具验证生成的SourceMap文件，可以确保其正确性和一致性。

       在前端开发中，合理利用Source Map可以提高调试效率，同时优化代码发布流程。通过源码探索，开发者能够更好地理解Source Map的底层机制，为项目调试和维护提供强有力的支持。

concurrenthashmap1.8源码如何详细解析?

       ConcurrentHashMap在JDK1.8的线程安全机制基于CAS+synchronized实现，而非早期版本的分段锁。

       在JDK1.7版本中，ConcurrentHashMap采用分段锁机制，包含一个Segment数组，每个Segment继承自ReentrantLock，并包含HashEntry数组，每个HashEntry相当于链表节点，用于存储key、value。默认支持个线程并发，每个Segment独立，互不影响。

       对于put流程，与普通HashMap相似，首先定位至特定的Segment，然后使用ReentrantLock进行操作，后续过程与HashMap基本相同。

       get流程简单，通过hash值定位至segment，再遍历链表找到对应元素。需要注意的是，value是volatile的，因此get操作无需加锁。

       在JDK1.8版本中，线程安全的关键在于优化了put流程。首先计算hash值，遍历node数组。若位置为空，则通过CAS+自旋方式初始化。

       若数组位置为空，尝试使用CAS自旋写入数据；若hash值为MOVED，表示需执行扩容操作；若满足上述条件均不成立，则使用synchronized块写入数据，同时判断链表或转换为红黑树进行插入。链表操作与HashMap相同，链表长度超过8时转换为红黑树。

       get查询流程与HashMap基本一致，通过key计算位置，若table对应位置的key相同则返回结果；如为红黑树结构，则按照红黑树规则获取；否则遍历链表获取数据。

MapReduce源码解析之Mapper

       MapReduce，大数据领域的标志性计算模型，由Google公司研发，其核心概念"Map"与"Reduce"简明易懂却威力巨大，打开了大数据时代的大门。对于许多大数据工作者来说，MapReduce是基础技能之一，而源码解析更是深入理解与实践的必要途径。

       MapReduce由两部分组成：Map与Reduce。Map阶段通过映射函数将一组键值对转换成另一组键值对，而Reduce阶段则负责合并这些新的键值对。这种并行计算模型极大地提高了大数据处理的效率。

       本文将聚焦于Map阶段的核心实现——Mapper。通过解析Mapper类及其子类的源码，我们可以更深入地理解MapReduce的工作机制，并在易观千帆等技术数据处理中发挥更大的效能。

       Mapper类内部包含四个关键方法与一个抽象类：

       setup()：主要为map()方法做准备，例如加载配置文件、传递参数。

       cleanup()：用于清理资源，如关闭文件、处理Key-Value。

       map()：程序的逻辑核心，对输入的文本进行处理（如分割、过滤），以键值对的形式写入context。

       run()：驱动Mapper执行的主方法，按照预设顺序执行setup()、map()、cleanup()。

       Context抽象类扮演着重要角色，用于跟踪任务状态和数据存储，如在setup()中读取配置信息，并作为Key-Value载体。

       下面是几个Mapper子类的详细解析：

       InverseMapper：将键值对反转，适用于不同需求的统计分析。

       TokenCounterMapper：使用StringTokenizer对文本进行分割，计算特定token的数量，适用于词频统计等。

       RegexMapper：对文本进行正则化处理，适用于特定格式文本的统计。

       MultithreadedMapper：利用多线程执行Mapper任务，提高CPU利用率，适用于并发处理。

       本文对MapReduce中Mapper及其子类的源码进行了详尽解析，旨在帮助开发者更深入地理解MapReduce的实现机制。后续将探讨更多关键类源码，以期为大数据处理提供更深入的洞察与实践指导。

map在golang的底层实现和源码分析

       在Golang 1..2版本中，map的底层实现由两个核心结构体——hmap和bmap（此处用桶来描述）——构建。初始化map，如`make(map[k]v, hint)`，会创建一个hmap实例，包含map的所有信息。makemap函数负责创建hmap、计算B值和初始化桶数组。

       Golang map的高效得益于其巧妙的设计：首先，key的hash值的后B位作为桶索引；其次，key的hash值的前8位决定桶内结构体的数组索引，包括tophash、key和value；tophash数组还用于存储标志位，当桶内元素为空时，标志位能快速识别。读写删除操作充分利用了这些设计，包括更新、新增和删除key-value对。

       删除操作涉及到定位key，移除地址空间，更新桶内tophash的标志位。而写操作，虽然mapassign函数返回value地址但不直接写值，实际由编译器生成的汇编指令提高效率。扩容和迁移机制如sameSizeGrow和biggerSizeGrow，针对桶利用率低或桶数组满的情况，通过调整桶结构和数组长度，优化查找效率。

       evacuate函数负责迁移数据到新的桶区域，并清理旧空间。最后，虽然本文未详述，但订阅"后端云"公众号可获取更多关于Golang map底层实现的深入内容。

MapBox源码解读 - style 的加载逻辑

       本文主要聚焦于MapBox实例化过程中style的加载和渲染流程。这个过程涉及多个步骤：首先，从数据源发起请求获取style数据，然后通过解析将数据转化为可操作的结构。数据进一步根据属性进行赋值，接着进行着色器的计算，最终在屏幕上呈现图层。为了更直观地理解，这里有一个定制化线侧渲染的demo示例。

       style的加载和渲染过程可以分解为：数据获取-解析-属性赋值-着色器执行。如果你对这个过程还感到困惑，可参考相关附件获取详细信息。

       通过上述步骤，创建mapbox对象时，源代码中添加source和layer的代码其实遵循这样的逻辑：数据驱动图层展现。现在，让我们通过一个简单的线单侧绘制的案例，实际演示这个过程。

       今天的讲解就到这里，额外提一个小贴士：在WebGL的web端调试中，Spector.js是一个非常实用的工具，适用于Firefox和Chrome，你可以自行下载并进行探索使用。