当我们创建HashMap时，底层到底做了什么？

jdk1.7中的底层实现过程（底层基于数组+链表）

在我们new HashMap()时，底层创建了默认长度为16的一维数组Entry[ ] table。当我们调用map.put(key1,value1)方法向HashMap里添加数据的时候：

首先，调用key1所在类的hashCode()计算key1的哈希值，通过key1的hash值与数组的最大索引进行位运算以后，得到了在 Entry数组中的存放位置：

如果此位置上的数据为空，此时的key1-value1添加成功。

如果此位置上的数据不为空（意味着此位置已经存在一个或多个数据），比较key1和已经存在的一个或多个数据的哈希值：

如果key1的哈希值与已经存在的数据的哈希值都不相同，此时key1-value1添加成功。

如果key1的哈希值与已经存在的数据的某一个数据的哈希值相同，继续比较：调用key1所在类的equals()方法：

如果equals()返回false，此时key1-value1添加成功；

如果equals()返回true，使用value1替换value2。

需要注意的是，若原来位置已有数据，则此时key1-value1和原来的数据以链表的方式存储。

在不断的添加过程中，会涉及到扩容问题，当数组容量大于数组现有长度乘以加载因子（如16*0.75，默认的加载因子为0.75）的时候，就会进行数组扩容，以减少哈希冲突（哈希冲突是指哈希函数算出来的地址被别的元素占用了），提高查询效率。默认的扩容方式，扩容为原来容量的2倍，并将原有的数据复制过来。

jdk1.8的底层实现过程（底层基于数组+链表+红黑树）

jdk1.8与jdk1.7中底层的创建过程相似，但有不同，首先，new HashMap()底层没有创建出一个长度为16的数组，在调用put()方法时，判断数组是否存在，如果不存在创建长度为16的Node[ ]数组。接下来的过程与jdk1.7相似。最后，当某一个索引位置上的元素以链表形式存在的数据个数>8且当前数组的长度>64时，此时此索引位置上的所有数据改为使用红黑树存储。

在jdk1.7中，即使在“数组容量大于数组现有长度乘以加载因子”时扩容，也不可避免地会有哈希冲突存在，因此，在jdk1.8中引入红黑树是为了进一步减少哈希冲突，提高查询效率。

红黑树是一种自平衡的二叉查找树，是一种数据结构，典型的用途是实现关联数组。根节点必须是黑色，其他每个节点要么是红色，要么是黑色。

结论：HashMap键是不能重复的，去除重复的条件是依赖键的hashCode方法和equals方法，如果键是自己的对象类型，必须要重写hashCode方法和equals方法，否则，不能去除重复的键。

原文：https://www.cnblogs.com/fairboyllil/p/13197735.html