什麼是哈希表

哈希表 是 Hash Table 一詞的中文翻譯，演算法書裏通常稱這種數據結構為「散列表」。之所以稱之為 散列表 和這種數據結構的存儲方式有關，每個按序進入的數據經過 散列函數 的計算後會無序的分佈在哈希表不同的位置，這是與數組、鏈表等有序結構所不同的。

哈希表實際上是數組的一種擴展。在哈希表中通過 哈希函數 我們可以將數字、字元串等數據中比較有代表性的數據作為 鍵值 轉換成數組的 索引，在數組中存儲 鍵值 代表的數據。而通過 哈希函數 轉化的數組索引我們稱之為 散列值（也稱哈希值），鍵值與哈希值轉換的過程我們稱之為 散列函數（即 哈希函數）。

哈希表的優點

  • 可以像數組一樣通過下標隨機訪問。
  • 彌補了數組只能通過整數索引訪問的缺陷。

哈希表的缺點

  • 每次存取數據之前要通過散列函數計算對應的散列值，消耗了更多內存。

裝載因子 是散列表性能的衡量標準之一。因為散列表實際上還是數組，所以能承載的數據是有限的，當哈希表存儲的數據超過數組索引的長度時則必然會出現散列衝突。

裝載因子的計算公式：

裝載因子 = 散列表元素個數 / 散列表長度。

通常，當裝載因子大於 0.75 時，我們需要擴容我們的散列表重新計算散列值。

應用場景

在 13 億人中，公安系統快速的查找某一身份證（通常為 18 位數字）信息 可以通過哈希表的來處理。首先根據身份證的前 6 位找到對應的省份區縣信息（可以是哈希表，可以是數組），再根據剩下 13 位信息製作哈希表，合理的選定計算散列值的數，可以以身份證後 8 位來生成（前 8 位出生日期容易重複易形成 散列衝突）散列值。因為身份證是整數形式的（X 代表 10），我們假設 1 個區縣的人數在 100 萬人以內則 100 萬對應的就是散列表的長度。散列函數我們可以用身份證後 8 位除以 100 0000 來生成對應的索引，而散列表中可以存放指向公民身份信息的指針。

而查找每一個身份證號所對應的信息時只要將輸入身份證號就可以通過下標在散列表中快速找到公民信息。

在這個案例中採用的就是常見的散列函數生成法 除留餘數法。常用於整數類型的鍵值生成特定的散列值。

參考代碼（劃區縣因代碼長度沒有寫出）

import java.util.*;

class Test {

public static void main(String[] args) {
HashTest people = new HashTest();

Scanner in = new Scanner(System.in);

for (int i = 0; i < 3; i++) // 輸入個人信息,3 個測試數據
 {
String identity = in.next();
String name = in.next();
int age = Integer.parseInt(in.next());
ChinesePerson person = new ChinesePerson(identity, name, age);
people.put(identity, person);// 以身份證為鍵，person 類為值
 }

System.out.print("輸入你想要查找的身份證號： ");
String id =in.next();
if (people.containsKey(id) == false)
System.out.println("你要查找的信息不存在");
else {
ChinesePerson result = people.get(id);
System.out.println(
"查找成功，" + "居民身份證為：" + result.getIdCard() + "，姓名為：" + result.getName() + "，年齡為：" + result.getAge());
}
}
}

class HashTest {
private ChinesePerson[] hashTable;
private int count;

public HashTest() // 初始化散列表
 {
hashTable = new ChinesePerson[10000];
count = 0;
}

private int HashCode(String identity) // 散列函數，除留餘數法
 {
int key = Integer.valueOf(identity.substring(9, 17)) / 10000;
return key;
}

public void put(String identity, ChinesePerson person) { // 增加鍵和值，測試案例不做溢出判斷
 int k = HashCode(identity);
hashTable[k] = person;
count++;
}

public boolean containsKey(String key) { // 判斷鍵值是否存在
 int index = HashCode(key);
if (index < 0 || index >= 10000 || count == 0 || hashTable[index] == null)
return false;
return true;
}

public ChinesePerson get(String key) { // 獲取鍵對應的值
 if (containsKey(key) == false)
throw new NullPointerException(); // 若不存在則拋出異常
 return hashTable[HashCode(key)];
}

public int size() { // 獲取散列表對應的元素個數
 return count;
}

}

class ChinesePerson { // 定義類存儲身份信息
 private String idCard;
private String name;
private int age;

public ChinesePerson(String identity, String name, int age) {
this.idCard = identity;
this.name = name;
this.age = age;
}

public String getIdCard() {
return this.idCard;
}

public void setIdCard(String identity) {
this.idCard = identity;
}

public String getName() {
return this.name;
}

public void setName(String name) {
this.name = name;
}

public int getAge() {
return this.age;
}

public void setAge(int age) {
this.age = age;
}
}

對於非整數類型的鍵值，通常將其轉換成大整數，再採用整數的除留餘數法。

Java 中的散列函數設計原則

  • 鍵值生成的散列值必須為非負整數

因為散列值實際為數組的索引所以必須為非負整數

  • 同一散列值對應相同的鍵值

  • 同一鍵值對應相同的散列值

散列表的衝突

表現：不同的鍵值生成了相同的散列值。

產生的原因：

  • 散列函數設計的不合理。
  • 散列表的容量有限

解決方法：

對散列表擴容。在裝載因子達到一定比例（通常設置為 0.75）時，對散列函數動態擴容，則對應的散列函數也應修改。

開放定址法。當出現散列衝突時，新的數據放入散列表中空閑塊。可以通過 線性探測（按順序向後遍歷空閑區）、二次探測、雙重散列 等方法實現。

拉鏈法。以鏈表的形式存儲衝突的散列表，散列表只記錄指向鏈表的指針，鏈表中只存放衝突但不重複的元素。

推薦閱讀：

相關文章