简单了解散列(hash)算法思想

(本文转载,自己做了少许修正,若有侵权请联系删除) 简单了解散列(hash)算法思想 设分别有两个集合,分别有M个和N个元素。问N个元素中每个数是否在是否在M中出现过。 一个很直观的想法就是:分别输入两组数据,然后用两个for循环来遍历查找。 时间复杂度为O(MN),当N M足够大的时候,显然效率会非常低。 所以我们不妨用空间换取时间,当输入M集合中的数据x的时候,我们都用一个数组hashTable[10000](初始设置为0,默认每个元素都没在这个集合中出现过)来设置hashTable[x] = 1来表明这个数x在M中存在。 这样我们在输入N集合中的数据,直接将输入的这个数作为hashTable数组的下标,就会直接得到我们想要的结果。这是的时间复杂度就降到了O(M+N)。* //下面是实现的代码 int m,n,hashTable[10000] = {0}; cin >>m>>n; //m和n指的是集合M和集合N的元素个数 for (int i = 0,x;i<m ;i++ ){ cin>>x; hashTable[x] = 1; } for (int i = 0,x;i<n ;i++ ){ cin>>x; if(hashTable[x] == 1){ cout<<"YES"; }else{ cout<<"NO"; } } 这里的精华思想就是:将输入的数据直接作为数组的下标来记录数据的状态。 但是这个策略依旧存在很多问题:上面的问题将输入的数据大小控制在了10^5 ,但是如果我们输入的数据为大约为10^9 这么大时,或者甚至是字符串如(“Hello World”)时,就不能直接将他们作为数组下标了。所以我们这时的目标就是将这些数据转化为一个可用的整数下标,而这种方法就叫做——散列 什么是散列 散列用一句话来说就是:将输入的数据用一个函数转化为一个整数,使其尽量唯一的代表该元素。 我们不妨称这个转换函数为H,如果一个元素之前是key,那么它转化后就成了H(key),下面我们来分类讨论一下。 先是整数hash 当key为整数的时候,有哪些常见的散列函数呢?一般有直接定址法、除留取余法和平方取中法等。...

April 21, 2021 · 2 min · Rufus