Java HashMap簡單實現原理的理解

正常情況下，Map的key和Value都可以用數組實現，一邊ArrayList是key的keys，另一邊是ArrayList value的values。

通過key獲取value的方式是這樣的values.get(keys.indexOf(key)).

然而，數組的長度是有限的。不符合map可以無限放入元素的要求。所以要對這個數組進行特殊的要求。

那就是同一個數組的index可以存放多個值，只是這些相同index的hascode值不同，這樣就能把他們卻別開了。同時也就實現無限個元素要求了（用數組實現主要是性能的優勢）。那么要確定value就要計算hascode和數組下標。

數組不直接執行value的值，而是用equals()方法線性的查找；正常情況下這樣的查找方式也會慢，但是只要hascode方法設計的合理，每個插槽將會只有少量的value.這樣查找也就快很多；

import java.util.Map;

public class MapEntry<K,V> implements Map.Entry<K, V> {
    private K key;
    private V value;
    public MapEntry(K key, V value) {
        this.key = key;
        this.value = value;
    }
    @Override
    public K getKey() {
        return key;
    }
    @Override
    public V getValue() {
        return value;
    }
    @Override
    public V setValue(V value) {
        V result = this.value;
        this.value =value;
        return result;
    }
    @Override
    public int hashCode() {
        return (key == null ? 0:key.hashCode())^(value == null ? 0: value.hashCode());
    }
    @Override
    public boolean equals(Object obj) {
        if(!(obj instanceof MapEntry)) {
            return false;
        }
        MapEntry me = (MapEntry)obj;
        return (key ==null ? me.getKey() == null : key.equals(me.getKey())) &&
                (value == null ? me.getValue()==null : value.equals(me.getValue()));
    }
    @Override
    public String toString() {
        return key+"="+value;
    }
}

import java.util.AbstractMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Map;
import java.util.Set;

public class SimpleHashMap<K,V> extends AbstractMap<K, V> {
    static final int SIZE = 997;
    /**集合類型數組,數組的每個元素都是一個List集合類型**/
    LinkedList<MapEntry<K, V>>[] buckets = new LinkedList[SIZE];
    public V put(K key, V value) {
        V oldValueV = null;
        /**根據hascode對數組長度求模，計算得出應該放入數組的index位置**/
        int index = Math.abs(key.hashCode())%SIZE;
        if(buckets[index] == null) {
            /**如果該下標下還沒有集合，則創建**/
            buckets[index] = new LinkedList<MapEntry<K, V>>();
        }
        LinkedList<MapEntry<K, V>> bucket = buckets[index];
        /**把傳進來的key和value封裝為MapEntry類型**/
        MapEntry<K, V> pair = new MapEntry<K, V>(key, value);
        /**假設在該數組index下的機會里找不到與pair對應的值**/
        boolean found = false;
        ListIterator<MapEntry<K, V>> it = bucket.listIterator();
        while(it.hasNext()) {
            MapEntry<K, V> iPair = it.next();
            if(iPair.getKey().equals(key)) {
                /**如果已經存在,則替換掉**/
                oldValueV = iPair.getValue();
                it.set(pair);
                found = true;
                break;
            }
        }
        if(!found) {
            /**如果不存在，則把封裝后的MapEntry對象加入的集合中**/
            buckets[index].add(pair);
        }
        return oldValueV;
    }
    public V ge(Object key) {
        /**已同樣的方式計算出應該的index**/
        int index = Math.abs(key.hashCode())%SIZE;
        if(buckets[index]==null) {
            /**對應的index里沒有機會**/
            return null;
        }
        for(MapEntry<K, V> iPair : buckets[index]) {
            if(iPair.getKey().equals(key)) {
                /**對該index下的機會進行查找，比較MapEntr的key值**/
                return iPair.getValue();
            }
        }
        return null;
    }
    @Override
    public Set<Map.Entry<K, V>> entrySet() {
        Set<Map.Entry<K, V>> set = new HashSet<Map.Entry<K,V>>();
        for(LinkedList<MapEntry<K, V>> bucket : buckets) {
            if(bucket == null) continue;
            for(MapEntry<K, V> mpair : bucket) {
                /**用2個for循環，遍歷這個二維的集合，把遍歷到的每個值放到Set里**/
                set.add(mpair);
            }
        }
        return set;
    }
    public static void main(String[] args) {
        SimpleHashMap<String, String> mMap = new SimpleHashMap<String,String>();
        mMap.put("YYY", "yyy");
        mMap.put("QQQ", "qqq");
        mMap.put("AAA", "aaa");
        mMap.put("GGG", "ggg");
        System.out.println(mMap);
        System.out.println(mMap.get("GGG"));
        System.out.println(mMap.entrySet());
    }
}

摘自thinking in java