哈希表

散列数据结构的性能取决于以下三个因素：

1. 哈希函数
2. 哈希表的大小
3. 碰撞处理方法 Q：为什么哈希表同时包含线性数据结构和非线性数据结构？

哈希表底层是数组，而为了解决哈希冲突，我们可能会使用“链式地址”（后续“哈希冲突”章节会讲）：数组中每个桶指向一个链表，当链表长度超过一定阈值时，又可能被转化为树（通常为红黑树）。

从存储的角度来看，哈希表的底层是数组，其中每一个桶槽位可能包含一个值，也可能包含一个链表或一棵树。因此，哈希表可能同时包含线性数据结构（数组、链表）和非线性数据结构（树）。

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash)表，函数f(key)为哈希(Hash) 函数

哈希函数构造方法:

1. 直接定址法
2. 数字分析法
3. 平方取中法
4. 除留余数法

冲突解决

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。

1. 开放定址法:
   1. 线性探测法
   2. 平方探测法
   3. 随机探测法
2. 再哈希法: 同时构造多个哈希函数, 如果一个有了,再用另一个. 不易产生聚集,但是会增加计算时间
3. 建立公共溢出区: 分为基本表和溢出表. 凡是和基本表发生冲突的元素,都填入溢出表
4. 拉链法(链地址法)