1. 什么是哈希

Hash，一般翻譯做散列、雜湊，或音譯為哈希，是一個典型的利用空間換取時間的算法，把任意長度的輸入（又叫做預(yù)映射pre-image）通過散列算法變換成固定長度的輸出，該輸出就是散列值。

如有一個學(xué)生信息表：學(xué)生的學(xué)號為：年紀+學(xué)院號+班級號+順序排序號【如：19(年紀)+002(2號學(xué)院)+01(一班)+17(17號)---à190020117】類似于一個這樣的信息，當(dāng)我們需要找到這個學(xué)號為【190020117】的學(xué)生，在不適用哈希的時候，我們通常是使用一個順序遍歷的方式在數(shù)據(jù)中進行查詢大類，再查詢子類得到，這樣的作法很明顯不夠快 ，需要O(n)左右的時間花費，對于大型的數(shù)據(jù)規(guī)模而言這顯然不行，而哈希的做法是，根據(jù)一定的規(guī)律(比如說年紀不存在過老和過小的情況，以此將【190020117】進行壓縮成一個簡短的數(shù)據(jù)如：【192117】)并且將這個數(shù)據(jù)直接作用于內(nèi)存的地址，屆時我們查詢【190020117】只需要進行一次壓縮并訪問【192117】這個地址即可，而這個壓縮的方法（函數(shù)），就可以稱之為哈希函數(shù)。

一般的對于哈希函數(shù)需要考慮如下內(nèi)容:

a) 計算散列地址所需要的時間（即hash函數(shù)本身不要太復(fù)雜）

b) 關(guān)鍵字的長度

c) 表長(不宜過長或過短，避免內(nèi)存浪費和算力消耗)

d) 關(guān)鍵字分布是否均勻，是否有規(guī)律可循

e) 設(shè)計的hash函數(shù)在滿足以上條件的情況下盡量減少沖突

2.哈希與哈希表

在理解了哈希的思維之后，我們要了解什么是哈希表，哈希表顧名思義就是經(jīng)過哈希函數(shù)進行轉(zhuǎn)換后的一張表，通過訪問哈希表，我們可以快速查詢哈希表，從而得出所需要得到的數(shù)據(jù)，構(gòu)建哈希表的核心就是要考慮哈希函數(shù)的沖突處理（即經(jīng)過數(shù)據(jù)壓縮之后可能存在多數(shù)據(jù)同一個地址，需要利用算法將沖突的數(shù)據(jù)分別存儲）。

沖突處理的方法有很多，最簡單的有+1法，即地址數(shù)直接+1，當(dāng)兩個數(shù)據(jù)都需要存儲進【2019】時，可以考慮將其中的一個存進【2020】

此外還有，開放定址法，鏈?zhǔn)降刂钒l(fā)，公共溢出法，再散列法，質(zhì)數(shù)法等等，各方法面對不同的數(shù)據(jù)特征有不同的效果。

3.哈希的思維

Hash算法是一個廣義的算法，也可以認為是一種思想，使用Hash算法可以提高存儲空間的利用率，可以提高數(shù)據(jù)的查詢效率，也可以做數(shù)字簽名來保障數(shù)據(jù)傳遞的安全性。所以Hash算法被廣泛地應(yīng)用在互聯(lián)網(wǎng)應(yīng)用中。

比如，利用哈希的思維在O(1)的復(fù)雜度情況下任意查詢1000以內(nèi)所有的質(zhì)數(shù)（在創(chuàng)建是否是質(zhì)數(shù)的時候并不是O(1)的復(fù)雜度），注意本樣例只是演示思維，面對本需求可以有更好的空間利用方式（本寫法比較浪費空間，僅供了解）。

#include<iostream>
using namespace std;
 
const int maxn=1002;
int arr[maxn]={0};
 
//判斷是否是質(zhì)數(shù) 
bool is_pri(int n){
    for(int i=n-1;i>=2;i--){
        if(n%i==0)  return false;
    }
    return true;
}
 
void create(){
    for(int i=3;i<=maxn;i++){
        if(is_pri(i)){
            arr[i]=1;
        }
    }
}
 
int main(){
    create();
    int input;
    while(cin>>input){
        if(arr[input]){
            cout<<input<<" 是質(zhì)數(shù)"<<endl;
        }else{
            cout<<input<<" 不是質(zhì)數(shù)"<<endl;
        }
    }
    return 0;
}