HashMap

1.什么是HashMap

为什么会有Map呢,想象一下我们要到一栋楼去找一个人,如果门上都没有门牌号的的话,那我们得挨家挨户的敲门去问啊,运气好刚好第一家就是你要找的人,那运气不好不得跑断腿啊.但如果每家都有门牌号,你又知道是1栋1单元904,那你直接坐电梯到9楼敲4号房就是了.这个房号就是 Map 的 key ,而里面的人就是 Map 的 value 了.顺便我们也可以知道Map的两个特点
1.Map 的 key 一定是唯一的.
2.它的查询是高效的.

我们常常使用Map,一般顺手就是一个HashMap,反正只要是键值对的就来个HashMap就是了,HashMap 的value 也是可循环打印的,循环有三种方式

        //遍历 key 取值
        Set<Integer> keys = map.keySet();
        for (Integer key : keys) {
            System.out.println(map.get(key));
        }
        //直接遍历 value
        Collection<String> values = map.values();
        for (String value : values) {
            System.out.println(value);
        }
        //直接遍历 key 和 value
        Set<Map.Entry<Integer, String>> entries = map.entrySet();
        for(Map.Entry<Integer, String> entry:entries){
            System.out.println("key is "+entry.getKey()+" : value is "+entry.getValue());
        }

直到有一天你遍历打印的它的时候,什么鬼!居然顺序是乱的

顺序被改变了

WHY

其实保证 get 顺序和 put 顺序保持一致的话就要使用 LinkedHashMap,如果想让Map根据key排序.
的话就得使用 TreeMap.但如果没有轮循的操作,那还是推荐使用 HashMap 因为效率是最高的.

那HashMap内部究竟是怎样存储的呢,为什么顺序和想象的不一致呢?

2.HashMap的存储过程

我们知道存储一组元素最快的数据结构是数组,当我们 map.put(key, value) 时,如果直接将key放入到数组中会遇见一个问题,即数组的长度是固定的,而 map 需要放入的元素却不是固定的,但我们又不可能让 key 的数量收到数组的限制.map 是这样解决的根据key 的 hash 值换算出数组的下标.这样我们就可以将 key 存储起来了.所以 HashMap 存储的顺序只和 key 的 hash 值有关,而和 key-value 的放入顺序无关

但好像还是没有解决数组长度是固定的问题.例如第一个 key 根据hashcode计算出下标为5,第二个新加入的 key 计算出的下标还是5,岂不是会覆盖老的 key ?其实数组并不直接存储 key 而是存储的一个链表,当有新的 key 加入时就直接往链表后面就可以啦

这里给你梳理一下一个 key-value 放入 HashMap 的过程,当进行 put(key,value) 时,HashMap 会根据 key 的 hash 值计算出一个数组下标,并将它们放入到数组指定的链表中,此时会有3种情况:

链表为空,即之前没有 key 存储过,直接新建链表,添加 key-value
链表不为空,即冲突.轮询链表发现有和自己重复的 key,覆盖之前的 key-value
也是上面的情况,遇见冲突,但没有发现和自己重复的 key,那就直接在链表后面追加

3.hash 和 hash 值

hashcode 是 Object 的方法,所以所有的对象都有 hash 值,但 hash 值并不一定是唯一的,但没有问题,hash 值存在的意义是为了高效的查询,所以hash必须要保证统一性,即生成了后不会再改变.

4.equals

当 key 放入链表时发现冲突时(即链表不为空),怎么判断 key 是不是重复呢,其实是通过 key 的 equals 方法来判定的

5.如何正确重写hashCode和equals

其他使用 hash 来存储的集合也类似于 HashMap,都会使用到 hashCode 和 equals,而两个对象相等(a.equals(b)) 则 hashCode 必然相等(反之不成立) 这也就是为什么说重写 equals 同时也需要重写 hashCode.
这里有一种 hashCode 和 equals 标准写法

    @Override
    public int hashCode() {
        int result = 17;
        if (name != null) {
            result = 37 * result + name.hashCode() + (int) id;
        }
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        return obj instanceof CountedString && id == ((CountedString) obj).id;
    }

其实上面的核心思想是:

hashCode 依赖于唯一标示的对象,且且每次生成都相等
必然能通过 equals 确定对象