散清單（Hash table，也叫哈希表），是根據鍵（Key）而直接通路在記憶體存儲位置的資料結構。也就是說，它通過計算一個關于鍵值的函數，将所需查詢的資料映射到表中一個位置來通路記錄，這加快了查找速度。這個映射函數稱做散列函數，存放記錄的數組稱做散清單。
關于散清單更加詳細可以看這裡散列及散列函數
下面我們通過幾個leetcode上的題目加深對散列的了解和使用
兩數之和
給定一個整數數組 nums 和一個目标值 target，請你在該數組中找出和為目标值的那 兩個 整數，并傳回他們的數組下标。
你可以假設每種輸入隻會對應一個答案。但是，你不能重複利用這個數組中同樣的元素
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
是以傳回 [0, 1] 暴力解法
暴力雙循環找出符合target - nums[i] = nums[j]條件的 i和j
/**
* 暴力解
* 【O(n^2)】
* @param nums
* @param target
* @return
*/
public int[] twoSum1(int[] nums, int target) {
for(int i = 0; i < nums.length;i++){
for(int j = i+1; j < nums.length;j++){
if(target-nums[j]==nums[i]){
return new int[] { i, j };
}
}
}
throw new IllegalArgumentException("不存在這兩個數");
} 基于散列解法
因為他要求傳回的是索引，且相加兩數不是同一個數，是以可以使用一個hashMap将nums中每一個數的數值和對應的索引存到散清單中，數值作為key，索引作為value，周遊哈希表找出符合條件且索引不同的數即可
/**
* 一次哈希表
* O(n)
* @param nums
* @param target
* @return
*/
public int[] twoSum3(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<>();
for (int i = 0;i<nums.length;i++){
int k = target - nums[i];
if(map.containsKey(k) && map.get(k) != i){
return new int[]{map.get(k) , i };
}
map.put(nums[i],i);
}
throw new IllegalArgumentException("不存在這兩個數");
} 去重問題
給定一個整數數組，判斷是否存在重複元素。
如果任何值在數組中出現至少兩次，函數傳回 true。如果數組中每個元素都不相同，則傳回 false。
輸入: [1,2,3,1]
輸出: true
輸入: [1,2,3,4]
輸出: false 基于hashSet
關于去重問題其實有更友善的做法就是使用set，set是不包含重複元素的嘛，比較使用set前後的長度差，不相等則有重複值
/**
* 基于set
* 去重後判斷前後長度是否一緻
* @param nums
* @return
*/
public boolean containsDuplicate2(int[] nums) {
Set<Integer> set = new HashSet<>();
int len = nums.length;
for(int i : nums){
set.add(i);
}
return set.size() != len;
} 基于hashMap
如果我們使用的散清單，在存放元素時出現同一個元素映射到散清單的一個位置，就是屬于散列沖突問題，那麼當出現沖突時，就是出現重複元素的時候
/**
* 基于hashmap
* @param nums
* @return
*/
public boolean containsDuplicate(int[] nums) {
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0;i<nums.length;i++){
if(map.containsKey(nums[i])){
return true;
}
map.put(nums[i],i);
}
return false;
} 滑動視窗問題
給定一個整數數組和一個整數 k，判斷數組中是否存在兩個不同的索引 i 和 j，使得 nums [i] = nums [j]，
并且 i 和 j 的差的絕對值最大為 k。
輸入: nums = [1,2,3,1], k = 3
輸出: true
輸入: nums = [1,2,3,1,2,3], k = 2
輸出: false 其實這是一類跟去重問題很相似的問題，但是他要求的是在視窗内去重，或者在視窗内找出符合條件的元素
暴力解
/**
* 暴力解，維護一個長度是k的滑動視窗
* @param nums
* @param k
* @return
*/
public boolean containsNearbyDuplicate(int[] nums, int k) {
for(int i = 0;i < nums.length;i++){
//相當于 j --- 相隔k --- i
for(int j = Math.max(i - k,0);j < i;j++){
if(nums[j] == nums[i]){
return true;
}
}
}
return false;
} 基于hashMap
/**
* hashmap
*/
public boolean containsNearbyDuplicate3(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0;i < nums.length;i++){
// i 一定大于 map.get(nums[i])
if(map.containsKey(nums[i]) && i - map.get(nums[i]) <= k){
return true;
}
map.put(nums[i],i);
}
return false;
} 兩數組交集問題
基于set
給定兩個數組，編寫一個函數來計算它們的交集。
示例 1:
輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2]
示例 2:
輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [9,4] 輸出結果中的每個元素一定是唯一的。
我們可以不考慮輸出結果的順序。
/**
* 暴力解法（很低效）
* @param nums1
* @param nums2
* @return
*/
public int[] intersection(int[] nums1, int[] nums2) {
// 1.去重
Set<Integer> set1 = new HashSet<>();
Set<Integer> set2 = new HashSet<>();
for(int i : nums1){
set1.add(i);
}
for(int i : nums2){
set2.add(i);
}
ArrayList<Integer> list = new ArrayList<>();
// 2.探尋
for(int i : set1){
for(int j : set2){
if(i == j){
list.add(i);
}
}
}
int[] result = new int[list.size()];
for(int i = 0;i<list.size();i++){
result[i] = list.get(i);
}
return result;
} 使用内置函數
/**
* 使用内置函數
* @param nums1
* @param nums2
* @return
*/
public int[] intersection1(int[] nums1, int[] nums2) {
// 1.去重
Set<Integer> set1 = new HashSet<>();
Set<Integer> set2 = new HashSet<>();
for(int i : nums1){
set1.add(i);
}
for(int i : nums2){
set2.add(i);
}
ArrayList<Integer> list = new ArrayList<>();
//取交集
set1.retainAll(set2);
for(int i : set1){
list.add(i);
}
int[] result = new int[list.size()];
for(int i = 0;i<list.size();i++){
result[i] = list.get(i);
}
return result;
} 基于map
給定兩個數組，編寫一個函數來計算它們的交集。
示例 1:
輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2,2]
示例 2:
輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [4,9] 說明：
輸出結果中每個元素出現的次數，應與元素在兩個數組中出現的次數一緻。
/**
* 使用hashMap
* @param nums1
* @param nums2
* @return
*/
public int[] intersect(int[] nums1, int[] nums2) {
//統計重複次數
int k = 0;
Map<Integer,Integer> map = new HashMap<>();
//将nums數值和出現的次數存入map中
for(int i = 0;i<nums1.length;i++){
if(map.containsKey(nums1[i])){
map.put(nums1[i],map.get(nums1[i]) + 1);
}else{
map.put(nums1[i],1);
}
}
//找出重複數，存到list，并減少相應的重複次數
List<Integer> list = new LinkedList<>();
for(int j = 0;j<nums2.length;j++){
if(map.containsKey(nums2[j]) && map.get(nums2[j]) > 0){
list.add(nums2[j]);
map.put(nums2[j],map.get(nums2[j])-1);
}
}
//最後，将list中的值放入數組中
int count = list.size();
int[] aux = new int[count];
for(int i = 0; i < count; i++){
aux[i] = ((LinkedList<Integer>) list).poll();
}
return aux;
} ![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)