散列表与dict字典

散列表

1. 什么是散列表
   通过key-value的形式进行快速查找，类似函数形式 ：f (key) = value，本质上是通过对关键字key进行指定规则的计算。
2. 特点
   快速查找
   不可一对多（类比函数定义）
   可多对一，会出现散列冲突
   总结：适合关键字唯一的情况（身份证、手机号等），不适合关键字相同（多对一查找、范围查找）的情况。
3. 计算规则
   平方取中法
   除留余数法...（映射函数好坏决定了散列冲突的情况）

4. 散列冲突
   (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值。