初识HashMap真面目

HashMap是java中应用最广的集合类之一,以key/value(键值对)的方式保存数据。

你可以把HashMap叫做集合类,也可以把它叫做容器,java中许多容器框架比如Spring,其实好多都是用HashMap来存储数据的。

当然,java秉承“一切都是对象”,HashMap中存储的当然也是对象,只不过是以“键值”对组成的对象。

HashMap继承自AbstractMap,并实现了Map接口。所以,想要彻底搞懂HashMap,还是需要先从Map接口、以及AbstractMap入手。

Map接口

其实Map接口没啥东西,接口而已。定义了size()、isEmpty()、get()、put()、containsKey()、containsValue()......等通用的Map类方法。

相对重要一点的是,Map接口定义了一个Entry内部接口,这个Entry其实就是Map包含的对象,不同的Map的实现类会有不同的实现。

Map接口也实现了几个方法,具体暂时就不详细分析了,这其实是一个很好的针对“接口是否可以实现方法?”这个问题的很好的答案。

AbstractMap抽象类

AbstractMap抽象类实现了Map接口,具体化了部分Map接口定义的方法。

实现了一个叫SimpleEntry的Entry(就是Map接口中定义的内部接口),还有一个叫SimpleImmutableEntry的Entry。

暂且不表,不影响主题:识别HashMap真面目。

HashMap的数据结构

回过头来再继续研究HashMap,首先识别HashMap的数据结构,我们先从简单的入手,一步一步抽丝剥茧、先易后难,逐步研究。

首先来认识一下Node。
Node是Entry的实现,数据结构非常简单:

 final int hash;
 final K key;
 V value;
 Node next;

哈希值、key、vaue以及指向下一节点的简单的链表结构。

HashMap桶内Node链表容量增大之后会自动修改简单链表结构为红黑树,本篇暂不研究红黑树。

table数组
table数组是HashMap真正存储数据的地方,所以说白了HashMap底层实际上还是数组。

不过HashMap的table是比较特殊的数组,数组内的每一个对象其实就是我们常说的,桶内装的是Node对象,也就是我们放置到HashMap中的键值对。

HashMap的初始化

HashMap提供了几个不同的初始化方法,区别无非就是有没有初始化容量大小、有没有初始化对象、有没有初始化的loadFactor和threshold。

这几个概念需要我们一个个慢慢去了解。

  1. 容量
    就是HashMap中table数组的大小,HashMap的容量是2的n次方,初始化不设置容量的话,默认16,初始化如果设置了
    initialCapacity 的话,则HashMap的容量是最接近initialCapacity并且大于initialCapacity的2的整数次幂,比如initialCapacity设置为3,4,5则HaspMap最终容量为8,设置为9,10,11...则HashMap的最终容量为16,以此类推。

    这个容量计算是通过tableSizeFor方法实现的,我们暂时按下好奇心(这个方法为什么能实现大于输入参数cap的最近的2的整数次幂?)。

    static final int tableSizeFor(int cap) {
         int n = cap - 1;
         n |= n >>> 1;
         n |= n >>> 2;
         n |= n >>> 4;
         n |= n >>> 8;
         n |= n >>> 16;
         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
     }
  2. loadFactor
    直译为装载因子,意译为扩容因子,初始值设置为0.75。
  3. threshold
    threshold是扩容阈值,HashMap的容量*loadFactor=threshold。当HashMap存放对象的数量增长到threshold的时候进行扩容。
    比如HashMap初始化容量为16,默认loadFactor为0.75,则threshold=16*0.75=12。则当HashMap存储对象的数量(size)大于12的时候,HaspMap调用resize()方法自动扩容。
    4.size
    可以通过调用size()方法获取到,HashMap内实际存放的对象数。我们如果要想搞清楚HashMap的真面目,最好能对size和容量Capacity有清楚的认识。size是对应用很有价值的数据,我们开发过程中所说的一个HashMap的大小其实指的就是size。而Capacity对应用来说没有什么意义,只是HashMap内部使用的概念,只对那些对HashMap内部结构有兴趣、想要研究清楚其工作机制的同学有意义。

HashMap赋值

HashMap的赋值逻辑如下(假设待存放的数据为e):

  1. 检查table数组为空的话,初始化指定容量或者默认容量的table数组
  2. 根据key1的哈希值计算得出(算法为(容量 - 1) & hash(key1))对应的桶。这一步很重要,一般来讲优秀的hash算法能够尽可能确保不同的key值得到不同的hash值,也就可以确保放入不同的桶内。但是不可避免的,可能会存在不同key值得到相同hash值的情况(hash冲突:key1<>key2,hash(key1)=hash(key2)),这种情况下就会放置在相同的桶(比如table[5])内。
  3. 得到桶之后,判断桶内是否已经有数据。
  4. 没有数据则直接new一个Node:newNode(hash, key1, value1, null),放在桶中,结束。
  5. 否则,桶内有数据,有两种情况:一是为键值key1重复赋值、二是hash冲突。
  6. 如果是hash冲突,则new一个Node:newNode(hash, key1, value1, null)并将其设置为桶内的最后一个Node。
  7. 如果是重复赋值(桶内数据的key值=key1),则为key1重新赋值value1,并返回key1的旧值

所以我们可以看到,针对key而言,HashMap不重复,意思是说,相同的key只在HashMap中只保留一份数据。

并且,一般情况下,HashMap的一个桶内只保留一个对象,只有在hash冲突发生了之后,桶内才有可能放置多于一个对象,以链表结构保存。

HashMap中的null对象

此处null对象指的是HashMap中的key值为null的Node对象。

大家都知道HashMap允许且仅能存储key=null的一个对象,比如代码:

    HashMap hm = new HashMap();
    hm.put(null,"it's null");
    hm.put(null,"i am null");
    hm.put(null,"null loves null");

最终hm容器中只有一个null对象,并且hm.get(null)得到的应该是 "null loaves null"。

这背后的原因可以从上述HashMap赋值逻辑中找到答案,你只要知道null的hash值是0就可轻易得出以上结论。

从HashMap获取数据

通过get(key)方法获取数据的逻辑如下(假设要获取的数据key=key1):

  1. table数组不为空并且数组长度大于0,则采用与put数据相同的算法得到key1值对应的桶。
  2. 桶内不空则从第一个节点开始检查,如果节点key值等于key1,则返回该节点的value。如果第一个节点不满足条件,则依次检查桶内所有其他节点。
  3. 桶内空,或者桶内不空但是没有找到满足条件的对象(应该不可能)则返回null,表明当前HashMap中不存在key值为key1的对象

需要注意的一点是,检查节点key值等于key1的逻辑是:
两个对象相等,或者两个对象不为null且key1.equals(key)。

好了,以上!相信已经能够揭开HashMap神秘面纱之一角了。

你可能感兴趣的