Java核心技术面试精讲
杨晓峰
前Oracle首席工程师
立即订阅
43250 人已学习
课程目录
已完结 43 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 以面试题为切入点,有效提升你的Java内功
免费
模块一 Java基础 (14讲)
第1讲 | 谈谈你对Java平台的理解?
第2讲 | Exception和Error有什么区别?
第3讲 | 谈谈final、finally、 finalize有什么不同?
第4讲 | 强引用、软引用、弱引用、幻象引用有什么区别?
第5讲 | String、StringBuffer、StringBuilder有什么区别?
第6讲 | 动态代理是基于什么原理?
第7讲 | int和Integer有什么区别?
第8讲 | 对比Vector、ArrayList、LinkedList有何区别?
第9讲 | 对比Hashtable、HashMap、TreeMap有什么不同?
第10讲 | 如何保证集合是线程安全的? ConcurrentHashMap如何实现高效地线程安全?
第11讲 | Java提供了哪些IO方式? NIO如何实现多路复用?
第12讲 | Java有几种文件拷贝方式?哪一种最高效?
第13讲 | 谈谈接口和抽象类有什么区别?
第14讲 | 谈谈你知道的设计模式?
模块二 Java进阶 (16讲)
第15讲 | synchronized和ReentrantLock有什么区别呢?
第16讲 | synchronized底层如何实现?什么是锁的升级、降级?
第17讲 | 一个线程两次调用start()方法会出现什么情况?
第18讲 | 什么情况下Java程序会产生死锁?如何定位、修复?
第19讲 | Java并发包提供了哪些并发工具类?
第20讲 | 并发包中的ConcurrentLinkedQueue和LinkedBlockingQueue有什么区别?
第21讲 | Java并发类库提供的线程池有哪几种? 分别有什么特点?
第22讲 | AtomicInteger底层实现原理是什么?如何在自己的产品代码中应用CAS操作?
第23讲 | 请介绍类加载过程,什么是双亲委派模型?
第24讲 | 有哪些方法可以在运行时动态生成一个Java类?
第25讲 | 谈谈JVM内存区域的划分,哪些区域可能发生OutOfMemoryError?
第26讲 | 如何监控和诊断JVM堆内和堆外内存使用?
第27讲 | Java常见的垃圾收集器有哪些?
第28讲 | 谈谈你的GC调优思路?
第29讲 | Java内存模型中的happen-before是什么?
第30讲 | Java程序运行在Docker等容器环境有哪些新问题?
模块三 Java安全基础 (2讲)
第31讲 | 你了解Java应用开发中的注入攻击吗?
第32讲 | 如何写出安全的Java代码?
模块四 Java性能基础 (3讲)
第33讲 | 后台服务出现明显“变慢”,谈谈你的诊断思路?
第34讲 | 有人说“Lambda能让Java程序慢30倍”,你怎么看?
第35讲 | JVM优化Java代码时都做了什么?
模块5 Java应用开发扩展 (4讲)
第36讲 | 谈谈MySQL支持的事务隔离级别,以及悲观锁和乐观锁的原理和应用场景?
第37讲 | 谈谈Spring Bean的生命周期和作用域?
第38讲 | 对比Java标准NIO类库,你知道Netty是如何实现更高性能的吗?
第39讲 | 谈谈常用的分布式ID的设计方案?Snowflake是否受冬令时切换影响?
周末福利 (2讲)
周末福利 | 谈谈我对Java学习和面试的看法
周末福利 | 一份Java工程师必读书单
结束语 (1讲)
结束语 | 技术没有终点
Java核心技术面试精讲
登录|注册

第9讲 | 对比Hashtable、HashMap、TreeMap有什么不同?

杨晓峰 2018-05-24
Map 是广义 Java 集合框架中的另外一部分,HashMap 作为框架中使用频率最高的类型之一,它本身以及相关类型自然也是面试考察的热点。
今天我要问你的问题是,对比 Hashtable、HashMap、TreeMap 有什么不同?谈谈你对 HashMap 的掌握。

典型回答

Hashtable、HashMap、TreeMap 都是最常见的一些 Map 实现,是以键值对的形式存储和操作数据的容器类型。
Hashtable 是早期 Java 类库提供的一个哈希表实现,本身是同步的,不支持 null 键和值,由于同步导致的性能开销,所以已经很少被推荐使用。
HashMap 是应用更加广泛的哈希表实现,行为上大致上与 HashTable 一致,主要区别在于 HashMap 不是同步的,支持 null 键和值等。通常情况下,HashMap 进行 put 或者 get 操作,可以达到常数时间的性能,所以它是绝大部分利用键值对存取场景的首选,比如,实现一个用户 ID 和用户信息对应的运行时存储结构。
TreeMap 则是基于红黑树的一种提供顺序访问的 Map,和 HashMap 不同,它的 get、put、remove 之类操作都是 O(log(n))的时间复杂度,具体顺序可以由指定的 Comparator 来决定,或者根据键的自然顺序来判断。

考点分析

上面的回答,只是对一些基本特征的简单总结,针对 Map 相关可以扩展的问题很多,从各种数据结构、典型应用场景,到程序设计实现的技术考量,尤其是在 Java 8 里,HashMap 本身发生了非常大的变化,这些都是经常考察的方面。
很多朋友向我反馈,面试官似乎钟爱考察 HashMap 的设计和实现细节,所以今天我会增加相应的源码解读,主要专注于下面几个方面:
理解 Map 相关类似整体结构,尤其是有序数据结构的一些要点。
从源码去分析 HashMap 的设计和实现要点,理解容量、负载因子等,为什么需要这些参数,如何影响 Map 的性能,实践中如何取舍等。
理解树化改造的相关原理和改进原因。
除了典型的代码分析,还有一些有意思的并发相关问题也经常会被提到,如 HashMap 在并发环境可能出现无限循环占用 CPU、size 不准确等诡异的问题。
我认为这是一种典型的使用错误,因为 HashMap 明确声明不是线程安全的数据结构,如果忽略这一点,简单用在多线程场景里,难免会出现问题。
理解导致这种错误的原因,也是深入理解并发程序运行的好办法。对于具体发生了什么,你可以参考这篇很久以前的分析,里面甚至提供了示意图,我就不再重复别人写好的内容了。

知识扩展

1.Map 整体结构
首先,我们先对 Map 相关类型有个整体了解,Map 虽然通常被包括在 Java 集合框架里,但是其本身并不是狭义上的集合类型(Collection),具体你可以参考下面这个简单类图。
Hashtable 比较特别,作为类似 Vector、Stack 的早期集合相关类型,它是扩展了 Dictionary 类的,类结构上与 HashMap 之类明显不同。
HashMap 等其他 Map 实现则是都扩展了 AbstractMap,里面包含了通用方法抽象。不同 Map 的用途,从类图结构就能体现出来,设计目的已经体现在不同接口上。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《Java核心技术面试精讲》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(81)

  • 天凉好个秋 置顶
    解决哈希冲突的常用方法有:

    开放定址法
    基本思想是:当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…,直到找出一个不冲突的哈希地址pi ,将相应元素存入其中。

    再哈希法
    这种方法是同时构造多个不同的哈希函数:
    Hi=RH1(key)  i=1,2,…,k
    当哈希地址Hi=RH1(key)发生冲突时,再计算Hi=RH2(key)……,直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间。

    链地址法
    这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

    建立公共溢出区
    这种方法的基本思想是:将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表。
    2018-05-24
    109
  • 三口先生 置顶
    最常用的方法就是线性再散列。即插入元素时,没有发生冲突放在原有的规则下的空槽下,发生冲突时,简单遍历hash表,找到表中下一个空槽,进行元素插入。查找元素时,找到相应的位置的元素,如果不匹配则进行遍历hash表。
    然后就是我们非线性再散列,就是冲突时,再hash,核心思想是,如果产生冲突,产生一个新的hash值进行寻址,如果还是冲突,则继续。
    上述的方法,主要的缺点在于不能从表中删除元素。
    还有就是我们hashmap的思想外部拉链。
    2018-05-24
    13
  • 公号-代码荣耀
    Hashtable、HashMap、TreeMap心得

    三者均实现了Map接口,存储的内容是基于key-value的键值对映射,一个映射不能有重复的键,一个键最多只能映射一个值。

    (1) 元素特性
    HashTable中的key、value都不能为null;HashMap中的key、value可以为null,很显然只能有一个key为null的键值对,但是允许有多个值为null的键值对;TreeMap中当未实现 Comparator 接口时,key 不可以为null;当实现 Comparator 接口时,若未对null情况进行判断,则key不可以为null,反之亦然。

    (2)顺序特性
    HashTable、HashMap具有无序特性。TreeMap是利用红黑树来实现的(树中的每个节点的值,都会大于或等于它的左子树种的所有节点的值,并且小于或等于它的右子树中的所有节点的值),实现了SortMap接口,能够对保存的记录根据键进行排序。所以一般需要排序的情况下是选择TreeMap来进行,默认为升序排序方式(深度优先搜索),可自定义实现Comparator接口实现排序方式。

    (3)初始化与增长方式
    初始化时:HashTable在不指定容量的情况下的默认容量为11,且不要求底层数组的容量一定要为2的整数次幂;HashMap默认容量为16,且要求容量一定为2的整数次幂。
    扩容时:Hashtable将容量变为原来的2倍加1;HashMap扩容将容量变为原来的2倍。

    (4)线程安全性
    HashTable其方法函数都是同步的(采用synchronized修饰),不会出现两个线程同时对数据进行操作的情况,因此保证了线程安全性。也正因为如此,在多线程运行环境下效率表现非常低下。因为当一个线程访问HashTable的同步方法时,其他线程也访问同步方法就会进入阻塞状态。比如当一个线程在添加数据时候,另外一个线程即使执行获取其他数据的操作也必须被阻塞,大大降低了程序的运行效率,在新版本中已被废弃,不推荐使用。
    HashMap不支持线程的同步,即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步(1)可以用 Collections的synchronizedMap方法;(2)使用ConcurrentHashMap类,相较于HashTable锁住的是对象整体, ConcurrentHashMap基于lock实现锁分段技术。首先将Map存放的数据分成一段一段的存储方式,然后给每一段数据分配一把锁,当一个线程占用锁访问其中一个段的数据时,其他段的数据也能被其他线程访问。ConcurrentHashMap不仅保证了多线程运行环境下的数据访问安全性,而且性能上有长足的提升。

    (5)一段话HashMap
    HashMap基于哈希思想,实现对数据的读写。当我们将键值对传递给put()方法时,它调用键对象的hashCode()方法来计算hashcode,让后找到bucket位置来储存值对象。当获取对象时,通过键对象的equals()方法找到正确的键值对,然后返回值对象。HashMap使用链表来解决碰撞问题,当发生碰撞了,对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。当两个不同的键对象的hashcode相同时,它们会储存在同一个bucket位置的链表中,可通过键对象的equals()方法用来找到键值对。如果链表大小超过阈值(TREEIFY_THRESHOLD, 8),链表就会被改造为树形结构。
    2018-05-24
    1
    189
  • 清风
    感觉每个知识点都很重要,但又点到为止,感觉读完不痛不痒,好像学到什么,但细想又没掌握什么,希望能够深入一点!
    2018-07-05
    1
    182
  • amourling
    提个意见,文章中请不要出现太多似乎,怀疑之类的必须,该是什么就是什么,不确定的不要拿出来。
    2018-07-11
    98
  • 小飞哥 ‍超級會員
    总觉得还是不太深,只是每个map的区别。我觉得每个map的实现都能讲出很多问题来,在面试时也经常碰壁,看完但也没觉得学到什么深入的地方
    2018-07-20
    1
    43
  • Jerry银银
    为什么HashMap要树化?

    文章说『本质是个安全问题』,但是导致安全问题的本质其实是性能问题。哈希碰撞频繁,导致链表过长,查询时间陡升,黑客则会利用这个『漏洞』来攻击服务器,让服务器CPU被大量占用,从而引起了安全问题。 而树化(使用红黑树)能将时间复杂度降到O(logn),从而避免查询时间过长。所以说,本质还是个性能问题。

    ----------
    个人理解哈


    作者回复: 竟然无法反驳,哈哈

    2018-11-27
    2
    25
  • 鲤鱼
    读到最后链表树化刚准备开始飙车,结果突然跳车。树化讲细点更好

    作者回复: 感谢反馈,最近几章篇幅都超标了……只能照顾大多数需求,抱歉

    2018-05-29
    20
  • Darcy
    equals 的对称、反射、传递等特性。
    这里的反射是不是写错了,应该是自反性,对称性,传递性,一致性等等
    2018-07-28
    12
  • j.c.
    这是面试必问题。什么时候也能讲讲红黑树的树化具体过程,那个旋转一直没搞懂。另外treeifyBin这个单词的词面意思是什么?
    2018-05-24
    1
    10
  • 陈大麦
    老师我想问一下,hashmap明明继承了abstractmap,而abstractmap已经实现了map接口,为什么hashmap还要实现map接口呢?
    2018-07-28
    1
    9
  • xinfangke
    老师 如果hashmap中不存在hash冲突 是不是就相当于一个数组结构呢 就不存在链表了呢

    作者回复: 我理解是

    2018-05-29
    9
  • 睡骨
    希望作者分享源码的时候,最好备注是基于哪个版本的 毕竟有些地方不同版本差异较大
    2018-08-31
    8
  • Lh
    Hashtable、HashMap、TreeMap心得

    三者均实现了Map接口,存储的内容是基于key-value的键值对映射,一个映射不能有重复的键,一个键最多只能映射一个值。

    (1) 元素特性
    HashTable中的key、value都不能为null;HashMap中的key、value可以为null,很显然只能有一个key为null的键值对,但是允许有多个值为null的键值对;TreeMap中当未实现 Comparator 接口时,key 不可以为null;当实现 Comparator 接口时,若未对null情况进行判断,则key不可以为null,反之亦然。

    (2)顺序特性
    HashTable、HashMap具有无序特性。TreeMap是利用红黑树来实现的(树中的每个节点的值,都会大于或等于它的左子树种的所有节点的值,并且小于或等于它的右子树中的所有节点的值),实现了SortMap接口,能够对保存的记录根据键进行排序。所以一般需要排序的情况下是选择TreeMap来进行,默认为升序排序方式(深度优先搜索),可自定义实现Comparator接口实现排序方式。

    (3)初始化与增长方式
    初始化时:HashTable在不指定容量的情况下的默认容量为11,且不要求底层数组的容量一定要为2的整数次幂;HashMap默认容量为16,且要求容量一定为2的整数次幂。
    扩容时:Hashtable将容量变为原来的2倍加1;HashMap扩容将容量变为原来的2倍。

    (4)线程安全性
    HashTable其方法函数都是同步的(采用synchronized修饰),不会出现两个线程同时对数据进行操作的情况,因此保证了线程安全性。也正因为如此,在多线程运行环境下效率表现非常低下。因为当一个线程访问HashTable的同步方法时,其他线程也访问同步方法就会进入阻塞状态。比如当一个线程在添加数据时候,另外一个线程即使执行获取其他数据的操作也必须被阻塞,大大降低了程序的运行效率,在新版本中已被废弃,不推荐使用。
    HashMap不支持线程的同步,即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步(1)可以用 Collections的synchronizedMap方法;(2)使用ConcurrentHashMap类,相较于HashTable锁住的是对象整体, ConcurrentHashMap基于lock实现锁分段技术。首先将Map存放的数据分成一段一段的存储方式,然后给每一段数据分配一把锁,当一个线程占用锁访问其中一个段的数据时,其他段的数据也能被其他线程访问。ConcurrentHashMap不仅保证了多线程运行环境下的数据访问安全性,而且性能上有长足的提升。

    (5)一段话HashMap
    HashMap基于哈希思想,实现对数据的读写。当我们将键值对传递给put()方法时,它调用键对象的hashCode()方法来计算hashcode,让后找到bucket位置来储存值对象。当获取对象时,通过键对象的equals()方法找到正确的键值对,然后返回值对象。HashMap使用链表来解决碰撞问题,当发生碰撞了,对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。当两个不同的键对象的hashcode相同时,它们会储存在同一个bucket位置的链表中,可通过键对象的equals()方法用来找到键值对。如果链表大小超过阈值(TREEIFY_THRESHOLD, 8),链表就会被改造为树形结构。
    2019-02-20
    5
  • 鲸息
    为什么重写了 hashCode 也要重写 equals 呢?官方文档写的是重写了 equals 一定要重写 hashCode
    2018-09-14
    5
  • coolboy
    removeEldestEntry这个方法是不是指移除最旧的对象,也就是按照最先被put进来的顺序,而不是指不常访问的对象。
    2018-06-24
    5
  • Jerry银银
    我一直认为:JAVA集合类是非常好的学习材料。

    如果敢说精通JAVA集合类,计算机功底肯定不会太差
    2018-05-24
    5
  • kevin
    看不太懂,讲的还不是不太浅显,既然是面试题,最好不要太浅,但也不要太深,你这个度掌握的不是很好

    作者回复: 嗯,谢谢指出

    2018-09-27
    1
    4
  • zjh
    受教了,把java集合的源代码掌握了,对java和数据结构的了解都会有很大的提升
    2018-05-28
    4
  • 代码狂徒
    针对负载因子,您所指的存太满会影响性能是指什么?毕竟已经开辟了相应内存空间的,没什么不用呢?

    作者回复: 冲突可能会增加,影响查询之类性能,当然看具体的需求

    2018-05-24
    4
收起评论
81
返回
顶部