展开

关键词

帮你面试——HashMap

这几天学习了HashMap的底层实现,但是发现好几个版本的,代码不一,而且看了Android包的HashMap和JDK中的HashMap的也不是一样,原来他们没有指定JDK版本,很多文章都是旧版本JDK1.6 现在我来分析一哈最新的JDK1.8的HashMap及性能优化。  在JDK1.6,JDK1.7中,HashMap采用位桶+链表实现,即使用链表处理冲突,同一hash值的链表都存储在一个链表里。 的构造函数 HashMap的构造方法有4种,主要涉及到的参数有,指定初始容量,指定填充比和用来初始化的Map //构造函数1 public HashMap(int initialCapacity, float 最坏的情况下,所有的key都映射到同一个桶中,这样hashmap就退化成了一个链表——查找时间从O(1)到O(n)。  随着HashMap的大小的增长,get()方法的开销也越来越大。 如果哈希值相等,HashMap希望key值最好是实现了Comparable接口的,这样它可以按照顺序来进行插入。这对HashMap的key来说并不是必须的,不过如果实现了当然最好。

22620

hashmap 实现原理_面试hashmap底层实现原理

HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解,一个线性的数组怎么实现按键值对来存取数据呢?这里HashMap有做一些处理。    首先HashMap里面实现一个静态内部类Entry,其重要的属性有 key , value, next,从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean HashMap的存取实现 既然是线性数组,为什么能随机存取? 到这里为止,HashMap的大致实现,我们应该已经清楚了。 HashMap里面设置一个因子,随着map的size越来越大,Entry[]会以一定的规则加长长度。

6810
  • 广告
    关闭

    【玩转 Cloud Studio】有奖调研征文,千元豪礼等你拿!

    想听听你玩转的独门秘籍,更有机械键盘、鹅厂公仔、CODING 定制公仔等你来拿!

  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    HashMap,HashTable,ConcurrentHashMap面试总结!!!

    原文:https://www.cnblogs.com/hexinwei1/p/10000779.html 一、小总结 1、HashMap 、HashTable、 ConcurrentHashMap HashMap 类似 Collections.synchronizedMap(hashMap) 对读写加锁,独占式,一个线程在读时其他线程必须等待,吞吐量较低,性能较为低下。 数据结构同HashMap。 2、ConcurrentHashMap如何实现线程安全? ) // 这个方法和 HashMap 中稍微有一点点不同,那就是它不是一定会进行红黑树转换, // 如果当前数组的长度小于 和 ConcurrentHashMap 全解析(https://javadoop.com/post/hashmap#Java8%20HashMap)

    21920

    面试必问之HashMap

    问题1 hashmap原理? 问题1.1 hashmap底层数据结构是什么 哈希表结构(链表散列:数组+链表)实现,结合数组和链表的优点。当链表长度超过 8 时,链表转换为红黑树。 不能,因为在特定条件下二叉树可能会退化为线性结构 问题2 hashmap在什么条件下扩容 HashMap在什么条件下扩容? 为什么扩容是2的n次幂? 为什么要先高16位异或低16位再取模运算? 问题4 HashMap并发问题 问题4.1 HashMap 和 HashTable 有什么区别? ①、HashMap 是线程不安全的,HashTable 是线程安全的; ②、由于线程安全,所以 HashTable 的效率比不上 HashMap; ③、HashMap最多只允许一条记录的键为null,允许多条记录的值为 多线程put后可能导致get死循环 问题4.3 怎么得到线程安全的HashMap 一般情况下可以使用下面三种集合来替换hashMap,性能最好是ConcurrentHashMap HashTable

    10011

    面试-HashMap底层实现原理 原

    参考博客:https://www.cnblogs.com/wuhuangdi/p/4175991.html

    81820

    HashMap常见面试问题

    1、HashMap的底层数据结构? HashMap是由数组和链表组合构成的数据结构。 ---- 2、HashMap的存取原理? 因为HashMap本身所有的位置都是null,在put插入的时候会根据key的hash去计算一个index值。 Java7在多线程操作HashMap时可能会引起死循环,原因是扩容转移后前后链表顺序不变,保持之前节点的引用关系。 ---- 4、为啥会线程不安全? Hash的公式---> index = HashCode(Key) & (Length - 1) 扩容前: 扩容后: ---- 8、HashMap的主要参数都有哪些? 而当HashMap的红黑树的元素小于等于6时候重新转化为链表结构。 为什么JDK1.8 HashMap选择红黑树而不是其他的树?

    5410

    面试 | Java8 HashMap原理

    概述 在官方文档中是这样描述HashMap的: Hash table based implementation of the Map interface. HashMap继承自父类(AbstractMap),实现了Map、Cloneable、Serializable接口 2. { // 初始化填充因子 this.loadFactor = DEFAULT_LOAD_FACTOR; } //HashMap(Map<? extends K>)型构造函数 public HashMap(Map<? extends K, ? extends V> m) { putMapEntries(m, true); } //将m的所有元素存入本HashMap实例中,evict为false时表示构造初始HashMap final

    41530

    面试HashMap看这篇就够了

    常见问题 随机搜罗了一些常见HashMap问题,如果把下述代码都看懂了应付这些应该没问题。 HashMap原理,内部数据结构。 HashMap中的put,get,remove大致过程。 HashMap中 hash函数实现。 HashMap如何扩容。 HashMap几个重要参数为什么这样设定。 HashMap为什么线程不安全,如何替换。 HashMap在JDK7跟JDK8中的区别。 HashMap中链表跟红黑树切换思路。10.HashMap中链表跟红黑树是怎么个维持方法。 HashMap的时间复杂读几乎可以接近O(1)(如果出现了 哈希冲突可能会波动下),并且HashMap的空间利用率一般就是在40%左右。HashMap的大致图如下: ? java.util.HashMap.Node 就是我们HashMap中存储的基本的KV。 ?

    30210

    《吊打面试官》系列-HashMap

    于是在一个寂寞难耐的夜晚,我痛定思痛,决定开始写互联网技术栈面试相关的文章,希望能帮助各位读者以后面试势如破竹,对面试官进行360°的反击,吊打问你的面试官,让一同面试的同僚瞠目结舌,疯狂收割大厂Offer

    10140

    今日面试HashMap考点

    关于HashMap常见面试考点(底层原理+扩容机制) 问:简单说说 HashMap 的底层原理? Entry 元素,然后通过 key 的 equals 方法在对应位置的链表中找到需要的 Entry 元素,所以 HashMap 的数据结构是数组和链表的结合,此外 HashMap 中 key 和 value 通过上面两个假设例子可以看出 HashMap 的长度为 2 的幂时减一的值的二进制位数一定全为 1,这样数组下标 index 的值完全取决于 key 的 hash 值的后几位,因此只要存入 HashMap 答:这两个参数对于 HashMap 来说很重要,直接从一定程度决定了 HashMap 的性能问题。 问:简单说说 JDK1.7 中 HashMap 什么情况下会发生扩容?如何扩容?

    18540

    HashMap源码解析之面试必备

    今天我们就面试会问到关于HashMap的问题进行一个汇总,以及对这些问题进行解答。 1、HashMap的数据结构是什么? 2、为啥是线程不安全的? 以上这些问题在面试中出现的频率往往比较高,在对HashMap不太了解的情况下,往往很难将这些问题答全,笔者就带领对这块不熟悉的小伙伴们一起,一步一步解析以上的问题。 1、HashMap的数据结构是什么? 对于这个问题,笔者建议回答的时候对JAVA版本进行区分,因为不同版本下,HashMap的结构是有些差异的。 回答:在JDK1.8之前HashMap是数组+链表的形式,JDK1.8包括之后是数组+链表+红黑树。本文讲的HashMap是基于JDK1.8。 2、为啥是线程不安全的? 4、HashMap是如何处理Hash碰撞的? HashMap采用的是链表法,将hash值相同的元素放在一个链表下。 5、增加元素的方法是怎么实现的? ?

    16720

    《吊打面试官》系列-HashMap

    好了我们开始今天的面试吧,小伙子你了解数据结构中的HashMap么?能跟我聊聊他的结构和底层原理么? 切,这也太看不起我了吧,居然问这种低级问题,不过还是要好好回答。 嗯嗯面试官,我知道HashMap是我们非常常用的数据结构,由数组和链表组合构成的数据结构。 面试官您好,我们在创建HashMap的时候,阿里巴巴规范插件会提醒我们最好赋初值,而且最好是2的幂。 ? 篇幅和精力的原因我就介绍到了一部分的主要知识点,我总结了一些关于HashMap常见的面试题,大家问下自己能不能回答上来,不能的话要去查清楚哟。 HashMap常见面试题: HashMap的底层数据结构? HashMap的存取原理? Java7和Java8的区别? 为啥会线程不安全? 有什么线程安全的类代替么? 默认初始化大小是多少?

    53120

    HashMap面试?我是谁?我在哪?

    片刻后~ 小鲁班:666,听说你拿到了阿里的 Offer,能透露一下面试内容和技巧吗? 达摩:嘿嘿嘿,没问题鸭,叫声爸爸我就告诉你。 小鲁班:问这么多内容,那岂不是一个人都面试很久吗? 达摩:不是的,面试官一般都会用连环炮的方式提问的。 小鲁班:你说的连环炮是什么意思鸭? 达摩:那我举个例子: 就比如问你 HashMap 是不是有序的?你回答不是有序的。 那面试官就会可能继续问你,有没有有序的Map实现类呢?你如果这个时候说不知道的话,那这块问题就到此结束了。 那么面试官还会继续问你,你觉得它们两个哪个的有序实现比较好?如果你依然可以回答的话,那么面试官会继续问你,你觉得还有没有比它更好或者更高效的实现方式? 无穷无尽深入,直到你回答不出来或者面试官认为问题到底了。

    39210

    去哪面试都会问的HashMap

    前言 HashMap可以说是面试的重中之重,去10家公司面试,8家都会问道,为什么大家都爱用HashMap打开话题? HashMap是怎么实现的? jdk1.7的HashMap是用数组+链表实现的 jdk1.8的HashMap是用数组+链表+红黑树实现的 ? 在树中查找的效率为O(logn),在链表中查找的效率为O(n) 常见面试HashMap,HashTable,ConcurrentHashMap之间的区别 对象 key和value是否允许为空 是否线程安全 HashMap key和value都允许为null 否 HashTable key和value都不允许为null 是 ConcurrentHashMap key和value都不允许为null 是 HashMap 多线程扩容,会让链表形成环,从而造成死循环 多线程put可能导致元素丢失 如何避免HashMap在高并发下的问题?

    15710

    面试必问之HashMap VS HashTable

    HashMap和HashTable有什么不同?在面试和被面试的过程中,我问过也被问过这个问题,也见过了不少回答,今天决定写一写自己心目中的理想答案。 JDK每一版本都在改进。 本文讨论的HashMap和HashTable基于JDK 1.7.0_67。 1. 时间 HashTable产生于JDK 1.1,而HashMap产生于JDK 1.2。 从时间的维度上来看,HashMap要比HashTable出现得晚一些。 2. HashMap默认的初始化大小为16,之后每次扩充为原来的2倍。 所以从hash计算的效率上,又是HashMap更胜一筹。 所以,事实就是HashMap为了加快hash的速度,将哈希表的大小固定为了2的幂。

    25120

    HashMap面试?我是谁?我在哪

    达摩:不是的,面试官一般都会用连环炮的方式提问的。 小鲁班:你说的连环炮是什么意思鸭? 达摩:那我举个例子 就比如问你HashMap是不是有序的? 你回答不是有序的。 那面试官就会可能继续问你,有没有有序的Map实现类呢? 你如果这个时候说不知道的话,那这块问题就到此结束了。如果你说有TreeMap和LinkedHashMap。 那么面试官接下来就可能会问你,TreeMap和LinkedHashMap是如何保证它的顺序的? 如果你回答不上来,那么到此为止。 那么面试官还会继续问你,你觉得它们两个哪个的有序实现比较好? 如果你依然可以回答的话,那么面试官会继续问你,你觉得还有没有比它更好或者更高效的实现方式。。 无穷无尽深入,直到你回答不出来或者面试官认为问题到底了 小鲁班捏了一把汗,我去。。。

    32230

    HashMap 精选面试题(背诵版)

    对于 Java 求职者来说,HashMap 可谓是重中之重,是面试的必考点。然而 HashMap 的知识点非常多,复习起来花费精力很大。 为了减轻大家在面试时的痛苦,二哥将读者库森的这篇 HashMap面试专题文章整理出来分享给大家,希望对小伙伴们有所帮助! JDK 7 中,HashMap 由“数组+链表”组成,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的。 在 JDK 8 中,HashMap 由“数组+链表+红黑树”组成。 HashMap用的哪种? 11、HashMap 的扩容方式? HashMap 在容量超过负载因子所定义的容量之后,就会扩容。 详情参照这篇 12、一般用什么作为HashMap的key?

    20730

    面试必会:HashMap 实现原理解读

    个人原创+1博客:点击前往,查看更多 作者:冯立彬 blog.csdn.net/fenglibing/article/details/91565912 HashMap是Java开发当中使用得非常多的一种数据结构 本文以Java8中的HashMap做为分析原型,因为不同的JDK版本中的HashMap,可能存在着底层实现上的不一样。 HashMap是通过数组存储所有的数据,每个元素所存放数组的下标,是根据该存储元素的key的Hash值与该数组的长度减去1做与运算,如下所示: index = (length_of_array - 1) 因为在单个Hash值对应的元素小于等于8个时,其查询时间最差为O(8),但是当单个Hash值对应的元素大于8个时,再通过Node的单向链表的方式进行查询,速度上就会变得更慢了;这个时候HashMap就会将 以下是一张关于HashMap存储结构的示意图: ?

    30610

    BAT面试必问HashMap源码分析

    HashMap 简介 HashMap 主要用来存放键值对,它基于哈希表的Map接口实现,是常用的Java集合之一。 JDK1.8 之前 HashMap 由 数组+链表 组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突).JDK1.8 以后在解决哈希冲突时有了较大的变化, 底层数据结构分析 JDK1.8之前 JDK1.8 之前 HashMap 底层是数组和链表结合在一起使用也就是链表散列。 JDK 1.8 HashMap 的 hash 方法源码: JDK 1.8 的 hash方法 相比于 JDK 1.7 hash 方法更加简化,但是原理不变。  }  // 包含另一个“Map”的构造函数  publicMore ...HashMap(Map<?

    18440

    Java程序员面试HashMap

    介绍 JAVA中的基础HashMap在工作中使用的频率极高。相信很多同学在平时面试的时候经常被问到晕,今天我们来聊一下HashMap中常见的面试题吧! 常见面试题 1、 JavaJDK1.7到1.8HashMap做了那些优化? java1.7中HashMap是由数组+链表组成的。1.8之后加了红黑树。 当链表大于8并且容量超过64时。 3、HashMap源码分析 HashMap中有这些属性: // HashMap 初始化长度 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4 有人曾经把这个问题反馈给了 Sun 公司,但 Sun 公司认为这不是一个问题,因为 HashMap 本身就是非线程安全的,如果要在多线程下,建议使用 ConcurrentHashMap 替代,但这个问题在面试中被问到的几率依然很大 总结 以上就是常见的HashMap常见面试题。

    12720

    相关产品

    • 腾讯会议

      腾讯会议

      腾讯会议(TM)是一款基于腾讯21年音视频通讯经验积累的高清流畅、便捷易用、安全可靠的云视频会议产品,让您随时随地高效开会,全方位满足不同场景下的会议需求。

    相关资讯

    热门标签

    活动推荐

      运营活动

      活动名称
      广告关闭

      扫码关注腾讯云开发者

      领取腾讯云代金券