刷题笔记 哈希表-1 哈希表理论基础
O(1)复杂度查找，牺牲了空间换取了时间
一、哈希表概念
1.定义（Hash table，散列表）
哈希表是根据关键码的值而直接进行访问的数据结构。
一般哈希表都是用来快速判断一个元素是否出现集合里。
数组就是一种哈希表，关键码就是数组的索引下标
2.哈希函数（hash function）
将查找映射为哈希表索引的函数，通过查询索引下标快速查找
3.哈希碰撞
多个查找映射到了同一个位置索引，这一现象叫做哈希碰撞。
4.哈希碰撞解决方法
一般哈希碰撞有两种解决方法， 拉链法和线性探测法。
（1）拉链法
将发生冲突的元素都被存储在链表中
（2）线性探测法
发生冲突后向下找一个空位放置信息
一定要保证tableSize大于dataSize
二、常见的哈希结构和应用
常见的哈希结构有三种：数组(list, python)、集合(set, python)、映射(dict/collection.defaultdict(*), python)
其中映射的key(query)常用元组tuple，出现相应报错就尝试把数据类型改为tuple
常见的应用也有三种：充当查找表、标记状态（特征提取）、统计次数等功能
但三种哈希结构和应用不存在对应关系