手写HashMap+HashMap原理解说（二）

    了解HashMap原理可以看上一篇：手写HashMap+HashMap原理解说（一）

    本次代码添加了size()方法、map的key可以为null，自动扩容功能，当   map.size() >= 数组长度*扩容因子   时，将数组长度变成原来的二倍，从hashmap存储原理来看，元素的存储位置是由key的hash值来决定的，hash值又与数组长度密切相关，因此数组长度变化是，所有的键值对要重新调整位置，这样就会产生一个全新的数组，具体代码如下：（以下代码有什么不对的地方欢迎指正）

public interface MyMap<K, V> {

    V put(K key, V value);

    V get(K key);

    interface Entry<K, V> {
        K getKey();

        V getValue();
    }

    int size();

    void resize();
}

public class MyHashMap<K, V> implements MyMap<K, V> {

    private static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    private static final float DEFAULT_LOAD_FACTOR = 0.25f;
    private float loadFactor = 0;
    private int initCapacity = 0;
    private Entry<K, V>[] table = null;
    private int size;

    public MyHashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        this.initCapacity = DEFAULT_INITIAL_CAPACITY;
        table = new Entry[this.initCapacity];
        size = 0;
    }

    public MyHashMap(int initCapacity, float loadFactor) {
        this.loadFactor = loadFactor;
        this.initCapacity = initCapacity;
        table = new Entry[this.initCapacity];
        size = 0;
    }

    public int size(){
        return size;
    }

    private int hash(K key) {
        int h;
        return (key == null) ? 0 : Math.abs((h = key.hashCode())) ^ (h >>> 16);
    }

    @Override
    public V put(K key, V value) {
        int index = hash(key) % initCapacity;
        if (table[index] != null) {
            Entry<K, V> e = table[index];
            Entry<K, V> e2 = null;
            while (e != null) {
                if (hash(e.key) == hash(key) && e.key.equals(key)) {
                    e.value = value;
                    size--;
                    return value;
                }
                e2 = e;
                e = e.next;
            }
            e2.next = new Entry<>(key, value, null, index);
        } else {
            Entry<K, V> e = new Entry<>(key, value, null, index);
            table[index] = e;
        }
        size++;
        if(size >= initCapacity * loadFactor){
            resize();
        }
        return value;
    }

    public V put(K key, V value, Entry<K,V>[] newTable) {
        int index = hash(key) % initCapacity;
        if (newTable[index] != null) {
            Entry<K, V> e = newTable[index];
            Entry<K, V> e2 = null;
            while (e != null) {
                if (hash(e.key) == hash(key) && e.key.equals(key)) {
                    e.value = value;
                    return value;
                }
                e2 = e;
                e = e.next;
            }
            e2.next = new Entry<>(key, value, null, index);
        } else {
            Entry<K, V> e = new Entry<>(key, value, null, index);
            newTable[index] = e;
        }
        if(size >= initCapacity * loadFactor){
            resize();
        }
        return value;
    }

    @Override
    public void resize() {
        initCapacity = initCapacity * 2;
        Entry<K, V>[] newTable = new Entry[initCapacity];
        for(int i = 0; i < table.length; i++){
            Entry<K, V> e = table[i];
            while (e != null) {
                put(e.key, e.value, newTable);
                e = e.next;
            }
        }
        table = newTable;
    }

    @Override
    public V get(K key) {
        int index = hash(key) % initCapacity;
        Entry<K, V> e = table[index];
        if (e == null) {
            return null;
        }

        while (e != null) {
            if (e.key == null && key == null ||
                    hash(e.key) == hash(key) && e.key.equals(key)) {
                return e.value;
            }
            e = e.next;
        }
        return null;
    }


    class Entry<K, V> implements MyMap.Entry<K, V> {

        K key;

        V value;

        Entry<K, V> next;

        int index;//记录下标

        Entry(K k, V v, Entry<K, V> next, int inx) {
            this.key = k;
            this.value = v;
            this.index = inx;
            this.next = next;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public Entry getNext() {
            return next;
        }

    }
}

public class Test {

    public static void main(String[] args) {

//        Map<String, String> map = new HashMap();
//        map.put("name","sophia");
//        map.put("age", "18");
//        System.out.println(map.get("name"));
//        System.out.println(map.get("age"));

        MyMap<String, Object> map = new MyHashMap<>();
        map.put("name", "sophia");
        map.put("age", 18);
        map.put("hahaha", "hehehe");
        map.put("hehehe", "lalala");
        System.out.println(map.size());
        map.put(null, "lalala");
        System.out.println(map.size());

        System.out.println(map.get("name"));
        System.out.println(map.get("age"));
        System.out.println(map.get("hahaha"));
        System.out.println(map.get("hehehe"));
        System.out.println(map.get(null));
        System.out.println(map.size());
    }
}

为了方便测试扩容功能，把默认的扩容因子调成了0.25，这样当map的size达到16*0.25=4的时候，即第一次扩容，开启debug模式进行测试，这里贴一下测试结果：

map的长度为3时：

map的长度为4时：（这里已经扩容成功，所有的元素都根据hash值重新放到了新的桶里）