哈希查找（Hash Search）

概念:

哈希法：又稱散列法、雜湊法或關鍵字地址計算法等，相應的表稱為哈希表。

哈希表的裝填因子α： α = 哈希表中元素個數 / 哈希表的長度
α可描述哈希表的裝滿程度。顯然，α越小，發(fā)生沖突的可能性越小，而α越大，發(fā)生沖突的可能性也越大。

基本思想:

首先在元素的關鍵字k和元素的存儲位置p之間建立一個對應關系H，使得p=H(k)，H稱為哈希函數。

除留余數法:

假設哈希表長為m， p為小于等于m的最大素數， 則哈希函數為 H（k）=k%p，其中%為模p取余運算。

處理沖突的方法:

開放定址法:（這種方法也稱再散列法）

這種方法有一個通用的再散列函數形式：
Hi=（H（key）+di）%m, i=1,2,…, n
其中H（key）為哈希函數，m 為表長，di稱為增量序列。增量序列的取值方式不同，相應的再散列方式也不同。主要有以下三種：

1.線性探測再散列： di=1，2，3，…，m-1 2.二次探測再散列：di=12,-12,22,-22,…,k2,-k2 (k≤m/2) 3.偽隨機探測再散列：di=偽隨機數序列。

再哈希法:

這種方法是同時構造多個不同的哈希函數：
Hi=RH1（key）， i=1，2， …， k
當哈希地址Hi=RH1（key）發(fā)生沖突時，再計算Hi=RH2（key）……直到沖突不再產生。這種方法不易產生聚集，但增加了計算時間。

鏈地址法:

這種方法的基本思想是將所有哈希地址為i的元素構成一個稱為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的第i個單元中， 因而查找、插入和刪除主要在同義詞鏈中進行。 鏈地址法適用于經常進行插入和刪除的情況。

哈希查找概念摘自博客：https://blog.csdn.net/De_lovely_crane/article/details/93882963

了解完哈希查找原理，我們來實踐一下:

來源：力扣（leetCode）第1題：兩數之和
給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出 和為目標值 的那 兩個 整數，并返回它們的數組下標。
你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素在答案里不能重復出現。
你可以按任意順序返回答案。
示例：

示例 1： 輸入：nums = [2,7,11,15], target = 9 輸出：[0,1] 解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1] 。示例 2： 輸入：nums = [3,2,4], target = 6 輸出：[1,2]示例 3： 輸入：nums = [3,3], target = 6 輸出：[0,1]

記錄一下看到該題的菜雞寫法：

private static int[] twoSum(int[] nums, int target) {//1、定義一個keys數組，存放有效數據的下標//2、定義一個map，將下標當作key，值當作value存放List<Integer> keys = new ArrayList<>();Map<Integer, Integer> numMap = new HashMap<>(nums.length);for (int i = 0; i < nums.length; i++) {numMap.put(i, nums[i]);keys.add(i);}int[] result = new int[]{0, 1};//3、雙重for循環(huán)每一個數與另外數相加是否等于該目標值，若相等則結束本次循環(huán)for (int i = 0; i < keys.size() - 1; i++) {for (int j = i; j < keys.size() - 1; j++) {if (numMap.get(keys.get(i)) + numMap.get(keys.get(j + 1)) == target) {result[0] = keys.get(i);result[1] = keys.get(j + 1);return result;}}}throw new RuntimeException("沒有查找到正確答案！");}

雖然通過了leetCode的測試用例可是不管是從時間還是空間上效率都比較低。。。

后續(xù)看到該題的標簽“哈希表”，才想到使用哈希查找來解題：

leetCode官方解題思路：
使用哈希表，可以將尋找 target - x 的時間復雜度降低到從 O(N) 降低到 O(1)。
這樣我們創(chuàng)建一個哈希表，對于每一個 x，我們首先查詢哈希表中是否存在 target - x，然后將 x 插入到哈希表中，即可保證不會讓 x 和自己匹配。

時間復雜度：O(N)，其中 N 是數組中的元素數量。對于每一個元素 x，我們可以 O(1) 地尋找 target - x。
空間復雜度：O(N)，其中 N 是數組中的元素數量。主要為哈希表的開銷。

private static int[] twoSumHash(int[] nums, int target) {//定義hash表存放要匹配的數組Map<Integer, Integer> hash = new HashMap<>(nums.length);for (int i = 0; i < nums.length; i++) {//該判斷條件參考官方題解可優(yōu)化使用containsKey()方法來判斷if (hash.get(target - nums[i]) != null) {//判斷hash table 中是否存在 target - nums[i] 的值 存在則直接返回兩數下標return new int[]{hash.get(target - nums[i]), i};}//若不存在則將 當前數作為 key 下標作為 value 存入 hash table 中//重復存入相同 key 會覆蓋原來的 value ，此處不需考慮重復存入問題hash.put(nums[i], i);}throw new RuntimeException("沒有查找到正確答案！");}

最終通過測試用例執(zhí)行用時：0 ms, 在所有 Java 提交中擊敗了100.00%的用戶；內存消耗：38.7 MB, 在所有 Java 提交中擊敗了35.33%的用戶，解題思路上被完爆了…

總結

以上是生活随笔為你收集整理的JAVA算法：哈希查找的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。