[toc]
哈希表定义
Hash ，一般翻译做“ 散列” ，也有直接音译为“ 哈希” 的，就是把任意长度的输入（又叫做预映射， pre-image ），通过散列算法，变换成固定长度的输出，该输出就是散列值。
这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。 简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
HASH 主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128 位的编码, 这些编码值叫做 HASH 值. 也可以说， hash 就是找到一种数据内容和数据存放地址之间的映射关系 例如字符串 hello 的哈希算法
char value = "hello"; int key = (((((((27 (int)'h'+27) (int)'e') + 27) (int)'l') + 27) (int)'l' +27) 27 ) + (int)'o' ; 。
HashMap实现原理
特点
数组的特点：
寻址容易，插入和删除困难；
链表的特点：
寻址困难，插入和删除容易。
那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易 的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法—— 拉链法，我们可以理解为 “ 链表 的数组” ，如图：
实现原理
1、首先 HashMap里面实现一个静态内部类 Entry 其重要的属性有 key , value, next,从属性 key,value我们就能很明显的看出来 Entry就是 HashMap键值对实现的一个基础 bean,我们上面说到 HashMap的基础就是一个线性数组,这个数组就是 Entry[]，Map里面的内容都保存在 Entry[]里面。
2、既然是线性数组，为什么能随机存取？这里 HashMap用了一个小算法，大致是这样实现：
存储时:
int hash = key.hashCode();--> 这个hashCode方法这里不详述,只要理解每个key的hash是一个固定的int值
int index = hash % Entry[].length;
Entry[index] = value;
取值时: int hash = key.hashCode(); int index = hash % Entry[].length; return Entry[index]
3、疑问：如果两个key通过hash % Entry[].length得到的index相同，会不会有覆盖的危险？
这里 HashMap里面用到链式数据结构的一个概念.上面我们提到过 Entry 类里面有一个 next属性,作用是指向下一个 Entry。打个比方, 第一个键值对A进来,通过计算其 key的 hash得到的 index=0， 记做: Entry[0] = A.一会后又进来一个键值对B,通过计算其 index也等于0,现在怎么办？ HashMap会这样做 :B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。
当然HashMap里面也包含一些优化方面的实现，这里也啰嗦一下。 比如：Entry[]的长度一定后，随着map里面数据的越来越长，这样同一个index的链就会很长，会不会影响性能？HashMap里面设置一个因素（也称为因子），随着map的size越来越大，Entry[]会以一定的规则加长长度。
hash冲突解决办法
开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）
这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：
Hi=（H（key）+di）% m i=1，2，…，n
其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种：
线性探测再散列
dii=1，2，3，…，m-1
这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
二次探测再散列
di=12，-12，22，-22，…，k2，-k2 ( k<=m/2 )
这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。 伪随机探测再散列
di=伪随机数序列。
再哈希法
这种方法是同时构造多个不同的哈希函数：
Hi=RH1（key） i=1，2，…，k
当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
链地址法
这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
例如，已知一组关键字（32，40，36，53，16，46，71，27，42，24，49，64），哈希表长度为13，哈希函数为：H（key）= key % 13，则用链地址法处理冲突的结果如图所示：
建立一 公共溢出区
这种方法的基本思想是：将哈希表分为 基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表