java數據結構之哈希表及示例（數據結構哈希查找例題）

本文目錄一覽：

• 1、java中的Hashtable怎麼用，請詳細舉例子說明，拜託了 謝謝
• 2、數據結構與演算法-基礎（十八）哈希表
• 3、數據結構（java版）哈希表的設計

java中的Hashtable怎麼用，請詳細舉例子說明，拜託了 謝謝

就是哈希表，下面這個示例創建了一個數字的哈希表。它將數字的名稱用作鍵： HashtableString, Integer numbers = new HashtableString, Integer(); 　

　numbers.put(“one”, 1); 　

　numbers.put(“two”, 2); 　

　numbers.put(“three”, 3);

要獲取一個數字，可以使用以下代碼：

Integer n = numbers.get(“two”); 　

　if (n != null) { 　

　System.out.println(“two = ” + n); 　

　}

數據結構與演算法-基礎（十八）哈希表

上期使用 紅黑樹 實現映射結構，這樣的結構滿足 Key 必須具備可比性，元素有順序地分布 這兩個特點。在實際的應用場景中，存在結構中的 元素是不需要有序的，並且 Key 也不具備可比較性 ，哈希表完全滿足這樣的應用場景。

比如設計一個公司的通訊錄，存放所有員工的通訊信息，就可以拿手機號作為 index，員工的名稱、職位等作為 value。用哈希表的方式可以將添加、刪除和搜索的時間複雜度控制在 O(1)。

這時創建一個數組，手機號作為 index，然後存放 value。這樣能將複雜度控制在 O(1)，但是這種 空間換時間 的方式也造成了一些其他問題，比如空間複雜度大（需要更多的空間），空間使用率極其低，非常浪費內存空間。

哈希表 就是空間換時間的處理方式，但是做了優化，在空間和時間兩個緯度中達到適當的平衡。

哈希表也叫做散列表，整體結構就是一個數組 ，哈希表會將 key 用哈希函數處理之後返回 hash（哈希值），hash 就是哈希表中的 index這樣的處理方式就可以滿足搜索時間是 O(1)，這樣的處理方式就可以滿足搜索時間是 O(1)。因為哈希表中的 key 可能不具備可比較性，所以要做哈希處理。

在執行哈希函數之後返回的 hash，可能會出現相同的情況 ，這樣的情況就是 哈希衝突 。解決哈希衝突常見的方法有這三種：

JDK1.8 解決哈希衝突的方式就是使用鏈地址法，其中的鏈表就是通過鏈表+紅黑樹的組合來實現 。比如當哈希表中的容量大於等於 64，並且單向鏈表的節點數大於 8 時，轉換為紅黑樹，不滿足這個條件時就使用單向鏈表。

哈希函數 是生成哈希值的實現方法，哈希函數的實現步驟大致分為兩步：

hash_code 是生成哈希值的函數，也可以直接用 JAVA 中的標準函數 hashCode() 。

這裡可以用 位運算替換 % 運算，來提高效率。因為 位運算是二進位運算，所以在設計數組的時候，需要將數組的長度設計為 2 的冪次方。

一個良好的哈希函數，可以讓生成的哈希值分布更加均勻，減少哈希衝突的次數，最終可以提升哈希表的性能。

Key 的常見類型可能有證書、浮點數、字元串或者自定義對象，不同的類型生成哈希值的方式也會不一樣，但是目標是一致的，就是 盡量讓每個 Key 的哈希值唯一，盡量讓 Key 中的所有信息參與運算 。

比如在 Java 中， Long 的哈希值實現如下代碼：

這裡的 和 ^ 就是將高 32 bit 和低 32 bit 混合計算出 32 bit 的哈希值。

在計算字元串的哈希值時，可以將字元串拆解成若干個字元，比如 jack，將它拆解成 j、a、c、k（字元的本質就是一個整數，所以 jack 的哈希值可以表示為 j * n3 + a * n2 + c * n1 + k * n0，表達式也可以寫成 [(j * n + a) * n + c] * n + k，代碼實現如下：

看上面代碼時，可以發現，表達式中的 n 使用的是 31 這個數字，那麼為什麼用 31 呢？

因為 31 不僅符合 22 – 1 , 而且它還是個奇素數（既是技術，又是素數，還是質數），素數和其他數相乘的結果比其他方式更容易產生唯一性，減少哈希衝突。

JDK 中，乘數 n 也是用 31，31 也是經過觀測分布結果後的選擇，關於 31 的變體可以有以下幾種：

31 * i = (25 – 1) * i = i * 25 – i = (i 5) – i

數據結構（java版）哈希表的設計

1.什麼是哈希表？

哈希表是一種數據結構，它提供了快速的插入操作和查找操作。其基於數組來實現。

2.哈希化

1)直接將關鍵字作為索引。

2)將單詞轉換成索引。

1將字母轉換成ASCII碼，然後進行相加

2冪的連乘

3壓縮可選值

3.壓縮後仍然可能出現的問題。

衝突：不能保證每個單詞都映射到數組的空白單元。

解決辦法：

1開放地址法

2鏈地址法

/**

* 員工信息類

* @author Administrator

*

*/

public class Info {

private String key;

private String name;

public Info(String key, String name) {

this.key = key;

this.name = name;

}

public String getKey() {

return key;

}

public void setKey(String key) {

this.key = key;

}

public String getName() {

return name;

}

public void setName(String name) {

this.name = name;

}

}

import java.math.BigInteger;

public class HashTable {

private Info[] arr;

/**

* 默認的構造方法

*/

public HashTable() {

arr = new Info[100];

}

/**

* 指定數組初始化大小

*/

public HashTable(int maxSize) {

arr = new Info[maxSize];

}

/**

* 插入數據

*/

public void insert(Info info) {

arr[hashCode(info.getKey())] = info;

}

/**

* 查找數據

*/

public Info find(String key) {

return arr[hashCode(key)];

}

public int hashCode(String key) {

// int hashVal = 0;

// for(int i = key.length() – 1; i = 0; i–) {

// int letter = key.charAt(i) – 96;

// hashVal += letter;

// }

// return hashVal;

BigInteger hashVal = new BigInteger(“0”);

BigInteger pow27 = new BigInteger(“1”);

for(int i = key.length() – 1; i = 0; i–) {

int letter = key.charAt(i) – 96;

BigInteger letterB = new BigInteger(String.valueOf(letter));

hashVal = hashVal.add(letterB.multiply(pow27));

pow27 = pow27.multiply(new BigInteger(String.valueOf(27)));

}

return hashVal.mod(new BigInteger(String.valueOf(arr.length))).intValue();

}

}

public class TestHashTable {

public static void main(String[] args) {

HashTable ht = new HashTable();

ht.insert(new Info(“a”,”張三”));

ht.insert(new Info(“ct”,”李四”));

ht.insert(new Info(“wangwu”,”王五”));

System.out.println(ht.find(“a”).getName());

System.out.println(ht.find(“ct”).getName());

}

}