HashMap


阳光少年     2020-07-28     2487

HashMap

目录

HashMap

HashMap的key就是HashSet集合,无序、不可重复
HashMap底层是一个Hash表,属性有key,value,hash,next
数组中每个元素中的单向链表的每个节点的hash值是相同的,该hash值就是该单向链表所在的元素的 下标,hash值是通过调用key的hashCode()方法经过hash算法得到的.

HashMap的put(k,v)方法实现原理:

  • 1. 当调用put(k,v)时,会将传入的key和value封装到Node对象中
  • 2.再调用key的hashCode()方法得出hash值,通过hash算法计算出对于数组中的下标,如果下标中没有元素,那么直接将此Node对象添加到当前位置,如果下标中已经存在链表了,那将会用Node中的key和每一个节点中的key进行equals(),如何全部返回false,就将Node添加至链表的末尾,如果有一个返回true,那么将其value值覆盖(也就是hashMap中的key重复,value覆盖)

HashMap的get(k)方法实现原理:

  • 当调用get(k)方法时,先调用k的hashCode()方法,得出hash值,再通过hash算法的到数组对应的下标,如果当前下标没有元素,那麽直接返回null,否则用key对链表中的每一个节点的key进行equals(),如果为true,将会返回此key对应的value值!如果每一个节点都返回false,表示没有找到,返回null

重点:

  • 1. 在Hash表中,每一个下标对应的节点中的hash值是相同的,表示这些节点存在于同一张单向链表上,这也是为什么需要重写hashCode()方法,如果不重写,将会调用Object中的hashCode(),那样会导致每一个节点对象的hash值都不相同,每个Node都会被添加到数组对应下标的第一个元素中!
  • 2. 为了保证元素的不重复,所以需要重写equals()方法,因为HashMap中的key就是HashSet集合,所以存储在HashSet中的元素也需要重写HashCode()和equals()方法
  • 3. 如果重写的hashCode()都返回固定的值,那样会导致所有的Node的hash值相同,全部挂在一张链表上,此时的hash表就成了单向链表,反之,如果重写的hashCode()方法全都返回不同的值,那么每个Node的hash值都不同,就变成了一维数组,以上问题称之为:散列分布不均匀
  • 4. HashMap的默认初始化容量为16,默认加载因子是0.75,当数组容量达到75%时,进行扩容
    比如当前默认初始化容量为16,负载因子为0.75,16*0.75 = 12, 当数组容量达到12,进行扩容
  • 5. HashMap的初始化容量必须是2的倍数,这是为了散列分布均匀,和提高存取效率
  • ♦6.对于存储在HashMapkey部分和存储在HashSet集合中的元素,都需要同时重写hashCode()和equals()方法
  • 7.关于扩容:resize()方法,进行扩容,扩容之后是原容量的2倍

关于HashMap的负载因子

  • 负载因子相当于是一个扩容机制的阈值,当容量超过这个阈值,就会引发扩容机制,默认是0.75,但是可以通过构造方法指定
  • 为什么要设置为0.75?
    • 我们先要了解,数据一开始是保存在数组里面的,当发生了Hash碰撞的时候,就是在这个数据节点上,生出一个链表,当链表长度达到一定长度的时候,默认为8,就会把链表转化为红黑树,当树上的分支小于6后又会变成单向链表
    • 设想我们将负载因子设置为1,如果数组长度为10,只有将这10个元素全部填满,才会引发扩容机制,这样会导致很大的问题,因为hash冲突是不可避免的,当负载因子为1,会导致大量的hash冲突,底层的红黑树会很复杂,查询效率变低,这样空间的利用率虽然是最大化的,但是效率降低了!
    • 如果我们将负载因子设置为0.5呢?那样会导致数组容量使用到一半时就开始扩容,那也填充的数据少了,hash冲突也会减少,底层链表的长度和红黑树的高度也会降低,检索效率增加,但是又会导致空间利用率降低,原本10m的数据,需要用20m来存储这样虽然时间效率提升了,但是空间利用率降低了
    • 将负载因子设置为0.75是一个折中的方法,此时空间利用率较高,也会减少较多的hash冲突,底层的链表和红黑树的长度较低,提升了时间效率

jdk代码


 		/**
         * 默认初始化容量16
         */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

        /**
         * 默认负载因子0.75
         */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;

		//当链表长度到达8时,将链表转换为红黑树
		static final int TREEIFY_THRESHOLD = 8;

		//当长度为6时再转换成链表
		static final int UNTREEIFY_THRESHOLD = 6;

Node对象

    transient Node<K,V>[] table;

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }