Java深入了解數(shù)據(jù)結(jié)構(gòu)之哈希表篇
1，概念
順序結(jié)構(gòu)以及平衡樹(shù)中，元素關(guān)鍵碼與其存儲(chǔ)位置之間沒(méi)有對(duì)應(yīng)的關(guān)系，因此在查找一個(gè)元素時(shí)，必須要經(jīng)過(guò)關(guān)鍵 碼的多次比較。順序查找時(shí)間復(fù)雜度為O(N)，平衡樹(shù)中為樹(shù)的高度，即O( )，搜索的效率取決于搜索過(guò)程中 元素的比較次數(shù)。
理想的搜索方法：可以不經(jīng)過(guò)任何比較，一次直接從表中得到要搜索的元素。 如果構(gòu)造一種存儲(chǔ)結(jié)構(gòu)，通過(guò)某種函 數(shù)(hashFunc)使元素的存儲(chǔ)位置與它的關(guān)鍵碼之間能夠建立一一映射的關(guān)系，那么在查找時(shí)通過(guò)該函數(shù)可以很快找到該元素。
當(dāng)向該結(jié)構(gòu)中：
插入元素
根據(jù)待插入元素的關(guān)鍵碼，以此函數(shù)計(jì)算出該元素的存儲(chǔ)位置并按此位置進(jìn)行存放
搜索元素
對(duì)元素的關(guān)鍵碼進(jìn)行同樣的計(jì)算，把求得的函數(shù)值當(dāng)做元素的存儲(chǔ)位置，在結(jié)構(gòu)中按此位置取元素比較，若關(guān)鍵碼相等，則搜索成功
例如：數(shù)據(jù)集合{1，7，6，4，5，9}；
哈希函數(shù)設(shè)置為：hash(key) = key % capacity; capacity為存儲(chǔ)元素底層空間總的大小。
2，沖突-避免
首先，我們需要明確一點(diǎn)，由于我們哈希表底層數(shù)組的容量往往是小于實(shí)際要存儲(chǔ)的關(guān)鍵字的數(shù)量的，這就導(dǎo)致一 個(gè)問(wèn)題，沖突的發(fā)生是必然的，但我們能做的應(yīng)該是盡量的降低沖突率。
3，沖突-避免-哈希函數(shù)設(shè)計(jì)
常見(jiàn)哈希函數(shù)
直接定制法--(常用)
取關(guān)鍵字的某個(gè)線性函數(shù)為散列地址：Hash（Key）= A*Key + B 優(yōu)點(diǎn)：簡(jiǎn)單、均勻 缺點(diǎn)：需要事先知道關(guān) 鍵字的分布情況 使用場(chǎng)景：適合查找比較小且連續(xù)的情況
除留余數(shù)法--(常用)
設(shè)散列表中允許的地址數(shù)為m，取一個(gè)不大于m，但最接近或者等于m的質(zhì)數(shù)p作為除數(shù)，按照哈希函數(shù)： Hash(key) = key% p(p<=m),將關(guān)鍵碼轉(zhuǎn)換成哈希地址
平方取中法--(了解)
假設(shè)關(guān)鍵字為1234，對(duì)它平方就是1522756，抽取中間的3位227作為哈希地址； 再比如關(guān)鍵字為4321，對(duì) 它平方就是18671041，抽取中間的3位671(或710)作為哈希地址 平方取中法比較適合：不知道關(guān)鍵字的分 布，而位數(shù)又不是很大的情況
4，沖突-避免-負(fù)載因子調(diào)節(jié)
?負(fù)載因子和沖突率的關(guān)系粗略演示
所以當(dāng)沖突率達(dá)到一個(gè)無(wú)法忍受的程度時(shí)，我們需要通過(guò)降低負(fù)載因子來(lái)變相的降低沖突率。 、已知哈希表中已有的關(guān)鍵字個(gè)數(shù)是不可變的，那我們能調(diào)整的就只有哈希表中的數(shù)組的大小。
5，沖突-解決-閉散列
閉散列：也叫開(kāi)放定址法，當(dāng)發(fā)生哈希沖突時(shí)，如果哈希表未被裝滿，說(shuō)明在哈希表中必然還有空位置，那么可以 把key存放到?jīng)_突位置中的“下一個(gè)” 空位置中去。
①線性探測(cè)
比如上面的場(chǎng)景，現(xiàn)在需要插入元素44，先通過(guò)哈希函數(shù)計(jì)算哈希地址，下標(biāo)為4，因此44理論上應(yīng)該插在該 位置，但是該位置已經(jīng)放了值為4的元素，即發(fā)生哈希沖突。 線性探測(cè)：從發(fā)生沖突的位置開(kāi)始，依次向后探測(cè)，直到尋找到下一個(gè)空位置為止。
插入
通過(guò)哈希函數(shù)獲取待插入元素在哈希表中的位置 如果該位置中沒(méi)有元素則直接插入新元素，如果該位置中有元素發(fā)生哈希沖突，使用線性探測(cè)找到 下一個(gè)空位置，插入新元素
采用閉散列處理哈希沖突時(shí)，不能隨便物理刪除哈希表中已有的元素，若直接刪除元素會(huì)影響其他 元素的搜索。比如刪除元素4，如果直接刪除掉，44查找起來(lái)可能會(huì)受影響。因此線性探測(cè)采用標(biāo) 記的偽刪除法來(lái)刪除一個(gè)元素。
②二次探測(cè)
線性探測(cè)的缺陷是產(chǎn)生沖突的數(shù)據(jù)堆積在一塊，這與其找下一個(gè)空位置有關(guān)系，因?yàn)檎铱瘴恢玫姆绞骄褪前?著往后逐個(gè)去找，因此二次探測(cè)為了避免該問(wèn)題，找下一個(gè)空位置的方法為： = ( + )% m, 或者： = ( - )% m。其中：i = 1,2,3…， 是通過(guò)散列函數(shù)Hash(x)對(duì)元素的關(guān)鍵碼 key 進(jìn)行計(jì)算得到的位置， m是表的大小。 對(duì)于2.1中如果要插入44，產(chǎn)生沖突，使用解決后的情況為：
研究表明：當(dāng)表的長(zhǎng)度為質(zhì)數(shù)且表裝載因子a不超過(guò)0.5時(shí)，新的表項(xiàng)一定能夠插入，而且任何一個(gè)位置都不 會(huì)被探查兩次。因此只要表中有一半的空位置，就不會(huì)存在表滿的問(wèn)題。在搜索時(shí)可以不考慮表裝滿的情 況，但在插入時(shí)必須確保表的裝載因子a不超過(guò)0.5，如果超出必須考慮增容。
6，沖突-解決-開(kāi)散列/哈希桶
開(kāi)散列法又叫鏈地址法(開(kāi)鏈法)，首先對(duì)關(guān)鍵碼集合用散列函數(shù)計(jì)算散列地址，具有相同地址的關(guān)鍵碼歸于同一子 集合，每一個(gè)子集合稱為一個(gè)桶，各個(gè)桶中的元素通過(guò)一個(gè)單鏈表鏈接起來(lái)，各鏈表的頭結(jié)點(diǎn)存儲(chǔ)在哈希表中。
static class Node {
public int key;
public int val;
public Node next;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
private Node[] array;
public int usedSize;
public HashBucket() {
this.array = new Node[10];
this.usedSize = 0;
}
public void put(int key,int val){
int index = key % this.array.length;
Node cur = array[index];
while (cur != null){
if(cur.val == key){
cur.val = val;
return;
}
cur = cur.next;
}
//頭插法
Node node = new Node(key,val);
node.next = array[index];
array[index] = node;
this.usedSize++;
if(loadFactor() >= 0.75){
resize();
}
}
public int get(int key) {
//以什么方式存儲(chǔ)的 那就以什么方式取
int index = key % this.array.length;
Node cur = array[index];
while (cur != null) {
if(cur.key == key) {
return cur.val;
}
cur = cur.next;
}
return -1;//
}
public void resize(){
Node[] newArray = new Node[2*this.array.length];
for (int i = 0; i < this.array.length; i++){
Node cur = array[i];
Node curNext = null;
while (cur != null){
curNext = cur.next;
int index = cur.key % newArray.length;
cur.next = newArray[i];
newArray[i] = cur;
cur = curNext.next;
cur = curNext;
}
}
this.array = newArray;
}
7，完整代碼
class HashBucket {
static class Node {
public int key;
public int val;
public Node next;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
private Node[] array;
public int usedSize;
public HashBucket() {
this.array = new Node[10];
this.usedSize = 0;
}
public void put(int key,int val) {
//1、確定下標(biāo)
int index = key % this.array.length;
//2、遍歷這個(gè)下標(biāo)的鏈表
Node cur = array[index];
while (cur != null) {
//更新val
if(cur.key == key) {
cur.val = val;
return;
}
cur = cur.next;
}
//3、cur == null 當(dāng)前數(shù)組下標(biāo)的 鏈表 沒(méi)要key
Node node = new Node(key,val);
node.next = array[index];
array[index] = node;
this.usedSize++;
//4、判斷 當(dāng)前 有沒(méi)有超過(guò)負(fù)載因子
if(loadFactor() >= 0.75) {
//擴(kuò)容
resize();
}
}
public int get(int key) {
//以什么方式存儲(chǔ)的 那就以什么方式取
int index = key % this.array.length;
Node cur = array[index];
while (cur != null) {
if(cur.key == key) {
return cur.val;
}
cur = cur.next;
}
return -1;//
}
public double loadFactor() {
return this.usedSize*1.0 / this.array.length;
}
public void resize(){
Node[] newArray = new Node[2*this.array.length];
for (int i = 0; i < this.array.length; i++){
Node cur = array[i];
Node curNext = null;
while (cur != null){
curNext = cur.next;
int index = cur.key % newArray.length;
cur.next = newArray[i];
newArray[i] = cur;
cur = curNext.next;
cur = curNext;
}
}
this.array = newArray;
}
}
到此這篇關(guān)于Java深入了解數(shù)據(jù)結(jié)構(gòu)之哈希表篇的文章就介紹到這了,更多相關(guān)Java 哈希表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
如何讀取properties或yml文件數(shù)據(jù)并匹配
這篇文章主要介紹了如何讀取properties或yml文件數(shù)據(jù)并匹配方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-12-12
詳解eclipse項(xiàng)目中的.classpath文件原理
這篇文章介紹了eclipse項(xiàng)目中的.classpath文件的原理，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-12-12
Java 關(guān)于String字符串原理上的問(wèn)題
字符串廣泛應(yīng)用 在 Java 編程中，在 Java 中字符串屬于對(duì)象，Java 提供了 String 類來(lái)創(chuàng)建和操作字符串，讓我們一起來(lái)了解它2022-04-04
java實(shí)現(xiàn)KFC點(diǎn)餐小程序
這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)KFC點(diǎn)餐系統(tǒng)小程序，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-01-01
spring的Cache注解和redis的區(qū)別說(shuō)明
這篇文章主要介紹了spring的Cache注解和redis的區(qū)別說(shuō)明，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-12-12
ShardingSphere如何進(jìn)行sql重寫(xiě)示例詳解
這篇文章主要為大家介紹了ShardingSphere如何進(jìn)行sql重寫(xiě)示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-09-09
深入解析Java編程中的StringBuffer與StringBuider
這篇文章主要介紹了Java編程中的StringBuffer與StringBuider,是Java入門(mén)學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-09-09
springmvc接收json串,轉(zhuǎn)換為實(shí)體類List方法
今天小編就為大家分享一篇springmvc接收json串,轉(zhuǎn)換為實(shí)體類List方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2018-08-08
HotSpot的Java對(duì)象模型之Oop-Klass模型詳解
這篇文章主要介紹了HotSpot的Java對(duì)象模型之Oop-Klass模型詳解,在JVM層面,不僅Java類是對(duì)象,Java 方法也是對(duì)象, 字節(jié)碼常量池也是對(duì)象,一切皆是對(duì)象,JVM使用不同的oop-klass模型來(lái)表示各種不同的對(duì)象,需要的朋友可以參考下2023-08-08
本篇文章是對(duì)jdbc處理Clob的使用進(jìn)行了分析介紹，需要的朋友參考下2013-05-05