怎样看网站建设,wordpress白色简约,企业彩页设计模板,海淀网站开发公司一、前言#xff1a;面试过的人都知道#xff0c;HashMap是Java程序员在面试中最最最经常被问到的一个点#xff0c;可以说#xff0c;不了解HashMap都不好意思说自己是做Java开发的。基本上你去面试十家公司#xff0c;有七八家都会问到你HashMap。那么今天#xff0c;就…一、前言 面试过的人都知道HashMap是Java程序员在面试中最最最经常被问到的一个点可以说不了解HashMap都不好意思说自己是做Java开发的。基本上你去面试十家公司有七八家都会问到你HashMap。那么今天就带着大家从源码的角度去分析一下HashMap具体是怎么实现的。 二、HashMap的构造方法 1.HashMap构造方法 我们先来看HashMap的四个构造方法java
//initialCapacity给定的初始化容量loadFactor扩容因子publicHashMap(int initialCapacity ,float loadFactor){if(initialCapacity 0)thrownewIllegalArgumentException(Illegal initial capacity: initialCapacity);if(initialCapacity MAXIMUM_CAPACITY)initialCapacity MAXIMUM_CAPACITY;if(loadFactor 0||Float.isNaN(loadFactor))thrownewIllegalArgumentException(Illegal load factor: loadFactor);this.loadFactor loadFactor;this.threshold tableSizeFor(initialCapacity);}publicHashMap(int initialCapacity){//内部调用了上边的构造方法this(initialCapacity, DEFAULT_LOAD_FACTOR);}publicHashMap(){//空参构造this.loadFactor DEFAULT_LOAD_FACTOR;// all other fields defaulted}publicHashMap(Map?extendsK,?extendsV m){//构造传入一个map将map中的值放到hashmap中this.loadFactor DEFAULT_LOAD_FACTOR;putMapEntries(m,false);}2.构造方法里的putMapEntries方法 刚才构造方法中提到了putMapEntries这个方法接下来就让我们一起看一下//该函数用于将一个map赋值给新的HashMapfinalvoidputMapEntries(Map?extendsK,?extendsV m,boolean evict){//定义变量接收旧hashmap的size int s m.size();//判断s的容量是否大于0if(s 0){//判断当前数组有没有初始化if(table null){// pre-size求出以 旧hashmap数组容量为阈值 的数组容量赋值给ftfloat ft ((float)s / loadFactor)1.0F;//判断是不是大于最大容量如果是赋值为最大容量否则将ft赋值给tint t ((ft (float)MAXIMUM_CAPACITY)?(int)ft : MAXIMUM_CAPACITY);//判断t是否大于threshold(数组扩容阈值)if(t threshold)//通过tablesizefor方法求出大于等于t的最小2的次幂值赋值给threshold数组扩容阈值threshold tableSizeFor(t);}//如果数组长度大于扩容阈值进行resize扩容操作 elseif(s threshold)resize();//循环遍历取出旧hashmap的值放入当前hashmapfor(Map.Entry?extendsK,?extendsV 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扩容操作
*/tableSizeFor方法 刚才putMapEntries方法中调用了tableSizeFor方法接下来我们看一下这个tableSizeFor方法。 作用创建hashMap对象时调用有参构造传入初始容量需要保证hashMap的初始长度为2的n次幂。 tableSizeFor方法用来计算大于等于并离传入值最近的2的n次幂的数值比如传入15算出结果为16传入17算出结果为32。 通过二进制的位移第一次右移一位第二次右移两位第三次右移四位。。。通过五次位移将范围内所有的位数都变为1高位补0最后得出来的结果再加上1最后算出来的结果一定是2的n次幂。//这个方法的作用是找到大于等于给定容量的最小2的次幂值//表示无符号右移也叫逻辑右移即若该数为正则高位补0而若该数为负数则右移后高位同样补07--》816--》16staticfinalinttableSizeFor(int cap){//先将数组长度减1之所以在开始移位前先将容量-1是为了避免给定容量已经是8,16这样2的幂时不减一 直接移位会导致得到的结果比预期大。比如预期16得到应该是16直接移位的话会得到32。int n cap -1;//右移一位在进行或运算这个时候最高位和次高位就已经都是1此时是2个1n | n 1;//右移两位在进行或运算这个时候由上次运算得出的两个1变成了四个1n | n 2;//右移四位n | n 4;//右移八位n | n 8;//右移十六位这个时候所有的位数都变为了1n | 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位的int类型整数最高有效位之后的位都能变为1。 三、HashMap的底层原理 先来看几个重要的参数staticfinalint DEFAULT_INITIAL_CAPACITY 14;// 默认数组初始容量staticfinalint MAXIMUM_CAPACITY 130;//数组最大容量staticfinalfloat DEFAULT_LOAD_FACTOR 0.75f;//默认加载因子staticfinalint TREEIFY_THRESHOLD 8;//树化的阈值staticfinalint UNTREEIFY_THRESHOLD 6;//由树退化到链表的阈值staticfinalint MIN_TREEIFY_CAPACITY 64;//树化最小数组容量//node节点继承了Map.entry,在Entry原有的K,V的基础上追加了hash和next字段//分别表示key的hash值和下一个节点staticclassNodeK,VimplementsMap.EntryK,V{finalint hash;finalK key;V value;NodeK,V next;}//重写了计算hash的方法//将 Hash 值的高 16 位右移并与原 Hash 值取异或运算(^)混合高 16 位和低 16 位的值//得到一个更加散列的低 16 位的 Hash 值。staticfinalinthash(Object key){int h;return(key null)?0:(h key.hashCode())^(h 16);}HashMap在JDK1.8之前的实现方式数组链表, 但是在JDK1.8后对HashMap进行了底层优化,改为了由 **数组链表或者数值红黑树**实现,主要的目的是提高查找效率 1. Jdk8数组链表或者数组红黑树实现当链表中的元素大于等于8 个并且数组长度大于等于64以后 会将链表转换为红黑树当红黑树节点 小于 等于6 时又会退化为链表。 2. 当new HashMap()时底层没有创建数组首次调用put()方法示时会调用resize方法底层创建长度为16的数组jdk8底层的数组是Node[],而非Entry[]用数组容量大小乘以加载因子得到一个值一旦数组中存储的元素个数超过该值就会调用resize方法将数组扩容到原来的两倍在做扩容的时候会生成一个新的数组原来的所有数据需要重新计算哈希码值重新分配到新的数组所以扩容的操作非常消耗性能。 默认的负载因子大小为0.75数组大小为16。也就是说默认情况下那么当HashMap中元素个数超过16*0.7512的时候就把数组的大小扩展为2*1632即扩大一倍。 3. 在我们Java中任何对象都有hashcodehash算法就是通过hashcode与自己进行向右位移16的异或运算。这样做是为了使高位的16位hash也能参与运算使运算出来的hash值足够随机足够分散还有产生的数组下标足够随机。 map.put(k,v)实现原理 (1)首先将k,v封装到Node对象当中(节点)。 (2)先调用k的hashCode()方法得出哈希值并通过哈希算法转换成数组的下标。 (3)下标位置上如果没有任何元素就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true那么这个节点的value将会被覆盖。 HashMap中的put()方法java
publicVput(K key,V value){returnputVal(hash(key), key, value,false,true);}putVal()方法。finalVputVal(int hash,K key,V value,boolean onlyIfAbsent,boolean evict){NodeK,V[] tab;NodeK,V 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{NodeK,V e;K k;//判断该位置数据的key和新来的数据是否一样if(p.hash hash ((k p.key) key ||(key !null key.equals(k))))//如果一样证明为修改操作该节点的数据赋值给e,后边会用到e p;//判断是不是红黑树elseif(p instanceofTreeNode)//如果是红黑树的话进行红黑树的操作e ((TreeNodeK,V)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);//因为新插入了一条数据所以判断链表长度是不是大于等于8if(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传进来的是falseif(!onlyIfAbsent || oldValue null)//将新值赋值当前节点e.value value;afterNodeAccess(e);//返回老值return oldValue;}}//计数器计算当前节点的修改次数modCount;//当前数组中的数据数量如果大于扩容阈值if(size threshold)//进行扩容操作resize();//空方法afterNodeInsertion(evict);//添加操作时 返回空值returnnull;}map中resize方法//扩容、初始化数组finalNodeK,V[]resize(){NodeK,V[] oldTab table;//如果当前数组为null的时候把oldCap老数组容量设置为0int 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需要大于16elseif((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)newThr oldThr 1;// double threshold 等价于oldThr*2}//如果oldCap0但是已经初始化了像把元素删除完之后的情况那么它的临界值肯定还存在 如果是首次初始化它的临界值则为0elseif(oldThr 0)// initial capacity was placed in thresholdnewCap oldThr;//数组未初始化的情况将阈值和扩容因子都设置为默认值else{// zero initial threshold signifies using defaultsnewCap 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})//根据上边计算得出的容量 创建新的数组 NodeK,V[] newTab (NodeK,V[])newNode[newCap];//赋值table newTab;//扩容操作判断不为空证明不是初始化数组if(oldTab !null){//遍历数组for(int j 0; j oldCap;j){NodeK,V e;//判断当前下标为j的数组如果不为空的话赋值个e进行下一步操作if((e oldTab[j])!null){//将数组位置置空oldTab[j]null;//判断是否有下个节点if(e.next null)//如果没有就重新计算在新数组中的下标并放进去newTab[e.hash (newCap -1)] e;//有下个节点的情况并且判断是否已经树化elseif(e instanceofTreeNode)//进行红黑树的操作((TreeNodeK,V)e).split(this, newTab, j, oldCap);//有下个节点的情况并且没有树化链表形式else{//比如老数组容量是16那下标就为0-15//扩容操作*2容量就变为32下标为0-31//低位0-15高位16-31//定义了四个变量// 低位头 低位尾NodeK,V loHead null, loTail null;// 高位头 高位尾NodeK,V hiHead null, hiTail null;//下个节点NodeK,V next;//循环遍历do{//取出next节点next e.next;//通过 与操作 计算得出结果为0if((e.hash oldCap)0){//如果低位尾为null证明当前数组位置为空没有任何数据if(loTail null)//将e值放入低位头loHead e;//低位尾不为null证明已经有数据了else//将数据放入next节点loTail.next e;//记录低位尾数据loTail e;}//通过 与操作 计算得出结果不为0else{//如果高位尾为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的hashCode()方法得出哈希值并通过哈希算法转换成数组的下标。 (2)、在通过数组下标快速定位到某个位置上。重点理解如果这个位置上什么都没有则返回null。如果这个位置上有单向链表那么它就会拿着参数K和单向链表上的每一个节点的K进行equals如果所有equals方法都返回false则get方法返回null。如果其中一个节点的K和参数K进行equals返回true那么此时该节点的value就是我们要找的value了get方法最终返回这个要找的value。 HashMap中的get()方法publicVget(Object key){NodeK,V e;return(e getNode(hash(key), key))null?null: e.value;}getNode()方法finalNodeK,VgetNode(int hash,Object key){NodeK,V[] tab;NodeK,V 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 instanceofTreeNode)//进行红黑树查询操作return((TreeNodeK,V)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);}}//没有查询到返回nullreturnnull;} 四、HashMap常见面试题分析 为何HashMap的数组长度一定是2的次幂? 首先HashMap的初始化的数组长度一定是2的n次的每次扩容仍是原来的2倍的话就不会破坏这个规律每次扩容后原数据都会进行数据迁移根据二进制的计算扩容后数据要么在原来位置要么在【原来位置扩容长度】这样就不需要重新hash效率上更高。 HashMap中如果想存入数据首先它需要根据key的哈希值去定位落入哪个桶中 HashMap的做法我总结的是三步无符号右移、^异或、与 具体是拿着key的哈希值先“”无符号右移16位然后“^”异或上key的哈希值得到一个值再拿着这个值去“”上数组长度减一 最后得出一个数(如果数组长度是15的话那这个数就是一个0-15之间的一个数)这个数就是得出的数组脚标位置也就是存入的桶的位置。 由上边可以知道定位桶的位置最后需要做一个 “” 与运算完了得出一个数就是桶的位置 知道了这些以后再来说为什么HashMap的长度之所以一定是2的次幂? 至少有以下**两个原因** 1、HashMap的长度是2的次幂的话可以让**数据更散列更均匀的分布**更充分的利用数组的空间 怎么理解呢?下面举例子说一下如果不是2的次幂的数的话假设数组长度是一个奇数那参与最后的运算的肯定就是偶数那偶数的话它二进制的最后一个低位肯定是00做完运算得到的肯定也是0那意味着完后得到的数的最低位一定是0最低位一定是0的话那说明一定是一个偶数换句话说就是完得到的数一定是一个偶数所以完获取到的脚标永远是偶数位那意味着奇数位的脚标永远都没值**有一半的空间是浪费的**奇数说完了来说一下偶数假设数组长度是一个偶数比如6那参与运算的就是55的二进制 00000000 00000000 00000000 00000101发现任何一个数上5倒数第二低位永远是0那就意味着完以后最起码肯定得不出2或者3(这点刚开始不好理解但是好好想一下就能明白)意味着第二和第三脚标位肯定不会有值。 虽然偶数的话不会像奇数那么夸张会有一半的脚标位得不到但是也总会有一些脚标位得不到的。**所以不是2的次幂的话不管是奇数还是偶数就肯定注定了某些脚标位永远是没有值的而某些脚标位永远是没有值的就意味着浪费空间会让数据散列的不充分这对HashMap来说绝对是个灾难!** 2、HashMap的长度一定是2的次幂还有另外一个原因那就是在扩容迁移的时候不需要再重新通过哈希定位新的位置了。扩容后元素新的位置要么在原脚标位要么在原脚标位扩容长度这么一个位置。 比如扩容前长度是8扩容后长度是16第一种情况扩容前00000000000000000000000000000101000000000000000000000000000001118-17-------------------------------------1015 原来脚标位是5扩容后000000000000000000000000000001010000000000000000000000000000111116-115-------------------------------------1015 扩容后脚标位是5(原脚标位)第二种情况扩容前00000000000000000000000000001101000000000000000000000000000001118-17-------------------------------------1015 原来脚标位是5扩容后000000000000000000000000000011010000000000000000000000000000111116-115-------------------------------------110113 扩容后脚标位是13(原脚标位扩容长度) 扩容后到底是在原来位置还是在原脚标位扩容长度的位置主要是看新扩容最左边一个1对应的上方数字是0还是1如果是0则扩容后在原来位置如果是1则扩容后在原脚标位扩容长度的位置HashMap源码里扩容也是这么做的。 总结来说就是hash(n-1)这个计算有关。如果不为n不为2的n次方的话那转换为二进制情况下n-1就会有某一位为0那与hash做了运算后该位置永远为0那么计算出来的数组位置就永远会有某个下标的数组位置是空的也就是这个位置永远不会有值。 JDK1.8中HashMap的性能优化 JDK1.8在1.7的基础上对一些操作进行了优化。 | 不同 | JDK1.7 | JDK1.8 | | ------------------------ | ------------------------------------------------------------ | ------------------------------------------------------------ | | 存储结构 | 数组链表 | 数组链表红黑树 | | 初始化方式 | 单独函数inflateTable() | 集成至扩容方法resize() | | hash值计算方式 | 扰动处理9次扰动4次位运算5次异或运算 | 扰动处理2次扰动1次位运算1次异或运算 | | 存放数据规则 | 无冲突时存放数组;冲突时存放链表 | 无冲突时存放数组;冲突链表长度8:c存放单链表;冲突链表长度 8:树化并存放红黑树 | | 插入数据方式 | 头插法(将原位置的数据移动到后一位再插入数据到该位置) | 尾插法 (直接插入链表尾部/红黑树) | | 扩容后存储位置的计算方式 | 全部按照原来的方法进行运算(hashCode()-扰动函数-(hlength-1)) | 按照扩容后的规则计算(即扩容后位置原位置或原位置旧容量) | 注意JDK1.8里转换为红黑树的时候数组长度必须大于64如果数组长度小于64链表长度达到8的话会进行resize扩容操作。 五、总结 看到这里我们已经HashMap的源码和实现有了清晰的理解并且对它的构造方法再到它的一个put数据和get数据的一个源码解析还有一些它里边比较精妙和重要的一些方法也都探索清楚了希望这些知识点可以在大家以后的面试中也能够帮助到大家斩获一个心仪的offer。
