基于拉鏈式和線性探測式散列表實現Map
前言
前幾篇我們一起學習了基于數組、鏈表、二叉樹、紅黑樹來實現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》。
- 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
