哈希:
用于unorder_map和unorder_set,其本身是一种思想,即通过一个值利用某种算法去映射到另一个值上。利用哈希思想具体实现的是哈希表。
哈希通常函数:插入和查找
1.插入:用某种算法算出插入值对应的插入下标。
2.查找:利用插入的算法找出待查找的值可能出现的下标。
哈希冲突:
概念:不同的数通过算法计算出的插入下标相同,此时发生哈希冲突。
一般来说数的个数越多越容易发生冲突,有点类似雀巢原理?
解决哈希冲突:
法一:开散列
相同下标的元素放在同一个链表中,此时该链表中所有元素共同为一个桶,每个桶中所有元素彼此哈希冲突。
法二:闭散列
发生哈希冲突时,后插入的元素依次往下标+1、+2...的空闲位置放(线性探测),也也可以往下标+1、下标+4、下标+9...的空闲位置差(二次探测)
哈希扩容:
当插入元素很多时,哈希冲突的概率会越来愈大,为了减少哈希冲突概率,需要扩容。对于开散列,一般在原本链表数组基础上扩容,然后直接将链表上所有元素重新插入。对于闭散列,一般开一份新空间,其长度是原本数组二倍,然后复用插入函数将原数组上的元素拷贝一份放到新空间,后释放原数组,指向新数组。
位图:
一种基于哈希思想的应用,用于海量整形数据的查找、判断是否存在。
原理:每一个数用一个比特位表示是否存在,极大程度减少所占空间。插入时通过一个函数。将整形数据映射到对应比特位上。查找时只需根据函数判断对应比特位是否为1即可。
缺陷:位图只能用于全是整形数据,例如字符串之类的不能使用。
针对位图的缺陷,有了布隆过滤器。
布隆过滤器:
对于字符串,会先通过一个算法转换成对应的一个整形数据,在通过哈希函数找出对应下标(比特位)。
缺陷:虽然可以适用于字符串等非整形类型,但是仍然会有哈希冲突的存在,如不同字符串对应的下标相同。因此只能正确判断字符串不在,无法百分百判断字符串是不是在。(存在误判),因此在查找一个字符串时可以过滤掉不在的数,不能过滤掉可能在的数,因此是过滤器。
布隆过滤器一般无法进行删除,因为不同字符串可能对应同一个下标,若删除可能导致错误。若想要实现删除,需要额外增加一个计数位置,记录当前有几个字符串在此下标,但这样又会额外开辟大量空间。