查看: 393|回复: 0

JDK8中的HashMap实现原理及源码分析

[复制链接]
发表于 2020-2-4 08:29:30 | 显示全部楼层 |阅读模式
大纲

一.什么是Hash?什么是HashMap?

二.HashMap的内部实现机制



  • 1.HashMap根本元素

    • ①DEFAULT_INITIAL_CAPACITY&MAXIMUM_CAPACITY

    • ②DEFAULT_LOAD_FACTOR&loadFactor
    • ③size&threshold

  • 2.HashMap的构造函数
  • 3.HashMap的put添加功能实现

    • 第一步:table为空,则调用resize()函数创建一个
    • 第二步:计算元素所要储存的位置index,并对null做出处置惩罚

      • (1).取key的hashcode值:
      • (2).hashCode()的高16位异或低16位
      • (3). (n-1) & hash; 取余运算

    • 第三步,判定该链是否为红黑树并添加元素
    • 第四步:凌驾最大容量限制,扩容

  • 4.HashMap扩容机制的实现
本篇所述源码基于JDK1.8.0_121

一.什么是Hash?什么是HashMap?

Hash音译为“哈希”,直译为“散列”,是一种信息摘要算法,但他不是加密散列函数(或散列算法,又称哈希函数,英语:Hash function是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要,使得数据量变小,将数据的格式固定下来。该函数将数据打乱混合,重新创建一个叫做散列值(hash values,hash codes,hash sums,或hashes)的指纹(维基百科)。
我们平常常用的MD5,SSL等都属于Hash算法,通过Key进行Hash的计算,就可以获取Key对应的HashCode。
之前我们讲了ArrayList和LinkedList的优缺点——数组的特点是:寻址轻易,插入和删除困难;而链表的特点是:寻址困难,插入和删除轻易。
如果我们综合两者的特点,就可以得到本篇我们要讲的内容——HashMap(直译散列表,音译哈希表)。我们知道,java.util中的clloection集合类中, 最为常用的两种是List和Map类,我们之前将的ArrayList和LinkedList都是List集合类旗下的,而HashMap则是属于Map集合的阵营。为什么说HashMap集合了前面两种数据布局的特点呢?HashMap最常见的实现方法是拉链法——即一系列链表为数组元素组成的数组。如图:

从上图我们可以看到,HashMap由链表+数组组成,他的底层布局是一个数组,而数组的元素是一个单向链表。图中是一个长度为16位的数组,每个数组储存的元素代表的是每一个链表的头结点。
上面我们说了有关Hash算法的事情,通过Key进行Hash的计算,就可以获取Key对应的HashCode。好的Hash算法可以计算出几乎出独一无二的HashCode,如果出现了重复的hashCode,就称作碰撞,就算是MD5如许良好的算法也会发生碰撞,即两个不同的key也有可能天生雷同的MD5。
正常情况下,我们通过hash算法,往HashMap的数组中插入元素。如果发生了碰撞变乱,那么意味这数组的一个位置要插入两个或者多个元素,这个时候数组上面挂的链表起作用了,链表会将数组某个节点上多出的元素按照尾插法(jdk1.7及以前为头差法)的方式添加。
二.HashMap的内部实现机制

1.HashMap根本元素

  1. public class HashMap extends AbstractMap     implements Map, Cloneable, Serializable {     ......      //默认初始容量为16,这里这个数组的容量必须为2的n次幂。     static final int DEFAULT_INITIAL_CAPACITY = 1 >> 1;         n |= n >>> 2;         n |= n >>> 4;         n |= n >>> 8;         n |= n >>> 16;         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;     }
复制代码
cap是我们初始通报的Capacity值(或者默认的24),看注释我们可以知道,这么一系列位移操作算法最后是为了得到一个power of two size的值。为什么jdk中一再要强调这个2n这个值呢?这个等会我们再分析。
④Node[] table

最后来重点说说这个Node[] table,他是整个HashMap的组成子元素,是构成HashMap的一砖一瓦:
  1.     static class Node implements Map.Entry {         final int hash;     //每个储存元素key的哈希值         final K key;        //key         V value;            //value         Node next;     //链表下一个node          Node(int hash, K key, V value, Node next) {             this.hash = hash;             ......         }          public final K getKey()        { return key; }         public final V getValue()      { return value; }         public final String toString() { return key + "=" + value; }         public final int hashCode() { ...... }         public final V setValue(V newValue) { ...... }         public final boolean equals(Object o) { ....... }     }
复制代码
可以看到,这个Node[]是HashMap的一个内部类,他既是HashMap底层数组的组成元素,又是每个单向链表的组成元素。它此中包罗了数组元素所需要的key与value,以及链表所需要的指向下一个节点的引用域next。当然这个hash值是系统在创建Node时通过一定的算法计算出来的一个int值,之后我们会讲。
2.HashMap的构造函数

jdk1.8中,HashMap共有四种构造函数:
[code]    public HashMap(int initialCapacity, float loadFactor) {         if (initialCapacity < 0)             throw new IllegalArgumentException("Illegal initial capacity: " +                                                initialCapacity);         if (initialCapacity > MAXIMUM_CAPACITY)             initialCapacity = MAXIMUM_CAPACITY;         if (loadFactor

相关技术服务需求,请联系管理员和客服QQ:2753533861或QQ:619920289
您需要登录后才可以回帖 登录 | 用户注册

本版积分规则

帖子推荐:
客服咨询

QQ:2753533861

服务时间 9:00-22:00

快速回复 返回顶部 返回列表