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()的时候如果数组满了就要扩容

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;// 分成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) & (length -1)

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

上文我们自己写的indexFor方法是index = hashCode%length，为什么JDK要写成index=hash&(length - 1)，关键点在于HashMap设定的length是2的幂次方，那么hashCode%length就等同于hashCode & (length - 1)，2的幂次方-1有个特点就是高位都是0，低位全是1，那hashCode&(length - 1)时，hashCode只有低位参与运算，为了优化、降低碰撞的概率，让hashCode的高位也参与运算，就有了hash=hashCode^(hashCode>>>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的值是唯一的了，非常简单。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • HashMap的实现
    实际上，HashSet 和 HashMap 之间有很多相似之处，对于 HashSet 而言，系统采用 Hash 算...
    曹振华阅读 2,529评论 1赞 37
  • JDK 1.7 HashMap 解析
    HashMap 可以算是 Java 中最常用的几个集合类之一。这一篇文章将在代码层面上详细解释 HashMap 的...
    王聪帅阅读 755评论 0赞 1
  • Java集合干货系列-（三）HashMap源码解析
    前言 今天来介绍下HashMap，之前的List，讲了ArrayList、LinkedList，就前两者而言，反映...
    嘟爷MD阅读 2,899评论 2赞 56
  • HashMap
    5.1、对于HashMap需要掌握以下几点 Map的创建：HashMap() 往Map中添加键值对：即put(Ob...
    rochuan阅读 700评论 0赞 0
  • “简书”我心灵的寄托
    遇见了简书如同是遇见了心灵的归宿 一个人的生活难免会孤单寂寞，尤其是夜深人静的时候。我时常会用看电视、听...
    点滴奇遇阅读 373评论 0赞 0