皮皮网

1.HashMap实现原理一步一步分析(1-put方法源码整体过程)
2.BoltDB源码解析（七）Put和Delete操作
3.JDK成长记7：3张图搞懂HashMap底层原理！码详
4.FREE SOLO - 自己动手实现Raft - 16 - leveldb源码分析与调试-2

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的其他特性，如数组长度的优化、多线程环境下的性能优化和红黑树的引入。

BoltDB源码解析（七）Put和Delete操作

       Put和Delete的实现

       上一篇文章我们了解了BoltDB的Get API的实现。现在，我们来探讨Put和Delete API的实现：

       Put API的主要功能是将一对键值对插入到Bucket中，如果键已经存在，则更新对应的值。首先，进行一些限制条件的检查，例如Put操作是否由写事务发起的，因为Put只能由写事务调用。此外，还需要检查键和值的大小是否符合限制条件。需要注意的是，Put操作和Get操作一样，源码 区块链这里也使用了Cursor来定位键应该放置的位置。

       在实际的Put操作中，会调用Cursor的一个不显眼的方法：

       这个方法实际上非常有用，它从当前Bucket的B-tree的根节点开始，一直到Cursor定位到的leaf page，为每个page创建一个对应的node结构。当然，如果一个page已经有对应的node，就直接使用它。

       为什么要这么做呢？这是因为事务篇中提到的修改操作具有“传染性”，修改B-tree的leaf节点会导致从root到leaf的所有page都需要修改，而BoltDB的修改操作都是在page对应的node里进行的，不是直接在page上修改，因此需要为这些page建立node结构。具体建立node结构的是Bucket的node方法：

       Bucket的node方法有两处需要注意，一个是新建的node会被追加到parent node的children中，记录下这些修改的node之间的关系，这个children在node持久化时会有用(node.spill方法)。另一个是node的数据是如何从page中读取的，这是由node的read方法完成的。

       node建立好之后，就在要修改的leaf对应的node上调用put方法：

       node的put方法相对简单，它是在inodes数组上查找对应的位置，如果exact为true，表示找到了相同的key，直接更新value；如果exact为false，相当于找到了应该插入的位置，然后在对应的inode上记录数据。我们来看一下inodes数组的定义：

       inodes数组是node实际存储数据的地方，由多个inode组成，每个不同的key对应一个不同的inode，inode之间是按key排序的。对于leaf节点来说，inode里使用key和value；对于branch节点来说，inode里使用key和pgid，pgid代表一个child page的id。value和pgid不会同时使用。

       put方法结束后，当前的Put操作也就结束了。也就是说，Put操作所做的仅仅是把新增或修改的数据放入到它所在的page对应的node内存中。

       顺便提一下Delete操作，它和Put操作非常类似，在建立起node结构之后，在对应的node的inodes数组中删除找到的key相等的inode就完成了，这里不再展开。表白计时源码

       那么，什么时候会把这些node里的数据持久化到DB文件里呢？是在整个写事务commit的时候。

       事务的Commit实现

       下面是事务commit的代码简化，保留了重要部分：

       Commit的整体流程比较长，下面一点一点进行说明。

       tx.root.rebalance()，这个root是root Bucket，rebalance是对root Bucket下所有子Bucket的所有node进行rebalance。这是什么意思？注意node的初始数据虽然来自一个page，但在经历了一些Delete操作后，有些node里面的数据可能过少，这时会先把这个node和它的左兄弟或右兄弟node合并(node的rebalance方法)，合并后node数会减少，但不存在node里数据过少的情况。这个操作对应于B-tree的merge操作，只不过这些node都是Go的内存结构，合并起来非常简单。当然，合并后把这些node spill到page的操作，需要的page总数也会减少。

       tx.root.spill()，这个方法是把root Bucket下所有子Bucket的所有node的内容都写入这个事务分配的dirty page里。注意这些dirty page是这个事务临时分配在内存里的，结构和DB文件的page完全一样，但还不是mmap映射的DB的page。

       刚开始看到spill这个方法时，感觉它代价有些高，感觉像是把整个B-tree都走了一遍。后来仔细看才发现不是这么回事。这个spill只对有node结构的节点进行处理，那些没修改过的page没有对应的node，根本不会处理。

       注意在经过多次Put操作后，node里存放的数据可能出现一个page写不下的情况，比如insert了几千个key value。spill会先把这样的node split成多个大小合适的node(node的split方法)，然后把这些node分别写入不同的page中。这个操作对应于B-tree的split操作。和rebalance方法类似的道理，因为这些node都是Go的内存结构，split起来非常容易。

       if tx.meta.pgid > opgid，这个判断是看当前事务需要的page数是否大于事务执行前DB文件有的page数，如果大于，说明DB文件放不下了，就调用db.grow增大文件，照片论坛源码以容纳新增的page。

       紧接着是freelist的持久化操作，因为写事务可能使用了freelist里的一些page，同时也可能释放了一些page到freelist里，所以freelist很可能发生了变化，需要持久化。

       tx.write()，这个方法就是把所有的临时分配的dirty page都写入DB文件对应的page里。

       tx.writeMeta()，这个方法是把这个tx里的meta写到meta0或者meta1里面（写事务会交替写这两个meta page，这也是个常用技术，叫ping-pong buffer）。它的代码值得看一下：

       首先把meta写到临时分配的buf里，然后用文件IO写到DB文件里，最后调用fdatasync，把OS文件的buffer cache持久化到磁盘上。至此，写事务的所有数据都已经落盘完毕。后面新开启的事务会因为这个meta的txid是最大的，而选择使用这个最新的meta page。而这个meta page包括最新的root bucket，最新的freelist，最新的pgid，这些总体构成了一个DB的最新版本，保证新开启的事务读到最新版本的数据。

       看tx.write()和tx.writeMeta()的实现可以发现，写入数据用的是db.ops.writeAt，而这个方法默认值就是File.WriteAt方法，所以实际写入文件用的是文件IO，而不是直接写mmap内存。而BoltDB使用mmap一开始就把mmap映射的内存标记为只读的，压根不允许直接写mmap内存。为什么要这么做呢？

       猜测可能是为了安全。前面讲到Get操作为了性能是zero copy的，发现Get返回来的value是mmap上数据的指针，如果mmap设置为可读写的，应用程序代码五花八门，可能会通过指针一不小心修改了mmap上的数据，这样的修改因为走的不是API是无法保证事务的。把mmap设置为只读的消除了这种可能性。反过来说，如果mmap设置为可读写的，Get就不能返回mmap上的指针了，为了安全一定要copy一份数据出来才行，降低了Get的性能。

       这里还有个很自然而且很重要的vb围棋源码问题是，如果事务commit失败了呢，BoltDB如何保证事务的原子性（ACID的A），确保这个写事务的所有操作，不论是落盘的，还是没落盘的，都不会生效？

       原子性要求，不管是commit走到哪一步，哪怕是已经把修改的数据，甚至包括修改的freelist已经落盘，只要最终事务commit失败，都不能对正确性产生任何影响。这里的正确性是指，数据库的状态（有实际的key value数据，freelist， pgid等共同构成）必须是在这个写事务运行之前的状态，数据不能被破坏，这个写事务也不能留下可被后续事务读到的任何更新。

       要做到原子性貌似挺难的，因为事务的commit里包括很多步骤，这些步骤都不是原子性的。不过重要的一点是，不论commit运行到哪一步，因为tx.writeMeta是最后一步，只有这一步运行成功commit才算成功，如果说commit失败了，那么tx.writeMeta一定是没运行，或者运行了半截，这个meta page没写完整，机器断电了。总之，这些情况下我们不会得到一个合法的新的meta page(这种情况下meta的validate方法会失败，因为meta的checksum不对)。这时候ping-pong buffer的meta page就起重要的作用了，因为交替写meta page的原因，即使这个写事务新的meta page没写成功，这个写事务运行前版本的meta page还在，而这个meta page包括这个写事务运行前的DB版本所有的状态（kv数据，freelist，pgid等）。这个meta page会被后续事务使用，就像那个失败的写事务从来没有运行过一样。而那个写事务留下的kv数据的page，freelist的page，即使是持久化了，也因为没有写成新的meta，没有机会被用到。

       还有个自然的疑问，即使这个失败的写事务写的page因为没有合法的meta无法被引用，不会影响正确性，但无法被引用是不是也意味着这些page无法被回收，浪费了磁盘空间？

       答案是也不会。在原来版本的meta里的free list和pgid的共同作用下，这些page会被视为free的，还可以使用，不会出现无法回收这些page的情况。

       还有个疑问，既然BoltDB交替写meta0和meta1，是不是连续两个事务commit正好在写meta时失败，数据库就废了？

       仔细研究发现，还是没事！因为写事务的txid也是meta的一部分，一个写事务失败，导致txid不会增长，下一次写事务的txid还是一样，meta的交替写是因为txid的变化引起的，既然没变化，就不交替了。所以下一个写事务即使写meta还失败了，也还是写的上一个写事务写的那个meta，不会把两个meta都写坏。

       总结一下，ping-pong buffer的meta page真是设计得精巧，是BoltDB达到原子性的关键！

JDK成长记7：3张图搞懂HashMap底层原理！

       一句话讲， HashMap底层数据结构，JDK1.7数组+单向链表、JDK1.8数组+单向链表+红黑树。

       在看过了ArrayList、LinkedList的底层源码后，相信你对阅读JDK源码已经轻车熟路了。除了List很多时候你使用最多的还有Map和Set。接下来我将用三张图和你一起来探索下HashMap的底层核心原理到底有哪些？

       首先你应该知道HashMap的核心方法之一就是put。我们带着如下几个问题来看下图：

       如上图所示，put方法调用了putVal方法，之后主要脉络是：

       如何计算hash值？

       计算hash值的算法就在第一步，对key值进行hashCode()后，对hashCode的值进行无符号右移位和hashCode值进行了异或操作。为什么这么做呢？其实涉及了很多数学知识，简单的说就是尽可能让高和低位参与运算，可以减少hash值的冲突。

       默认容量和扩容阈值是多少？

       如上图所示，很明显第二步回调用resize方法，获取到默认容量为，这个在源码里是1<<4得到的，1左移4位得到的。之后由于默认扩容因子是0.，所以两者相乘就是扩容大小阈值*0.=。之后就分配了一个大小为的Node[]数组，作为Key-Value对存放的数据结构。

       最后一问题是，如何进行hash寻址的？

       hash寻址其实就在数组中找一个位置的意思。用的算法其实也很简单，就是用数组大小和hash值进行n-1&hash运算，这个操作和对hash取模很类似，只不过这样效率更高而已。hash寻址后，就得到了一个位置，可以把key-value的Node元素放入到之前创建好的Node[]数组中了。

       当你了解了上面的三个原理后，你还需要掌握如下几个问题:

       还是老规矩，看如下图：

       当hash值计算一致，比如当hash值都是时，Key-Value对的Node节点还有一个next指针，会以单链表的形式，将冲突的节点挂在数组同样位置。这就是数据结构中所提到解决hash 的冲突方法之一：单链法。当然还有探测法+rehash法有兴趣的人可以回顾《数据结构和算法》相关书籍。

       但是当hash冲突严重的时候，单链法会造成原理链接过长，导致HashMap性能下降，因为链表需要逐个遍历性能很差。所以JDK1.8对hash冲突的算法进行了优化。当链表节点数达到8个的时候，会自动转换为红黑树，自平衡的一种二叉树，有很多特点，比如区分红和黑节点等，具体大家可以看小灰算法图解。红黑树的遍历效率是O(logn)肯定比单链表的O(n)要好很多。

       总结一句话就是，hash冲突使用单链表法+红黑树来解决的。

       上面的图，核心脉络是四步，源码具体的就不粘出来了。当put一个之后，map的size达到扩容阈值，就会触发rehash。你可以看到如下具体思路：

       情况1:如果数组位置只有一个值：使用新的容量进行rehash，即e.hash & (newCap - 1)

       情况2:如果数组位置有链表，根据 e.hash & oldCap == 0进行判断，结果为0的使用原位置，否则使用index + oldCap位置,放入元素形成新链表，这里不会和情况1新的容量进行rehash与运算了，index + oldCap这样更省性能。

       情况3：如果数组位置有红黑树，根据split方法，同样根据 e.hash & oldCap == 0进行树节点个数统计，如果个数小于6，将树的结果恢复为普通Node，否则使用index + oldCap，调整红黑树位置，这里不会和新的容量进行rehash与运算了，index + oldCap这样更省性能。

       你有兴趣的话，可以分别画一下这三种情况的图。这里给大家一个图，假设都出发了以上三种情况结果如下所示：

       上面源码核心脉络，3个if主要是校验了一堆，没做什么事情，之后赋值了扩容因子，不传递使用默认值0.，扩容阈值threshold通过tableSizeFor(initialCapacity);进行计算。注意这里只是计算了扩容阈值，没有初始化数组。代码如下：

       竟然不是大小*扩容因子？

       n |= n >>> 1这句话，是在干什么？n |= n >>> 1等价于n = n | n >>>1; 而|表示位运算中的或，n>>>1表示无符号右移1位。遇到这种情况，之前你应该学到了，如果碰见复杂逻辑和算法方法就是画图或者举例子。这里你就可以举个例子：假设现在指定的容量大小是,n=cap-1=，那么计算过程应该如下：

       n是int类型，java中一般是4个字节，位。所以的二进制： 。

       最后n+1=，方法返回，赋值给threshold=。再次注意这里只是计算了扩容阈值，没有初始化数组。

       为什么这么做呢？一句话，为了提高hash寻址和扩容计算的的效率。

       因为无论扩容计算还是寻址计算，都是二进制的位运算，效率很快。另外之前你还记得取余(%)操作中如果除数是2的幂次方则等同于与其除数减一的与(&)操作。即 hash%size = hash & (size-1)。这个前提条件是除数是2的幂次方。

       你可以再回顾下resize代码，看看指定了map容量，第一次put会发生什么。会将扩容阈值threshold，这样在第一次put的时候就会调用newCap = oldThr;使得创建一个容量为threshold的数组，之后从而会计算新的扩容阈值newThr为newCap*0.=*0.=。也就是说map到了个元素就会进行扩容。

       除了今天知识，技能的成长，给大家带来一个金句甜点，结束我今天的分享：坚持的三个秘诀之一目标化。

       坚持的秘诀除了上一节提到的视觉化，第二个秘诀就是目标化。顾名思义，就是需要给自己定立一个目标。这里要提到的是你的目标不要定的太高了。就比如你想要增加肌肉，给自己定了一个目标，每天5组，每次个俯卧撑，你看到自己胖的身形或者海报，很有刺激，结果开始前两天非常厉害，干劲十足，特别奥利给。但是第三天，你想到要个俯卧撑，你就不想起床，就算起来，可能也会把自己撅死过去......其实你的目标不要一下子定的太大，要从微习惯开始，比如我媳妇从来没有做过俯卧撑，就让她每天从1个开始,不能多，我就怕她收不住，做多了。一开始其实从习惯开始，先变成习惯，再开始慢慢加量。量太大养不成习惯，量小才能养成习惯。很容易做到才能养成，你想想是不是这个道理？

       所以，坚持的第二个秘诀就是定一个目标，可以通过小量目标，养成微习惯。比如每天你可以读五分钟书或者5分钟成长记，不要多，我想超过你也会睡着了的.....

       最后，大家可以在阅读完源码后，在茶余饭后的时候问问同事或同学，你也可以分享下，讲给他听听。

FREE SOLO - 自己动手实现Raft - - leveldb源码分析与调试-2

       继续探讨leveldb的内部操作，首先解析写入过程。write-batch和leveldb key是核心数据结构，它们在数据写入中的角色至关重要。

       1. 数据写入流程：当通过DBImpl::Put或DB::Put添加键值对时，数据会被封装成write-batch。这个batch随后交给DBImpl::Write，最终由log::Writer::AddRecord负责将数据写入log。这样，数据便有了持久化的记录。

       2. 写入memtable：写入log后，数据还会被添加到memtable，便于快速查询。同样，DBImpl::Write通过MemTableInserter::Put调用MemTable::Add，将数据写入memtable，形成内存中的临时存储。

       3. 数据读取：对于查询，DBImpl::Get是起点，通过MemTable::Get调用SkipList::FindGreaterOrEqual在SortedTable的SkipList中搜索，提供即时的数据访问。

       总结：通过上述调用栈，我们可以对leveldb的写入和读取有更深入的理解。在后续的内容中，我们将关注大量数据写入对内存和磁盘影响的详细分析。

       期待在下次与您分享更多内容，再见！

       联系信息：email: castermode@gmail.com | 网站：vectordb.io | 项目未指定