深入理解Java HashMap遍历元素的顺序-程序员宅基地
技术标签： java map遍历顺序
HashMap遍历元素的顺序。
一，HashMap元素的底层存储顺序
我们都知道HashMap是“无序”的，也就是说不能保证插入顺序。但是，HashMap其实也是有序的，一组相同的key-value对，无论他们插入的顺序是什么样的，遍历时，顺序都是一致的。
图片发自简书App
上面的代码，分别使用两种方式插入，也就是说插入顺序是不同的，但是遍历的结果是一样的。可以这样理解，只要你插入的是这19个元素，HashMap存储的时候，都是按照同一个顺序来存储的。
这一点其实也很容易理解，因为HashMap是使用hash算法来定位key的逻辑存储位置，只要你的key是一样的，逻辑存储位置也是一样的。
遍历结果如下：
11=11
12=12
13=13
14=14
15=15
16=16
17=17
18=18
19=19
0=0
1=1
2=2
3=3
4=4
5=5
6=6
7=7
8=8
9=9
10=10
为什么是这个顺序呢？本人很不理解。
如果说是根据key的hashcode来定位逻辑存储位置的话，关键key的hashcode也不支持这种说法啊。key的hashcode打印如下：
1568
1569
1570
1571
1572
1573
1574
1575
1576
49
50
51
52
53
54
55
56
57
1567
HashMap是通过hash算法把key映射到table数组的某个位置。以这个例子为例来说明，HashMap初始化容量指定为20，最终HashMap会把容量转化为32，那么这个HashMap的数组是一个长度为32的数组。
(为什么？稍后会说明)
OK，我们有一个长度为32的数组，接下来我们插入第一个元素，也就是key为0的一个字符串，这个key的hashcode值为48。那么这个key会被映射到数组的哪个位置呢？这个key对应数组的下标是多少呢？
这里有一个问题需要注意，长度为32的数组的下标必然是从0到31。然后这个数组的遍历顺序也是从0到31的顺序开始遍历。
查看源码我才发现，原来，数组的下标并不是key的hashcode值，而是key的hashcode值再经过按位与逻辑运算得到的。
先看一下源码，其他的代码我这里就不贴了，我只看最下面这行最关键的代码，如下图。
图片发自简书App
newTab[e.hash & (newCap - 1)] = e;
就是这行代码，这行代码就是把新增的节点Node放到数组中，放到数组中的哪个位置呢？
放到下标=e.hash & (newCap - 1)的位置！
好，那我就把e.hash & (newCap - 1)打印出来，看看到底是什么？
因为我们有20个元素，HashMap最终扩容以后的大小是32，也就是说：
newCap = 32
e. hash刚才说了，就是key的hashcode值，好，打印看看到底是什么鬼！
0-1-2-3-4-5-6-7-8-16-17-18-19-20-21-22-23-24-25-31
这就是结果！
这就是HashMap元素的存储顺序！
这就是HashMap元素的底层逻辑地址！
这！我的疑惑总算解开了！
下面再说一下2个关键问题：
1，指定的size大小是20，容量大小为什么变成了32。
2，HashMap为什么不直接用key的hashcode值来定位数组下标。
二，HashMap扩容的容量大小问题
HashMap初始化时，如果不指定，那么默认的容量大小为16。源代码中是这样的：
DEFAULT_INITIAL_CAPACITY = 1 << 4
但是我指定了容量为20，为什么就变成了32呢？
想搞清楚这个问题，必须清楚HashMap容量大小的计算逻辑。
源码如下：
图片发自简书App
这个方法是一系列的逻辑位运算。反正我现在是看不懂了，不过没关系，我把代码拿过来跑一下看看结果。
当入参是16的时候，返回16。
当入参是20的时候，返回是32。
原来如此啊，HashMap的容量大小必须是2的N次方。
结论：HashMap的容量必须是2的N次方，如果你指定了一个非2的N次方的整数S，那么HashMap在内部会把它转化为大于S的2的N次方的整数。
当然，这个整数是大于S的2的N次方的整数中最小的那一个。
三，HashMap为什么不直接用key的hashcode值来定位数组下标。
原因其实很简单，因为本例中HashMap的数组是一个长度为32的数组，下标从0到31。
key的hashcode值超过了31，就不行了。
所以，java的开发者做了一个映射，把key的hashcode值映射到0到31的区间范围。如何映射的呢？就是上面提到的：
e.hash & (newCap - 1)
把key的hashcode值与31做位与操作。
java的位与操作，忘记的可以自行脑补，我这里不在赘述，网上有很多讲解。我这里说一下java设计者的实现思路，为什么要这样实现。
为什么呢？因为HashMap是可以扩容的，newCap这个变量是动态的，本例中是32，但是如果是64呢，如果是256呢？
这时我就把这个newCap当做一个变量，接受用户输入。这样就成功把key的hashcode值映射到了指定范围的区间内：
【0到newCap减1】
这里的位与操作是关键，我们想把一些随机的整数映射到指定范围的区间时，可以考虑使用位与操作。这是计算机逻辑运算的特性，java的开发者们很好的利用了这一特性。
好了，今天的分享到此结束。
智能推荐
从零开始搭建Hadoop_创建一个hadoop项目-程序员宅基地
文章浏览阅读331次。第一部分：准备工作1 安装虚拟机2 安装centos73 安装JDK以上三步是准备工作，至此已经完成一台已安装JDK的主机第二部分：准备３台虚拟机以下所有工作最好都在root权限下操作1 克隆上面已经有一台虚拟机了,现在对master进行克隆,克隆出另外2台子机;1.1 进行克隆21.2 下一步1.3 下一步1.4 下一步1.5 根据子机需要,命名和安装路径1.6 ..._创建一个hadoop项目
心脏滴血漏洞HeartBleed CVE-2014-0160深入代码层面的分析_heartbleed代码分析-程序员宅基地
文章浏览阅读1.7k次。心脏滴血漏洞HeartBleed CVE-2014-0160 是由heartbeat功能引入的，本文从深入码层面的分析该漏洞产生的原因_heartbleed代码分析
java读取ofd文档内容_ofd电子文档内容分析工具（分析文档、签章和证书）-程序员宅基地
文章浏览阅读1.4k次。前言ofd是国家文档标准，其对标的文档格式是pdf。ofd文档是容器格式文件，ofd其实就是压缩包。将ofd文件后缀改为.zip，解压后可看到文件包含的内容。ofd文件分析工具下载：点我下载。ofd文件解压后，可以看到如下内容： 对于xml文件，可以用文本工具查看。但是对于印章文件(Seal.esl)、签名文件(SignedValue.dat)就无法查看其内容了。本人开发一款ofd内容查看器，..._signedvalue.dat
基于FPGA的数据采集系统（一）_基于fpga的信息采集-程序员宅基地
文章浏览阅读1.8w次，点赞29次，收藏313次。整体系统设计本设计主要是对ADC和DAC的使用，主要实现功能流程为：首先通过串口向FPGA发送控制信号，控制DAC芯片tlv5618进行DA装换，转换的数据存在ROM中，转换开始时读取ROM中数据进行读取转换。其次用按键控制adc128s052进行模数转换100次，模数转换数据存储到FIFO中，再从FIFO中读取数据通过串口输出显示在pc上。其整体系统框图如下：图1：FPGA数据采集系统框图从图中可以看出，该系统主要包括9个模块：串口接收模块、按键消抖模块、按键控制模块、ROM模块、D.._基于fpga的信息采集
微服务 spring cloud zuul com.netflix.zuul.exception.ZuulException GENERAL-程序员宅基地
文章浏览阅读2.5w次。1.背景错误信息：-- [http-nio-9904-exec-5] o.s.c.n.z.filters.post.SendErrorFilter : Error during filteringcom.netflix.zuul.exception.ZuulException: Forwarding error at org.springframework.cloud..._com.netflix.zuul.exception.zuulexception
邻接矩阵-建立图-程序员宅基地
文章浏览阅读358次。1.介绍图的相关概念 图是由顶点的有穷非空集和一个描述顶点之间关系-边（或者弧）的集合组成。通常，图中的数据元素被称为顶点，顶点间的关系用边表示，图通常用字母G表示，图的顶点通常用字母V表示，所以图可以定义为: G=(V,E)其中，V(G)是图中顶点的有穷非空集合，E(G)是V(G)中顶点的边的有穷集合1.1 无向图：图中任意两个顶点构成的边是没有方向的1.2 有向图：图中..._给定一个邻接矩阵未必能够造出一个图
随便推点
MDT2012部署系列之11 WDS安装与配置-程序员宅基地
文章浏览阅读321次。（十二）、WDS服务器安装通过前面的测试我们会发现，每次安装的时候需要加域光盘映像，这是一个比较麻烦的事情，试想一个上万个的公司，你天天带着一个光盘与光驱去给别人装系统，这将是一个多么痛苦的事情啊，有什么方法可以解决这个问题了？答案是肯定的，下面我们就来简单说一下。WDS服务器，它是Windows自带的一个免费的基于系统本身角色的一个功能，它主要提供一种简单、安全的通过网络快速、远程将Window..._doc server2012上通过wds+mdt无人值守部署win11系统.doc
python--xlrd/xlwt/xlutils_xlutils模块可以读xlsx吗-程序员宅基地
文章浏览阅读219次。python–xlrd/xlwt/xlutilsxlrd只能读取，不能改,支持 xlsx和xls 格式xlwt只能改，不能读xlwt只能保存为.xls格式xlutils能将xlrd.Book转为xlwt.Workbook，从而得以在现有xls的基础上修改数据，并创建一个新的xls，实现修改xlrd打开文件import xlrdexcel=xlrd.open_workbook('E:/test.xlsx') 返回值为xlrd.book.Book对象,不能修改获取sheett_xlutils模块可以读xlsx吗
关于新版本selenium定位元素报错：‘WebDriver‘ object has no attribute ‘find_element_by_id‘等问题_unresolved attribute reference 'find_element_by_id-程序员宅基地
文章浏览阅读8.2w次，点赞267次，收藏656次。运行Selenium出现'WebDriver' object has no attribute 'find_element_by_id'或AttributeError: 'WebDriver' object has no attribute 'find_element_by_xpath'等定位元素代码错误，是因为selenium更新到了新的版本，以前的一些语法经过改动。..............._unresolved attribute reference 'find_element_by_id' for class 'webdriver
DOM对象转换成jQuery对象转换与子页面获取父页面DOM对象-程序员宅基地
文章浏览阅读198次。一：模态窗口//父页面JSwindow.showModalDialog(ifrmehref, window, 'dialogWidth:550px;dialogHeight:150px;help:no;resizable:no;status:no');//子页面获取父页面DOM对象//window.showModalDialog的DOM对象var v=parentWin..._jquery获取父window下的dom对象
什么是算法？-程序员宅基地
文章浏览阅读1.7w次，点赞15次，收藏129次。算法（algorithm）是解决一系列问题的清晰指令，也就是，能对一定规范的输入，在有限的时间内获得所要求的输出。 简单来说，算法就是解决一个问题的具体方法和步骤。算法是程序的灵 魂。二、算法的特征1.可行性 算法中执行的任何计算步骤都可以分解为基本可执行的操作步，即每个计算步都可以在有限时间里完成（也称之为有效性） 算法的每一步都要有确切的意义，不能有二义性。例如“增加x的值”，并没有说增加多少，计算机就无法执行明确的运算。 _算法
【网络安全】网络安全的标准和规范_网络安全标准规范-程序员宅基地
文章浏览阅读1.5k次，点赞18次，收藏26次。网络安全的标准和规范是网络安全领域的重要组成部分。它们为网络安全提供了技术依据，规定了网络安全的技术要求和操作方式，帮助我们构建安全的网络环境。下面，我们将详细介绍一些主要的网络安全标准和规范，以及它们在实际操作中的应用。_网络安全标准规范