散列表
- 什么是散列表
通过key-value的形式进行快速查找，类似函数形式 ：f (key) = value，本质上是通过对关键字key进行指定规则的计算。 - 特点
快速查找
不可一对多（类比函数定义）
可多对一，会出现散列冲突
总结：适合关键字唯一的情况（身份证、手机号等），不适合关键字相同（多对一查找、范围查找）的情况。 - 计算规则
平方取中法
除留余数法...（映射函数好坏决定了散列冲突的情况） -
散列冲突
(1) 链地址法
若某位置key a、b对应的value值重复，则在该位置存储一个指向a的地址，作为链表头指针指向a的位置。该位置value值重复的依次存储在该链表中。
下图中存放的是key值，经过指定规则计算得到1~12之间的数字（对应的value值可以存放在某块连续的区域），数字可作索引取得相应value值。
当然，加入链表会影响key数组的查找速度。
链地址法
(2) 公共溢出区法
开辟一块区域，专门用于存放冲突的value值。
(3)开放定址法
python dict 字典
dict与list区别在于是时间换空间还是空间换时间，前者占内存，查找快，后者相反。
dict与set，与dict相比，set只是一组无序、无重复的集合且没存储value值。
