HashMap解析

从另一个角度来解析HashMap到底是怎么实现的，试着自己实现一个HashMap。我们就实现一些常用的方法，掌握了主要的几个方法就能知晓原理了。

把K和V封装成一个实体Entry，然后HashMap内部维护一个Entry[]数组，就可以实现最基本的功能了。

public class HashMap<K, V> {

    public HashMap() {
        table = new Entry[16];// 源码方案，默认16
    }

    public HashMap(int initialCapacity) {
        int capacity = 2;
        while (capacity < initialCapacity)
            capacity = capacity * 2;// 源码方案，一定是2的倍数
        table = new Entry[capacity];
    }

    private Entry<K, V>[] table;
    private int size;

    public V put(K key, V value) {
        for (int i = 0; i < size; i++) {
            Entry<K, V> e = table[i];
            V oldValue = e.value;
            if (key.equals(e.key)) {
                e.value = value;
                return oldValue;
            }
        }
        table[size] = new Entry(key, value);
        size++;
        return null;
    }

    public V get(K key) {
        for (int i = 0; i < size; i++) {
            Entry<K, V> e = table[i];
            if (key.equals(e.key)) {
                return e.value;
            }
        }
        return null;
    }

    public int size() {
        return size;
    }

    class Entry<K, V> {
        private final K key;
        private V value;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}

put()的时候如果size超过table.length就有问题，当数组满了就要扩容

public V put(K key, V value) {
    for (int i = 0; i < size; i++) {
        Entry<K, V> e = table[i];
        V oldValue = e.value;
        if (e.key.equals(key)) {
            e.value = value;
            return oldValue;
        }
    }
    table[size] = new Entry(key, value);
    size++;
    if (size == table.length) {
        resize();
    }
    return null;
}

private void resize() {
    Entry<K, V>[] newTable = new Entry[table.length * 2];// 源码方案，满了就将数组长度翻倍
    for (int i = 0; i < table.length; i++) {
        newTable[i] = table[i];
    }
    table = newTable;
}

写到这里，一个最基本的HashMap就实现了。

一个合格的程序员，写完代码都应该思考下，这样写效率是不是太低了。
如果已经存了1000个值，那每次get和put都有可能需要遍历1000次，想想有没有办法可以优化。
如有有一个方法只要根据key，就可以知道在数组table的index，那就不用遍历了。比如index = key.hashcode()%2，这样index不是0就是1，显然不对，但是至少提示了我们可以把Entry分成2组进行存储，然后再去这2组里面去找我们想要的Entry。同一个index，table[index]怎么同时存储多个Entry呢？稍微改下Entry类，增加一个next

class Entry<K, V> {
    private final K key;
    private V value;
    private Entry<K, V> next;

    public Entry(K key, V value, Entry<K, V> next) {
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

增加一个获取index的方法

private int indexFor(int hash, int length) {
    return hash % length;// 这样分组当然比分2组好了，想想为什么这样分组最容易分散，而且根据table.length求余可以确保index不越界
}

然后改造下put()和get()

public V get(K key) {
    int index = indexFor(key.hashCode(), table.length);
    Entry<K, V> e = table[index];
    while (e != null) {
        if (key.equals(e.key)) {
            return e.value;
        }
        e = e.next;
    }
    return null;
}

public V put(K key, V value) {
    int index = indexFor(key.hashCode(), table.length);
    Entry<K, V> e = table[index];
    while (e != null) {
        if (key.equals(e.key)) {
            V oldValue = e.value;
            e.value = value;
            return oldValue;
        }
        e = e.next;
    }
    /*
     * 相同的index通过next连接起来，比如Entry a、b、c的index相同，put先后顺序是 c、b、a
     * 那么他们的关系就是
     * a.next = b
     * b.next = c
     * c.next = null
     */
    table[index] = new Entry<K, V>(key, value, table[index]);
    size++;
    if (size == table.length) {
        resize();
    }
    return null;
}

只要让index尽可能分散（即next层次尽可能浅）遍历的次数就会远远低于没改造前了，是不是感觉优化了不少。

有没有发现还有个问题，如果调用过resize()呢，那么indexFor()返回的值就会跟之前的不一样了。
解决方法就是resize()的时候把所有的Entry取出来，再根据indexFor()算法赋予给newTable[]

private void resize() {
    Entry<K, V>[] newTable = new Entry[table.length * 2];
    for (int i = 0; i < table.length; i++) {
        Entry<K, V> e = table[i];
        if (e != null) {
            do {
                Entry<K, V> next = e.next;
                int index = indexFor(e.key.hashCode(), newTable.length);
                Entry<K, V> oldEntry = newTable[index];
                newTable[index] = e;
                newTable[index].next = oldEntry;
                e = next;
            } while (e != null);
        }
    }
    table = newTable;
}

写到这里，应该基本掌握了HashMap的原理，当然源码还是比这复杂一些，比如我没处理key==null的情况，还有一些其他方法没有实现，JDK1.8引入了红黑树，当链表长度超过8的时候，使用红黑树。

其实HashMap源码里获取index，会对key.hashCode()再次加工，让index更加分散，int index = hash(key)
这个hash()为什么会让index更分散，有待继续研究，JDK1.8中

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

再说说hashCode()和equals()
我们知道HashMap里存取都是先去取table[index]，而index是根据key.hashCode()来生成的，看Object类

public native int hashCode();

public boolean equals(Object obj) {
    return (this == obj);
}

hashCode()就是返回内存地址，而equals()直接判断内存地址，举个例子

class Student {
    public int id;
    public String name;
}

Student a = new Student();
Student b = new Student();
a.id = 1;
a.name = "小明";
b.id = 1;
b.name = "小明";

那么a.equals(b)就是false，而且a.hashCode()也和b.hashCode()不相等
如果用Student做HashMap的key，我们显然想要的是a和b就是同一个key，那么我们只能自己重写这2个方法了，比如

class Student {
    public int id;
    public String name;
    public int hashCode(){
        return id + name.hashCode();
    }
    public boolean equals(Student s){
        return s.id == id && s.name.equals(name);
    }
}

为什么我们用String、Integer等做key没有问题，是因为它们已经实现了这两个方法。

总得来说，equals()返回true，那么hashCode()必须相等，而hashCode()相等，equals()可以返回false

---

额外说下HashSet，由于比较简单，就不开新篇

public HashSet() {
    map = new HashMap<>();
}

private static final Object PRESENT = new Object();

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

内部维护一个map，把element当做key，put到map，这样就能确保HashSet的值是唯一的了，非常简单。