文章目錄

• • 題目分析
  • 題目鏈接

題目分析

來(lái)源:acwing
分析：
本題建立hash表是利用只具有正增量的二次探測(cè)法來(lái)解決沖突，
索引 = 數(shù) % 哈希表的大小
如果映射到同一個(gè)索引idx，hash表的長(zhǎng)度是s，需要解決沖突：先看$(idx+1^2）mods$是否使用，如果使用，再看$(idx+2^2）mods$是否使用過(guò)，以此類推，這就是具有正增量的二次探測(cè)法。

具體代碼如下：

//開放尋址法的find函數(shù):找索引 int find(int x){int t = x % s;for(int k = 0; k<s; k++){int i = (t + k*k) % s;if(!h[i]) return i;}return -1; //放不進(jìn)去 }

ac代碼

#include<bits/stdc++.h> using namespace std; const int N = 1e5+10; int h[N]; //hash表 int s ,n; //s是哈希表長(zhǎng)度//判質(zhì)數(shù) bool is_prime(int x){if( x == 1) return false;for(int i =2; i <= x/i ;i++)if( x %i ==0) return false;return true; }//開放尋址法的find函數(shù):找索引 int find(int x){int t = x % s;for(int k = 0; k<s; k++){int i = (t + k*k) % s;if(!h[i]) return i;}return -1; //放不進(jìn)去 } int main(){cin >> s >> n;//s變成大于s的最小質(zhì)數(shù)while(!is_prime(s)) s++;for(int i = 0; i<n ;i ++){int x; cin >> x;int t = find(x);//要插入的位置（索引）if(t == -1) cout<<"-";else{h[t] = x;cout << t;}if( i != n -1) cout<<" ";}}

題目鏈接

PAT甲級(jí)1078 Hashing
https://www.acwing.com/problem/content/1566/

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的PAT甲级1078 Hashing：[C++题解]哈希表、哈希表开放寻址法、二次探测法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。