一、HashMap 概述

　　java.util.HashMap<k,v> 集合 implements Map<k,v> 接口

　　HashMap 集合的特点：

　　　　1、HashMap 集合底层是哈希表：查询速度特别的快

　　　　　　JDK 1.8 之前：数组+单向链表

　　　　　　JDK 1.8 之后：数组+单向链表 | 红黑树（链表的长度超过8）：提高查询的速度

　　　　2、HashMap 集合是一个无序的集合，存储元素和取出元素的顺序有可能不一致

二、HashMap 存储自定义类型键值

　　HashMap存储自定义类型键值

　　Map集合保证key是唯一的：作为key的元素,必须重写hashCode方法和equals方法,以保证key唯一

三、遍历集合

　　　　参考 Map 集合的遍历方式：Map 遍历

四、Hashmap 源码分析

　　1、hashCode 值

　　　　hash算法是一种可以从任何数据中提取出其“指纹”的数据摘要算法，它将任意大小的数据映射到一个固定大小的序列上，这个序列被称为hash code、数据摘要或者指纹。比较出名的hash算法有MD5、SHA。hash是具有唯一性且不可逆的，唯一性是指相同的“对象”产生的hash code永远是一样的。

　　2、Entry 数组

　　　　HashMap和Hashtable是散列表，其中维护了一个长度为2的幂次方的Entry类型的数组table，数组的每一个元素被称为一个桶(bucket)，你添加的映射关系(key,value)最终都被封装为一个Map.Entry类型的对象，放到了某个table[index]桶中。

　　　　使用数组的目的是查询和添加的效率高，可以根据索引直接定位到某个table[index]。

　　　　（1）数组元素类型： Map.Entry

　　　　（2）初始容量：16

　　　　（3）扩容为原来的2倍

　　　　（4）那么 HashMap 是如何决定某个映射关系存在哪个桶的呢？

　　　　　　因为hash code是一个整数，而数组的长度也是一个整数，有两种思路：

　　　　　　①hash code值 % table.length会得到一个[0,table.length-1]范围的值，正好是下标范围，但是用%运算，不能保证均匀存放，可能会导致某些table[index]桶中的元素太多，而另一些太少，因此不合适。

　　　　　　②hash code值 & (table.length-1)，因为table.length是2的幂次方，因此table.length-1是一个二进制低位全是1的数，所以&操作完，也会得到一个[0,table.length-1]范围的值。

　　3、HashMap 中的散列函数 hash()

　　　　JDK1.7和JDK1.8关于hash()的实现代码不一样，但是不管怎么样都是为了提高hash code值与 (table.length-1)的按位与完的结果，尽量的均匀分布。

　　　这里用 JDK1.8 的实例分析一下：

　　　　思考：那么，JDK1.8为什么要保留高16位呢？

　　　　因为一个HashMap的table数组一般不会特别大，至少在不断扩容之前，那么table.length-1的大部分高位都是0，直接用hashCode和table.length-1进行&运算的话，就会导致总是只有最低的几位是有效的，那么就算你的hashCode()实现的再好也难以避免发生碰撞，这时保留高16位的意义就体现出来了。它对hashcode的低位添加了随机性并且混合了高位的部分特征，显著减少了碰撞冲突的发生。

　　4、如何解决冲突？

　　　　虽然从设计hashCode()到上面HashMap的hash()函数，都尽量减少冲突，但是仍然存在两个不同的对象返回的hashCode值相同，或者hashCode值就算不同，通过hash()函数计算后，得到的index也会存在大量的相同，因此key分布完全均匀的情况是不存在的。那么发生碰撞冲突时怎么办？

　　　　JDK1.8之间使用：数组+链表的结构。

　　　　JDK1.8之后使用：数组+链表/红黑树的结构。