引用する

前のブログでHashMapのソースコードを学び、hash関数の設計原理と基本的な添削と拡張の実現を理解しました.今日は、配列と単鎖表に基づいて簡単なHashMapを手書きで試し、putgetremoveresize操作を実現します.

Mapインタフェース

基本的な操作が含まれています:putgetremovesizeメソッド:

package hash;

/**
 * Created by chenming on 2018/6/10
 *  map 
 */
public interface Map {
    /**
     *  
     * @return
     */
    int size();

    /**
     *  
     * @param key
     * @param object
     */
    void put(K key, V object);

    /**
     *  
     * @param key
     * @return
     */
    V get(K key);

    /**
     *  
     * @param key
     * @return
     */
    V remove(K key);
}

ノードノードノード定義

ノードは単一チェーンテーブルノードであり,構想はJDKと同様である.

package hash;

/**
 * Created by chenming on 2018/6/10
 */
public class Node {
    private int hash;// hash , key 
    private K key;
    private V value;
    public Node next;

    public Node(int hash, K key, V value) {
        this.hash = hash;
        this.key = key;
        this.value = value;
    }

    public final K getKey() {
        return key;
    }

    public final V getValue() {
        return value;
    }

    public final String toString() {
        return key + "=" + value;
    }

    public int getHash() {
        return hash;
    }

    public void setHash(int hash) {
        this.hash = hash;
    }

    public void setKey(K key) {
        this.key = key;
    }

    public void setValue(V value) {
        this.value = value;
    }
}

hash関数

参考JDK 1.8、具体的な設計思想は前編のソースコード分析を参考にし、ここでは後述しない.

   /**
     *  key hash
     *
     * @param key
     * @return
     */
    private int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

   /**
     * hash ，hash 
     *
     * @param hash
     * @param len
     * @return
     */
    private int indexFromHash(int hash, int len) {
        int index = (len - 1) & hash;
        return index;
    }

判定キーヒット

前提:1.hashcodeは等しい.2.keyオブジェクトは同じです.

   /**
     *  key 
     *
     * @param key
     * @param n
     * @return
     */
    private boolean isNodeHit(K key, Node n) {
        int hash = hash(key);
        if (n.getHash() == hash) {
            if (key == n.getKey() || (key != null) && (key.equals(n.getKey()))) {
                return true;
            }
        }
        return false;
    }

putメソッド

   /**
     * put 
     * @param key
     * @param value
     */
    @Override
    public void put(K key, V value) {
        int hash = hash(key);
        int index = indexFromHash(hash, table.length);
        Node first = table[index];
        if (first == null) {// 
            first = new Node(hash, key, value);
            table[index] = first;
        } else {
            Node p = first;
            while (p.next != null) {
                if (isNodeHit(key, p)) {// hit node
                    // value, 
                    p.setValue(value);
                    return;
                }
                p = p.next;
            }
            p.next = new Node(hash, key, value);
        }
        if (++size > threhold) {
            resize();// 
        }
        return;
    }

プログラム構造とJDK 1.8出入りがあって、考え方は同じです.

getメソッド

   /**
     *  
     * @param key
     * @return
     */
    @Override
    public V get(K key) {
        int index = indexFromHash(hash(key), table.length);
        Node first = table[index];
        if (first == null) {
            return null;
        } else {
            Node p = first;
            while (p != null) {
                if (isNodeHit(key, p)) {// 
                    return p.getValue();
                }
                p = p.next;
            }
        }
        return null;
    }

removeメソッド

    /**
     *  
     * @param key
     * @return
     */
    @Override
    public V remove(K key) {
        int index = indexFromHash(hash(key), table.length);
        Node first = table[index];
        V oldVal = null;
        if (first != null) {
            if (first.next == null) {// ， 
                oldVal = first.getValue();
                // 
                table[index] = null;
            } else {
                if (isNodeHit(key, first)) {// ， 
                    // 
                    table[index] = first.next;
                } else {
                    // ， key 
                    Node pre = first;
                    Node p = pre.next;
                    while (p != null) {
                        if (isNodeHit(key, p)) {// 
                            oldVal = p.getValue();
                            pre.next = p.next;// 
                            p.next = null;
                            break;
                        }
                        pre = p;
                        p = p.next;
                    }

                    if (p == null) {// , 
                        return null;
                    }
                }

            }
        }
        size--;
        return oldVal;
    }

考え方:対応する位置に要素が1つしかない場合は、直接削除します.そうしないと、単一チェーンテーブルを巡り、ノードを削除します.

キャパシタンス操作

 /**
     *  
     */
    private void resize() {
        int oldCap = table.length;
        int newCap = oldCap << 1;
        threhold = (int) (newCap * DEFAULT_LOAD_FACTOR);
        Node[] newTable = new Node[newCap];
        for (int i = 0; i < oldCap; i++) {
            Node first = table[i];

            if (first != null) {
                int hash = first.getHash();
                if (first.next == null) {
                    newTable[indexFromHash(hash, newCap)] = first;
                } else {// ， ， 
                    Node next;// 
                    // 
                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node p = first;
                    do {
                        next = p.next;
                        if ((oldCap & p.getHash()) == 0) {// 
                            if (loTail == null) {
                                loHead = p;
                            } else {
                                loTail.next = p;
                            }
                            loTail = p;
                        } else {// 
                            if (hiTail == null) {
                                hiHead = p;
                            } else {
                                hiTail.next = p;
                            }
                            hiTail = p;
                        }
                    } while ((p = next) != null);

                    if (loHead != null) {
                        loTail.next = null;
                        newTable[i] = loHead;
                    }

                    if (hiHead != null) {
                        hiTail.next = null;
                        newTable[i + oldCap] = hiHead;
                    }
                }
            }
        }
        table = newTable;// 
    }

単一チェーンテーブルの分割操作と設計思想はjdkと同じで、具体的な分析は前の文章を見てください.最後にテストコードを提示します.

   /**
     *  
     */
    @Test
    public void testHashMap() {
        HashA a = new HashA("ABC");
        HashB b = new HashB("ABC");
        //HashMap key 
        hash.HashMap

完全なコードアドレス:データ構造とアルゴリズム学習JAVA説明GayHubアドレス