一、什么是哈希表
在讨论哈希表之前，我们先大概了解下其他数据结构在新增，查找等基础操作执行性能
数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)
线性链表：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)
二叉树：对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。
哈希表：相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下（后面会探讨下哈希冲突的情况），仅需一次定位即可完成，时间复杂度为O(1)，接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的。
我们知道，数据结构的物理存储结构只有两种：顺序存储结构和链式存储结构（像栈，队列，树，图等是从逻辑结构去抽象的，映射到内存中，也这两种物理组织形式），而在上面我们提到过，在数组中根据下标查找某个元素，一次定位就可以达到，哈希表利用了这种特性，哈希表的主干就是数组。
比如我们要新增或查找某个元素，我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。
这个函数可以简单描述为：存储位置 = f(关键字) ，这个函数f一般称为哈希函数，这个函数的设计好坏会直接影响到哈希表的优劣。举个例子，比如我们要在哈希表中执行插入操作：
插入过程如下图所示：
二、哈希冲突
如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办？
也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。
前面我们提到过，哈希函数的设计至关重要，好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。
那么哈希冲突如何解决呢？
哈希冲突的解决方案有多种:
- 开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法，而HashMap即是采用了链地址法，也就是数组+链表的方式。
三、HashMap定义的基本属性
// 初始化容量为16且使用位运算来获取
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大值为2d的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
// 负载因子为0.75 也就说说当默认容量存储到12的时候就会扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当链表的长度大于8的时候就会转换为红黑树
static final int TREEIFY_THRESHOLD = 8;
// 当树中的容量小于6了则会把树转换为链表
static final int UNTREEIFY_THRESHOLD = 6;
// 只有当hash表中的容量大于64的时候才允许把链表转换为树
// 如果容量小于64但是某一个链表超过了8那么会通过resize进行数组扩容来解决
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储数据的数组
transient Node<K,V>[] table;
/**实际存储的key-value键值对的个数*/
transient int size;
/**
扩容的阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold，后面会详细谈到
*/
int threshold;
/**
负载因子，代表了table的填充度有多少，默认是0.75,负载因子存在的原因，是为了减缓哈希冲突，如果初始桶为16，等到满16个元素才扩容，某些桶里可能就有不止一个元素了。
所以加载因子默认为0.75，也就是说大小为16的HashMap，到了第13个元素，就会扩容成32。
他是一个典型的以空间换时间的思想
*/
final float loadFactor;
/**
HashMap被改变的次数，由于HashMap非线程安全,所以该变量主要是用来实现fail fast机制的,后面会详细谈到
*/
transient int modCount;
大家看到初始化容量的值并没有写死成16而是通过一个位运算来表示的,同时在HashMap种还大量运用到了位运算,这样的代码没有个七八年的功力是写不出来这样的优秀的代码的。
需要特别注意的是DEFAULT_INITIAL_CAPACITY和TREEIFY_THRESHOLD,我们经常会听到很多人说创建一个HashMap的时候初始化容量默认是16,HashMap存储数据的时候如果链表的长度达到了8那么就会转换位树这个说法真的正确嘛？
四、HashMap的构造方法
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
默认的构造方法只是做了默认负载因子的设置并没有对table数组进行初始化,也就是说当我们new HashMap的时候实际上他的初始化容量是0的他并没有使用默认的容量进行初始化。
既然他没有初始化那么大家一定好奇他是在什么时候进行的初始化的呢？其实他是在put方法种进行了检测并完成了初始化的工作,代码如下:
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;// 此处通过resize方法进行扩容的时候进行的初始化操作
......
除了以上使用最多的无参的构造方法以外还有一个构造方法也需要特别关注:
//指定初始化容量-在开发的过程种如果能估算容量一定要使用该方法进行创建-主要是为了避免频繁扩容
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
小结：
本篇文章主要给大家介绍了：
- 什么是哈希表
- 哈希冲突
- HashMap定义的基本属性
- HashMap的构造方法
下篇文章将继续深入：
- HashMap对象hash冲突的优化
- put方法如何存储数据
- 高效的寻址算法
- hash冲突了如何解决
- resize以后链表的rehash过程
