HashMap源码分析
一、概述
HashMap 在我们平常的开发中是经常会用到的，HashMap 的读取速度是非常快的，基本上可以达到 O(1)，但是因为他内部的实现，导致他的存储速度相对来说弱一些。那下面我们就去分析一下它内部的实现和它的特点。
Hash 算法：
在了解 HashMap 之前，我们首先要了解一下 Hash 算法，Hash 算法的意思就是你给出一个实体（包括一个 key 和一个 value）的 key ，然后通过 Hash 算法算出一个 hash 值，然后把这个值存入 Hash 表中，当我们需要查询某个 key 对应的 value 的时候，你可以先通过 Hash 算法算出 key 的 hash 值，然后通过这个 hash 值去 Hash 表中去查询，这样通过一次计算就可以直接找到对应的 value ，这样查询速度是非常快的。
一些常用的 Hash 算法：
1、除法散列法
例如：
hash = key % 16
那当我们把 16,33,2,3,52,21,54 存入 Hash 表的位置为下图：
2、平方散列法
例如：
hash = (key * key) >> 6 （右移，除以2^6）
这个 28 可以是任何数字，
如果数值分配比较均匀的话这种方法能得到不错的结果，但我上面画的那个图的各个元素的值算出来的index都是0——非常失败。也许你还有个问题，value如果很大，value * value不会溢出吗？答案是会的，但我们这个乘法不关心溢出，因为我们根本不是为了获取相乘结果，而是为了获取index。
计算结果我就不写了，只是照着公司计算就可以了。
3、斐波那契（Fibonacci）散列法
平方散列法的缺点是显而易见的，所以我们能不能找出一个理想的乘数，而不是拿value本身当作乘数，所以就有了如下的算法：
· 对于16位整数而言，这个乘数是40503。
· 对于32位整数而言，这个乘数是2654435769。
· 对于64位整数而言，这个乘数是11400714819323198485。
这几个“理想乘数”是如何得出来的呢？这跟一个法则有关，叫黄金分割法则，而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列，即如此形式的序列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,233, 377, 610， 987, 1597, 2584, 4181, 6765, 10946，…。
对我们常见的32位整数而言，计算公式是下面这样的：
hash = (key * 2654435769) >> 6
哈希冲突：
当我们在计算一个 hash 值的时候，难免有两个 key 对应同一个 hash 的值，当有两个 key 对象hash 值相同的时候，例如我们的 key 为 16 和 32，当我们使用除法散列法的时候，两个 key 对应的 hash 值都为 0。这种情况我们称之为 hash 冲突，当有 hash 冲突的时候，我们通常的解决办法有两种，一种是开放定址法，一种是链地址法
开放定址法：
当有冲突的时候我们再通过以下方法进行计算 hash 值
hash = (Hash(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中Hash(key)为散列函数，m为hash表长，di为增量序列，可有下列三种取法：
· di=1,2,3,…, m-1，称线性探测再散列；
· di=1^2, (-1)^2, 2^2,(-2)^2, (3)^2, …, ±(k)^2,(k<=m/2)称二次探测再散列;
· di=伪随机数序列，称伪随机探测再散列。
链地址法：
当有 hash 冲突的时候，我们在冲突的位置创建一个链表，例如下面的样式：
当我们32 和 16 冲突的时候，我们就去把 32 链接到 16 的后面，当我们查询的时候去判断 key 的值是不是相同的，如果相同的就找到了。
二、HashMap 常用方法分析
我们在使用 HashMap 的时候常用的方法就以下几个：
V get(Object key); // 获得指定键的值
V put(K key, V value); // 添加键值对
void putAll(Map<? extends K, ? extends V> m); // 将指定Map中的键值对 复制到 此Map中
V remove(Object key); // 删除该键值对
boolean containsKey(Object key); // 判断是否存在该键的键值对；是 则返回true
boolean containsValue(Object value); // 判断是否存在该值的键值对；是 则返回true
Set<K> keySet(); // 单独抽取key序列，将所有key生成一个Set
Collection<V> values(); // 单独value序列，将所有value生成一个Collection
void clear(); // 清除哈希表中的所有键值对
int size(); // 返回哈希表中所有 键值对的数量 = 数组中的键值对 + 链表中的键值对
boolean isEmpty(); // 判断HashMap是否为空；size == 0时 表示为 空
我们首先看一下 HashMap 中的变量：
下面在看一幅从晚上找到的一个图片，有助于对加载因子的了解：
HashMap 方法讲解：
下面进入正题，下面内容主要讲解 HashMap 的以下几个方法：
1、HashMap 的构造方法
2、V get(Object key) 方法
3、put(K key, V value) 方法
HashMap 构造方法：
上面的注解已经说的很清楚了，就不做过多的解释了，下面说一下 get 方法是什么样一个流程
get 方法详解：
最后分析一下我们比较复杂的 put 方法：
我们首先看一下代码中的 put 方法：
上面的代码大致说了一下 put 方法做的工作，那么还需要明确一下几点：
1、inflateTable 做了什么
2、 putForNullKey 是怎么操作的
3、indexFor 如何计算 hash 值的
4、addEntry 做了什么操作
inflateTable 源码分析：
putForNullKey 源码分析：
HashMap的键key 可为null（区别于 HashTable的key 不可为null）
HashMap的键key 可为null且只能为1个，但值value可为null且为多个
indexFor 源码分析：
从上面的代码可以看出，hashMap 的 hash 值是通过 key 的 hash码与 table 表长度的 - 1 相与。
这也是为什么我们的 hash 表的长度为什么为 2 的幂次方的原因
我们考虑一下，如果我们的 hash表的长度为 2 的幂次方，那么它的长度的二进制-1 就一定是 1，11,111,1111,11111,111111 等等，那么这样在做与运算的时候每一位都会被用到，如果有 2 进制有一位为 0 ，那么就很容易出现重复的结果，这样也可以使我们的 hash 值最大化，下面看一张图：
addEntry 源码分析：
其实通过上面的分析，很好理解上面代码的用意了。
总结：
上面只是分析了 HashMap 在 Android SDK 中的源码，其实 HashMap 在 JDK 1.7 和 1.8 的版本中是有很大变化的，在之后的版本 HashMap 的性能会有很多的提升，其实主要的改造就是计算 Hash 值的改造。那这篇 HashMap 的介绍就到此结束了