Java數據結構之散列表詳解

/**
 * 基於線性探測法的散列表簡單實現
 *
 * @param <K> key類型
 * @param <V> value類型
 */
public class LinearProbingHashMap<K, V> {

    /**
     * 存儲節點數據的數組
     */
    transient Entry<K, V>[] table;

    /**
     * 存儲的節點對象
     *
     * @param <K>
     * @param <V>
     */
    private static class Entry<K, V> implements Map.Entry<K, V> {
        /**
         * 保存hash值,避免重復計算
         */
        final int hash;
        /**
         * key值
         */
        final K key;
        /**
         * value值
         */
        V value;

        /**
         * 構造器
         *
         * @param hash
         * @param key
         * @param value
         */
        private Entry(int hash, K key, V value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }

        @Override
        public final K getKey() {
            return key;
        }

        @Override
        public final V getValue() {
            return value;
        }

        /*@Override
        public final String toString() {

            return hash + "=" + key + "=" + value;
        }*/
        @Override
        public final String toString() {

            return key + "=" + value;
        }

        @Override
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        @Override
        public int hashCode() {
            return hash;
        }
    }

    /**
     * 散列表的容量,初始為16
     */
    private int capacity = 16;
    /**
     * 散列表節點數量
     */
    private int size;

    /**
     * 空構造器,並不會初始化內部數組
     */
    public LinearProbingHashMap() {
    }

    /**
     * 插入
     *
     * @param key   k
     * @param value v
     */
    public V put(K key, V value) {
        //初始化
        if (table == null) {
            table = new Entry[capacity];
        }
        //擴容,這裡判斷元素數量大於等於0.75*capacity
        if (size >= capacity * 0.75) {
            resize(2 * capacity);
        }
        int hash = hash(key);
        //計算應該插入的數組元素下標
        int position = hash & (capacity - 1);
        //插入邏輯,總會成功
        while (true) {
            if (table[position] == null) {
                table[position] = new Entry<>(hash, key, value);
                size++;
                break;
                //判斷是否是重復的key,這裡使用hash值和==判斷
            } else if (hash == table[position].hashCode() && table[position].getKey() == key) {
                return table[position].setValue(value);
            }
            position = nextIndex(position, capacity);
        }
        return null;
    }

    /**
     * 查找
     *
     * @param key 要查找的key
     * @return 查找到的value
     */
    public V get(K key) {
        if (table == null) {
            return null;
        }
        //計算出key對應的數組位置
        int position = hash(key) & (capacity - 1);
        //如果該位置不為null,則開始查找連續的元素
        if (table[position] != null) {
            do {
                if (table[position].getKey() == key) {
                    return table[position].getValue();
                }
                position = nextIndex(position, capacity);
            } while (table[position] != null);
        }
        return null;
    }


    /**
     * 刪除元素
     *
     * @param key 查找的元素
     * @return 被刪除的元素value;null不代表不是被刪除的value
     */
    public V delete(K key) {
        if (table == null) {
            return null;
        }
        //計算出key對應的數組位置
        int position = hash(key) & (capacity - 1);
        V value;
        //如果該位置不為null,則開始查找連續的元素
        if (table[position] != null) {
            do {
                if (table[position].getKey() == key) {
                    //刪除元素
                    value = table[position].getValue();
                    table[position] = null;
                    size--;
                    //將後面的連續的元素全部重新插入
                    position = nextIndex(position, capacity);
                    Entry<K, V> positionEntry;
                    while ((positionEntry = table[position]) != null) {
                        table[position] = null;
                        size--;
                        put(positionEntry.getKey(), positionEntry.getValue());
                        position = nextIndex(position, capacity);
                    }
                    return value;
                }
                position = nextIndex(position, capacity);
            } while (table[position] != null);
        }
        return null;
    }

    public int size() {
        return size;
    }

    /**
     * 獲取hash值,不是直接取hash值,而是借鑒瞭HashMap的擾動算法,這樣可以讓元素分佈更加均勻
     *
     * @param key k
     * @return hash值
     */
    private int hash(K key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    /**
     * 擴容
     *
     * @param newCapacity 新容量
     */
    private void resize(int newCapacity) {
        if (newCapacity <= 0) {
            throw new StackOverflowError("容量超出最大容量");
        }
        this.capacity = newCapacity;
        Entry<K, V>[] oldTab = table;
        table = new Entry[capacity];
        for (Entry<K, V> e : oldTab) {
            if (e != null) {
                int position = e.hashCode() & (capacity - 1);
                while (table[position] != null) {
                    position = nextIndex(position, capacity);
                }
                table[position] = e;
            }
        }
    }

    /**
     * 下一個位置
     *
     * @param i   當前位置
     * @param len 數組長度
     * @return 下一個位置, 此處包含循環的邏輯循環
     */
    private static int nextIndex(int i, int len) {
        return ((i + 1 < len) ? i + 1 : 0);
    }


    @Override
    public String toString() {
        return "LinearProbingHashST{" +
                "table=" + Arrays.toString(table) +
                '}';
    }
}

public class LinearProbingHashMapTest {
    public static void main(String[] args) {
        System.out.println("==========>插入一批元素");
        LinearProbingHashMap<Object, Object> objectObjectLinearProbingHashMap = new LinearProbingHashMap<>();
        objectObjectLinearProbingHashMap.put(49, 16);
        objectObjectLinearProbingHashMap.put("Aa", 1);
        objectObjectLinearProbingHashMap.put(34, 78);
        objectObjectLinearProbingHashMap.put(17, 85);
        //Aa與BB的hash值是一樣的
        objectObjectLinearProbingHashMap.put("BB", 2);
        objectObjectLinearProbingHashMap.put(36, 36);
        objectObjectLinearProbingHashMap.put(21, 37);
        objectObjectLinearProbingHashMap.put(9, 87);
        objectObjectLinearProbingHashMap.put("兓", 62);
        objectObjectLinearProbingHashMap.put(46, 43);
        objectObjectLinearProbingHashMap.put("呵呵", 3);
        objectObjectLinearProbingHashMap.put("嘻嘻", 4);
        System.out.println(objectObjectLinearProbingHashMap);
        System.out.println("size:" + objectObjectLinearProbingHashMap.size());
        System.out.println(objectObjectLinearProbingHashMap);

        System.out.println("==========>刪除 BB");
        Object delete = objectObjectLinearProbingHashMap.delete("BB");
        System.out.println(delete);
        System.out.println("size:" + objectObjectLinearProbingHashMap.size());
        System.out.println(objectObjectLinearProbingHashMap);

        System.out.println("==========>插入(46,44) 重復添加46,將會替換value");
        Object put = objectObjectLinearProbingHashMap.put(46, 44);
        System.out.println(put);
        System.out.println("size:" + objectObjectLinearProbingHashMap.size());
        System.out.println(objectObjectLinearProbingHashMap);

        System.out.println("==========>插入null 將會嘗試添加到第一個元素");
        Object putNull = objectObjectLinearProbingHashMap.put(null, "nullnull");
        System.out.println(putNull);
        System.out.println("size:" + objectObjectLinearProbingHashMap.size());
        System.out.println(objectObjectLinearProbingHashMap);

        System.out.println("==========>獲取null 對應的value");
        Object o = objectObjectLinearProbingHashMap.get(null);
        System.out.println(o);

        System.out.println("==========>擴容");
        objectObjectLinearProbingHashMap.put("BB", 5);
        System.out.println("size:" + objectObjectLinearProbingHashMap.size());
        System.out.println(objectObjectLinearProbingHashMap);

        System.out.println("==========>獲取BB 對應的value");
        Object bb = objectObjectLinearProbingHashMap.get("BB");
        System.out.println(bb);

        System.out.println("==========>刪除 34");
        Object delete34 = objectObjectLinearProbingHashMap.delete(34);
        System.out.println(delete34);
        System.out.println("size:" + objectObjectLinearProbingHashMap.size());
        System.out.println(objectObjectLinearProbingHashMap);
    }
}