详解JAVA中HashMap的面试题-创新互联
这篇文章主要详解JAVA中HashMap的面试题,内容清晰明了,对此有兴趣的小伙伴可以学习一下,相信大家阅读完之后会有帮助。
创新互联主要从事成都网站设计、成都做网站、网页设计、企业做网站、公司建网站等业务。立足成都服务泰来,十余年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:189820811081. 为什么我们建议在定义HashMap的时候,就指定它的初始化大小呢?
答:在当我们对HashMap初始化时,如果没有为其设置初始化容量,那么系统会默认创建一个容量为16的大小的集合。当我们向HashMap中添加元素时,如果HashMap的容量值超过了它的临界值(默认16*0.75=12)时,(0.75是HashMap的加载因子)HashMap将会重新扩容到下一个2的指数次幂(2^4=16 下一个2的指数次幂是2^5=32)。由于HashMap扩容要进行resize的操作,频繁的resize,会导致HashMap的性能下降,所以建议在确定HashMap集合的大小的情况下,指定其初始化大小,避免做过多的resize操作,导致性能下降。
2. HashMap什么时候进行扩容?
答:当我们不断的向HashMap中添加元素时,它会判断HashMap当前的容量值(当前元素的个数)是否超过了它的临界值(在没有指定其初始化大小时,默认16*0.75=12),如果添加的元素个数超过了临界值,它就会开始进行扩容。
3. HashMap在扩容时,扩容到多大?
答:HashMap在扩容时,它会扩容到下一个2的指数次幂,即当前容量的2倍,比如当前容量是2^4=16,将会扩容到下一个2的指数次幂2^5=32.
4. HashMap是如何进行扩容的?
答:HashMap进行扩容时会调用resize()函数,重新计算HashMap所需的新的容量,然后重新定义一个新的容器,将原数组数据进行Hash, 放入新的容器中。这个过程将会导致HashMap的性能下降。
resize()函数的源码:
//HashMap 扩容操作 final Node[] resize() { //保存当前table Node [] oldTab = table; //保存当前table的容量 int oldCap = (oldTab == null) ? 0 : oldTab.length; //保存当前阈值 int oldThr = threshold; //初始化新的table容量和阈值 int newCap, newThr = 0; //1. resize()函数在size(HashMap当前的元素个数) > threshold(当前阈值,默认16*0.75=12)时调用。 //当oldCap(HashMap的元素个数)大于0表示原来的table表非空,oldCap(threshold)为oldCap x load_factor(加载因子:0.75) if (oldCap > 0) { //若旧table容量大于等于大容量,更新阈值为Integer.MAX_VALUE(大整形值),这样以后就不会自动扩容了 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //扩容到下一个2的指数次幂,容量翻倍,使用左移,效率更高 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold //阈值翻倍 } //2. resize()函数在table为空被调用。oldCap小于等于0且oldThr大于0,表示用户使用HashMap的构造函数创建了一个HashMap, //使用的构造函数为HashMap(int initialCapacity, float loadFactor)或HashMap(int initialCapacity)或HashMap(Map<? extends K, ? extends V> m), //导致了oldTab为null,oldCap为0,oldThr为用户指定的HashMap的初始化容量 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; //当table没有初始化时,threshold为初始容量, threshold = tableSizeFor(t); //3. resize()函数在table为空被调用。oldCap小于等于0且oldThr大于0,表示用户使用HashMap的无参构造函数HashMap()函数创建了一个HashMap, //此时,所有值均采用默认值,oldTab(table)表为空,oldCap为0,oldThr等于0. else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //如果新的阈值为0 if (newThr == 0) { float ft = (float)newCap * loadFactor; //新的tbale容量*加载因子 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) //初始化table Node [] newTab = (Node [])new Node[newCap]; table = newTab; if (oldTab != null) { //把oldTab中的节点reHash到newTab中去 for (int j = 0; j < oldCap; ++j) { Node e; if ((e = oldTab[j]) != null) { oldTab[j] = null; //如果节点是单个节点,直接在newTab中进行重定位 if (e.next == null) newTab[e.hash & (newCap - 1)] = e; //如果节点是TreeNode节点,要进行红黑树的rehash操作 else if (e instanceof TreeNode) ((TreeNode )e).split(this, newTab, j, oldCap); //如果是链表,进行链表的rehash操作 else { // preserve order Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node next; //将同一桶中的元素根据(e.hash & oldCap)是否为0进行分割,分成两个不同的链表,完成rehash操作 do { next = e.next; //根据算法 e.hash & oldCap 判断节点位置rehash后是否发生改变,最高位==0,这是索引不变的链表 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } //最高位==1,这是索引发生改变的链表 else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { //原bucket位置的尾指针不为空(即还有node) loTail.next = null; //链表最后一个节点为null newTab[j] = loHead; //链表的头指针放在新桶的相同下标(j)处 } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; //rehash后节点新的位置一定为原来基础上加上oldCap } } } } } return newTab; }
另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网页名称:详解JAVA中HashMap的面试题-创新互联
网页地址:http://ybzwz.com/article/codccp.html