每一个java程序员, 很少有不知道HashMap底层结构的, 无非就是数组 + 链表, 然后巴拉巴拉能跟你说一大堆, 但是一个元素真正的插入流程你确定你真的清楚了吗?

HashMap插入元素的逻辑

(1) 首先我们要明确, 我们要插入的是一个键值对, 即key和value, 这是两个对象.

(2) 我们在插入的时候, 插在数组中的哪里, 是由key对象决定的, 跟value半毛线关系都没有

(3) 首先我们会计算key的hash值(注意只需要在插入的时候计算一次hash值), 根据hash值, 在数组中找到相应的位置.

(4) 找到数组位置后, 此时是一个链表, 从头节点开始向后遍历, 不断比较key对象, 一定要注意此时比较的是key对象, 即调用key的equal方法, 此时仍然跟value没有半毛线的关系.

(5) 如果遍历中遇见相同的key对象, 此时将value直接覆盖

(6) 如果没有遇见相同的key, 就将<key, value>作为一个entry 插入到链表中.

(7) 至此 元素的插入流程完成, 我们可以发现, 整个插入流程, value完全没用, 全部是由key决定的.

需要强调的是, 整个插入流程和key对象的两个方法息息相关:
(1) 第一个是key对象的hashCode()方法
(2) 第二个是key对象的equals()方法
复制代码

看了上面的逻辑, 你真的理解了吗?

下面来看一道题: 给出此时打印出的是什么结果?

public class Main {
    
    public static void main(String [] args) {

        LinkedHashMap<Person, String> personMap = new LinkedHashMap<>();

        Person person = new Person();

        person.name = "Jack";
        personMap.put(person, "Teacher");

        person.name = "Tom";
        personMap.put(person, "Lawyer");

        person.name = "Lily";
        personMap.put(person, "Student");

        for (Map.Entry<Person, String> entry : personMap.entrySet()) {
            Person k = entry.getKey();
            String v = entry.getValue();
            System.out.printf("%s is a %s\n", k.name, v);
        }

    }

    static class Person {
        private String name;

        @Override
        public boolean equals(Object o) {
            Person person = (Person) o;
            return name.equals(person.name);
        }

        @Override
        public int hashCode() {
            return name.length();
        }
    }
复制代码

正确答案

在分析之前 先给出正确答案, 看看你是否答对了

Lily is a Student
Lily is a Lawyer
复制代码

分析

(1) 这里利用LinkedHashMap是为了让最后遍历输出的是有顺序的. 保证答案是唯一的.

(2) 这里采用一个Person作为key对象, 其实是不建议的, 因此一旦修改了key的hash值, 就会导致各种各样的问题, 例如remove的时候, 就没办法找到这个entry了, 导致内存泄漏等问题, 但是这里就是为了考察对hashMap了解, 故意这么做的.

(3) 明确Person类的hashCode方法和equal方法被重写了, 在判断的时候要随时牢记.

(4) 题目中只实例化了一个对象, 因此key对象从头到尾都是一个

        Person person = new Person();
复制代码

(5) 此时key的hashCode是4, 插入到数组对应位置(假设是table[4]), 链表为空, 直接插入一个新节点<person, “Teacher”>, 这一步没什么好讲的

        person.name = "Jack";
        personMap.put(person, "Teacher");
复制代码

(6) 这一步修改了person对象的name值, 就改变了hashcode值, 此时hashCode变成了3, 插入到数组中的位置就变了, 插入到table[3], 和第五步中不是同一个数组位置, 此时链表为空, 直接插入一个新节点<person, “Lawyer”>.

需要强调的是, 因为是同一个对象, 此时table[4]中的person对象的name也是Tom, 并且hash值为3, 也就是一个hash值为3的key, 此时在table[4]位置上, 这就是因为, 只会在插入的时候计算一次hash值, 后面就不管了.

        person.name = "Tom";
        personMap.put(person, "Lawyer");
复制代码

(7) 此时name修改为Lily, 那么person对象的hasCode是4, 在数组中的位置是table[4], 和第五步对应的是同一个数组位置, 此时链表不为空, 然后判断链表节点的key对象和此时需要插入的是不是同一个对象(即调用equal方法), 因为是同一个对象, 当person.name = “Lily”的时候, map中的key对象都发生变化了, 因此这里链表的节点和要插入的key对象是相同的, 那么table[4]链表节点的value就被覆盖成了Student.

        person.name = "Lily";
        personMap.put(person, "Student");
复制代码

(8) 此时map中一共就被插入了两个entry, 一个在tabel[3], 一个在table[4]. 然后因为LinkedHashMap遍历的顺序是entry的插入顺序, 因此第一个entry应该是table[4]的, 然后第二个entry是table[3]的.

(9) 因此最后的正确答案就是如下, 你得到正确的结果了吗?