1. 哈希表 Hash Table

哈希表也叫散列表，是根据关键码值对（key-value）而直接进行访问的数据结构。它通过把关键码值对映射到内存中的一个位置来存储数据，以加快查询的速度。这个映射函数也叫做散列函数（hash function），存放数组的表叫做哈希表也叫做散列表。

常用的映射方法有除留余数法，即取key被某个不大于散列表长m的数p除后的余数作为散列地址。当使用哈希表进行查询的时候，就是在此使用哈希函数将key转换为对应的散列地址，并定位到该内存空间获取value。

对于不同的要存储的数据，经过哈希函数之后，映射到相同的散列地址，即为哈希碰撞（hash collision）。常用的解决方法有开放寻址法，再散列法，拉链法。拉链法即在冲突处再开一个新的链表依次存储数据。

哈希表的查询、插入和删除操作平均而言都是$O(1)$的时间复杂度，最坏情况下，如果产生过多的碰撞，会导致哈希表的查询、插入和删除的效率退化到$O(n)$。但只要精心设计和选择哈希函数，便可避免冲突。

2. 映射（Map） 和 集合（Set）

映射是指键值对组合，而集合只有值，且不包含重复的元素。

在Python中哈希表和映射都以字典dict的形式来体现，并且key不能够重复，但是value可以重复。同时，Python的set是一个不含有重复元素的集合，不存在key值，同时没有索引值index。集合中的单个元素不可更改，但集合本身可以被更改。