引言

基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。 此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。

HashMap介绍

HashMap的工作原理是近年来常见的Java面试题。几乎每个Java程序员都知道HashMap，都知道哪里要用HashMap，知道Hashtable和HashMap之间的区别，那么为何这道面试题如此特殊呢？是因为这道题考察的深度很深。这题经常出现在高级或中高级面试中。投资银行更喜欢问这个问题，甚至会要求你实现HashMap来考察你的编程能力。ConcurrentHashMap和其它同步集合的引入让这道题变得更加复杂。让我们开始探索的旅程吧！

HashMap的特点：

与HashMap对应的是HashTable，相比较而言，HashTable是线程安全的，HashMap是允许键值都是null的，但是相反的是HashTable中键值都是部允许为null的，

HashMap是无序的，并且随着世间的推移可能会出现某一个元素的位置可能会改变 （resize） 意思就是重新计算容量， 这里涉及到HashMap的扩容机制，既然HashMap的底层是一个数组那么可想而知在java中数组的扩容原理：重新建立一个容量更大的数组，把原来的数组copy到新的数组中即可，其实HashMap的扩容机制也是大相径庭，（ps:HashMap 的初始容量为16，一旦需要扩容的时候会扩大到原来的2倍）。

HashMap基本原理

1、首先判断Key是否为Null，如果为null，直接查找Enrty[0]，如果不是Null，先计算Key的HashCode，然后经过二次Hash。得到Hash值，这里的Hash特征值是一个int值。

2、根据Hash值，要找到对应的数组啊，所以对Entry[]的长度length求余，得到的就是Entry数组的index。

3、找到对应的数组，就是找到了所在的链表，然后按照链表的操作对Value进行插入、删除和查询操作。

设计理念

HashMap是基于hash表（hashtable）实现的，hash表又叫关联数组，所以HashMap的底层是一个数组，一种键值对数据结构，键是不可以重复的，这里说下HashMap键值对的报存过程，key在经过hash函数作用后会生成一个对应值槽的索引，但是在不同的key经过hash函数处理的时候可能会的到相同的索引，因此会产生重复的情况，因此：

. 设计一个好的hash函数可以尽可能的减少冲突的发生，

.其次是解决如果冲突发生后怎么解决这个冲突。

源码解析

构造函数

HashMap在设计之处的时候提供了四个构造函数：

//initialCapcity ：初始化容量；

//laodFactor ：平衡因子；

在代码中可以看见，HashMap对这两个值都是有默认值的设计：初始化容量为16，平衡因子为0.75；至于平衡因子为什么会选择0.75，JDK中说是平衡了时间和空间因素的最好取值。

这里解释下平衡因子这个东西：平衡因子表示Hash表中元素填满的程度，前面说到了每一个key在存入的时候都会经过hash函数生成一个对应的下表，如果说平衡因子越大，也就是hash表的填满程度越大，这样出现hash冲突的可能性就会越大，在做查找的时候就会花费大量的世间。但是相反的是如果平衡因子越小，这样空间的利用率就会降低，出现内存浪费的情况。所以说，楼主觉得JDK说是平衡了 时间和空间的因素的最好取值还是有道理的O^O。

HashMap 的实现

当 HashMap 的每个 bucket 里存储的 Entry 只是单个 Entry ——也就是没有通过指针产生 Entry 链时，此时的 HashMap 具有最好的性能：当程序通过 key 取出对应 value 时，系统只要先计算出该 key 的 hashCode() 返回值，在根据该 hashCode 返回值找出该 key 在 table 数组中的索引，然后取出该索引处的 Entry，最后返回该 key 对应的 value 即可。看 HashMap 类的 get(K key) 方法代码：

public V get(Object key) {

// 如果 key 是 null，调用 getForNullKey 取出对应的 value

if (key == null)

return getForNullKey();

// 根据该 key 的 hashCode 值计算它的 hash 码

int hash = hash(key.hashCode());

// 直接取出 table 数组中指定索引处的值，

for (Entry<K,V> e = table[indexFor(hash, table.length)];

e != null;

// 搜索该 Entry 链的下一个 Entr

e = e.next) // ①

{

Object k;

// 如果该 Entry 的 key 与被搜索 key 相同

if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

return e.value;

}

return null;

}

从上面代码中可以看出，如果 HashMap 的每个 bucket 里只有一个 Entry 时，HashMap 可以根据索引、快速地取出该 bucket 里的 Entry；在发生“Hash 冲突”的情况下，单个 bucket 里存储的不是一个 Entry，而是一个 Entry 链，系统只能必须按顺序遍历每个 Entry，直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中），那系统必须循环到最后才能找到该元素。

归纳起来简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据 Hash 算法来决定其存储位置；当需要取出一个 Entry 时，也会根据 Hash 算法找到其存储位置，直接取出该 Entry。由此可见：HashMap 之所以能快速存、取它所包含的 Entry，完全类似于现实生活中母亲从小教我们的：不同的东西要放在不同的位置，需要时才能快速找到它。

当创建 HashMap 时，有一个默认的负载因子（load factor），其默认值为 0.75，这是时间和空间成本上一种折衷：增大负载因子可以减少 Hash 表（就是那个 Entry 数组）所占用的内存空间，但会增加查询数据的时间开销，而查询是最频繁的的操作（HashMap 的 get() 与 put() 方法都要用到查询）；减小负载因子会提高数据查询的性能，但会增加 Hash 表所占用的内存空间。

掌握了上面知识之后，我们可以在创建 HashMap 时根据实际需要适当地调整 load factor 的值；如果程序比较关心空间开销、内存比较紧张，可以适当地增加负载因子；如果程序比较关心时间开销，内存比较宽裕则可以适当的减少负载因子。通常情况下，程序员无需改变负载因子的值。

如果开始就知道 HashMap 会保存多个 key-value 对，可以在创建时就使用较大的初始化容量，如果 HashMap 中 Entry 的数量一直不会超过极限容量（capacity * load factor），HashMap 就无需调用 resize() 方法重新分配 table 数组，从而保证较好的性能。当然，开始就将初始容量设置太高可能会浪费空间（系统需要创建一个长度为 capacity 的 Entry 数组），因此创建 HashMap 时初始化容量设置也需要小心对待。

总结

以 上就是我对Java开发大型互联网深入理解HashMap实现之源码分析            问题及其优化总结，分享给大家，觉得收获的话可以点个关注收藏转发一波喔，谢谢大佬们支持！

最后，每一位读到这里的网友，感谢你们能耐心地看完。希望在成为一名更优秀的Java程序员的道路上，我们可以一起学习、一起进步！都能赢取白富美，走向架构师的人生巅峰!

想了解学习Java方面的技术内容以及Java技术视频的内容可加群：722040762 验证码：简书（666 必过）欢迎大家的加入哟！