hashmap的底層實現，hashmap底層實現

hashmap的底層實現，hashmap底層實現

HashMap的底層實現都是數組+鏈表結構實現的，添加、刪除、獲取元素都是先計算hash值，根據hash值和table.length計算出index也就是table的數組的下標，然後進行相應的操作。

不過HashMap和HashTable計算hash的方法不同：

HashMap是直接用key的hashcode對table數組長度取模；而HashMap則是對key的hashcode進行兩次hash，以獲得更好的散列值，然後再對table數組的長度取模。

具體方法的實現：

HashMap默認初始化時會創建一個容量為16的Entry數組，默認加載因子為0.75，同時設置臨界值16*0.75；

  public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
        init();
    }

對於put方法：

HashMap會對null值key進行特殊處理，總是放到table[0]位置
put過程是先計算hash然後通過hash與table.length取摸計算index值，然後將key放到table[index]位置，當table[index]已存在其它元素時，會在table[index]位置形成一個鏈表，將新添加的元素放在table[index]，原來的元素通過Entry的next進行鏈接，這樣以鏈表形式解決hash沖突問題，當元素數量達到臨界值(capactiy*factor)時，則進行擴容，是table數組長度變為table.length*2；

對於get方法：

同樣當key為null時會進行特殊處理，在table[0]的鏈表上查找key為null的元素
get的過程是先計算hash然後通過hash與table.length取摸計算index值，然後遍歷table[index]上的鏈表，直到找到key，然後返回

對於remove方法：

remove方法和put get類似，計算hash，計算index，然後遍歷查找，將找到的元素從table[index]鏈表移除

對於resize方法：

resize方法在hashmap中並沒有公開，這個方法實現了非常重要的hashmap擴容，具體過程為：先創建一個容量為table.length*2的新table，修改臨界值，然後把table裡面元素計算hash值並使用hash與table.length*2重新計算index放入到新的table裡面，這裡需要注意下是用每個元素的hash全部重新計算index，而不是簡單的把原table對應index位置元素簡單的移動到新table對應位置

對於containsKey方法：

containsKey方法是先計算hash然後使用hash和table.length取摸得到index值，遍歷table[index]元素查找是否包含key相同的值

簡單的MyHashMap：

public class MyHashMap {

    //默認初始化大小 16
    private static final int DEFAULT_INITIAL_CAPACITY = 16;
    //默認負載因子 0.75
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    //臨界值
    private int threshold;

    //元素個數
    private int size;

    //擴容次數
    private int resize;

    private HashEntry[] table;

    public MyHashMap() {
        table = new HashEntry[DEFAULT_INITIAL_CAPACITY];
        threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        size = 0;
    }

    private int index(Object key) {
        //根據key的hashcode和table長度取模計算key在table中的位置
        return key.hashCode() % table.length;
    }

    public void put(Object key, Object value) {
        //key為null時需要特殊處理，為簡化實現忽略null值
        if (key == null) return;
        int index = index(key);

        //遍歷index位置的entry，若找到重復key則更新對應entry的值，然後返回
        HashEntry entry = table[index];
        while (entry != null) {
            if (entry.getKey().hashCode() == key.hashCode() && (entry.getKey() == key || entry.getKey().equals(key))) {
                entry.setValue(value);
                return;
            }
            entry = entry.getNext();
        }
        //若index位置沒有entry或者未找到重復的key，則將新key添加到table的index位置
        add(index, key, value);
    }

    private void add(int index, Object key, Object value) {
        //將新的entry放到table的index位置第一個，若原來有值則以鏈表形式存放
        HashEntry entry = new HashEntry(key, value, table[index]);
        table[index] = entry;
        //判斷size是否達到臨界值，若已達到則進行擴容，將table的capacicy翻倍
        if (size++ >= threshold) {
            resize(table.length * 2);
        }
    }

    private void resize(int capacity) {
        if (capacity <= table.length) return;

        HashEntry[] newTable = new HashEntry[capacity];
        //遍歷原table，將每個entry都重新計算hash放入newTable中
        for (int i = 0; i < table.length; i++) {
            HashEntry old = table[i];
            while (old != null) {
                HashEntry next = old.getNext();
                int index = index(old.getKey());
                old.setNext(newTable[index]);
                newTable[index] = old;
                old = next;
            }
        }
        //用newTable替table
        table = newTable;
        //修改臨界值
        threshold = (int) (table.length * DEFAULT_LOAD_FACTOR);
        resize++;
    }

    public Object get(Object key) {
        //這裡簡化處理，忽略null值
        if (key == null) return null;
        HashEntry entry = getEntry(key);
        return entry == null ? null : entry.getValue();
    }

    public HashEntry getEntry(Object key) {
        HashEntry entry = table[index(key)];
        while (entry != null) {
            if (entry.getKey().hashCode() == key.hashCode() && (entry.getKey() == key || entry.getKey().equals(key))) {
                return entry;
            }
            entry = entry.getNext();
        }
        return null;
    }

    public void remove(Object key) {
        if (key == null) return;
        int index = index(key);
        HashEntry pre = null;
        HashEntry entry = table[index];
        while (entry != null) {
            if (entry.getKey().hashCode() == key.hashCode() && (entry.getKey() == key || entry.getKey().equals(key))) {
                if (pre == null) table[index] = entry.getNext();
                else pre.setNext(entry.getNext());
                //如果成功找到並刪除，修改size
                size--;
                return;
            }
            pre = entry;
            entry = entry.getNext();
        }
    }

    public boolean containsKey(Object key) {
        if (key == null) return false;
        return getEntry(key) != null;
    }

    public int size() {
        return this.size;
    }

    public void clear() {
        for (int i = 0; i < table.length; i++) {
            table[i] = null;
        }
        this.size = 0;
    }


    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("size:%s capacity:%s resize:%s\n\n", size, table.length, resize));
        for (HashEntry entry : table) {
            while (entry != null) {
                sb.append(entry.getKey() + ":" + entry.getValue() + "\n");
                entry = entry.getNext();
            }
        }
        return sb.toString();
    }
}

class HashEntry {
    private final Object key;
    private Object value;
    private HashEntry next;

    public HashEntry(Object key, Object value, HashEntry next) {
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public Object getKey() {
        return key;
    }

    public Object getValue() {
        return value;
    }

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

    public HashEntry getNext() {
        return next;
    }

    public void setNext(HashEntry next) {
        this.next = next;
    }
}