基于拉鍊式和線性探測式散清單實作Map

程式員必讀書單：https://github.com/silently9527/ProgrammerBooks

微信公衆号：貝塔學Java

前言

前幾篇我們一起學習了基于數組、連結清單、二叉樹、紅黑樹來實作Map的操作，本篇我們将會一起來學習基于散清單來實作Map，這種方式對應着java裡面的HashMap，這也是使用最多的一種方式

散清單實作Map主要分為了兩個步驟:

基于散列函數将被查找鍵轉換為數組的下标
處理散列值沖突的情況，有兩種方式來處理沖突：拉鍊式和線性探測

散列函數

實作散清單的第一步就是需要考慮如何把一個鍵轉換為數組的下标，這時候就需要使用到散列函數，先把鍵值轉換成一個整數然後在使用除留餘數法計算出數組的下标。每種類型的鍵我們都需要一個不同的散列函數。

在java中對于常用的資料類型已經實作了hashCode，我們隻需要根據hashCode的值使用除留餘數法即可轉換成數組的下标

java中的約定：如果兩個對象的equals相等，那麼hashCode一定相同；如果hashCode相同，equals不一定相同。對于自定義類型的鍵我們通常需要自定義實作hashCode和equals；預設的hashCode傳回的是對象的記憶體位址，這種散列值不會太好。

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

Integer

由于hashCode需要傳回的值就是一個int值，是以Integer的hashCode實作很簡單，直接傳回目前的value值

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

Long

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

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

public static int hashCode(long value) {
    return (int)(value ^ (value >>> 32));
}

Double、Float

浮點類型的鍵java中hashCode的實作是将鍵表示為二進制

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值，是以字元串轉換成一個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;
}

軟緩存

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

拉鍊式的散清單

散列函數能夠将鍵值轉換成數組的下标；第二步就是需要處理碰撞沖突，也就是需要處理遇到了兩個散列值相同的對象應該如何存儲。有一種方式是數組中的每一個元素都指向一個連結清單用來存放散列值相同的對象，這種方式被稱為拉鍊法

拉鍊法可以使用原始的連結清單儲存鍵，也可以采用我們之前實作的紅黑樹來表示，在java8中采用的這兩種方式的混合，在節點數超過了8之後變為紅黑樹。

這裡我們就采用簡單的連結清單來實作拉鍊式散清單，資料結構使用在前幾篇中已經實作的

LinkedMap

，可以參考前面的文章《基于數組或連結清單實作Map》。

基于拉鍊式和線性探測式散清單實作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函數使用key的hashCode與上0x7fffffff得到一個非負的整數，然後再使用除留餘數法計算出數組的下标。其中0x7FFFFFFF 的二進制表示就是除了首位是 0，其餘都是1，也就是說，這是最大的整型數 int（因為第一位是符号位，0 表示他是正數）,可以使用Integer.MAX_VALUE代替

散清單的主要目的在于把鍵值均勻的分布到數組中，是以散清單是無序的，如果你需要的Map需要支援取出最大值，最小值，那麼散清單都不适合。

這裡我們實作的拉鍊式散清單的數組大小是固定的，但是通常在随着資料量的增大，越短的數組出現碰撞的幾率會增大，是以需要數組支援動态的擴容，擴容之後需要把原來的值重新插入到擴容之後的數組中。數組的擴容可以參考之前的文章《老哥是時候來複習下資料結構與算法了》

線性探測式散清單

實作散清單的另一種方式就是用大小為M來儲存N個鍵值，其中M>N；解決碰撞沖突就需要利用數組中的空位；這種方式中最簡單的實作就是線性探測。

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

下一個位置和待插入的鍵相等，那麼值就修改值
下一個位置和待插入的鍵不相等，那麼索引加一繼續查找
如果下一個位置還是一個空位，那麼直接把待插入對象放入到這個空位

初始化

線性探測式散清單使用兩個數組來存放keys和values，

capacity

表示初始化數組的大小

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];
}

插入

當插入鍵的位置超過了數組的大小，就需要回到數組的開始位置繼續查找，直到找到一個位置為null的才結束； index = (index + 1) % capacity
當數組已存放的容量超過了數組總容量的一半，就需要擴容到原來的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++;
}

動态調整數組的大小

我們可以參考之前在文章《老哥是時候來複習下資料結構與算法了》中實作的動态調整資料的大小；線上性探測中需要把原來的資料重新插入到擴容之後的資料，因為數組的大小變了需要重新計算索引的位置。

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;
}

查詢

線性探測散清單中實作查詢的思路：根據待查詢key的hash函數計算出索引的位置，然後開始判斷目前位置上的key是否和待查詢key相等，如果相等那麼就直接傳回value，如果不相等那麼就繼續查找下一個索引直到遇到某個位置是null才結束，表示查詢的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;
}

删除元素

線性探測式的删除稍微麻煩一些，首先需要查找出待删除的元素位置，删除元素之後需要把目前索引之後的連續位置上的元素重新插入；因為是否有空位對于線性探測式散清單的查找至關重要；例如：5->7->9，删除了7之後，如果不重新插入7的位置就是空位，那麼get方法将無法查詢到9這個元素；

每次删除之後都需要檢測一次數組中實際元素的個數，如果與數組的容量相差較大，就可以進行縮容操作；

@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);
    }

}

文中所有源碼已放入到了github倉庫:

https://github.com/silently9527/JavaCore

最後（點關注，不迷路）

文中或許會存在或多或少的不足、錯誤之處，有建議或者意見也非常歡迎大家在評論交流。

最後，寫作不易，請不要白嫖我喲，希望朋友們可以點贊評論關注三連，因為這些就是我分享的全部動力來源🙏

精美的淘客項目完全開源啦，有需要的朋友關注公衆号：貝塔學java ;發送「源碼」

基于拉鍊式和線性探測式散清單實作Map

基于拉鍊式和線性探測式散清單實作Map

前言

散列函數

Integer

Long

Double、Float

String

軟緩存

拉鍊式的散清單

線性探測式散清單

初始化

插入

動态調整數組的大小

查詢

删除元素

最後（點關注，不迷路）

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method