简介
哈希表（Hash table，也叫散列表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
结构
数组+链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
使用哈希函数通常考虑的因素有：
· 计算哈希函数所需时间
· 关键字的长度
· 哈希表的大小
· 关键字的分布情况
· 记录的查找频率
直接寻址法、数字分析法、数字分析法、平方取中法、折叠法、随机数法、除留余数法
冲突与处理
在哈希表中，不同的关键字值对应到同一个存储位置的现象。即关键字K1≠K2，但H（K1）= H（K2）。均匀的哈希函数可以减少冲突，但不能避免冲突。
⑴链接法（拉链法
将具有同一散列地址的记录存储在一条线性链表中
拉链法的优点
与开放定址法相比，拉链法有如下几个优点：
①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
③开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
④在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。
拉链法的缺点
指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。
⑵开放定址法
开放地址法有个非常关键的特征，就是所有输入的元素全部存放在哈希表里，也就是说，位桶的实现是不需要任何的链表来实现的，换句话说，也就是这个哈希表的装载因子不会超过1。它的实现是在插入一个元素的时候，先通过哈希函数进行判断，若是发生哈希冲突，就以当前地址为基准，根据再寻址的方法（探查序列），去寻找下一个地址，若发生冲突再去寻找，直至找到一个为空的地址为止。所以这种方法又称为再散列法。
常用的探查序列的方法如下：
Hi=(H(key) + di) MOD m,i=1,2，…，k(k<=m-1），其中H(key）为散列函数，m为散列表长，di为增量序列：
① di=1,2,3，…，m-1，称线性探测再散列；
冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表
②di=1^2,-1^2,2^2,-2^2，⑶^2，…，±（k)^2,(k<=m/2）称二次探测再散列；
冲突发生时，在表的左右进行跳跃式探测，比较灵活
③ di=伪随机数序列，称伪随机探测再散列。
(3)再散列法
就是再使用哈希函数去散列一个输入的时候，输出是同一个位置就再次散列，直至不发生冲突位置
Hi=(H(key) + di) MOD m缺点：每次冲突都要重新散列，计算时间增加。
性能 –负载因子
这里要提到两个参数：初始容量，加载因子，这两个参数是影响hash表性能的重要参数。
容量： 表示hash表中数组的长度，初始容量是创建hash表时的容量。(java默认是16)
加载因子： 是hash表在其容量自动增加之前可以达到多满的一种尺度（存储元素的个数），它衡量的是一个散列表的空间的使用程度。
负载因子 = 加载因子 / 容量
一般情况下，当loadFactor <= 1时，hash表查找的期望复杂度为O(1).
对使用链表法的散列表来说，负载因子越大，对空间的利用更充分，然后后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为0.75。
扩容
当hash表中元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对数组进行扩容。而在数组扩容之后，最消耗性能的点就出现了，原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是扩容。
什么时候进行扩容呢？当表中元素个数(加载因子) > 容量 * 加载因子 时，就会进行数组扩容。
备注
- 冒泡排序，就是典型的O(n^2)的算法
- 二分查找就是O(logn)的算法
- 归并排序就是O(nlogn)的时间复杂度
- 哈希算法就是典型的O(1)时间复杂度