【JAVA】HashMap底层实现原理浅谈

                                  HashMap底层实现原理浅谈

不论是实习还是正式工作，HashMap的底层实现原理一直是问地频率最高的一个内容，今天记录一下自己对HashMap的理解，如有不当之处，还请各位大佬指正。

---

一、前置名词解释

（1）哈希表

哈希表的主体躯干就是数组，我们可以利用下标对元素进行快速索引。新增一个元素时，元素的插入位置由哈希函数来定。

（2）哈希算法/哈希函数

哈希函数的作用是将一个不固定长度的二进制值经过运算，转化为一个固定长度的二进制值。将插入元素的key进行运算后，得到某个index值，从而确定在数组中的存储位置。但多个不相同的元素，经过哈希函数运算后，可能得到相同的index，这就出现了哈希冲突。

（3）哈希冲突/哈希碰撞

再好的哈希算法在有限长度的哈希表上，都会造成哈希冲突。那么怎么解决冲突呢？有多种解决方案

【1】开放地址法：放弃本次运算得到的index，继续寻找下一块未被占用的空间

【2】再散列法

【3】链地址法：采用数组（哈希表主体）+链表（为了解决哈希冲突而存在）的形式，哈希表中存储数组，数组中的元素空间存储链表的头结点。当发生冲突时，将相应的index位置上旧元素的指针next指向新元素即可。HashMap采用的就是这种方法。

---

二、HashMap的特点

（1）允许存放null键和null值，而HashTable都不允许

（2）不是线程安全的，而HashTable是线程安全的，当然我们可以使用ConcurrentHashMap来代替HashTable,而且ConcurrentHashMap的性能更好，因为它只对数组的一部分进行上锁，即分段锁，而不是锁住整个数组。

（3）数组的默认大小为16，源码中没有直接写16，而是1<<4。

  /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

（4）默认的负载因子是0.75，表示的是，如果数组中已经存储的元素个数大于数组长度的75%，将会引发扩容操作。

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

（5）扩容后，新数组的长度为原来数组的两倍。数组的默认大小与扩容倍数共同决定了数组长度永远是一个2的幂。

---

三、HashMap的实现原理

（1）HashMap的主干

HashMap的主干是一个Entry数组，里面存放Entry对象，每一个Entry对象包含（key,value）键值対和next指针以及对应的hash值。[jdk1.8之前用的是Entry，jdk1.8之后用的是Node，两者基本等价]

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

---

（2）put（key，value）的过程

【1】由key计算哈希值

【2】由哈希值计算在数组中的索引

【3】如果索引处的Entry为null的话，则直接在此处插入元素。如果索引出的Entry不为null的话，通过循环不断遍历链表查找是否有相同哈希值的key，如果有，再比较两个key的是否相同，当哈希值与key都相同时，则认为是同一个Entry对象并覆盖原对象的value值。当哈希值相同而key不相同时，则认为不是同一个Entry对象，那么在链表尾部新增元素。[jdk1.8之前插入链表头部，jdk1.8之后插入链表尾部]

当索引位置相同的key超过8个时，即链表长度大于8时，jdk1.8会将此链表转化为红黑树。

---

（3）get（key）的过程

【1】由key计算哈希值

【2】由哈希值计算在数组中的索引

【3】循环遍历链表，如果有某一个Entry的key与哈希值与搜索的key、哈希值都相同的话，则取出此key对应的value。

---

（4）扩容的过程

当数组中已经存储的元素个数大于数组长度的负载因子倍数时，将会引发扩容操作。

【1】创建一个长度为原来数组长度两倍的新数组。

【2】重新对原数组中的Entry对象进行哈希运算，以确定他们各自在新数组中的新位置。

当然扩容的过程也会有很多问题，比如在多线程的情况下，多个线程同时对数组进行扩容时，有可能会造成条件竞争，就会发生意料之外的结果。因此在多线程的情况下，还是得使用线程安全的HashMap，比如ConcurrentHashMap，或者是经过Collections.synchronized(HashMap<K,V>)封装后的HashMap。

---

四，总结

HashMap可以用在缓存处理，动态规划中的备忘录等，需要注意的是，HashMap不是线程安全的。

碍于博主才疏学浅，谈到的HashMap原理非常的粗浅，博主定会在日后的学习与工作中，不断的完善博文，努力提高博客的水准。