关于java:初识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<K,V> 外部接口，这个 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<K,V> next;

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

HashMap 桶内 Node 链表容量增大之后会主动批改简略链表构造为红黑树，本篇暂不钻研红黑树。

table 数组
table 数组是 HashMap 真正存储数据的中央， 所以说白了 HashMap 底层实际上还是数组。

不过 HashMap 的 table 是比拟非凡的数组，数组内的每一个对象其实就是咱们常说的 桶，桶内装的是 Node<K,V> 对象，也就是咱们搁置到 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 <key1,value1>）：

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<String,String> = 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 神秘面纱之一角了。