哈希表（hash table）也叫散列表，是一种非常重要的数据结构。许多缓存技术（比如memcached）的核心其实就是在内存中维护一张大的哈希表，本文会对Java集合框架中的对应实现HashMap的实现原理进行讲解，然后会对JDK8的HashMap源码进行分析。

先了解下基本数据结构。

我们知道，数据结构的物理存储结构只有两种：顺序存储结构和链式存储结构（像栈，队列，树，图等是从逻辑结构去抽象的，映射到内存中，也这两种物理组织形式），而在上面我们提到过，在数组中根据下标查找某个元素，一次定位就可以达到，哈希表利用了这种特性，哈希表的主干就是数组。存储位置 = f(关键字)，f函数就是哈希函数，关键字就是key，这个函数的设计好坏会直接影响到哈希表的优劣。

 　　5.哈希冲突 : 然而万事无完美，如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办？也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法，而HashMap即是采用了链地址法，也就是数组+链表的方式。

　　HashMap的主干是一个Node数组。Node是HashMap的基本组成单元，每一个Node包含一个key-value键值对。

　　 Node是HashMap中的一个静态内部类。代码如下：

　　几个重要属性：

　　HashMap构造函数：有4个构造器，其他构造器如果用户没有传入initialCapacity 和loadFactor这两个参数，会使用默认值initialCapacity默认为16，loadFactory默认为0.75

在常规构造器HashMap()中，没有为数组table分配内存空间，而是在执行put操作的时候才真正构建table数组。以下是put方法：

　　下面主要关注是三个函数：