1.JDK成长记7：3张搞懂HashMap底层原理！源码
2.Linux下垃圾文件的源码详解
3.结合源码探究HashMap初始化容量问题

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

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

       在看过了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指针，会以单链表的形式，将冲突的周易算命 php源码节点挂在数组同样位置。这就是数据结构中所提到解决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到了个元素就会进行扩容。

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

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

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

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

Linux下垃圾文件的详解

       Linux计算机安装后，在我们不断的使用过程中，因为添加、删除软件和上网冲浪、乾坤线指标源码调试程序等行为，硬盘中会产生各种各样的垃圾文件，而随着这些垃圾文件的不断膨胀，它们不仅会平白吞噬掉我们宝贵的硬盘空间，更会拖累机器的运行速度，影响我们的工作效率。本文介绍一下给 Linux 系统减肥的方法和工具的使用技巧，本文使用的 Linux 发行版本是Ubuntu. 。本文介绍的工具包括：Activity Log Manager、BleachBit、find、fdupes、Geeqie、GConf Cleaner，这些工具都是开源工具，Linux 用户可以通过下载编译源代码在其他流行的 Linux 版本（如 Redhat、SUSE 等）上使用。

Linux 下哪些文件属于垃圾文件

软件安装过程中产生的临时文件

       许多 bin 格式的软件在安装时，首先要把自身的安装文件解压缩到一个临时目录（一般为/tmp 目录）然后再进行安装。如果软件设计有疏忽或者系统有问题，当安装结束后，这些临时文件就会变得并不临时，成为硬盘里的一堆垃圾，很多时候它们以*.tmp 的面孔出现。

软件运行过程中产生的临时文件

       和安装过程一样，在软件的运行过程中通常也会产生一些临时交换文件，有些软件运行过后遗留下来的垃圾甚至多达数百兆，比如ssh服务器和客户端连接过程中时产生的文件。还有虚拟机运行时产生的文件。另外我们删除一个账户之后,还会存在一些无用垃圾文件及目录。

上网冲浪产生的临时文件

       我们在上网的时候，浏览器总是将网页文件下载到本地机器上，这些缓存文件不但占用了宝贵的磁盘空间，还常常会把我们的个人隐私公之于众。

一些不常用的鸡肋文件

       比如一些应用软件自带的帮助和系统手册页等。既然食之无味索性也将它们视作垃圾文件的一种表现。占用空间甚大，更会严重拖累系统和一些图形处理软件的运行速度。另外还有一些损坏的桌面文件，它包括损坏的应用程序菜单按钮和文件关联。

各种缓存文件

       如果 Linux 用户安装使用 GIMP 或者 Geeqie 等图形编辑工具，在这些软件都有预览功能，在保存了的文件夹下会产生一个名为Thumbs.db的文件，这个文件会随着文件的增加而膨胀。还有就是.DS_Store 文件，DS_Store 文件是用来存储这个文件夹的显示属性的：比如文件图标的摆放位置。删除以后的副作用就是这些信息的失去。另外还有使用 apt 或者yum软件包安装过程中生成的缓存文件。

       使用 Linux 命令删除垃圾文件 删除用户后遗留下的垃圾文件

       这里我们使用到的主要命令是 find 。举个例子： 我们删除一个账户之后,还会存在一些无用垃圾文件及目录,我们要找出属于这个用户的垃圾东西，使用 find / -user 用户名 :就可以找到根目录下属于这个用户的相关文件 ，使用命令：

       #find ./ -nouser |xargs rm rf

core 文件

       当我们在系统下运行某个程序出错的时候，系统会自动将残留在内存中的数据存成 core 文件，久而久之，系统中遗留下来的 core 会越来越多，就像灰尘一样散落在系统的每一个角落里很是烦人。这个时候，我们就可以应用 find 命令加上exec参数来清理它们。使用命令：

       # find / -name core -print -exec rm -rf { } ;

多余的手册页

       另外 Linux 提供了众多语言的手册页（man）比如 Ubuntu 的 手册页位于/usr/share/man 目录下 ，可以使用命令删除多余语言的手册页保留中英文即可。

       # cd /usr/share/man # find ./ -maxdepth 1 -type d | tail -n +2 | grep -E -v '(en|zh|man).*' | while read d; do rm -rf $d; done

       说明:关键字是(en|zh|man) ，您可以根据自己的情况修改。

       使用 fdupes 工具删除指定目录下重复文件

       fdupes 是一个命令行工具，它会查找和删除指定目录的重复文件，它通过文件的大小和 MD5 值进行比较 。一个字节一个字节进行对比。 首先安装这个工具

       # apt-get install fdupes

       在 /etc 目录查找重复文件 ，使用如下命令：

       #fdupes /etc

       可以与 Linux 命令组合使用，删除文件 ：

       #fdupes -r -f . | grep -v ^$ | tee duplicate.txt cat duplicate.txt | while read file; do rm -v $file; done

       另外也可以与sed命令组合使用，删除文件 ：

       # fdupes -r -n -S /tmp | sed -r s/^/#rm / | sed -r s/$// duplicate-files.sh

删除缓存文件

       清理旧版本的软件缓存

       # apt-get autoclean

       清理所有软件缓存：

       #apt-get clean

使用 Geeqie 工具找出相似图像文件

       现在的硬盘容量是越来越大，出于备份的考虑，很多朋友会采取宁滥勿缺的原则保存，这就可能出现文件重复的情况，造成文件搜索的效率低下。要在海量的存储空间中找出重复的文档，并不是一件容易的工作。其实借助著名的图像浏览工具 Geeqie 可以很轻松地找出系统中的重复和相似图像文件。这些文件相比文本文件更大，时间长了会占用很多硬盘空间。使用上面介绍的 fdupes 工具就不行，因为 fdupes 工具只能删除完全相同 (md5sum相同) 的重复文件, 但若要剔除 相似 的文件, 则可使用 geeqie 工具。首先安装这个工具：

       # apt-get install gqview

       下面运行这个工具，在要搜索的目录上按鼠标右键, 选择 Find duplicates recursive...见图 1 。

       选择左下角的 Compare by: 下拉菜单可选择比对方式 Similarity (custom)找出相似度 % 以上的，另外可以勾选 Thumbnails 可显示缩略图见图 2

       下面在被选取的项目上按鼠标右键, 点选 Delete 即可删除所有被选取的， 删除前会有一个的确认界面以免误删。说明 %是相似度的缺省值，用户可以通过如下方式修改参数：在 Edit Preferences Preferences... Behavior Miscellaneous: Custom similarity threshold 见图 3 。

使用 BleachBit 清理文件 简介

       BleachBit 是一款开源免费的系统清理工具，功能类似 Windows 平台的 CCleaner。BleachBit 能够删除隐藏的垃圾文件，以及简单的保护你的隐私。擦除缓存，删除 cookies 文件，清除互联网浏览历史，删除未使用的本地化碎片日志，删除临时文件，是一款非常实用的跨平台的系统清理工具。BleachBit 提供有rpm和 deb 二进制包，适用于Fedora/CentOS/RHEL、Debian/Ubuntu 等 Linux 发行版。其它 Linux 用户可以选择 BleachBit 的源码包（下载地址：/download.PHP）。使用 BleachBit，你可以清理系统中的缓存、历史、临时文件、cookies 等不需要的东西，这样可以释放你的磁盘空间。当前，BleachBit 能够清理 Beagle、Firefox、Epiphany、Flash、OpenOffice.org 、KDE、 GIMP、JAVA编程工具、vim、Gedit 编辑器等 多种软件所产生的垃圾文件。还有系统运行时生成的Thumbs.db的文件和使用 apt 或者 YUM 软件包安装过程中生成的缓存文件以及剪切板里面的历史文件信息等。

       首先安装软件：

       #apt-get install bleachbit

       安装之后系统工具菜单里就会多出两个工具：bleachbit 和 bleachbitasroot。对于 root 用户使用第 2 个，软件第一次运行，弹出首选项窗口，见图 4。

       简单说明一下设置界面：包括定制文件和文件夹，驱动器列表 ，语言，白名单（免于清理的）设置，以及是否开机启动 BleachBit 等一些选项。

       下面看看工作界面见图 5。

       BleachBit 软件功能单一因此使用起来也方便。从图 5 里我能看到。 软件的左边罗列出了能够清理的各种垃圾，点击预览按钮，就会分析出垃圾文件的明细和大小。 勾选好软件按 clean（清除）按钮即可。

以 Chrome 浏览器为例介绍操作实例

       Chrome 浏览器可以清理的文件主要包括：

       缓存: 删除那些网页缓冲文件(这些缓冲文件可以减少下次访问该网页的时间) Cookies: 删除 cookies 文件，它们保存网站首选项、认证和身份等信息 当前会话: 删除当前会话 DOM(文档对象模型) 存储: 删除HTML5cookies 表单历史: 网站表单输入历史 历史: 删除已浏览网站、下载及缩略图的历史记录 搜索引擎: 重置搜索引擎使用历史并删除非内置搜索引擎，其中一些引擎为自动添加 整理数据库: 清理数据库碎片以减少空间并提高速度(无需删除任何数据)

       首先查看可清理的 Chrome 浏览器文件见图 6 。

       选中欲清理的项目后，点击预览按钮即可执行对该类项目内所含垃圾文件的扫描操作，扫描过程非常快速，扫描过程完毕，用户将看到检测到的垃圾文件列表及其统计信息，下面用户只需鼠标点击清理按钮即可轻松清除这些已经被检测到的垃圾文件。

       上面笔者选择执行的是对 Chrome 浏览器的扫描清理任务，当然可以选择全部垃圾列表中的所有项目，用户只需逐一勾选扫描项目选择激活项即可。

       使用 Activity Log Manager 清理残留在系统中的使用痕迹

       上网冲浪，用账号登录系统，包括使用一些编辑软件都会在系统里留下蛛丝马迹，这些残留信息中包含个人信息，如果被不法分子利用，就会造成隐私泄露，下面介绍的工具是 Activity Log Manager，它是配置在 Zeitgeist 活动日志中记录的内容的 ，使用它可以有效保护隐私。首先安装这个工具：

       #apt-get install activity-log-manager

       Activity Log Manager 的中文名称是活动日志管理器，安装完成后出现在附件菜单中。它的使用方法也比较简单。最直接的就是设置停止记录的功能，然后删除所有历史文件见图 7 。

       当然用户也可以进行有区别的设置，可以根据具体情况设置哪些应用程序和文件可以保留历史文件那些不保留。下面通过文件界面进行设置见图 8

       这里笔者选择电子表格、文本、即时消息三个事关隐私的选项。另外对于一些特殊的应用程序用户还可以自己添加到活动日志管理器中，见图 9

使用 GConf Cleaner 清理 GConf

       GConf 是一个用于存储 GNOME 应用程序选项设置的系统。如果该系统充斥着大量无用键值，那么将使 GConf 臃肿不堪。这对应用程序的启动速度和性能都是有影响的。为了解决这个问题，你可以使用 GConf Cleaner 来对其进行清理。Gconf-Cleaner 是一款类似于 Windows 注册表清理器的工具。它会检查 Gconf 数据库（即 GNOME 配置数据库）并移除无用及过时的项目。

       首先安装这个工具：

       #apt-get install gconf-cleaner

       然后从终端执行 gconf-cleaner 启动 GConf Cleaner 程序。这个程序具有执行向导，只需按步骤操作即可。 向导初始画面，点击 Forward 会进入分析过程。图 是分析结果，它提供具体数据，并可保存。再次点击 Forward 则开始清理过程。

结合源码探究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的内部工作原理。如果您对此有任何疑问或不同的见解，欢迎在评论区讨论。

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