本文首發(fā)于vx公眾號(hào) 蘇伏
哈希表
1 簡(jiǎn)介
哈希表：又稱散列表，是一種根據(jù)給定的關(guān)鍵字來計(jì)算關(guān)鍵字在表中地址的數(shù)據(jù)結(jié)構(gòu)，即散列表建立了關(guān)鍵字和存儲(chǔ)地址之間的一種直接映射關(guān)系。
哈希函數(shù)：又稱散列函數(shù)，將給定關(guān)鍵字映射為該關(guān)鍵字對(duì)應(yīng)的地址的函數(shù)，記為Hash(key)=Addr。
哈希沖突：散列函數(shù)將兩個(gè)以上的不同關(guān)鍵字映射到同一個(gè)地址，這種情況成為哈希沖突，這些沖突的不同關(guān)鍵字稱為同義詞。
2 哈希函數(shù)和沖突處理方法
2.1 構(gòu)造哈希函數(shù)的要點(diǎn)
- 哈希函數(shù)定義域必須包含
需要存儲(chǔ)的全部關(guān)鍵字，值域的范圍依賴于哈希表的大小或者地址范圍。 - 哈希函數(shù)計(jì)算出來的地址應(yīng)該能等概率，均勻地分布在整個(gè)地址空間，減少?zèng)_突的發(fā)生。
- 哈希函數(shù)應(yīng)該盡量簡(jiǎn)單，計(jì)算時(shí)間短
2.2 常用的Hash函數(shù)的構(gòu)造方法
2.2.1.直接定址法
直接取關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址，散列函數(shù)為Hash(key)=a*key+b，其中，a和b是常數(shù)。這種方法計(jì)算最簡(jiǎn)單，不會(huì)產(chǎn)生沖突。
2.2.2.取模法
假定哈希表表長(zhǎng)為m，取一個(gè)不大于m但最接近或等于m的質(zhì)數(shù)p，用取模運(yùn)算把關(guān)鍵字轉(zhuǎn)換成哈希地址。散列函數(shù)為Hash(key)=key%p。該方法的關(guān)鍵是選好p，使得每一個(gè)關(guān)鍵字通過該函數(shù)轉(zhuǎn)換后等概率的映射到散列空間上任一地址，從而盡可能的減少?zèng)_突的可能性。
2.2.3.數(shù)字分析法
設(shè)關(guān)鍵字是r進(jìn)制數(shù)（如十進(jìn)制），而r個(gè)數(shù)碼在各位上出現(xiàn)的概率不一定相同，可能在某些位上分布均勻些，每種數(shù)碼出現(xiàn)的幾率均等；而在某些位上分布不均勻，只有集中數(shù)碼經(jīng)常出現(xiàn)，則應(yīng)選取數(shù)碼分布較為均勻的若干位做為散列地址。這種方法是用于已知的關(guān)鍵字集合。
2.2.4.平方取中法
取關(guān)鍵字的平方值的中間幾位作為散列地址。具體取多少位要看實(shí)際情況而定。這種方法得到的散列地址與關(guān)鍵字的每一位都有關(guān)系，是的散列分布比較均勻。
2.2.5.折疊法
將關(guān)鍵字拆分為相同的幾個(gè)部分（最后一部分位數(shù)可以短一些），然后取這部分的疊加和作為散列地址，這種方法稱為折疊法。這種方法適合用于關(guān)鍵字位數(shù)較多且關(guān)鍵字中每一位數(shù)字分布大致均勻時(shí)。
2.3 常用Hash函數(shù)沖突處理方法
2.3.1.開放定址法
將產(chǎn)生沖突的Hash地址作為自變量，通過某種沖突解決函數(shù)得到一個(gè)新的空閑的Hash地址。
2.3.1.1 線性探測(cè)法
沖突發(fā)生時(shí)，順序查看表中的下一單元（循環(huán)），直到出現(xiàn)一個(gè)空閑單元或者查遍全表。（表不為空的時(shí)候一定可以找到）
缺點(diǎn)：會(huì)造成大量元素在相鄰散列地址上聚集起來，大大降低了查找效率。
2.3.1.2 平方探測(cè)法
設(shè)發(fā)生沖突的地址為d，平方探測(cè)法得到新的地址序列為d+12，d-12，d+22，d-22......平方探測(cè)法是一種比較好的探測(cè)方法，可以避免出現(xiàn)聚集問題。
缺點(diǎn)：不能探測(cè)到哈希表上的所有單元，但是至少能探測(cè)一半單元。
2.3.1.3 再哈希法
又稱雙哈希法。需要使用兩個(gè)散列函數(shù)，當(dāng)通過第一個(gè)散列函數(shù)Hash(key)得到的地址發(fā)生沖突時(shí)，則利用第二個(gè)散列函數(shù)Hash2(key)計(jì)算該關(guān)鍵字的地址增量。哈希函數(shù)為Hi=(H(key)+i*Hash2(key))%m，其中m是表長(zhǎng)，i是沖突次數(shù)。
2.3.1.4 偽隨機(jī)序列法
發(fā)生哈希沖突時(shí)，地址增量為隨機(jī)數(shù)序列，稱為偽隨機(jī)序列法。
2.3.2 拉鏈法
對(duì)于不同的關(guān)鍵字可能會(huì)通過哈希函數(shù)映射到同一地址，為了避免非同義詞發(fā)生沖突，可以把所有的同義詞存儲(chǔ)在一個(gè)線性鏈表中，這個(gè)線性鏈表由其散列地址唯一表示。拉鏈法是用于經(jīng)常進(jìn)行插入和刪除的情況。
3 散列表的查找
給定一個(gè)關(guān)鍵字key，根據(jù)哈希函數(shù)計(jì)算其哈希地址，然后檢查哈希地址有沒有關(guān)鍵字。
- 如果沒有，表明該關(guān)鍵字不存在，返回查找失??；
- 如果有，則檢查該記錄是否等于關(guān)鍵字，1)如果等于，返回改字，查找成功。2)如果不等，則按照給定的沖突解決辦法計(jì)算懸疑散列地址，再執(zhí)行上述過程。
4 散列表查找性能
散列表查找性能跟裝填因子有關(guān)，一般記為α，定義為一個(gè)表的裝滿程度。計(jì)算方法為 α=表中記錄數(shù)n/表長(zhǎng)m
散列表的平均查找長(zhǎng)度依賴于散列表的裝填因子α，而不直接依賴于n或者m。α越大，表示裝天的紀(jì)錄越滿，發(fā)生沖突的可能性就大，反之發(fā)生沖突的可能性越小`。
5 實(shí)例
5.1 問題描述
設(shè)計(jì)散列表，實(shí)現(xiàn)電話號(hào)碼查找系統(tǒng)。設(shè)電話號(hào)碼簿長(zhǎng)度為n（0≤n≤10000），系統(tǒng)應(yīng)該實(shí)現(xiàn)如下工作：
⑴ 電話號(hào)碼簿保存在磁盤文件中，每一條電話號(hào)碼記錄包含數(shù)據(jù)項(xiàng)：編號(hào)（唯一），用戶名，通信地址，電話號(hào)碼（手機(jī)號(hào)）
⑵ 創(chuàng)建散列表：系統(tǒng)運(yùn)行時(shí)，讀取磁盤文件的電話號(hào)碼，構(gòu)建散列表，用于查詢。要求：自選散列函數(shù)(至少2種)，自選解決沖突的方法(至少2種)，分別以電話號(hào)碼和用戶名為關(guān)鍵字，建立散列表。
⑶ 查詢：根據(jù)輸入的用戶名，查找并顯示給定用戶的信息。
⑷ 性能分析：
① 計(jì)算并輸出不同散列函數(shù)、不同解決沖突方法的平均查找長(zhǎng)度。
② 通過改變裝填因子、改變哈希函數(shù)等方式，改善平均查找長(zhǎng)度：通過數(shù)據(jù)表、柱形圖、折線圖等方式，記錄實(shí)驗(yàn)數(shù)據(jù)的變化情況，對(duì)影響平均查找長(zhǎng)度變化的原因進(jìn)行分析。
5.2 問題分析
以電話號(hào)碼為關(guān)鍵字建立哈希表，散列函數(shù)選用折疊法，將手機(jī)號(hào)的后八位拆分成兩個(gè)四位，然后相加再模哈希表長(zhǎng)度得到地址。，如圖一
?
其中，x，y分別是輸入手機(jī)號(hào)后八位的前四位與后四位，10000是哈希表的長(zhǎng)度。
以姓名為關(guān)鍵字建立哈希表，哈希函數(shù)選用平方取中法，由于我生成的隨機(jī)數(shù)據(jù)中姓名是由4個(gè)字符組成，因此計(jì)算四個(gè)字符與’a’的差值再乘10/27得到一個(gè)4位10進(jìn)制數(shù)字，即是散列地址。具體操作如圖二
初始散列因子為0.7，哈希表長(zhǎng)度是10000，數(shù)據(jù)量是7000條。
解決沖突辦法分別是1.線性探測(cè)法，即出現(xiàn)沖突線性尋找下一個(gè)非空位置放數(shù)據(jù)，缺點(diǎn)是容易產(chǎn)生數(shù)據(jù)堆積。2.其次是平方探測(cè)法，平方探測(cè)法得到新的地址序列為d+12，d-12，d+22，d-22……計(jì)算如圖三
5.3 實(shí)驗(yàn)結(jié)果及分析
（1）實(shí)驗(yàn)數(shù)據(jù)描述
電話簿初始為7000條數(shù)據(jù)，哈希表長(zhǎng)固定為10000，每一條記錄包含四個(gè)字段，分別是id(唯一)，四位隨機(jī)字符串姓名，20位隨機(jī)字符串地址，150開始，后八位隨機(jī)數(shù)字表示電話號(hào)碼。以txt文件存儲(chǔ)在磁盤中，每一行數(shù)據(jù)就是一條記錄，讀取/寫入一次操作一行。
（2）實(shí)驗(yàn)結(jié)果
某一次程序輸入結(jié)果如圖四
?
α為裝填因子，AVL為平均查找長(zhǎng)度。
電話號(hào)碼為關(guān)鍵字，哈希方法為折疊法，解決沖突方法線性探測(cè)法。
電話號(hào)碼為關(guān)鍵字，哈希方法為折疊法，解決沖突平方探測(cè)法。
姓名為關(guān)鍵字，哈希方法為平方取中法，解決沖突方法線性探測(cè)法。
姓名為關(guān)鍵字，哈希方法為平方取中法，解決沖突平方探測(cè)法。
| 序號(hào) | α | AVL | α | AVL | α | AVL | α | AVL | α | AVL |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 0.6 | 1.703 | 0.65 | 1.941 | 0.7 | 2.279 | 0.75 | 2.491 | 0.8 | 2.823 |
| 2 | 0.6 | 1.736 | 0.65 | 1.858 | 0.7 | 2.158 | 0.75 | 2.481 | 0.8 | 3.012 |
| 3 | 0.6 | 2.969 | 0.65 | 3.544 | 0.7 | 5.364 | 0.75 | 6.726 | 0.8 | 8.938 |
| 4 | 0.6 | 2.790 | 0.65 | 3.046 | 0.7 | 3.784 | 0.75 | 4.577 | 0.8 | 5.759 |
表一
5.4 結(jié)論
結(jié)論：根據(jù)表一與圖五可知，由于哈希函數(shù)和沖突處理方法不同，以及關(guān)鍵字不同，建立哈希表的查找性能也不同，α越大，即表填的越‘滿’，查找性能越低，反之查找性能越高。
6 源代碼
代碼寫的渣渣，能測(cè)試就行。
實(shí)體類：
package com.sufu.data.structure.experiments;
import java.io.Serializable;
/**
* @author sufu
* @version 1.0.0
* @date 2020/5/17 3:27
* @description 電話號(hào)碼實(shí)體類
*/
public class PhoneNumber implements Serializable {
private int id;
private String username;
private String stress;
private String phoneNumber;
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getUsername() {
return username;
}
public void setUsername(String username) {
this.username = username;
}
public String getStress() {
return stress;
}
public void setStress(String stress) {
this.stress = stress;
}
public String getPhoneNumber() {
return phoneNumber;
}
public void setPhoneNumber(String num) {
this.phoneNumber = num;
}
public PhoneNumber(int id, String username, String stress, String phoneNumber) {
this.id = id;
this.username = username;
this.stress = stress;
this.phoneNumber = phoneNumber;
}
public PhoneNumber(String s){
String[] info = s.split(",");
this.id = Integer.parseInt(info[0]);
this.username = info[1];
this.stress = info[2];
this.phoneNumber = info[3];
}
@Override
public String toString() {
return id+","+username+","+stress+","+phoneNumber;
}
}
主函數(shù)：
package com.sufu.data.structure.experiments;
import java.io.*;
import java.util.Date;
/**
* @author sufu
* @version 1.0.0
* @date 2020/5/17 3:29
* @description
*/
public class Main {
static char[] CHARS = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N', 'O','P','Q','R','S','T','U','V','W','X','Y','Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
static char[] NUMS = {'0','1','2','3','4','5','6','7','8','9'};
static String FILE_PATH = "C:\\Users\\DELL\\Desktop\\數(shù)據(jù)結(jié)構(gòu)\\";
static int DATA_SIZE = 8000;//數(shù)據(jù)大小
static int HASH_TABLE_LENGTH = 10000;//哈希表長(zhǎng)
static int HASH_TYPE = 1;//哈希方法選用類型 1或非1
static int DEAL_TYPE = 2;//沖突處理方法選用類型 1或非1
static double CPMPARETIMES = 0;
static int ADDR = 1;//解決沖突方法2中的地址增量
static boolean ISADD = false;//結(jié)局沖突方法2中是否是加號(hào)
public static void main(String[] args) {
System.out.println("創(chuàng)建隨機(jī)數(shù)據(jù).....");
getRandomData();//創(chuàng)建DATA_SIZE條測(cè)試數(shù)據(jù),輸出創(chuàng)建時(shí)間
System.out.println("初始化哈希表中..............");
PhoneNumber[] hashTable = init();//創(chuàng)建并返回哈希表
System.out.println("初始化完成！");
// int op;
// while(true){
// System.out.println("歡迎使用！ 輸入編號(hào)執(zhí)行響應(yīng)操作：\n1.根據(jù)電話號(hào)碼查找 2.根據(jù)姓名查找 3.性能分析\n輸入-1結(jié)束");
// Scanner scanner = new Scanner(System.in);
// op = scanner.nextInt();
// if(op == 1){
// System.out.println("請(qǐng)輸入電話號(hào)碼：");
// String s = scanner.next();
// PhoneNumber result = search(s, hashTable);
// if(result!=null){
// System.out.println(result);
// }else
// System.out.println("查找失敗，沒有該用戶！");
// System.out.println("比較次數(shù)："+compareTimes);
// }else if(op == 2){
// System.out.println("2");
// }else if(op == -1)
// break;
// else
// System.out.println("輸入有誤");
// }
PhoneNumber[] original = readFromDisk();//源數(shù)據(jù)
for(int i =0;i<DATA_SIZE;i++){
if(search(original[i].getPhoneNumber(),hashTable)==null){
System.out.println("false");
};
}
// for(int i =0;i<DATA_SIZE;i++){
// if(search(original[i].getUsername(),hashTable)==null){
// System.out.println("false");
// };
// }
System.out.println(CPMPARETIMES /DATA_SIZE);
}
static PhoneNumber search(String key,PhoneNumber[] hashTable){
int index;
if(HASH_TYPE == 1){
index = hash1(key);
}else {
index = hash2(key);
}
while(true){
PhoneNumber re = hashTable[index];
CPMPARETIMES++;
if(re == null){
return null;
}
else if(re.getPhoneNumber().equals(key)){
return re;
}else {
if(DEAL_TYPE == 1){
index = deal1(index);
}else {
index = deal2(index);
}
}
}
}
public static PhoneNumber[] init(){
PhoneNumber[] data = readFromDisk();
PhoneNumber[] hashTable = new PhoneNumber[HASH_TABLE_LENGTH];
String num;
int index,count = 0;
for(int i =0;i<data.length;i++){
num = data[i].getPhoneNumber();
if(HASH_TYPE==1){
//選擇第一個(gè)哈希函數(shù)
index = hash1(num);
}else {
//否則是第二個(gè)哈希函數(shù)
index = hash2(num);
}
while(true){
if(hashTable[index]==null){
//無沖突 直接存放數(shù)據(jù)
hashTable[index] = data[i];
break;
}else {
if(DEAL_TYPE == 1){
index = deal1(index);
}else {
index = deal2(index);
}
}
}
}
saveItemsToDisk(FILE_PATH+"test.txt",hashTable);
return hashTable;
}
public static String getRandomString(Integer len,char[] chars){
char[] chrs = new char[len];
int index = 0;
for(int i=0;i<len;i++){
index = (char) (Math.random()*chars.length);
chrs[i] = chars[index];
}
return String.valueOf(chrs);
}
public static void saveItemsToDisk(String path,PhoneNumber[] items){
File file = new File(path);
if(file.exists()){
file.delete();
}
try {
file.createNewFile();
FileWriter fileWriter = new FileWriter(file);
PrintWriter printWriter = new PrintWriter(fileWriter);
for (PhoneNumber item : items) {
printWriter.println(item);
}
printWriter.close();
fileWriter.close();
} catch (IOException e) {
e.printStackTrace();
}
}
public static void getRandomData(){
Date date1 = new Date();
int index = 0;
PhoneNumber[] items = new PhoneNumber[DATA_SIZE];
for (int i=0;i<items.length;i++) {
items[i] = new PhoneNumber(index+","+getRandomString(4,CHARS)+","+getRandomString(20,CHARS)+","+"150"+getRandomString(8, NUMS));
index++;
}
saveItemsToDisk(FILE_PATH+"data.txt", items);
Date date2 = new Date();
System.out.println(date2.getTime()-date1.getTime()+"ms");
}
public static PhoneNumber[] readFromDisk(){
PhoneNumber[] phoneNumber = new PhoneNumber[DATA_SIZE];
File filePath = new File(FILE_PATH+"data.txt");
if (filePath.exists()){
try {
FileReader fileReader = new FileReader(filePath);
BufferedReader reader = new BufferedReader(fileReader);
for (int i=0;i<DATA_SIZE;i++){
phoneNumber[i] = new PhoneNumber(reader.readLine());
}
return phoneNumber;
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}
return null;
}
static int hash1(String input){
//折疊法，輸入電話號(hào)碼后八位，得到索引，此法只針對(duì)輸入電話號(hào)碼查找
//input = input.substring(3, 11);//取后八位
int x = Integer.parseInt(input.substring(0, 4));//去后八位中的前四位
int y = Integer.parseInt(input.substring(4, 8));//取后八位中的后四位
return (x+y)%HASH_TABLE_LENGTH;
}
static int hash2(String input){
//平方取中法，輸入四個(gè)字符，計(jì)算每個(gè)字符與字符a的差值做平方再取中間四位
int index = 0;
for(int i =0;i<input.length();i++){
index = index + (int)((input.charAt(i)-'a')*10/27*Math.pow(10,3-i));
}
index*=index;
return (index/100)%HASH_TABLE_LENGTH;
}
static int deal1(int input){
//線性探測(cè)法解決沖突
return ++input%HASH_TABLE_LENGTH;
}
static int deal2(int input){
//平方探測(cè)法解決哈希沖突
if(ISADD){
input = input+ADDR*ADDR;
ADDR++;
}else
input = (HASH_TABLE_LENGTH+input-ADDR*ADDR)%HASH_TABLE_LENGTH;
return input;
}
}
