基于拉鏈?zhǔn)胶途€性探測式散列表實現(xiàn)Map的方法教程

本篇內(nèi)容介紹了“基于拉鏈?zhǔn)胶途€性探測式散列表實現(xiàn)Map的方法教程”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

散列函數(shù)

實現(xiàn)散列表的第一步就是需要考慮如何把一個鍵轉(zhuǎn)換為數(shù)組的下標(biāo)，這時候就需要使用到散列函數(shù)，先把鍵值轉(zhuǎn)換成一個整數(shù)然后在使用除留余數(shù)法計算出數(shù)組的下標(biāo)。每種類型的鍵我們都需要一個不同的散列函數(shù)。

在java中對于常用的數(shù)據(jù)類型已經(jīng)實現(xiàn)了hashCode，我們只需要根據(jù)hashCode的值使用除留余數(shù)法即可轉(zhuǎn)換成數(shù)組的下標(biāo)

java中的約定：如果兩個對象的equals相等，那么hashCode一定相同;如果hashCode相同，equals不一定相同。對于自定義類型的鍵我們通常需要自定義實現(xiàn)hashCode和equals;默認(rèn)的hashCode返回的是對象的內(nèi)存地址，這種散列值不會太好。

下面我來看看Java中常用類型的hashCode計算方式

Integer

由于hashCode需要返回的值就是一個int值，所以Integer的hashCode實現(xiàn)很簡單，直接返回當(dāng)前的value值

@Override public int hashCode() {     return Integer.hashCode(value); } public static int hashCode(int value) {     return value; }

Long

Java中Long類型的hashCode計算是先把值無符號右移32位，之后再與值相異或，保證每一位都用用到，最后強制轉(zhuǎn)換成int值

@Override public int hashCode() {     return Long.hashCode(value); }  public static int hashCode(long value) {     return (int)(value ^ (value >>> 32)); }

Double、Float

浮點類型的鍵java中hashCode的實現(xiàn)是將鍵表示為二進制

public static int hashCode(float value) {     return floatToIntBits(value); } public static int floatToIntBits(float value) {     int result = floatToRawIntBits(value);     // Check for NaN based on values of bit fields, maximum     // exponent and nonzero significand.     if ( ((result & FloatConsts.EXP_BIT_MASK) ==           FloatConsts.EXP_BIT_MASK) &&          (result & FloatConsts.SIGNIF_BIT_MASK) != 0)         result = 0x7fc00000;     return result; }

String

java中每個char都可以表示成一個int值，所以字符串轉(zhuǎn)換成一個int值

public int hashCode() {     int h = hash;     if (h == 0 && value.length > 0) {         char val[] = value;          for (int i = 0; i < value.length; i++) {             h = 31 * h + val[i];         }         hash = h;     }     return h; }

軟緩存

如果計算一個散列值比較耗時，那么我可以這個計算好的值緩存起來，即使用一個變量把這個值保存起來，在下一次調(diào)用時直接返回。Java中的String就是采用的這種方式。

拉鏈?zhǔn)降纳⒘斜?/h4>

散列函數(shù)能夠?qū)㈡I值轉(zhuǎn)換成數(shù)組的下標(biāo);第二步就是需要處理碰撞沖突，也就是需要處理遇到了兩個散列值相同的對象應(yīng)該如何存儲。有一種方式是數(shù)組中的每一個元素都指向一個鏈表用來存放散列值相同的對象，這種方式被稱為拉鏈法

拉鏈法可以使用原始的鏈表保存鍵，也可以采用我們之前實現(xiàn)的紅黑樹來表示，在java8中采用的這兩種方式的混合，在節(jié)點數(shù)超過了8之后變?yōu)榧t黑樹。

這里我們就采用簡單的鏈表來實現(xiàn)拉鏈?zhǔn)缴⒘斜?，?shù)據(jù)結(jié)構(gòu)使用在前幾篇中已經(jīng)實現(xiàn)的LinkedMap，可以參考前面的文章《基于數(shù)組或鏈表實現(xiàn)Map》。

public class SeparateChainingHashMap<K, V> implements Map<K, V> {      private int size;     private LinkedMap<K, V>[] table;      public SeparateChainingHashMap(int capacity) {         this.table = (LinkedMap<K, V>[]) new LinkedMap[capacity];         for (int i = 0; i < capacity; i++) {             this.table[i] = new LinkedMap<>();         }     }      @Override     public void put(K key, V value) {         this.table[hash(key)].put(key, value);         size++;     }      private int hash(K key) {         return (key.hashCode() & 0x7fffffff) % table.length;     }      @Override     public V get(K key) {         return this.table[hash(key)].get(key);     }      @Override     public void delete(K key) {         this.table[hash(key)].delete(key);         size--;     }      @Override     public int size() {         return size;     }  }

這的hash函數(shù)使用key的hashCode與上0x7fffffff得到一個非負(fù)的整數(shù)，然后再使用除留余數(shù)法計算出數(shù)組的下標(biāo)。其中0x7FFFFFFF  的二進制表示就是除了首位是 0，其余都是1，也就是說，這是最大的整型數(shù) int(因為第一位是符號位，0  表示他是正數(shù)),可以使用Integer.MAX_VALUE代替

散列表的主要目的在于把鍵值均勻的分布到數(shù)組中，所以散列表是無序的，如果你需要的Map需要支持取出最大值，最小值，那么散列表都不適合。

這里我們實現(xiàn)的拉鏈?zhǔn)缴⒘斜淼臄?shù)組大小是固定的，但是通常在隨著數(shù)據(jù)量的增大，越短的數(shù)組出現(xiàn)碰撞的幾率會增大，所以需要數(shù)組支持動態(tài)的擴容，擴容之后需要把原來的值重新插入到擴容之后的數(shù)組中。數(shù)組的擴容可以參考之前的文章《老哥是時候來復(fù)習(xí)下數(shù)據(jù)結(jié)構(gòu)與算法了》

線性探測式散列表

實現(xiàn)散列表的另一種方式就是用大小為M來保存N個鍵值，其中M>N;解決碰撞沖突就需要利用數(shù)組中的空位;這種方式中最簡單的實現(xiàn)就是線性探測。

線性探測的主要思路：當(dāng)插入一個鍵，發(fā)生碰撞沖突之后直接把索引加一來檢查下一個位置，這時候會出現(xiàn)三種情況:

下一個位置和待插入的鍵相等，那么值就修改值

下一個位置和待插入的鍵不相等，那么索引加一繼續(xù)查找

如果下一個位置還是一個空位，那么直接把待插入對象放入到這個空位

初始化

線性探測式散列表使用兩個數(shù)組來存放keys和values，capacity表示初始化數(shù)組的大小

private int size; private int capacity; private K[] keys; private V[] values;  public LinearProbingHashMap(int capacity) {     this.capacity = capacity;     this.keys = (K[]) new Object[capacity];     this.values = (V[]) new Object[capacity]; }

插入

當(dāng)插入鍵的位置超過了數(shù)組的大小，就需要回到數(shù)組的開始位置繼續(xù)查找，直到找到一個位置為null的才結(jié)束;index = (index + 1) %  capacity

當(dāng)數(shù)組已存放的容量超過了數(shù)組總?cè)萘康囊话耄托枰獢U容到原來的2倍

@Override public void put(K key, V value) {     if (Objects.isNull(key)) {         throw new IllegalArgumentException("Key can not null");     }     if (this.size > this.capacity / 2) {         resize(2 * this.capacity);     }     int index;     for (index = hash(key); this.keys[index] != null; index = (index + 1) % capacity) {         if (this.keys[index].equals(key)) {             this.values[index] = value;             return;         }     }     this.keys[index] = key;     this.values[index] = value;     size++; }

動態(tài)調(diào)整數(shù)組的大小

我們可以參考之前在文章《老哥是時候來復(fù)習(xí)下數(shù)據(jù)結(jié)構(gòu)與算法了》中實現(xiàn)的動態(tài)調(diào)整數(shù)據(jù)的大小;在線性探測中需要把原來的數(shù)據(jù)重新插入到擴容之后的數(shù)據(jù)，因為數(shù)組的大小變了需要重新計算索引的位置。

private void resize(int cap) {     LinearProbingHashMap<K, V> linearProbingHashMap = new LinearProbingHashMap<>(cap);     for (int i = 0; i < capacity; i++) {         linearProbingHashMap.put(keys[i], values[i]);     }     this.keys = linearProbingHashMap.keys;     this.values = linearProbingHashMap.values;     this.capacity = linearProbingHashMap.capacity; }

查詢

線性探測散列表中實現(xiàn)查詢的思路：根據(jù)待查詢key的hash函數(shù)計算出索引的位置，然后開始判斷當(dāng)前位置上的key是否和待查詢key相等，如果相等那么就直接返回value，如果不相等那么就繼續(xù)查找下一個索引直到遇到某個位置是null才結(jié)束，表示查詢的key不存在;

@Override public V get(K key) {     if (Objects.isNull(key)) {         throw new IllegalArgumentException("Key can not null");     }     int index;     for (index = hash(key); this.keys[index] != null; index = (index + 1) % capacity) {         if (this.keys[index].equals(key)) {             return this.values[index];         }     }     return null; }

刪除元素

線性探測式的刪除稍微麻煩一些，首先需要查找出待刪除的元素位置，刪除元素之后需要把當(dāng)前索引之后的連續(xù)位置上的元素重新插入;因為是否有空位對于線性探測式散列表的查找至關(guān)重要;例如：5->7->9，刪除了7之后，如果不重新插入7的位置就是空位，那么get方法將無法查詢到9這個元素;

每次刪除之后都需要檢測一次數(shù)組中實際元素的個數(shù)，如果與數(shù)組的容量相差較大，就可以進行縮容操作;

@Override public void delete(K key) {     if (Objects.isNull(key)) {         throw new IllegalArgumentException("Key can not null");     }     int index;     for (index = hash(key); this.keys[index] != null; index = (index + 1) % capacity) {         if (this.keys[index].equals(key)) {             this.keys[index] = null;             this.values[index] = null;             break;         }     }      for (index = (index + 1) % capacity; this.keys[index] != null; index = (index + 1) % capacity) {         this.size--;         this.put(this.keys[index], this.values[index]);         this.keys[index] = null;         this.values[index] = null;     }     this.size--;     if (size > 0 && size < capacity / 4) {         resize(capacity / 2);     }  }

“基于拉鏈?zhǔn)胶途€性探測式散列表實現(xiàn)Map的方法教程”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！