pymongo查询列表元素_数据结构与算法 | 散列表

散列表是啥？

散列表(Hash table，也叫哈希表)，是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录。这个映射函数称做散列函数，存放记录的数组称做散列表。

散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展。通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应的下标的位置；当按照键值查询元素的时候，用同样的散列函数，将键值转化为数组下标，从对应的数组下标的位置取数据；

可能你还是不清楚散列表长啥样，还是不知道散列到底有啥用？不要着急，接着往下看就明白了！

为什么要用散列？

散列是一种常用的算法思想，在很多任务中(特别是快速查询)我们都会有意无意地使用到。因为个人感觉直接阐述散列表的优点不够直观，所以我引入了一个简单的例子，方便大家迅速get到散列表的优势。

给出N个正整数，再给出M个正整数，问着M个数中的每个数分别是否在N个数中出现过，其中N，M≤10^5。例如N = 5， M = 3， N个正整数为{8,3,7,6,2}，欲查询的M个正整数为{7,4,2}，于是后者中只有7和2在N个正整数中出现过，4是没有出现过的。

对于这个问题，最直观的思路是：对每个欲查询的正整数x，遍历所有N个数，看是否有一个数与x相等，这种做法的时间复杂度为O(M*N)，当N和M都很大时显然计算机是很难承受的。

那么该如何做嘞？—— 不妨用空间换时间，即设定一个bool型数组hashTable[100010], 其中hashTable[x] == true 表示正整数x在N个正整数中出现过，而hashTable[x] == false 表示正整数x没有出现过。这样就可以在一开始读入N个正整数就预处理，即当读入的数为x时，就令hashTable[x] = true (说明：hashTable数组需要初始化为false，表示初始状态下所有数都没有出现过)。于是对于M个欲查询的数，就能直接通过hashTable数组判断出每个数是否出现过。显然这种做法的时间复杂度为O(N+M)，代码如下：

# includeconst int maxn = 100010;bool hashTable[maxn] = {false};int main(){  int n,m,x;  scanf("%d%d",&n,&m);  for(int i = 0; i    scanf("%d",&x);    hashTable[x] = true;  }  for(int i = 0; i    scanf("%d",&x);    if(hashTable[x]){      printf("YES\n");    }else{      printf("NO \n");     }  }    return 0;}

同样的，如果题目要求M个欲查询的数中每个数在N个数中出现的次数，那么可以把hashTable数组替换成为int型数组，然后在输入N个数就进行预处理，即当输入的数为x时，就令hashTable[x]++，这样就可以用O(N+M)的时间复杂度输出欲查询数出现的次数。代码如下：

# includeconst int maxn = 100010;int hashTable[maxn] = {0};int main(){  int n,m,x;  scanf("%d%d",&n,&m);  for(int i = 0; i    scanf("%d",&x);    hashTable[x]++;  }  for(int i = 0; i        scanf("%d",&x);    printf("%d \n",hashTable[x]);  }    return 0;}

构造散列函数

散列函数在散列表中起着非常关键的作用。顾名思义，它是一个函数，可以把它定义成 hash()，其中 key 表示元素的键值，hash(key) 的值表示经过散列函数计算得到的散列值。那么有哪些常用的哈希函数嘞(对于Key是常数的情况)？

01

直接地址法

直接地址法其实就是恒等变换：Hash(key) = a*key + b，这是最简单的散列函数，适合查找表较小且连续的情况。我们在上面的例子中构造的散列函数就是利用了直接地址法。

02

平方取中法

平方取中法是指取key的平方的中间若干位作为hash值，比较适合于不知道关键字的分布，而位数又不是很大的情况。比如假设关键字是 4321，那么它的平方就是 18671041，抽取中间的 3 位就可以是 671，也可以是 710，用做散列地址。

03

除留余数法

除留余数法是最常用的散列函数构造方法，是指把Key除以一个数mod得到的余数作为hash值的方法，即Hash(key) = key % mod。通过这个散列函数，我们可以把很大的数转换为不超过mod的整数，这样就可以将它作为可行的数组下标(注意：散列表长size必须不小于mod，否则就会越界)。本方法的关键就在于如何选择合适的mod，根据经验，一般mod为小于或等于表长size(最后接近size)的最大质数或不包含小于20质因子的合数。比如某散列表长度为100 ，那么P最好选97，因为它是离表长最近的最大质数。

总之，构造哈希函数的原则是：

①函数本身便于计算；

②计算出来的地址分布均匀，即对任一关键字key，hash(key) 对应不同地址的概率相等，目的是尽可能减少冲突。

解决冲突

虽然我们不希望发生冲突，但实际上发生冲突的可能性仍是存在的。当关键字值域远大于哈希表的长度且事先并不知道关键字的具体取值时，冲突就难免会发生。

既然冲突不可避免，那就要想办法解决冲突。下面讲解三种常用方法，其中第一、第二种都计算了新的hash值，又称为开放地址法。

01

线性探查法

当得到key的hash值Hash(key)，但是表中下标为Hash(key)的位置已经被其他元素使用了，那么就检查下一个位置Hash(key) + 1是否被占用，如果没有就用这个位置；否则就继续检查下一个位置。如果检查过程中超过表长，那么就回到表的首位继续循环，直到找到一个可以使用的位置，或者发现表中所有位置都已经被使用了。显然这种方法的缺点在于容易导致扎堆现象，即表中连续若干个位置都被使用，这在一定程度上会降低效率。

02

平方探查法

为了避免线性探查法的不足(避免扎堆现象)，当表中下标为Hash(key)的位置被占时，将按着下面的顺序检查表中的位置：Hash(key) + 1^2、Hash(key) - 1^2、Hash(key) + 2^2、Hash(key) - 2^2....。如果检查过程中Hash(key)+k^2超过表长size，那么就把Hash(key)+k^2对size取模；如果H(key)-k^2<0，那么将((Hash(key)-k^2) % size + size) % size作为结果。可以证明如果当0size时，也一定无法找到位置。

03

链地址法(拉链法)

和上面两种方法不同，链地址法不计算新的hash值，而是把所有Hash(key)相同的key连接成一个单链表，这种方法和除留余数法经常结合在一起进行使用。我们可以设定一个数组Link，范围是Link[0] ~ Link[mod-1]，其中Link[h]存放Hash(key) = h的一条单链表，于是当多个关键字key的hash值都是h时，就可以直接把这些冲突的key用单链表连接起来，此时就可以遍历这条单链表来寻找Hash(key)= h的key。

散列表的应用

01

实现Word文档的单词拼写功能

常用的英文单词有 20 万个左右，假设单词的平均长度是 10 个字母，平均一个单词占用 10 个字节的内存空间，那 20 万英文单词大约占 2MB 的存储空间，就算放大 10 倍也就是 20MB。

对于现在的计算机来说，这个大小完全可以放在内存里面。所以我们可以用散列表来存储整个英文单词词典。

当用户输入某个英文单词时，我们拿用户输入的单词去散列表中查找。如果查到，则说明拼写正确；如果没有查到，则说明拼写可能有误，给予提示。借助散列表这种数据结构，我们就可以轻松实现快速判断是否存在拼写错误。