1、定義
哈希表(或散列表)是利用哈希函數(shù)(散列函數(shù))把數(shù)據(jù)的存儲位置與關(guān)鍵字碼值關(guān)聯(lián)后大脉，直接根據(jù)關(guān)鍵字訪問數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。
2镰矿、為什么需要哈希表？
鏈表、棧棍矛、隊列抛杨、數(shù)組够委、字符串怖现、樹等數(shù)據(jù)結(jié)構(gòu)根據(jù)數(shù)值訪問任意元素都需要至少O(logn)的時間復(fù)雜度茁帽，缺少一種能夠根據(jù)數(shù)值在O(1)的復(fù)雜度快速訪問數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)屈嗤。
3、特點
3.1饶号、優(yōu)點
根據(jù)關(guān)鍵字訪問元素的效率很高铁追；增刪查操作的效率很高茫船。
3.2、缺點
存在哈希沖突問題算谈，需要設(shè)計合理的哈希函數(shù)涩禀；存儲的數(shù)據(jù)是無序的，不適用于存儲需要排序的數(shù)據(jù)然眼；key不能重復(fù)，不適用于存儲重復(fù)性高的數(shù)據(jù)高每。
4、常用哈希函數(shù)
4.1鲸匿、直接定址法
設(shè)計關(guān)鍵字key到散列地址的線性函數(shù)。例如f(key)=a*key+b晒骇；
4.2、數(shù)字分析法
如果任意關(guān)鍵字key由多位數(shù)字組成洪囤，則從中提取若干分布均勻且差異明顯的數(shù)字組成散列地址徒坡。
4.3瘤缩、平方取中法
如果無法確定關(guān)鍵字key中分布均勻的數(shù)字，則先計算關(guān)鍵字key的平方值剥啤，再取平方值的中間幾位組成散列地址锦溪。
4.4不脯、折疊法
如果關(guān)鍵字key的位數(shù)很多刻诊，則先將關(guān)鍵字分割為幾個等長的部分防楷，再取其疊加和的值(去除進位)組成散列地址则涯。
4.5复局、除留余數(shù)法
先設(shè)置一個常數(shù)P粟判，再對關(guān)鍵字key進行取余計算，余數(shù)key mod p作為散列地址档礁。
4.6角钩、隨機數(shù)法
選擇某個隨機函數(shù)計算關(guān)鍵字key的隨機值作為散列地址呻澜。
5、解決哈希沖突的方法
5.1易迹、開放尋址法
設(shè)置增量的探測序列依次查找散列表中的散列地址宰衙，直到在序列中查找的值未哈希沖突睹欲，將該值作為新的散列地址。
5.1.1窘疮、線性探測法
增量序列形如1袋哼，2闸衫，3，...蔚出，m-1弟翘，m為散列表長骄酗。
5.1.2稀余、偽隨機數(shù)法
增量序列為偽隨機數(shù)序列趋翻。
5.2、鏈地址法
將哈希沖突的散列地址存儲在鏈表中。
6师骗、Java代碼描述哈希表
package com.zy.demo.util;
import java.util.HashMap;
import java.util.Map;
/**
* 哈希表
* @author zy
*/
public class HashTableUtil{
/**
* HashMap是數(shù)組+單向鏈表+紅黑樹的復(fù)合數(shù)據(jù)結(jié)構(gòu)。
*
* HashMap擴容(即rehash過程)需要重建一整套數(shù)組+單向鏈表+紅黑樹辟癌，非常影響迭代性能。
* 避免或減少rehash是維持HashMap高性能的關(guān)鍵因素愿待。
*
* HashMap使用直接地址法定義哈希函數(shù)靴患。
* 哈希函數(shù)f(key) = (capacity-1) & h(key)仍侥。
* capacity：數(shù)組容量鸳君。
* h(key)：計算key哈希碼的函數(shù)农渊。h(key) = key.hashCode() ^ (key.hashCode() >>> 16)
*
* 基礎(chǔ)數(shù)據(jù)通過哈希函數(shù)存儲在數(shù)組對應(yīng)位置或颊，每個數(shù)組的元素是一個單向鏈表砸紊。
* 當新添加的數(shù)據(jù)發(fā)生哈希沖突囱挑，則該數(shù)據(jù)會通過鏈地址法，存儲在鏈表的下個結(jié)點平挑。
*
* 當鏈表長度大于等于8時，單向鏈表結(jié)構(gòu)會轉(zhuǎn)化為紅黑樹結(jié)構(gòu)通熄；當紅黑樹按照擴容哈希算法(hash & capacity)計算的結(jié)點數(shù)小于等于6時唆涝，紅黑樹結(jié)構(gòu)會轉(zhuǎn)化為單向鏈表結(jié)構(gòu)唇辨。
*
* HashMap增刪查的時間復(fù)雜度：
* 無哈希沖突：O(1)
* 有哈希沖突：出現(xiàn)紅黑樹結(jié)構(gòu)是O(logn)；未出現(xiàn)紅黑樹結(jié)構(gòu)是O(1)
* 數(shù)組的時間復(fù)雜度：O(1)
* 鏈表的時間復(fù)雜度：O(1)赏枚，因為鏈表最大長度是8亡驰，是有限值饿幅，即O(1)隐解。
* 紅黑樹的時間復(fù)雜度：O(logn)，紅黑樹可以看作是平衡的二叉搜索樹诫睬。
*
*/
private Map<Object,Object> map;
public HashTableUtil(){
this.map = new HashMap<>();
}
/**
* 計算指定字符串被提交的次數(shù)
* 時間復(fù)雜度：哈希沖突少的情況下是O(1)；哈希沖突多的情況下是O(logn)。
* 空間復(fù)雜度：O(n) --新建HashMap對象
* @return 次數(shù)
*/
public int calcKeySubmit(String key){
//入?yún)⑿ｒ? if(key == null){
return -1;
}
//獲取指定字符串的提交次數(shù)
Integer count = (Integer) map.get(key);
//如果字符串第一次被提交蚓曼，次數(shù)為1；否則次數(shù)累加纫版。
count = count == null ? 1 : count+1;
//記錄當前字符串新的提交次數(shù)
map.put(key,count);
return count;
}
/**
* 給定一個已去重的正整數(shù)數(shù)組arr和一個目標值target，請在數(shù)組中找出相加結(jié)果等于目標值的兩個整數(shù)客情，并返回它們在數(shù)組中的下標。
* 假設(shè)答案只有一組且數(shù)據(jù)中的元素只能使用1次膀斋。
* 時間復(fù)雜度：哈希沖突少的情況下是O(1)；哈希沖突多的情況下是O(logn)仰担。
* 空間復(fù)雜度：O(n) --新建HashMap對象
*/
public static void findTwoSum(int[] arr,int target){
//校驗正整數(shù)數(shù)組
if(arr == null || arr.length < 2){
return;
}
//校驗?zāi)繕酥? if(target < 1){
return;
}
//新建哈希表
Map<Integer,Integer> map = new HashMap<>();
//數(shù)組長度
int arrLen = arr.length;
//遍歷數(shù)組
for(int i = 0 ; i < arrLen ; i++){
//計算另一個整數(shù)的期望值
int otherNum = target - arr[i];
//去重校驗
if(map.containsKey(arr[i])){
System.out.println("Illegal array:the array has duplicate element!");
return;
}
//如果當前期望值符合，則找到答案摔蓝。
if(map.containsKey(otherNum)){
System.out.println("答案：value1="+arr[i]+",index1="+i+";value2="+otherNum+",index2="+map.get(otherNum));
}
//用哈希表記錄數(shù)據(jù)元素與數(shù)組索引的關(guān)系
map.put(arr[i],i);
}
}
}
