散列的介紹

散列（hash）是常用的算法思想之一，在很多程序上都會有意無意的使用到。用一句話來概括散列思想的話就是：“將元素通過一個函數轉換為整數，使得該整數可以盡量唯一地代表這個元素”。其中把轉換函數稱為散列函數H。

那么對key是整數來說，有哪些常用的散列函數呢？一般來說，常見的散列函數有直接定址法、平方取中法、除留余數法，其中直接定址法是指恒等變換（即H(key)=key，很多問題都是直接把key作為數組下標，是最常見最實用的散列應用）。

散列的適用情形

那么，什么情況下使用散列思想呢？如何在競賽或者考試中聯想到散列思想呢？

在使用散列思想時，題目一般會給出兩個字符串或者兩個數組，這兩個字符串或者的元素之間存在ans=S1-S2的類似關系；

題目用于其中某個字符串查詢另一個字符串中的元素的情形；

散列的運用

下面給出一些散列思想的運用。

【PAT】B1039?

#include <stdio.h> #include <string.h> int main(){char hashTable[1010]={0};char str1[1010],str2[1010]; int sum=0;gets(str1);gets(str2);int len_a=strlen(str1);int len_b=strlen(str2);for(int i=0;i<len_a;i++){ //數組的下標是珠子顏色的代表字符，統計每種顏色各有多少個珠子hashTable[str1[i]]++; }for(int i=0;i<len_b;i++){ //統計完畢后，將需要得到的珠子減去原有的珠子，若出現負數，則表 示某種顏色的珠子少于需求hashTable[str2[i]]--;}for(int i=0;i<len_b;i++){if(hashTable[str2[i]]<0){sum=sum+hashTable[str2[i]];hashTable[str2[i]]=0;}}if(sum<0) printf("No %d",0-sum);else printf("Yes %d",len_a-len_b);return 0; }

【PAT】B1042

#include <stdio.h> #include <string.h> int main(){int HashTable[256]={0};int k=0,len;char str[1010],j;gets(str);len=strlen(str);for(int i=0;i<len;i++){if(str[i]>='A'&&str[i]<='Z'){HashTable[str[i]-'A']++; //將標記字符轉化為唯一字符表示，這適用于字符串中給出大小寫，但實際不需要區分大小寫的情況}else if(str[i]>='a'&&str[i]<='z'){HashTable[str[i]-'a']++;}else HashTable[str[i]]=0;}for(int i=0;i<26;i++){if(HashTable[i]>HashTable[k]){k=i;}}printf("%c %d\n",'a'+k,HashTable[k]);return 0; }

【PAT】A1048

#include <stdio.h> #include <iostream> #include <algorithm> using namespace std; int main(){int n,m,a;int hashtable[1005]={0};scanf("%d%d",&n,&m);for(int i=0;i<n;i++){scanf("%d",&a);++hashtable[a]; //將輸入的數字作為數組的下標存儲起來，把數組+下標的組合來存放該下標（即數字）的個數}for(int i=1;i<m;i++){if(hashtable[i]&&hashtable[m-i]){if(i==m-i&&hashtable[i]<=1){continue;}printf("%d %d\n",i,m-i);return 0;}}printf("No Solution\n");return 0; }

?

綜? ? 述

使用散列表示的方式一般有：

以數組的下標作為記錄該數字的存在與否（通過int hashtable[maxn]={0}或者bool hashtable[maxn]={false}）；

以數組的下標作為改為字符記錄；

以數組的下標和數組本身結合，記錄下標（即數字或者字符）出現的次數（如hashtable[3]=2,hashtable['P']=3分別表示3出現了2次，字符P出現了3次）。

看到題目后應結合題目具體分析尋找最簡單的解法。?

?

?

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

總結

以上是生活随笔為你收集整理的【PAT笔记】PAT中的散列思想的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。