hash 表
哈希表也叫散列表，我们在中使用的对象就是一种hash结构。哈希表根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
hash表的结构
hash表的结构本质上是结合了数组和链表两种结构。
数组：寻址容易，插入和删除困难，需要预先给定数组的大小
链表：寻址困难，插入和删除容易，不需要预先给定空间
hash 表的可以看做是一个存储链表的数组。
hash 函数
我们对哈希表进行put操作的时候，底层会对 key 用hash函数映射到数组中。哈希函数需要具有以下几个特点：
- 运算过程要尽量简单高效，以提高哈希表的插入和检索效率；
- 哈希函数应该具有较好的散列型，以降低哈希冲突的概率；
- 哈希函数应具有较大的压缩性，以节省内存。
常用的方法有以下几种：
- 直接地址法：以关键字的某个线性函数值为哈希地址，可以表示为hash(K)=aK+C;优点是不会产生冲突，缺点是空间复杂度可能会较高，适用于元素较少的情况
- 除留余数法：它是由数据元素关键字除以某个常数所留的余数为哈希地址，该方法计算简单，适用范围广，是经常使用的一种哈希函数
- 数字分析法：该方法是取数据元素关键字中某些取值较均匀的数字来作为哈希地址的方法，这样可以尽量避免冲突，但是该方法只适合于所有关键字已知的情况，对于想要设计出更加通用的哈希表并不适用
- 平方求和法：对当前字串转化为Unicode值，并求出这个值的平方，去平方值中间的几位为当前数字的hash值，具体取几位要取决于当前哈希表的大小。
- 分段求和法：根据当前哈希表的位数把所要插入的数值分成若干段，把若干段进行相加，舍去调最高位结果就是这个值的哈希值。
hash 冲突
当两个不同key通过hash函数映射到了数组同一个地址中，此时就存在了hash冲突。
哈希冲突主要与两个因素有关：
- 填装因子，填装因子是指哈希表中已存入的数据元素个数与哈希地址空间的大小的比值，a=n/m ; a越小，冲突的可能性就越小，相反则冲突可能性较大；但是a越小空间利用率也就越小，a越大，空间利用率越高，为了兼顾哈希冲突和存储空间利用率，通常将a控制在0.6-0.9之间，
- 与所用的哈希函数有关，如果哈希函数得当，就可以使哈希地址尽可能的均匀分布在哈希地址空间上，从而减少冲突的产生，但一个良好的哈希函数的得来很大程度上取决于大量的实践，
解决 hash冲突
一般使用拉链法来解决这个问题。即不在数组中直接存储value而是存储一个链表，当存在hash冲突的时候只需要在冲突的位置的结尾加多一个节点。
扩容
一般我们会预先设定一个临界值，当达到临界值会对hash表进行扩容操作，不过扩容操作是非常损耗性能的