前两篇文章粗略的介绍了java中的List，既然已经讲了两种java的数据结构，那么这篇就接着讲java中的数据结构了。
HashMap作为最常用的一种Map，就放在第一个讲了。
Map是一个较复杂的结构，本身内容不是太难，但是各个实现的思想完全不同，所以可能关于Map的介绍会比较多，源码分析会放在后边，主要是算法分析。
要讲HashMap，首先要对HashMap有个大体上的的认识，那就是HashMap是什么，为什么用HashMap，HashMap有什么优势等等，等对HashMap有个清晰的认识后再去看源码就很简单了。
HashMap是什么？
HashMap是基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。 此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。
将上述描述逐一分条，就是下面的内容：
1、HashMap允许null值和null键；
2、此类不保证映射的顺序，也就是HashMap是无序的，但是这个无序可能与很多人的认知是不同的，并不是很多初学者所理解的无序（实际上HashMap在某些时候其实是有序的），后边会详细的讲解；
3、 此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。注意，这句话有一点儿很重要，也是一个使用中可能存在的隐患，那就是“此实现假定哈希函数将元素适当地分布在各桶之间”，是假定，而不是肯定，说明还有可能不是适当的分布，而实际上不是适当分布的这种情况是存在的，而且有人会通过构造特殊hash值去做hash碰撞攻击（不过一般不用考虑），具体后续会讲。
4、迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。这句话给我们一个提示，如果需要较好的迭代性能，就不要将初始容量设置得太高，至于为什么，后续会给出详细分析。
第一条就不用讲了，首先是第二条，为什么HashMap是无序的？为什么此类不能保证映射的顺序？
这个问题要从HashMap的存储结构来讲，HashMap并不会直接使用用户设置的key作为key，而是会使用用户设置的key的hash值作为实际key，这句可能有些拗口，下面我们以put方法为切入点，从源码分析。
public V put(K key, V value)
put方法的源码如下：
可以看到put方法调用了hash方法，然后调用了putVal方法，首先看hash方法的源码：
可以看到，hash方法很简单，判断了一下key是否等于null，如果等于null就返回0，否则就返回后边一串，后边的是一个简单的hash算法，有兴趣的同学可以看些注释为什么采用该hash算法，这里不做过多介绍（该hash算法很重要，建议有一定能力的同学一定要看一下为什么选用该hash算法，尝试去验证一下，然后有兴趣的可以自己写一个hash算法比较一下是否比他这个更优——记住，系统的不一定是最优的，只是在大多数情况下是较好的）。
接下来就是putVal了，putVal的源码如下：
首先是判断当前的table是不是空或者null，如果是的话调用resize方法（该方法是一个很核心的方法，后边会单独介绍）初始化，然后用将初始化后tab的大小赋值给n，然后下一行就用上了，下面看这一行：
对于一些基础不好的同学，可能这一行看起来就不是那么的容易搞懂了，其核心是在:
i = (n - 1) & hash
这一段，为什么这么写呢？因为hash值有可能是比tab的size大的，而如果不处理的话就有可能数组越界了，所以需要将hash值处理为比size小的数，而该操作就能做到，至于为什么可以自行思考，不难（取模运算也能达到这样的效果，但是位操作比较快）。
然后就是判断，如果为null了后续的操作都很好理解，构建一个新的node然后插入table中，如果不为null操作就会稍微复杂些，会在下一节中讲解。
由于Map的实现都比较复杂，所以打算做成连载的方式给剖析一遍，而且这两天事儿确实多，所以每节的内容不多，见谅。如有任何问题请加我Q1213812243。
PS：前边忘了介绍我本地的JDK了，我本地用的JDK版本是1.8，如果用的跟我的不同可能源码会有些许差别，不过一般不会有太大变化，另外标题图与java中实际的HashMap结构是有出入的，仅仅是作为一个封面图而已........
本文分享自微信公众号 - java初学者（JoeKerouac_public）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
