1.hash map

hash map本质上是一个数组，但每一个元素可以是链表，而下标是通过key进行hash计算之后得到的值。

当插入一个key-value对时，使用hash函数对key进行计算，得到一个hash值，用这个值来作为下标，然后存储key-value的键值对。如果当前hash值下标已经有值存在了(hash冲突)，就会将这个key-value插入到链表的后面。

当进行查询时，先对key进行hash计算得到下标，当此下标有多个值时，就使用equals()对key进行比较，最后拿到对应key的值。

hash map的负载因子通常为0.75，也就是说，hash map通常会预留25%的空间，通常空间是不能被用满的，而一旦你的值很多例如上亿的时候，那 HashMap占用的空间就非常大了，是一种以空间换时间的结构。

python的字典就是常见的hash map结构。

2.布隆过滤器

布隆过滤器是一种存储二进制数的数组，通常用来判断值是否存在。

当要往布隆过滤器插入一个值时，会使用多个hash函数进行计算生成多个hash值，并将这些下标处的值置位1。

当要判断一个值a是否存在时，也需要使用同样的方式计算多个hash值，而当存在一个下标的值为0时，就说明这个值a是不存在的。

但布隆过滤器只能判断值不存在，却不能断定一个值存在，因为当布隆过滤器中有大量值时，会存在误差,可能a、b、c三个值生成的9个hash值中，刚好包括d生成的3个hash值，这时就无法判断d到底存不存在了，会存在误判。

ps:同样因为误差的原因，布隆过滤器通常不能删除元素，但可以通过对每个下标进行计数来实现删除。

布隆过滤器常用于爬虫的去重，例如url去重。