❶ 實現一個哈希表
以下是一個簡單示例：
#include<iostream>
#include<string>
using namespace std;
#define m 5 //人數
#define n 10 //哈希表長度
#define q 7 //隨機數
struct name{
char *py;
int k;
};
name namelist[n];
struct hash{
char *py;
int k;
int s;
};
hash hashlist[n];
void listname()
{
char *f;
int s0,r,i;
namelist[0].py="as";
namelist[1].py="sa";
namelist[2].py="d";
namelist[3].py="f";
namelist[4].py="g";
for(i=0;i<m;i++)
{
s0=0;
f=namelist[i].py;
for(r=0;*(f+r)!='\0';r++)
s0+=*(f+r);
namelist[i].k=s0;
}
}
void creathash()
{
int i;
for(i=0;i<n;i++)
{
hashlist[i].py="";
hashlist[i].k=0;
hashlist[i].s=0;
}
for(i=0;i<m;i++)
{
int sum=0;
int adr=(namelist[i].k)%q;
int d=adr;
if(hashlist[adr].s==0)
{
hashlist[adr].py=namelist[i].py;
hashlist[adr].k=namelist[i].k;
hashlist[adr].s=1;
}
else
{
while(hashlist[d].k!=0)
{
d=(d+namelist[i].k%5+1)%q;
sum+=1;
}
hashlist[d].py=namelist[i].py;
hashlist[d].k=namelist[i].k;
hashlist[d].s=sum+1;
}
}
}
void find()
{
string nam;
int s0=0,r,sum=1,adr,d;
cout<<"請輸入姓名的拼音："<<endl;
cin>>nam;;
for(r=0;r<20;r++)
s0+=nam[r];
adr=s0%q;
d=adr;
if(hashlist[adr].k==s0)
cout<<"姓名:"<<hashlist[d].py<<" "<<"關鍵字:"<<s0<<" "<<"查找長度為: 1"<<endl;
else if(hashlist[adr].k==0)
cout<<"無此記錄！"<<endl;
else
{
int g=0;
while(g==0)
{
d=(d+s0%5+1)%q;
sum+=1;
if(hashlist[d].k==0)
{
cout<<"無此記錄！"<<endl;
g=1;
}
if(hashlist[d].k==s0)
{
cout<<"姓名:"<<hashlist[d].py<<" "<<"關鍵字:"<<s0<<" "<<"查找長度為: 1"<<endl;
g=1;
}
}
}
}
void display()
{
int i;
float av=0;
for(i=0;i<n;i++)
{
cout<<"姓名:"<<hashlist[i].py<<" "<<"關鍵字:"<<hashlist[i].k<<"搜索長度："<<hashlist[i].s<<endl;
}
for(i=0;i<7;i++)
{
av+=hashlist[i].s;
}
av/=m;
cout<<"平均查找長度：="<<av<<endl;
}
int main()
{
char x;
listname();
creathash();
cout<<"d. 顯示哈希表 f. 查找 任意鍵退出 請選擇："<<endl;
while(cin>>x){
if(x=='d'){display(); cout<<endl;}
else if(x=='f'){find();cout<<endl;}
else break;
}
return 0;
}
❷ 哈希表(散列表)設計與實現
用EXCEL直接做不得了
❸ C語言實現哈希表的相關運算演算法 編寫程序實現哈希表的構造過程。
#define MaxSize 100 //定義最大哈希表長度
#define NULLKEY -1 //定義空關鍵字值
#define DELKEY -2 //定義被刪關鍵字值
typedef int KeyType; //關鍵字類型
typedef char * InfoType; //其他數據類型
typedef struct
{
KeyType key; //關鍵字域
InfoType data; //其他數據域
int count; //探查次數域
} HashData;
typedef HashData HashTable[MaxSize]; //哈希表類型
void InsertHT(HashTable ha,int &n,KeyType k,int p) //將關鍵字k插入到哈希表中
{
int i,adr;
adr=k % p;
if (ha[adr].key==NULLKEY || ha[adr].key==DELKEY) //x[j]可以直接放在哈希表中
{
ha[adr].key=k;
ha[adr].count=1;
}
else //發生沖突時採用線性探查法解決沖突
{
i=1; //i記錄x[j]發生沖突的次數
do
{
adr=(adr+1) % p;
i++;
}
while (ha[adr].key!=NULLKEY && ha[adr].key!=DELKEY);
ha[adr].key=k;
ha[adr].count=i;
}
n++;
}
void CreateHT(HashTable ha,KeyType x[],int n,
❹ 誰知道哈希表的作用，以及怎樣實現程序設計
我有個之前寫的哈希表的簡單應用，你可以參考一下 #include <stdio.h>
#define N 10
#define HashFunction a[i]%10//定義哈希函數,這里採用模10的運算void main()
{
void Harsh(int a[],int n);
int a[N]={1,2,23,12,4,6,7,5,8,9};
Harsh(a,N);//調用哈希函數
}void Harsh(int a[],int n)
{
int hashlist[N];//定義哈希表
int usedlist[N]={0};//定義已經使用過的哈希表項
int i,j;
int temp;
for(i=0;i<N;i++)
{
temp=HashFunction;//將哈希函數計算結果賦給temp
j=temp;
while(1)
{
if(!usedlist[j])//是否該項沒有使用
{
hashlist[j]=a[i];//如果沒有使用則將值放入哈希表中
usedlist[j]=1;//同時將使用表相應項置為1,表示該項已經使用
break;
}
else
{
j=(j+1)%10;//否則按照一次散列法向下循環查找沒有使用的表項
}
}
}
for(i=0;i<N;i++)
{
printf("%d ",hashlist[i]);
}
printf("\n");
}
❺ 哈希表的設計與實現(線性探測再散列法解決沖突）
散列表（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。
[編輯本段]基本概念
* 若結構中存在關鍵字和K相等的記錄，則必定在f(K)的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關系f為散列函數(Hash function)，按這個思想建立的表為散列表。 * 對不同的關鍵字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，這種現象稱沖突。具有相同函數值的關鍵字對該散列函數來說稱做同義詞。綜上所述，根據散列函數H(key)和處理沖突的方法將一組關鍵字映象到一個有限的連續的地址集（區間）上，並以關鍵字在地址集中的「象」 作為記錄在表中的存儲位置，這種表便稱為散列表，這一映象過程稱為散列造表或散列，所得的存儲位置稱散列地址。 * 若對於關鍵字集合中的任一個關鍵字，經散列函數映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數為均勻散列函數(Uniform Hash function)，這就是使關鍵字經過散列函數得到一個「隨機的地址」，從而減少沖突。
[編輯本段]常用的構造散列函數的方法
散列函數能使對一個數據序列的訪問過程更加迅速有效，通過散列函數，數據元素將被更快地定位ǐ 1. 直接定址法：取關鍵字或關鍵字的某個線性函數值為散列地址。即H(key)=key或H(key) = a•key + b，其中a和b為常數（這種散列函數叫做自身函數） 2. 數字分析法 3. 平方取中法 4. 折疊法 5. 隨機數法 6. 除留余數法：取關鍵字被某個不大於散列表表長m的數p除後所得的余數為散列地址。即 H(key) = key MOD p, p<=m。不僅可以對關鍵字直接取模，也可在折疊、平方取中等運算之後取模。對p的選擇很重要，一般取素數或m，若p選的不好，容易產生同義詞。
[編輯本段]處理沖突的方法
1. 開放定址法：Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中H(key)為散列函數，m為散列表長，di為增量序列，可有下列三種取法： 1. di=1,2,3,…, m-1，稱線性探測再散列； 2. di=1^2, (-1)^2, 2^2,(-2)^2, (3)^2, …, ±(k)^2,(k<=m/2)稱二次探測再散列; 3. di=偽隨機數序列，稱偽隨機探測再散列。 == 2. 再散列法：Hi=RHi(key), i=1,2,…,k RHi均是不同的散列函數，即在同義詞產生地址沖突時計算另一個散列函數地址，直到沖突不再發生，這種方法不易產生「聚集」，但增加了計算時間。 3. 鏈地址法(拉鏈法) 4. 建立一個公共溢出區
[編輯本段]查找的性能分析
散列表的查找過程基本上和造表過程相同。一些關鍵碼可通過散列函數轉換的地址直接找到，另一些關鍵碼在散列函數得到的地址上產生了沖突，需要按處理沖突的方法進行查找。在介紹的三種處理沖突的方法中，產生沖突後的查找仍然是給定值與關鍵碼進行比較的過程。所以，對散列表查找效率的量度，依然用平均查找長度來衡量。 查找過程中，關鍵碼的比較次數，取決於產生沖突的多少，產生的沖突少，查找效率就高，產生的沖突多，查找效率就低。因此，影響產生沖突多少的因素，也就是影響查找效率的因素。影響產生沖突多少有以下三個因素： 1. 散列函數是否均勻； 2. 處理沖突的方法； 3. 散列表的裝填因子。 散列表的裝填因子定義為：α= 填入表中的元素個數 / 散列表的長度 α是散列表裝滿程度的標志因子。由於表長是定值，α與「填入表中的元素個數」成正比，所以，α越大，填入表中的元素較多，產生沖突的可能性就越大；α越小，填入表中的元素較少，產生沖突的可能性就越小。 實際上，散列表的平均查找長度是裝填因子α的函數，只是不同處理沖突的方法有不同的函數。 了解了hash基本定義，就不能不提到一些著名的hash演算法，MD5 和 SHA-1 可以說是目前應用最廣泛的Hash演算法，而它們都是以 MD4 為基礎設計的。那麼他們都是什麼意思呢? 這里簡單說一下： （1) MD4 MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年設計的，MD 是 Message Digest 的縮寫。它適用在32位字長的處理器上用高速軟體實現--它是基於 32 位操作數的位操作來實現的。 （2) MD5 MD5(RFC 1321)是 Rivest 於1991年對MD4的改進版本。它對輸入仍以512位分組，其輸出是4個32位字的級聯，與 MD4 相同。MD5比MD4來得復雜，並且速度較之要慢一點，但更安全，在抗分析和抗差分方面表現更好 （3) SHA-1 及其他 SHA1是由NIST NSA設計為同DSA一起使用的，它對長度小於264的輸入，產生長度為160bit的散列值，因此抗窮舉(brute-force)性更好。SHA-1 設計時基於和MD4相同原理,並且模仿了該演算法。 那麼這些Hash演算法到底有什麼用呢? Hash演算法在信息安全方面的應用主要體現在以下的3個方面： （1) 文件校驗 我們比較熟悉的校驗演算法有奇偶校驗和CRC校驗，這2種校驗並沒有抗數據篡改的能力，它們一定程度上能檢測並糾正數據傳輸中的信道誤碼，但卻不能防止對數據的惡意破壞。 MD5 Hash演算法的"數字指紋"特性，使它成為目前應用最廣泛的一種文件完整性校驗和(Checksum)演算法，不少Unix系統有提供計算md5 checksum的命令。 （2) 數字簽名 Hash 演算法也是現代密碼體系中的一個重要組成部分。由於非對稱演算法的運算速度較慢，所以在數字簽名協議中，單向散列函數扮演了一個重要的角色。 對 Hash 值，又稱"數字摘要"進行數字簽名，在統計上可以認為與對文件本身進行數字簽名是等效的。而且這樣的協議還有其他的優點。 （3) 鑒權協議 如下的鑒權協議又被稱作挑戰--認證模式：在傳輸信道是可被偵聽，但不可被篡改的情況下，這是一種簡單而安全的方法。 MD5、SHA1的破解 2004年8月17日，在美國加州聖芭芭拉召開的國際密碼大會上，山東大學王小雲教授在國際會議上首次宣布了她及她的研究小組近年來的研究成果——對MD5、HAVAL－128、MD4和RIPEMD等四個著名密碼演算法的破譯結果。 次年二月宣布破解SHA-1密碼。
[編輯本段]實際應用
以上就是一些關於hash以及其相關的一些基本預備知識。那麼在emule裡面他具體起到什麼作用呢? 大家都知道emule是基於P2P （Peer-to-peer的縮寫，指的是點對點的意思的軟體）， 它採用了"多源文件傳輸協議」(MFTP，the Multisource FileTransfer Protocol)。在協議中，定義了一系列傳輸、壓縮和打包還有積分的標准，emule 對於每個文件都有md5-hash的演算法設置，這使得該文件獨一無二，並且在整個網路上都可以追蹤得到。 什麼是文件的hash值呢? MD5-Hash-文件的數字文摘通過Hash函數計算得到。不管文件長度如何，它的Hash函數計算結果是一個固定長度的數字。與加密演算法不同，這一個Hash演算法是一個不可逆的單向函數。採用安全性高的Hash演算法，如MD5、SHA時，兩個不同的文件幾乎不可能得到相同的Hash結果。因此，一旦文件被修改，就可檢測出來。 當我們的文件放到emule裡面進行共享發布的時候，emule會根據hash演算法自動生成這個文件的hash值，他就是這個文件唯一的身份標志，它包含了這個文件的基本信息,然後把它提交到所連接的伺服器。當有他人想對這個文件提出下載請求的時候， 這個hash值可以讓他人知道他正在下載的文件是不是就是他所想要的。尤其是在文件的其他屬性被更改之後（如名稱等）這個值就更顯得重要。而且伺服器還提供了,這個文件當前所在的用戶的地址,埠等信息,這樣emule就知道到哪裡去下載了。 一般來講我們要搜索一個文件，emule在得到了這個信息後，會向被添加的伺服器發出請求，要求得到有相同hash值的文件。而伺服器則返回持有這個文件的用戶信息。這樣我們的客戶端就可以直接的和擁有那個文件的用戶溝通，看看是不是可以從他那裡下載所需的文件。 對於emule中文件的hash值是固定的，也是唯一的，它就相當於這個文件的信息摘要，無論這個文件在誰的機器上，他的hash值都是不變的，無論過了多長時間，這個值始終如一，當我們在進行文件的下載上傳過程中，emule都是通過這個值來確定文件。 那麼什麼是userhash呢? 道理同上，當我們在第一次使用emule的時候，emule會自動生成一個值，這個值也是唯一的，它是我們在emule世界裡面的標志，只要你不卸載，不刪除config，你的userhash值也就永遠不變，積分制度就是通過這個值在起作用，emule裡面的積分保存，身份識別，都是使用這個值，而和你的id和你的用戶名無關，你隨便怎麼改這些東西，你的userhash值都是不變的，這也充分保證了公平性。其實他也是一個信息摘要，只不過保存的不是文件信息，而是我們每個人的信息。 那麼什麼是hash文件呢? 我們經常在emule日誌裡面看到，emule正在hash文件，這里就是利用了hash演算法的文件校驗性這個功能了，文章前面已經說了一些這些功能，其實這部分是一個非常復雜的過程，目前在ftp,bt等軟體裡面都是用的這個基本原理，emule裡面是採用文件分塊傳輸，這樣傳輸的每一塊都要進行對比校驗，如果錯誤則要進行重新下載，這期間這些相關信息寫入met文件，直到整個任務完成，這個時候part文件進行重新命名，然後使用move命令，把它傳送到incoming文件裡面，然後met文件自動刪除，所以我們有的時候會遇到hash文件失敗，就是指的是met裡面的信息出了錯誤不能夠和part文件匹配，另外有的時候開機也要瘋狂hash，有兩種情況一種是你在第一次使用，這個時候要hash提取所有文件信息，還有一種情況就是上一次你非法關機，那麼這個時候就是要進行排錯校驗了。 關於hash的演算法研究，一直是信息科學裡面的一個前沿，尤其在網路技術普及的今天，他的重要性越來越突出，其實我們每天在網上進行的信息交流安全驗證，我們在使用的操作系統密鑰原理，裡面都有它的身影，特別對於那些研究信息安全有興趣的朋友，這更是一個打開信息世界的鑰匙，他在hack世界裡面也是一個研究的焦點。 一般的線性表、樹中，記錄在結構中的相對位置是隨機的即和記錄的關鍵字之間不存在確定的關系，在結構中查找記錄時需進行一系列和關鍵字的比較。這一類查找方法建立在「比較」的基礎上，查找的效率與比較次數密切相關。理想的情況是能直接找到需要的記錄，因此必須在記錄的存儲位置和它的關鍵字之間建立一確定的對應關系f，使每個關鍵字和結構中一個唯一的存儲位置相對應。因而查找時，只需根據這個對應關系f找到給定值K的像f(K)。若結構中存在關鍵字和K相等的記錄，則必定在f(K)的存儲位置上，由此不需要進行比較便可直接取得所查記錄。在此，稱這個對應關系f為哈希函數，按這個思想建立的表為哈希表（又稱為雜湊法或散列表）。 哈希表不可避免沖突(collision)現象：對不同的關鍵字可能得到同一哈希地址 即key1≠key2，而hash(key1)=hash(key2)。具有相同函數值的關鍵字對該哈希函數來說稱為同義詞(synonym)。 因此，在建造哈希表時不僅要設定一個好的哈希函數，而且要設定一種處理沖突的方法。可如下描述哈希表：根據設定的哈希函數H(key)和所選中的處理沖突的方法，將一組關鍵字映象到一個有限的、地址連續的地址集(區間)上並以關鍵字在地址集中的「象」作為相應記錄在表中的存儲位置，這種表被稱為哈希表。 對於動態查找表而言，1) 表長不確定；2)在設計查找表時，只知道關鍵字所屬范圍，而不知道確切的關鍵字。因此，一般情況需建立一個函數關系，以f(key)作為關鍵字為key的錄在表中的位置，通常稱這個函數f(key)為哈希函數。(注意：這個函數並不一定是數學函數) 哈希函數是一個映象，即：將關鍵字的集合映射到某個地址集合上，它的設置很靈活，只要這個地址集合的大小不超出允許范圍即可。 現實中哈希函數是需要構造的，並且構造的好才能使用的好。 用途：加密，解決沖突問題。。。。 用途很廣，比特精靈中就使用了哈希函數，你可 以自己看看。 具體可以學習一下數據結構和演算法的書。
[編輯本段]字元串哈希函數
（著名的ELFhash演算法） int ELFhash(char *key) return h%MOD; }
❻ Hash表的程序實現
哈希(Hash)表
以上講的查找方法基於比較的,查找效率依賴比較次數,其實理想的查找希望不經比較,一次存取便能得到所查記錄,那就必須在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系f,這樣查找k時,只要根據這個對應關系f找到給定值k的像f(k)。這種對應關系f叫哈希（hash）函數。按這種思想建立的表叫哈希表（也叫散列表）。哈希表存取方便但存儲時容易沖突（collision）：即不同的關鍵字可以對應同一哈希地址。如何確定哈希函數和解決沖突是關鍵。
1.哈希函數的構造方法
直接定址法:H(k)=k 或H(k)=a*k+b(線形函數)
如:人口數字統計表
地址 1 2 3 ... 100
年齡 1 2 3 ... 100
人數 67 3533 244 ... 4
數字分析法:取關鍵字的若干數位組成哈希地址
如：關鍵字如下：若哈希表長為100則可取中間兩位10進制數作為哈希地址。
81346532 81372242 81387422 81301367 81322817 81338967 81354157 81368537
平方取中法：關鍵字平方後取中間幾位數組成哈希地址
折疊法：將關鍵數字分割成位數相同的幾部分（最後一部分的位數可以不同）然後取幾部分的疊加和（捨去進位）作為哈希地址。
除留余數法：取關鍵字被某個不大於表長m的數p除後所得的余數為哈希地址。
H(k)=k mod p p<=m
隨機數法：H(k)=rondom(k)。
2.處理沖突的方法
假設地址集為0..n-1,由關鍵字得到的哈希地址為j(0<=j<=n-1)的位置已存有記錄,處理沖突就是為該關鍵字的記錄找到另一個"空"的哈希地址。在處理中可能得到一個地址序列Hi i=1，2，...k
0<=Hi<=n-1),即在處理沖突時若得到的另一個哈希地址H1仍發生沖突,再求下一地址H2,若仍沖突,再求H3...。怎樣得到Hi呢？
開放定址法：Hi=(H(k)+di) mod m （H(k)為哈希函數；m為哈希表長；di為增量序列）
當di=1，2，3，... m-1 時叫線性探測再散列。
當di=12，-12，22，-22，32，-32，...,k2,-k2時叫二次探測再散列。
當di=random（m）時叫偽隨機探測序列。
例：長度為11的哈希表關鍵字分別為17，60，29，哈希函數為H(k)=k mod 11,第四個記錄的關鍵字為38，分別按上述方法添入哈希表的地址為8，4，3（隨機數=9）。
再哈希法：Hi=RHi(key) i=1,2,...,k,其中RHi均為不同的哈希函數。
鏈地址法：這種方法很象基數排序，相同的地址的關鍵字值均鏈入對應的鏈表中。
建立公益區法：另設一個溢出表，不管得到的哈希地址如何，一旦發生沖突，都填入溢出表。
3.哈希表的查找
例:如下一組關鍵字按哈希函數H(k)=k mod 13和線性探測處理沖突所得的哈希表a[0..15]:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
14 01 68 27 55 19 20 84 79 23 11 10
當給定值k=84,則首先和a[6]比在依次和a[7],a[8]比結果a[8]=84查找成功。
當給定值k=38,則首先和a[12]比,再和a[13]比,由於a[13]沒有,查找不成功,表中不存在關鍵字等於38的記錄。
5.5 查找第k小元素
查找第k小元素即在n個元素中（未排序）找到第k小的元素。方法同快速排序，採用遞歸方式。
程序如下：
program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
b:arr;
i,k:integer;
function p(s,t:integer):integer;
var i,j,t1,x:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;
while (b[i]<=x) and (i<j) do i:=i+1;
if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
until i=j;
b[i]:=x;
p:=i;
end;
function find(s,t,k:integer):integer;
var p1,q:integer;
begin
if s=t then find:=b[s] else
begin
p1:=p(s,t);
q:=p1-s+1;
if k<=q then find:=find(s,p1,k) else find:=find(p1+1,t,k-q);
end;
end;
begin
write('input data:');
for i:=1 to n do read(b[i]);readln;
write('input k:');read(k);
write('output data:');
writeln('kthsmall:=',find(1,n,k));
end.
❼ 如何用C語言中實現哈希表
C++有 map,set
還有其他的，看STL相關的吧
數組還慢....