HashMap源码解析一
原文地址图解HashMap
概述
HashMap是日常开发中经常会用到的一种数据结构，在介绍HashMap的时候会涉及到很多术语，比如时间复杂度O、散列(也叫哈希)、散列算法等，这些在大学课程里都有教过，但是由于某种不可抗力又还给老师了，在深入学习HashMap之前先了解HashMap设计的思路以及以及一些重要概念，在后续分析源码的时候就能够有比较清晰的认识。
HashMap是什么
在回答这个问题之前先看个例子：小明打算从A市搬家到B市，拿了两个箱子把自己的物品打包就出发了。
image
到了B市之后，他想拿手机给家里报个平安，这时候问题来了，东西多了他忘记手机放在哪个箱子了？小明开始打开1号箱子找手机，没找到；再打开2号箱子找，找到手机。当只有2个箱子的时候，东西又不多的情况下，他可能花个2分钟就找到手机了，假如有20个箱子，每个箱子的东西又多又杂，那么花的时间就多了。小明总结了下查找耗时的原因，发现是因为这些东西放的没有规律，如果他把每个箱子分个类别，比如定一个箱子专门放手机、电脑等电子设备，有专门放衣服的箱子等等，那么他找东西花的时间就可以大大缩短了。
其实HashMap也是用到这种思路，HashMap作为一种数据结构，像数组和链表一样用于常规的增删改查，在存数据的时候(put)并不是随便乱放，而是会先做一次类似“分类”的操作再存储，一旦“分类”存储之后，下次取(get)的时候就可以大大缩短查找的时间。我们知道数组在执行查、改的效率很高，而增、删(不是尾部)的效率低，链表相反，HashMap则是把这两者结合起来，看下HashMap的数据结构
image
从上面的结构可以看出，通常情况下HashMap是以数组和链表的组合构成(Java8中将链表长度超过8的链表转化成红黑树)。结合上面找手机的例子，我们简单分析下HashMap存取操作的心路历程。put存一个键值对的时候(比如存上图盖伦)，先根据键值”分类”，”分类”一顿操作后告诉我们，盖伦应该属于14号坑，直接定位到14号坑。接下来有几种情况：
- 14号坑没人，nice，直接存值；
- 14号有人，也叫盖伦，替换原来的攻击值；
- 14号有人，叫老王！插队到老王前面去(单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置)
get取的时候也需要传键值，根据传的键值来确定要找的是哪个”类别”，比如找火男，”分类”一顿操作够告诉我们火男属于2号坑，于是我们直接定位到2号坑开始找，亚索不是…找到火男。
小结
HashMap是由数组和链表组合构成的数据结构，Java8中链表长度超过8时会把长度超过8的链表转化成红黑树；存取时都会根据键值计算出”类别”(hashCode)，再根据”类别”定位到数组中的位置并执行操作。
