哈希表(数据结构及算法06)

特点：

数组(顺序表)：寻址容易
链表：插入与删除容易
哈希表：寻址容易，插入删除也容易的数据结构

Hash table:

哈希表（Hash table，也叫散列表）：
是根据关键码值(Key value)而直接进行访问的数据结构，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。关键码值(Key value)也可以当成是key的hash值。这个映射函数叫做散列函数。存放记录的数组叫做散列表，如下图：

image.png

Hash table例子:

Key : {14, 19, 5, 7, 21, 1, 13, 0, 18}
散列表: 大小为13 的数组 a[13];
散列函数: f(x) = x mod 13;

hashtable需要自定义的内容:
1、散列函数与散列表大小？
2、hash 冲突的解决方案？
装填因子：为什么需要这个值？因为数据越接近数组最大值，可能产生冲突的情况就越多

缺点：扩容需要消费大量的空间和性能
由于装填因子的原因，Hash table不可能全部装满元素的，总有一部分是空着的，这样消费大量的空间。其次每一次扩容都会重新计算全部的Key值对应的Hash值，性能上的消耗也比较大。

Hash table设计：拉链法-解决哈希冲突

JDK1.8以前：小数据还可以，面对大数据这种存储结构存在很大压力

image.png

JDK1.8以后：不怕大数据当哈希值是一样的情况下，数据到了一定的阈值之后则会采用红黑树结构进行存储

image.png