直接寻址法
U表示所有可能出现的key范围，K表示实际的key。如图建一个列表，下标包含所有可能的key
缺点：
- 当U范围很大时，实际的K范围很小，费内存
- 只能处理key是 数字的情况
哈希表概念
哈希表又称散列表，是一种线性表存储结构。在直接寻址表上做了修改，由一个直接寻址表和一个哈希函数组成，哈希函数h(key)返回元素的存储下标。
哈希表通常支持如下操作：
- insert(key,value)：插入键值对
- get(key)：得到键为key的value值
- delete(key)：删除键为key的键值对
哈希冲突
由于哈希表(直接寻址表)大小是有限，存储的值总数量是无限的，对于任何哈希函数，都可能出现两个不同的元素映射到同一个下标
解决哈希冲突
- 开放寻址法：如果哈希函数返回的位置已经有值，可以向后探查新的位置来存储该值
- 线性探查：如果位置i被占用，探查i+1、i+2、...
- 二次探查：如果位置i被占用，探查i+12、i+22、...
- 二度哈希：有n个哈希函数，当第一个哈希函数h1发生冲突时，尝试使用h2、h3、...
- 拉链法：哈希表每个位置都连接一个链表，冲突的元素将被加到对应位置链表的最后
哈希表在python的应用
python中字典和集合都是通过哈希表实现
比如字典：{"name":"tom","age":12,"hobby":"swimming"}，假设h("name")=2，h("age"=1)，h("hobby")=0，哈希表的存储为["swimming",12,"tom"]
