一、前言经历过面试程序的人都清楚明白, 作为Java程序员, 在面试期间, 这是最为极其特别常常会被提及询问的一个要点内容。可以这么讲, 要是对此不了解知晓, 简直不好意思宣称声称自己从事的是Java开发。基本上而言, 当你前去参与十家面试公司的面试过程时, 其中有七八家公司都会针对此问题对你提问查问。照此情形这般, 就在今天这个时日, 引领着大家一起从源码的角度层面去展开剖析查看, 具体究竟实实在在是怎样进行实现达成的。二、的构造方法1.构造方法我们先来看的四个构造方法//initialCapacity给定的初始化容量loadFactor扩容因子 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 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException(Illegal load factor: loadFactor); this.loadFactor loadFactor; this.threshold tableSizeFor(initialCapacity); } public HashMap(int initialCapacity) { //内部调用了上边的构造方法 this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap() {//空参构造 this.loadFactor DEFAULT_LOAD_FACTOR; // all other fields defaulted } public HashMap(Map m) {//构造传入一个map将map中的值放到hashmap中 this.loadFactor DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }2.构造方法里的方法刚才构造方法中提到了这个方法接下来就让我们一起看一下//该函数用于将一个map赋值给新的HashMap final void putMapEntries(Map m, boolean evict) { //定义变量接收旧hashmap的size int s m.size(); //判断s的容量是否大于0 if (s 0) { //判断当前数组有没有初始化 if (table null) { // pre-size ////求出以 旧hashmap数组容量为阈值 的数组容量赋值给ft float ft ((float)s / loadFactor) 1.0F; //判断是不是大于最大容量如果是赋值为最大容量否则将ft赋值给t int t ((ft (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); //判断t是否大于threshold(数组扩容阈值) if (t threshold) //通过tablesizefor方法求出大于等于t的最小2的次幂值赋值给threshold数组扩容阈值 threshold tableSizeFor(t); } //如果数组长度大于扩容阈值进行resize扩容操作 else if (s threshold) resize(); //循环遍历取出旧hashmap的值放入当前hashmap for (Map.Entry e : m.entrySet()) { K key e.getKey(); V value e.getValue(); putVal(hash(key), key, value, false, evict); } } } /* if (table null)分支是判断当前数组是否初始化因为在jdk1.8之后只有当你第一次放值时才会帮你创建16位的数组。 float ft ((float)s / loadFactor) 1.0F经过除运算再加上1.0F是为了向上取整 if (t threshold)注意一个细节做判断的的时候数组还没有初始化这里的threshold的值还是给定的数组长度的值也就是capacity的值 else if (s threshold)说明传入的map集合大于当前的扩容阈值需要进行resize扩容操作 */方法刚才方法中调用了方法接下来我们看一下这个方法。用处是: 在创建对象之际调用带有参数的构造, 把初始容量传进去, 其需要确保最初的长度是2的n次方的形式。有这样一种计算方式, 它所针对的是, 去算出大于、等于以及离传入进来的值最近有关的, 幂是2的n的数值, 举例而言, 假若是把15传入, 那么所算出的结果就会是16, 要是把17传入, 那么算出的结果将会是32。凭借二进制的位移操作, 头一回是在右边移动一位, 接下来第二次则是在右边移动两位, 然后第三次又来到右边移动四位, 诸如此类。借助五次这样的移位, 使得范围之内的所有位都转变成1模式, 高位部分补充0, 最终得出的那个结果再去加上1之后, 最后所计较算得的结果必定是2被n次乘方的数值。//这个方法的作用是找到大于等于给定容量的最小2的次幂值 //表示无符号右移也叫逻辑右移即若该数为正则高位补0而若该数为负数则右移后高位同样补0 7--》8 16--》16 static final int tableSizeFor(int cap) { //先将数组长度减1之所以在开始移位前先将容量-1是为了避免给定容量已经是8,16这样2的幂时不减一 直接移位会导致得到的结果比预期大。比如预期16得到应该是16直接移位的话会得到32。 int n cap - 1; //右移一位在进行或运算这个时候最高位和次高位就已经都是1此时是2个1 n | n 1; //右移两位在进行或运算这个时候由上次运算得出的两个1变成了四个1 n | n 2; //右移四位 n | n 4; //右移八位 n | n 8; //右移十六位这个时候所有的位数都变为了1 n | n 16; //n1操作是为了进1这个时候算出来的数值就一点是 2的n次幂 return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1; }移位的思想2的整数幂用二进制表示都是最高有效位为1其余全是0。对任意一个十进制数, 将其朝着转换为2的整数幂的方向进行转换, 其结果呈现出这样的特征, 那就是这个数本身的最高有效位的前一位会变成为1, 而最高有效位以及紧随其后的那些位, 都会转变为0。首先, 核心思想在于这样做, 先把最高有效位去以及在那之后紧接着的位全都变成1 , 然后, 最后还要再去做加上数值1这个操作, 如此就会产生进位到前面的那一位那儿成为了1 , 在那儿以后所有的只要达到满2的情况就全变成0。于此, 至关重要的就是怎样能够把最高有效位往后的统统都变成1。先移位再或运算。右移一位再或运算就有两位变为1右移两位再或运算就有四位变为1首先进行右移操作, 将这个数右移16位, 然后再进行或运算, 通过这种方式, 确保32位的全称为整型的整数在最高有效位之后的那些位, 都能够转变为1。以传入参数 24 为例24转换为二进制是11000如下图所示经过一次位移如下图所示经过第二次位移如下图经过第三次位移如下图经过第三次位移运算后, 所有位数都变为了 1, 后续存在第四次和第五次位移, 然而已经右移到了最低位, 所以这属于无意义操作针对当前数值 24 来讲, 要是数值很大, 第四次和第五次操作能够确保所有位数都是 1, 此时所有位数都是 1, 故而最后再给它加上 1, 得出的数值必定是 2 的 n 次幂, 而且是离传入值最近的 2 的 n 次幂的数值。得出的数值是一万一千一百一十一, 于二进制里进行加一操作, 从而变为, 再就此转换为十进制, 其结果是三十二。能够看出, 无论传入的数值具体是多少, 我们都能够在二进制状态下把它的所有位均转换为1。并且分别历经1次、2次、4次、8次、16次转换, 不管这个int类型的数值有多大, 我们都会对其进行转换, 只是当值比较小时, 或许会多做几次没有实际意义的操作。三、的底层原理先来看几个重要的参数static final int DEFAULT_INITIAL_CAPACITY 1 4; // 默认数组初始容量 static final int MAXIMUM_CAPACITY 1 30;//数组最大容量 static final float DEFAULT_LOAD_FACTOR 0.75f;//默认加载因子 static final int TREEIFY_THRESHOLD 8;//树化的阈值 static final int UNTREEIFY_THRESHOLD 6;//由树退化到链表的阈值 static final int MIN_TREEIFY_CAPACITY 64;//树化最小数组容量 //node节点继承了Map.entry,在Entry原有的K,V的基础上追加了hash和next字段 //分别表示key的hash值和下一个节点 static class Node implements Map.Entry { final int hash; final K key; V value; Node next; } //重写了计算hash的方法 //将 Hash 值的高 16 位右移并与原 Hash 值取异或运算(^)混合高 16 位和低 16 位的值 //得到一个更加散列的低 16 位的 Hash 值。 static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }在JDK1.8之前的实现方式 数组链表,然而, 在JDK1.8之后, 针对其进行了底层方面的优化, 将其改成了由数组与链表, 或者数组与红黑树来实现, 主要的目标是提升查找的效率。Jdk8通过数组与链表结合, 或者数组与红黑树相连接来实现, 当链表之内的元素数目大于等于8个之时, 若是数组的长度进一步大于等于64以后, 链表届时就会被转换成为红黑树而当个红黑树当中节点数量呈现小于等于6这样一种情况的时候, 又将会退减转变成先前模样那样返回到链表结构状态。在进行new ()操作时, 底层并未创建数组, 当首次调用put()方法这一动作发生时, 会触发调用方法, 进而在底层创建长度为16的数组, jdk8底层数组类型是: Node, 并非Entry, 通过用数组容量大小去乘以加载因子获取一个值, 随着情况发展, 一旦数组里所存储的元素个数超越该值, 便会触发调用方法, 促使将数组容量扩充至原来的两倍, 在执行数组扩容这一行为之际, 会生成一个全新的数组, 原来数组中的全部数据被要求重新计算哈希码值, 之后重新分配至新的数组之中, 所以数组扩容的操作在性能消耗方面影响突出。默认的, 负载因子大小呈现为0.75。数组大小呢, 是16。这意味着, 在默认情形下, 当其中元素个数超出16乘以0.75等于12的时候, 就会将数组的大小拓展为2乘以16等于32 , 也就是扩大了一倍。在我们Java里, 任一对象都存在, hash算法借助与自身开展向右位移16的异或运算得以实现。这般操作是为了让高位的16位hash能够参与到运算之中, 要让运算产生的hash值极其随机, 十分分散, 以及能让产生的数组下标足够随机。至于map.put(k,v) 的实现原理。1在最开始的时候, 把作为键的k与作为值的v封装进名为节点的Node对象里。接着, 先调用k所拥有的()方法从而得出哈希值, 再借助哈希算法将其所得到的哈希值转换成为仅仅是数组的下标。要是在下标所处的位置那里并未存在任何一个元素, 那么就会把Node添加到这个位置上去。要是下标所对应的地方存在链表的话, 在这个时候, 就会拿着k与链表上每一个节点所具备中的k去进行对应的equal操作。要是所有的方法返回的结果都是false, 那么这个全新的节点就会被添加到链表的末端。如果其中存在一个返回了true, 此时这个节点的value就会被覆盖掉。中的put()方法public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }()方法。final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; //判断数组是否未初始化 if ((tab table) null || (n tab.length) 0) //如果未初始化调用resize方法 进行初始化 n (tab resize()).length; //通过 运算求出该数据key的数组下标并判断该下标位置是否有数据 if ((p tab[i (n - 1) hash]) null) //如果没有直接将数据放在该下标位置 tab[i] newNode(hash, key, value, null); //该数组下标有数据的情况 else { Node e; K k; //判断该位置数据的key和新来的数据是否一样 if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) //如果一样证明为修改操作该节点的数据赋值给e,后边会用到 e p; //判断是不是红黑树 else if (p instanceof TreeNode) //如果是红黑树的话进行红黑树的操作 e ((TreeNode)p).putTreeVal(this, tab, hash, key, value); //新数据和当前数组既不相同也不是红黑树节点证明是链表 else { //遍历链表 for (int binCount 0; ; binCount) { //判断next节点如果为空的话证明遍历到链表尾部了 if ((e p.next) null) { //把新值放入链表尾部 p.next newNode(hash, key, value, null); //因为新插入了一条数据所以判断链表长度是不是大于等于8 if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1st //如果是进行转换红黑树操作 treeifyBin(tab, hash); break; } //判断链表当中有数据相同的值如果一样证明为修改操作 if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) break; //把下一个节点赋值为当前节点 p e; } } //判断e是否为空e值为修改操作存放原数据的变量 if (e ! null) { // existing mapping for key //不为空的话证明是修改操作取出老值 V oldValue e.value; //一定会执行 onlyIfAbsent传进来的是false if (!onlyIfAbsent || oldValue null) //将新值赋值当前节点 e.value value; afterNodeAccess(e); //返回老值 return oldValue; } } //计数器计算当前节点的修改次数 modCount; //当前数组中的数据数量如果大于扩容阈值 if (size threshold) //进行扩容操作 resize(); //空方法 afterNodeInsertion(evict); //添加操作时 返回空值 return null; }map中方法//扩容、初始化数组 final Node[] resize() { Node[] oldTab table; //如果当前数组为null的时候把oldCap老数组容量设置为0 int oldCap (oldTab null) ? 0 : oldTab.length; //老的扩容阈值 int oldThr threshold; int newCap, newThr 0; //判断数组容量是否大于0大于0说明数组已经初始化 if (oldCap 0) { //判断当前数组长度是否大于最大数组长度 if (oldCap MAXIMUM_CAPACITY) { //如果是将扩容阈值直接设置为int类型的最大数值并直接返回 threshold Integer.MAX_VALUE; return oldTab; } //如果在最大长度范围内则需要扩容 OldCap 1等价于oldCap*2 //运算过后判断是不是最大值并且oldCap需要大于16 else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY) newThr oldThr 1; // double threshold 等价于oldThr*2 } //如果oldCap0但是已经初始化了像把元素删除完之后的情况那么它的临界值肯定还存在 如果是首次初始化它的临界值则为0 else if (oldThr 0) // initial capacity was placed in threshold newCap oldThr; //数组未初始化的情况将阈值和扩容因子都设置为默认值 else { // zero initial threshold signifies using defaults newCap DEFAULT_INITIAL_CAPACITY; newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //初始化容量小于16的时候扩容阈值是没有赋值的 if (newThr 0) { //创建阈值 float ft (float)newCap * loadFactor; //判断新容量和新阈值是否大于最大容量 newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } //计算出来的阈值赋值 threshold newThr; SuppressWarnings({rawtypes,unchecked}) //根据上边计算得出的容量 创建新的数组 Node[] newTab (Node[])new Node[newCap]; //赋值 table newTab; //扩容操作判断不为空证明不是初始化数组 if (oldTab ! null) { //遍历数组 for (int j 0; j oldCap; j) { Node e; //判断当前下标为j的数组如果不为空的话赋值个e进行下一步操作 if ((e oldTab[j]) ! null) { //将数组位置置空 oldTab[j] null; //判断是否有下个节点 if (e.next null) //如果没有就重新计算在新数组中的下标并放进去 newTab[e.hash (newCap - 1)] e; //有下个节点的情况并且判断是否已经树化 else if (e instanceof TreeNode) //进行红黑树的操作 ((TreeNode)e).split(this, newTab, j, oldCap); //有下个节点的情况并且没有树化链表形式 else { //比如老数组容量是16那下标就为0-15 //扩容操作*2容量就变为32下标为0-31 //低位0-15高位16-31 //定义了四个变量 // 低位头 低位尾 Node loHead null, loTail null; // 高位头 高位尾 Node hiHead null, hiTail null; //下个节点 Node next; //循环遍历 do { //取出next节点 next e.next; //通过 与操作 计算得出结果为0 if ((e.hash oldCap) 0) { //如果低位尾为null证明当前数组位置为空没有任何数据 if (loTail null) //将e值放入低位头 loHead e; //低位尾不为null证明已经有数据了 else //将数据放入next节点 loTail.next e; //记录低位尾数据 loTail e; } //通过 与操作 计算得出结果不为0 else { //如果高位尾为null证明当前数组位置为空没有任何数据 if (hiTail null) //将e值放入高位头 hiHead e; //高位尾不为null证明已经有数据了 else //将数据放入next节点 hiTail.next e; //记录高位尾数据 hiTail e; } //如果e不为空证明没有到链表尾部继续执行循环 } while ((e next) ! null); //低位尾如果记录的有数据是链表 if (loTail ! null) { //将下一个元素置空 loTail.next null; //将低位头放入新数组的原下标位置 newTab[j] loHead; } //高位尾如果记录的有数据是链表 if (hiTail ! null) { //将下一个元素置空 hiTail.next null; //将高位头放入新数组的(原下标原数组容量)位置 newTab[j oldCap] hiHead; } } } } } //返回新的数组对象 return newTab; }map.get(k)实现原理(1)事先去调用k的括号方法从而得出对应的哈希值, 并借助哈希算法将其转换形成数组的下标。在经由数组下标迅速地定位到某一个位置之上。着重去理解要是这个位置上什么东西也没有, 那就返回null。要是这个位置上存在单向链表, 那么它就会携带着参数K跟单向链表上的每一个节点的K展开比方, 要是所有的方法全都返回false, 那么get方法就返回null。若是其中一个节点的K跟参数K进行返回true, 那么在这个时候, 该节点的value便是我们所要找的value了, get方法最终返回这个所要找的value。中的get()方法public V get(Object key) { Node e; return (e getNode(hash(key), key)) null ? null : e.value; }()方法final Node getNode(int hash, Object key) { Node[] tab; Node first, e; int n; K k; //判断数组不为null并且长度大于0并且通过hash算出来的数组下标的位置不为空证明有数据 if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) { //判断数组的位置的key的hash和内容是否等同与要查询的数据 if (first.hash hash // always check first node ((k first.key) key || (key ! null key.equals(k)))) //相等的话直接返回 return first; //判断是否有下个节点 if ((e first.next) ! null) { //判断是否为为红黑树 if (first instanceof TreeNode) //进行红黑树查询操作 return ((TreeNode)first).getTreeNode(hash, key); //链表查询操作 do { //循环链表逐一判断 if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) //发现key的话就返回 return e; } while ((e e.next) ! null); } } //没有查询到返回null return null; }四、常见面试题分析为何的数组长度一定是2的次幂首先, 初始化的数组长度必定是 2 的 n 次幂的值, 每次要是扩容都保持为原来的 2 倍之举, 那就不会把这个规律给打破, 每次扩容之后, 原数据都将会进行数据迁移, 按照二进制的运算要求扩容之后的数据要么处于原来那里, 要么处于【原来位置加上当时的扩容长度】, 如此一来就用不着重新进行 hash 操作, 效率也就会更高些。当中, 要是想把数据存入, 首先它得依据key的哈希值, 去确定落入哪一个桶里。的做法我总结的是三步无符号右移、^异或、与具体而言: 拿着key的哈希值, 先进行“”无符号右移16位的操作, 接着“^”异或上key的哈希值, 进而得到一个值再拿着这个值去“”数组长度减一, 请查看结果返回值运算, 请查看结果返回值运算。最后会得出一个数, 倘若数组长度为15, 那么这个数便是处于0至15之间的一个数, 此数即是所得到的数组脚标位置, 而这位置也就是要存入的桶的位置。根据上边所能够明确的情况来看, 待确定的是, 找到定位桶的位置这一操作, 最终是要开展一次 “” 与运算的, 在进行该与运算之后, 会得出一个数值, 而这个数值实际上就是桶的位置。知道了这些以后再来说为什么的长度之所以一定是2的次幂至少有以下两个原因1、若其长度属于2的次幂范畴, 那么能够促使数据呈现出更为散列且更为均匀的分布态势, 进而更为充分地运用数组的空间。怎么理解呢下面举例说明, 若不是2的次幂的数, 假设数组长度为奇数, 那么参与最后的运算的必定是偶数, 对于偶数而言, 其二进制最后一个低位必定是0, 以0进行运算的结果肯定是0, 那就意味着完后得到的数的最低位必定是0, 最低位是0的话, 则表明一定是偶数, 也就是说: 完得到的数一定是偶数, 所以完获取到的脚标永远是偶数位, 这意味着奇数位的脚标永远都无值, 有一半的空间是被浪费的。说完奇数, 再来说偶数, 假设数组长度是偶数, 例如6, 那参与运算的就是5, 5的二进制是00, 发现任何一个数与5进行运算, 倒数第二低位永远是0, 那意味着完以后, 起码肯定得不出2或者3这点刚开始不好理解, 但好好思考就能明白, 意味着第二和第三脚标位肯定不会有值。万一它是偶数, 那不像奇数那般夸张, 会有一半的脚标位得不到? 但总归, 有部分脚标位是得不到的。因而, 若不是2的次幂, 无论奇数还是偶数, 必定那就注定了一些脚标位永远没值 , 而一些脚标位永远没值, 这意味着浪费空间, 会使数据散列不充分, 对其而言这绝对是场灾难2、的长度必然是2的次幂, 存在另外一个缘由, 即于扩容迁移之际无需再度借助哈希去定位新的位置。扩容之后, 元素新的位置, 要么处于原脚标位, 要么处于原脚标位加上扩容长度这般的一个位置。比如扩容前长度是8扩容后长度是16 第一种情况 扩容前 00000000 00000000 00000000 00000101 00000000 00000000 00000000 00000111 8-17 ------------------------------------- 101 5 原来脚标位是5 扩容后 00000000 00000000 00000000 00000101 00000000 00000000 00000000 00001111 16-115 ------------------------------------- 101 5 扩容后脚标位是5原脚标位 第二种情况 扩容前 00000000 00000000 00000000 00001101 00000000 00000000 00000000 00000111 8-17 ------------------------------------- 101 5 原来脚标位是5 扩容后 00000000 00000000 00000000 00001101 00000000 00000000 00000000 00001111 16-115 ------------------------------------- 1101 13 扩容后脚标位是13原脚标位扩容长度扩容之后, 究竟是处于原来的位置, 还是处于原脚标位加上扩容长度的位置呢? 关键在于新扩容那最左边的一个1, 其所对应的上方数字是0还是1。要是这个数字是0, 那么扩容以后就在原来位置要是这个数字是1, 那么扩容以后就在原脚标位加上扩容长度的位置。源码里面的扩容也是这样进行操作的。换言之, 这跟hashn - 1此计算是有关系的。要是n并非2的n次方, 且n不等于2, 那么在转换为二进制情形下, n - 1会存在某一位是0, 这样与hash进行运算后, 该位置将始终为0, 进而计算得出的数组位置会始终存在某个下标对应的数组位置呈现为空的状态, 也就是说这个位置永远不会有值。JDK1.7中形成的环形链表线程一读取到当前的情况在准备扩容时线程二介入线程二读取进行扩容线程一继续执行这个线程, 首先使得A进到新的链表那儿, 接着把B插进链条开头, 鉴于因另一个线程造成情况, B的随后部分指向了A, 于是B箭头A箭头B, 构成了循环。JDK1.8中的性能优化JDK1.8在1.7的基础上对一些操作进行了优化。不同JDK1.7JDK1.8存储结构数组链表数组链表红黑树初始化方式单独函数集成至扩容方法hash值计算方式扰动处理9次扰动4次位运算5次异或运算扰动处理2次扰动1次位运算1次异或运算存放数据规则无冲突时存放数组冲突时存放链表无冲突时存放数组冲突链表长度8:树化并存放红黑树插入数据方式头插法将原位置的数据移动到后一位再插入数据到该位置尾插法 直接插入链表尾部/红黑树扩容后存储位置的计算方式所有的都依照原本的方式去开展运算, 括号当中的内容, 转换成扰动函数, 再对其进行(h与负1按位与)的操作。依据扩容之后的规则来进行计算, 此计算规则为, 扩容之后的位置等于原来的位置, 又或者是原来的位置加上旧有的容量。留意: 在JDK1.8之中, 当转换成为红黑树之际, 数组的长度必然要大于64, 要是数组的长度小于64, 而链表的长度达到8, 将会去进行扩容行动。五、总结看到此处, 我们对于其源码以及实现已然有了明晰的理解, 而且针对它的构造方法, 直至它的一个put数据以及get数据的源头代码剖析, 另外其里边较为精巧且关键的一些方法也都探究透彻了。 期望这些知识要点在往后大家的面试里也能够对大家有所助益, 从而获取一个中意的雇用通知。 Java面试必问：HashMap源码深度解析
一、前言经历过面试程序的人都清楚明白, 作为Java程序员, 在面试期间, 这是最为极其特别常常会被提及询问的一个要点内容。可以这么讲, 要是对此不了解知晓, 简直不好意思宣称声称自己从事的是Java开发。基本上而言, 当你前去参与十家面试公司的面试过程时, 其中有七八家公司都会针对此问题对你提问查问。照此情形这般, 就在今天这个时日, 引领着大家一起从源码的角度层面去展开剖析查看, 具体究竟实实在在是怎样进行实现达成的。二、的构造方法1.构造方法我们先来看的四个构造方法//initialCapacity给定的初始化容量loadFactor扩容因子 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 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException(Illegal load factor: loadFactor); this.loadFactor loadFactor; this.threshold tableSizeFor(initialCapacity); } public HashMap(int initialCapacity) { //内部调用了上边的构造方法 this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap() {//空参构造 this.loadFactor DEFAULT_LOAD_FACTOR; // all other fields defaulted } public HashMap(Map m) {//构造传入一个map将map中的值放到hashmap中 this.loadFactor DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }2.构造方法里的方法刚才构造方法中提到了这个方法接下来就让我们一起看一下//该函数用于将一个map赋值给新的HashMap final void putMapEntries(Map m, boolean evict) { //定义变量接收旧hashmap的size int s m.size(); //判断s的容量是否大于0 if (s 0) { //判断当前数组有没有初始化 if (table null) { // pre-size ////求出以 旧hashmap数组容量为阈值 的数组容量赋值给ft float ft ((float)s / loadFactor) 1.0F; //判断是不是大于最大容量如果是赋值为最大容量否则将ft赋值给t int t ((ft (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); //判断t是否大于threshold(数组扩容阈值) if (t threshold) //通过tablesizefor方法求出大于等于t的最小2的次幂值赋值给threshold数组扩容阈值 threshold tableSizeFor(t); } //如果数组长度大于扩容阈值进行resize扩容操作 else if (s threshold) resize(); //循环遍历取出旧hashmap的值放入当前hashmap for (Map.Entry e : m.entrySet()) { K key e.getKey(); V value e.getValue(); putVal(hash(key), key, value, false, evict); } } } /* if (table null)分支是判断当前数组是否初始化因为在jdk1.8之后只有当你第一次放值时才会帮你创建16位的数组。 float ft ((float)s / loadFactor) 1.0F经过除运算再加上1.0F是为了向上取整 if (t threshold)注意一个细节做判断的的时候数组还没有初始化这里的threshold的值还是给定的数组长度的值也就是capacity的值 else if (s threshold)说明传入的map集合大于当前的扩容阈值需要进行resize扩容操作 */方法刚才方法中调用了方法接下来我们看一下这个方法。用处是: 在创建对象之际调用带有参数的构造, 把初始容量传进去, 其需要确保最初的长度是2的n次方的形式。有这样一种计算方式, 它所针对的是, 去算出大于、等于以及离传入进来的值最近有关的, 幂是2的n的数值, 举例而言, 假若是把15传入, 那么所算出的结果就会是16, 要是把17传入, 那么算出的结果将会是32。凭借二进制的位移操作, 头一回是在右边移动一位, 接下来第二次则是在右边移动两位, 然后第三次又来到右边移动四位, 诸如此类。借助五次这样的移位, 使得范围之内的所有位都转变成1模式, 高位部分补充0, 最终得出的那个结果再去加上1之后, 最后所计较算得的结果必定是2被n次乘方的数值。//这个方法的作用是找到大于等于给定容量的最小2的次幂值 //表示无符号右移也叫逻辑右移即若该数为正则高位补0而若该数为负数则右移后高位同样补0 7--》8 16--》16 static final int tableSizeFor(int cap) { //先将数组长度减1之所以在开始移位前先将容量-1是为了避免给定容量已经是8,16这样2的幂时不减一 直接移位会导致得到的结果比预期大。比如预期16得到应该是16直接移位的话会得到32。 int n cap - 1; //右移一位在进行或运算这个时候最高位和次高位就已经都是1此时是2个1 n | n 1; //右移两位在进行或运算这个时候由上次运算得出的两个1变成了四个1 n | n 2; //右移四位 n | n 4; //右移八位 n | n 8; //右移十六位这个时候所有的位数都变为了1 n | n 16; //n1操作是为了进1这个时候算出来的数值就一点是 2的n次幂 return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1; }移位的思想2的整数幂用二进制表示都是最高有效位为1其余全是0。对任意一个十进制数, 将其朝着转换为2的整数幂的方向进行转换, 其结果呈现出这样的特征, 那就是这个数本身的最高有效位的前一位会变成为1, 而最高有效位以及紧随其后的那些位, 都会转变为0。首先, 核心思想在于这样做, 先把最高有效位去以及在那之后紧接着的位全都变成1 , 然后, 最后还要再去做加上数值1这个操作, 如此就会产生进位到前面的那一位那儿成为了1 , 在那儿以后所有的只要达到满2的情况就全变成0。于此, 至关重要的就是怎样能够把最高有效位往后的统统都变成1。先移位再或运算。右移一位再或运算就有两位变为1右移两位再或运算就有四位变为1首先进行右移操作, 将这个数右移16位, 然后再进行或运算, 通过这种方式, 确保32位的全称为整型的整数在最高有效位之后的那些位, 都能够转变为1。以传入参数 24 为例24转换为二进制是11000如下图所示经过一次位移如下图所示经过第二次位移如下图经过第三次位移如下图经过第三次位移运算后, 所有位数都变为了 1, 后续存在第四次和第五次位移, 然而已经右移到了最低位, 所以这属于无意义操作针对当前数值 24 来讲, 要是数值很大, 第四次和第五次操作能够确保所有位数都是 1, 此时所有位数都是 1, 故而最后再给它加上 1, 得出的数值必定是 2 的 n 次幂, 而且是离传入值最近的 2 的 n 次幂的数值。得出的数值是一万一千一百一十一, 于二进制里进行加一操作, 从而变为, 再就此转换为十进制, 其结果是三十二。能够看出, 无论传入的数值具体是多少, 我们都能够在二进制状态下把它的所有位均转换为1。并且分别历经1次、2次、4次、8次、16次转换, 不管这个int类型的数值有多大, 我们都会对其进行转换, 只是当值比较小时, 或许会多做几次没有实际意义的操作。三、的底层原理先来看几个重要的参数static final int DEFAULT_INITIAL_CAPACITY 1 4; // 默认数组初始容量 static final int MAXIMUM_CAPACITY 1 30;//数组最大容量 static final float DEFAULT_LOAD_FACTOR 0.75f;//默认加载因子 static final int TREEIFY_THRESHOLD 8;//树化的阈值 static final int UNTREEIFY_THRESHOLD 6;//由树退化到链表的阈值 static final int MIN_TREEIFY_CAPACITY 64;//树化最小数组容量 //node节点继承了Map.entry,在Entry原有的K,V的基础上追加了hash和next字段 //分别表示key的hash值和下一个节点 static class Node implements Map.Entry { final int hash; final K key; V value; Node next; } //重写了计算hash的方法 //将 Hash 值的高 16 位右移并与原 Hash 值取异或运算(^)混合高 16 位和低 16 位的值 //得到一个更加散列的低 16 位的 Hash 值。 static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }在JDK1.8之前的实现方式 数组链表,然而, 在JDK1.8之后, 针对其进行了底层方面的优化, 将其改成了由数组与链表, 或者数组与红黑树来实现, 主要的目标是提升查找的效率。Jdk8通过数组与链表结合, 或者数组与红黑树相连接来实现, 当链表之内的元素数目大于等于8个之时, 若是数组的长度进一步大于等于64以后, 链表届时就会被转换成为红黑树而当个红黑树当中节点数量呈现小于等于6这样一种情况的时候, 又将会退减转变成先前模样那样返回到链表结构状态。在进行new ()操作时, 底层并未创建数组, 当首次调用put()方法这一动作发生时, 会触发调用方法, 进而在底层创建长度为16的数组, jdk8底层数组类型是: Node, 并非Entry, 通过用数组容量大小去乘以加载因子获取一个值, 随着情况发展, 一旦数组里所存储的元素个数超越该值, 便会触发调用方法, 促使将数组容量扩充至原来的两倍, 在执行数组扩容这一行为之际, 会生成一个全新的数组, 原来数组中的全部数据被要求重新计算哈希码值, 之后重新分配至新的数组之中, 所以数组扩容的操作在性能消耗方面影响突出。默认的, 负载因子大小呈现为0.75。数组大小呢, 是16。这意味着, 在默认情形下, 当其中元素个数超出16乘以0.75等于12的时候, 就会将数组的大小拓展为2乘以16等于32 , 也就是扩大了一倍。在我们Java里, 任一对象都存在, hash算法借助与自身开展向右位移16的异或运算得以实现。这般操作是为了让高位的16位hash能够参与到运算之中, 要让运算产生的hash值极其随机, 十分分散, 以及能让产生的数组下标足够随机。至于map.put(k,v) 的实现原理。1在最开始的时候, 把作为键的k与作为值的v封装进名为节点的Node对象里。接着, 先调用k所拥有的()方法从而得出哈希值, 再借助哈希算法将其所得到的哈希值转换成为仅仅是数组的下标。要是在下标所处的位置那里并未存在任何一个元素, 那么就会把Node添加到这个位置上去。要是下标所对应的地方存在链表的话, 在这个时候, 就会拿着k与链表上每一个节点所具备中的k去进行对应的equal操作。要是所有的方法返回的结果都是false, 那么这个全新的节点就会被添加到链表的末端。如果其中存在一个返回了true, 此时这个节点的value就会被覆盖掉。中的put()方法public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }()方法。final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; //判断数组是否未初始化 if ((tab table) null || (n tab.length) 0) //如果未初始化调用resize方法 进行初始化 n (tab resize()).length; //通过 运算求出该数据key的数组下标并判断该下标位置是否有数据 if ((p tab[i (n - 1) hash]) null) //如果没有直接将数据放在该下标位置 tab[i] newNode(hash, key, value, null); //该数组下标有数据的情况 else { Node e; K k; //判断该位置数据的key和新来的数据是否一样 if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) //如果一样证明为修改操作该节点的数据赋值给e,后边会用到 e p; //判断是不是红黑树 else if (p instanceof TreeNode) //如果是红黑树的话进行红黑树的操作 e ((TreeNode)p).putTreeVal(this, tab, hash, key, value); //新数据和当前数组既不相同也不是红黑树节点证明是链表 else { //遍历链表 for (int binCount 0; ; binCount) { //判断next节点如果为空的话证明遍历到链表尾部了 if ((e p.next) null) { //把新值放入链表尾部 p.next newNode(hash, key, value, null); //因为新插入了一条数据所以判断链表长度是不是大于等于8 if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1st //如果是进行转换红黑树操作 treeifyBin(tab, hash); break; } //判断链表当中有数据相同的值如果一样证明为修改操作 if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) break; //把下一个节点赋值为当前节点 p e; } } //判断e是否为空e值为修改操作存放原数据的变量 if (e ! null) { // existing mapping for key //不为空的话证明是修改操作取出老值 V oldValue e.value; //一定会执行 onlyIfAbsent传进来的是false if (!onlyIfAbsent || oldValue null) //将新值赋值当前节点 e.value value; afterNodeAccess(e); //返回老值 return oldValue; } } //计数器计算当前节点的修改次数 modCount; //当前数组中的数据数量如果大于扩容阈值 if (size threshold) //进行扩容操作 resize(); //空方法 afterNodeInsertion(evict); //添加操作时 返回空值 return null; }map中方法//扩容、初始化数组 final Node[] resize() { Node[] oldTab table; //如果当前数组为null的时候把oldCap老数组容量设置为0 int oldCap (oldTab null) ? 0 : oldTab.length; //老的扩容阈值 int oldThr threshold; int newCap, newThr 0; //判断数组容量是否大于0大于0说明数组已经初始化 if (oldCap 0) { //判断当前数组长度是否大于最大数组长度 if (oldCap MAXIMUM_CAPACITY) { //如果是将扩容阈值直接设置为int类型的最大数值并直接返回 threshold Integer.MAX_VALUE; return oldTab; } //如果在最大长度范围内则需要扩容 OldCap 1等价于oldCap*2 //运算过后判断是不是最大值并且oldCap需要大于16 else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY) newThr oldThr 1; // double threshold 等价于oldThr*2 } //如果oldCap0但是已经初始化了像把元素删除完之后的情况那么它的临界值肯定还存在 如果是首次初始化它的临界值则为0 else if (oldThr 0) // initial capacity was placed in threshold newCap oldThr; //数组未初始化的情况将阈值和扩容因子都设置为默认值 else { // zero initial threshold signifies using defaults newCap DEFAULT_INITIAL_CAPACITY; newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //初始化容量小于16的时候扩容阈值是没有赋值的 if (newThr 0) { //创建阈值 float ft (float)newCap * loadFactor; //判断新容量和新阈值是否大于最大容量 newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } //计算出来的阈值赋值 threshold newThr; SuppressWarnings({rawtypes,unchecked}) //根据上边计算得出的容量 创建新的数组 Node[] newTab (Node[])new Node[newCap]; //赋值 table newTab; //扩容操作判断不为空证明不是初始化数组 if (oldTab ! null) { //遍历数组 for (int j 0; j oldCap; j) { Node e; //判断当前下标为j的数组如果不为空的话赋值个e进行下一步操作 if ((e oldTab[j]) ! null) { //将数组位置置空 oldTab[j] null; //判断是否有下个节点 if (e.next null) //如果没有就重新计算在新数组中的下标并放进去 newTab[e.hash (newCap - 1)] e; //有下个节点的情况并且判断是否已经树化 else if (e instanceof TreeNode) //进行红黑树的操作 ((TreeNode)e).split(this, newTab, j, oldCap); //有下个节点的情况并且没有树化链表形式 else { //比如老数组容量是16那下标就为0-15 //扩容操作*2容量就变为32下标为0-31 //低位0-15高位16-31 //定义了四个变量 // 低位头 低位尾 Node loHead null, loTail null; // 高位头 高位尾 Node hiHead null, hiTail null; //下个节点 Node next; //循环遍历 do { //取出next节点 next e.next; //通过 与操作 计算得出结果为0 if ((e.hash oldCap) 0) { //如果低位尾为null证明当前数组位置为空没有任何数据 if (loTail null) //将e值放入低位头 loHead e; //低位尾不为null证明已经有数据了 else //将数据放入next节点 loTail.next e; //记录低位尾数据 loTail e; } //通过 与操作 计算得出结果不为0 else { //如果高位尾为null证明当前数组位置为空没有任何数据 if (hiTail null) //将e值放入高位头 hiHead e; //高位尾不为null证明已经有数据了 else //将数据放入next节点 hiTail.next e; //记录高位尾数据 hiTail e; } //如果e不为空证明没有到链表尾部继续执行循环 } while ((e next) ! null); //低位尾如果记录的有数据是链表 if (loTail ! null) { //将下一个元素置空 loTail.next null; //将低位头放入新数组的原下标位置 newTab[j] loHead; } //高位尾如果记录的有数据是链表 if (hiTail ! null) { //将下一个元素置空 hiTail.next null; //将高位头放入新数组的(原下标原数组容量)位置 newTab[j oldCap] hiHead; } } } } } //返回新的数组对象 return newTab; }map.get(k)实现原理(1)事先去调用k的括号方法从而得出对应的哈希值, 并借助哈希算法将其转换形成数组的下标。在经由数组下标迅速地定位到某一个位置之上。着重去理解要是这个位置上什么东西也没有, 那就返回null。要是这个位置上存在单向链表, 那么它就会携带着参数K跟单向链表上的每一个节点的K展开比方, 要是所有的方法全都返回false, 那么get方法就返回null。若是其中一个节点的K跟参数K进行返回true, 那么在这个时候, 该节点的value便是我们所要找的value了, get方法最终返回这个所要找的value。中的get()方法public V get(Object key) { Node e; return (e getNode(hash(key), key)) null ? null : e.value; }()方法final Node getNode(int hash, Object key) { Node[] tab; Node first, e; int n; K k; //判断数组不为null并且长度大于0并且通过hash算出来的数组下标的位置不为空证明有数据 if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) { //判断数组的位置的key的hash和内容是否等同与要查询的数据 if (first.hash hash // always check first node ((k first.key) key || (key ! null key.equals(k)))) //相等的话直接返回 return first; //判断是否有下个节点 if ((e first.next) ! null) { //判断是否为为红黑树 if (first instanceof TreeNode) //进行红黑树查询操作 return ((TreeNode)first).getTreeNode(hash, key); //链表查询操作 do { //循环链表逐一判断 if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) //发现key的话就返回 return e; } while ((e e.next) ! null); } } //没有查询到返回null return null; }四、常见面试题分析为何的数组长度一定是2的次幂首先, 初始化的数组长度必定是 2 的 n 次幂的值, 每次要是扩容都保持为原来的 2 倍之举, 那就不会把这个规律给打破, 每次扩容之后, 原数据都将会进行数据迁移, 按照二进制的运算要求扩容之后的数据要么处于原来那里, 要么处于【原来位置加上当时的扩容长度】, 如此一来就用不着重新进行 hash 操作, 效率也就会更高些。当中, 要是想把数据存入, 首先它得依据key的哈希值, 去确定落入哪一个桶里。的做法我总结的是三步无符号右移、^异或、与具体而言: 拿着key的哈希值, 先进行“”无符号右移16位的操作, 接着“^”异或上key的哈希值, 进而得到一个值再拿着这个值去“”数组长度减一, 请查看结果返回值运算, 请查看结果返回值运算。最后会得出一个数, 倘若数组长度为15, 那么这个数便是处于0至15之间的一个数, 此数即是所得到的数组脚标位置, 而这位置也就是要存入的桶的位置。根据上边所能够明确的情况来看, 待确定的是, 找到定位桶的位置这一操作, 最终是要开展一次 “” 与运算的, 在进行该与运算之后, 会得出一个数值, 而这个数值实际上就是桶的位置。知道了这些以后再来说为什么的长度之所以一定是2的次幂至少有以下两个原因1、若其长度属于2的次幂范畴, 那么能够促使数据呈现出更为散列且更为均匀的分布态势, 进而更为充分地运用数组的空间。怎么理解呢下面举例说明, 若不是2的次幂的数, 假设数组长度为奇数, 那么参与最后的运算的必定是偶数, 对于偶数而言, 其二进制最后一个低位必定是0, 以0进行运算的结果肯定是0, 那就意味着完后得到的数的最低位必定是0, 最低位是0的话, 则表明一定是偶数, 也就是说: 完得到的数一定是偶数, 所以完获取到的脚标永远是偶数位, 这意味着奇数位的脚标永远都无值, 有一半的空间是被浪费的。说完奇数, 再来说偶数, 假设数组长度是偶数, 例如6, 那参与运算的就是5, 5的二进制是00, 发现任何一个数与5进行运算, 倒数第二低位永远是0, 那意味着完以后, 起码肯定得不出2或者3这点刚开始不好理解, 但好好思考就能明白, 意味着第二和第三脚标位肯定不会有值。万一它是偶数, 那不像奇数那般夸张, 会有一半的脚标位得不到? 但总归, 有部分脚标位是得不到的。因而, 若不是2的次幂, 无论奇数还是偶数, 必定那就注定了一些脚标位永远没值 , 而一些脚标位永远没值, 这意味着浪费空间, 会使数据散列不充分, 对其而言这绝对是场灾难2、的长度必然是2的次幂, 存在另外一个缘由, 即于扩容迁移之际无需再度借助哈希去定位新的位置。扩容之后, 元素新的位置, 要么处于原脚标位, 要么处于原脚标位加上扩容长度这般的一个位置。比如扩容前长度是8扩容后长度是16 第一种情况 扩容前 00000000 00000000 00000000 00000101 00000000 00000000 00000000 00000111 8-17 ------------------------------------- 101 5 原来脚标位是5 扩容后 00000000 00000000 00000000 00000101 00000000 00000000 00000000 00001111 16-115 ------------------------------------- 101 5 扩容后脚标位是5原脚标位 第二种情况 扩容前 00000000 00000000 00000000 00001101 00000000 00000000 00000000 00000111 8-17 ------------------------------------- 101 5 原来脚标位是5 扩容后 00000000 00000000 00000000 00001101 00000000 00000000 00000000 00001111 16-115 ------------------------------------- 1101 13 扩容后脚标位是13原脚标位扩容长度扩容之后, 究竟是处于原来的位置, 还是处于原脚标位加上扩容长度的位置呢? 关键在于新扩容那最左边的一个1, 其所对应的上方数字是0还是1。要是这个数字是0, 那么扩容以后就在原来位置要是这个数字是1, 那么扩容以后就在原脚标位加上扩容长度的位置。源码里面的扩容也是这样进行操作的。换言之, 这跟hashn - 1此计算是有关系的。要是n并非2的n次方, 且n不等于2, 那么在转换为二进制情形下, n - 1会存在某一位是0, 这样与hash进行运算后, 该位置将始终为0, 进而计算得出的数组位置会始终存在某个下标对应的数组位置呈现为空的状态, 也就是说这个位置永远不会有值。JDK1.7中形成的环形链表线程一读取到当前的情况在准备扩容时线程二介入线程二读取进行扩容线程一继续执行这个线程, 首先使得A进到新的链表那儿, 接着把B插进链条开头, 鉴于因另一个线程造成情况, B的随后部分指向了A, 于是B箭头A箭头B, 构成了循环。JDK1.8中的性能优化JDK1.8在1.7的基础上对一些操作进行了优化。不同JDK1.7JDK1.8存储结构数组链表数组链表红黑树初始化方式单独函数集成至扩容方法hash值计算方式扰动处理9次扰动4次位运算5次异或运算扰动处理2次扰动1次位运算1次异或运算存放数据规则无冲突时存放数组冲突时存放链表无冲突时存放数组冲突链表长度8:树化并存放红黑树插入数据方式头插法将原位置的数据移动到后一位再插入数据到该位置尾插法 直接插入链表尾部/红黑树扩容后存储位置的计算方式所有的都依照原本的方式去开展运算, 括号当中的内容, 转换成扰动函数, 再对其进行(h与负1按位与)的操作。依据扩容之后的规则来进行计算, 此计算规则为, 扩容之后的位置等于原来的位置, 又或者是原来的位置加上旧有的容量。留意: 在JDK1.8之中, 当转换成为红黑树之际, 数组的长度必然要大于64, 要是数组的长度小于64, 而链表的长度达到8, 将会去进行扩容行动。五、总结看到此处, 我们对于其源码以及实现已然有了明晰的理解, 而且针对它的构造方法, 直至它的一个put数据以及get数据的源头代码剖析, 另外其里边较为精巧且关键的一些方法也都探究透彻了。 期望这些知识要点在往后大家的面试里也能够对大家有所助益, 从而获取一个中意的雇用通知。