HashMap又称之为散列表，这是一种使查找，插入和删除都具备良好性能的数据结构，其查找的时间复杂度为O()。散列表的核心技术就是散列，其核心原理就是依赖一个标识符来确定数据的位置，散列又分为静态散列和动态散列，下边来分析一下这两种散列方式：

1.静态散列

1.1散列表

        在静态散列表中，会将所有的标识符存在一张表中，这张表就叫做散列表。通过一个函数可以确定在散列表中位置，这个函数就叫做散列函数。散列表往往存放在一个连续的空间中，这个空间会被切割成n个空间，被称之为散列桶。每个散列桶可能又被切割成n个空间，被称之为槽，往往一个散列桶只包含一个槽。

散列表的基本结构

         为了统计衡量散列表的效率，分别用，和来表示一个散列表的标识符密度和装载密度。其中表示标识符可能不同的组合次数,,例如a和b两个字符，合组成如下a,b,aa,bb,ab,ba的6中组合。则标识符密度就为,即为。若散列表一共有个散列桶，每个散列桶有个槽，那么装载密度或者装载因子,按上图算即为。当两个不同的标识符和，通过散列函数得到,那么则称和为同义词，只要散列桶中有空闲的槽，就可以将互不相同的同义词放到同一个散列桶中，这种现象被称之为散列冲突。但是如果将一个同义词放入到一个已满的散列桶中，那么就会发生溢出。

1.2散列函数

        散列函数的作用就是将表示符转换成散列表中的地址。一个优秀的散列函数应该是不侧重某一个散列桶，而是均匀分布的。

1.3散列冲突和溢出处理

 1.3.1线性探测法 

        散列表被存储为一个线性数组，其下标从0到散列表的期望大小-1。当插入一个时，如果通过计算的位置没有值，那么则将存储在这个位置上，如果这个位置的散列桶已满，那么就将其存储在离最近的并且未满的散列桶中，这种解决散列冲突的方法就被称之为线性探测法。

线性探测法

        从上图可以看出ab和af是同义词当插入af的时候，首先会去找散列表下标为1的位置，发现这个位置有值了，并且不是af，那么继续往下找，一直找到下表为3的地方发现了一个未满的散列桶，将af存储在这个位置。

1.3.2拉链法

        通过上边的分析，我们可以看出线性探测法的效率是很低，容易形成标识符堆积。还有一种常用的方法就是拉链法。如上图ac和af是同义词，那么我们可以用一个单向的链表来存储同义词。

拉链法

        这种结构可以说比线性探测法要好上很多，插入的时候只需要计算散列值，将同义词放在一张同义词链表中，查找的时候只需要查找这张同义词链表即可。

2.动态散列

        静态散列有一个非常致命的缺点，那就是我们无法确定静态散列表的期望大小，如果过小，非常容易产生溢出，如果过大，因为静态散列表要提前非配好内存，这样就会造成内存浪费。而动态散列就是能够动态的对散列表进行扩展的一中技术。 

        对于动态散列表来说，散列桶被称之为页面。假如说一个页面容量为2，有以下几个标识符和散列值

以二进制对标识符进行散列

        要求根据散列值的低两位来确定标识符所处页面的位置，0选择上边的分支，1选择下边的分支，则有如下的存储

0在上边一个分支，1在下边一个分支

                加入说这个时候插入一个，并且,那么可以看到这个时候就会产生溢出了，如果溢出了动态散列表会怎么处理呢？

溢出之后新增一个页面

        因为一个页面的容量为2，a,b,c三者的低两位都为10，这个时候就会产生溢出，那么就新增一个页面，按照低三位来进行索引，这样就实现了动态扩容，所以动态散列的散列函数就是将标识符转换成二进制表示，来对标识符的在散列表中的位置进行索引。

3.散列表的实现及分析-----Java中的HashMap

        HashMap是Java中一个非常重要的集合，其基本原理也是基于散列表进行扩展而实现的，下边来仔细分析一下其核心代码。

数据节点的定义，相当于上文“标识符”

        可以看出数据节点中包含了一个节点的hash值，key，value已经一个next节点，通过这个基本可以看出它是采用拉链法来解决散列冲突的。

散列表定义

        这段代码定义了HashMap的散列表，可以看出它是一个线性数组。使用的是静态散列表的方式。其散列函数很简单，即节点元素的hashCode无符号右移16位即可，就不重点介绍了下边重点来分析它的插入和查找方法。

HashMap插入的核心逻辑

         通过代码我们可以看到Java中的HashMap是这样插入一条新数据的，首先通过散列函数来计算出节点所处于的散列桶位置，如果为空，那么直接将该节点放入到这个位置，如果这个位置不为空，但是插入的节点和老节点的key相同，那么会将新的value值赋予到这个节点上，如果不满足这一条件，即产生了散列冲突，那么这个时候就采用拉链法进行处理，当然Java中的HashMap在这里有一个细节，即当散列桶的链表长度超过8时，将其转换成红黑树，红黑树的好处下一章节来进行分析。

HashMap查找的核心逻辑

        这个逻辑就很简单了，首先判断第一个元素是不是要找的元素，如果是直接返回，如果不是，就遍历这个链表，找到了就返回这个元素，没找到就返回null值。