专栏首页silentcow【Java面试总结】Java集合

【Java面试总结】Java集合

Java 集合

1. 说说List、Set、Map三者的区别

  • List(对付顺序的好帮手):List接口存储一组不唯一(可以有多个元素引用相同的对象),有序的对象
  • Set(注重独一无二的性质)不允许重复的集合。不会有多个元素引用相同的对象
  • Map(用key来搜索的专家):使用键值对存储。Map会维护与key有关联的值。两个key可以引用相同的对象,但key不能重复,典型的key是String类型,也可以是任意类型

2. ArrayList与LinkedList的区别

  1. 是否保证线程安全ArrayListLinkedList都是不同步的,也就是不保证线程安全;
  2. 底层数据结构ArrayList底层使用的是Object数组;LinkedList底层使用的是双向链表 数据结构(JDK1.6之前为循环链表,JDK1.7取消了循环。注意双向链表和双向循环链表的区别,下面有介绍到!)
  3. 插入和删除是否受元素位置的影响: ① . ArrayList采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。比如:执行add(E e)方法的时候,ArrayList会默认将指定的元素追加到此列表的末尾,这种情况的时间复杂度就是 0(1)。但是如果要在指定位置 i 插入和删除元素的话(add(int index,E e))时间复杂度就是 0(n - i)。因为在进行上述操作的时候,集合中第 i 个元素和第 n- i 个之后的元素都要向后/向前移一位。 ② . LinkedList采用链表存储,所以对于add(E e)方法的插入和删除的时间复杂度不受元素位置的影响,近似 0(1),如果是要在指定位置 i 插入或删除元素的话(add(int index,E e))时间复杂度近似为 0(n),因为需要先移动到指定位置再插入
  4. 是否支持快速随机访问LinkedList不支持搞笑的随机元素访问,而ArrayList支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)
  5. 内存占用空间ArrayList的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间,而 LinkedList的空间花费则体现在它的每一个元素都需要消耗比 ArrayList更多的空间(因 为要存放直接后继和直接前驱以及数据)。

list 的遍历方式选择:

  • 实现了 RandomAccess接口的 list,优先选择普通的 for 循环,其次是 foreach
  • 未实现 RandomAccess接口的 list,则优先选择 iterator遍历(foreach遍历底层也是通过 iterator实现的),大 size 的数据,千万不要使用普通for循环

注: ArrayList实现了RandomAccess接口,而LinkedList没有实现。为什么呢?我觉得还是和底层数据结构有关!ArrayList底层是数组,而LinkedList底层是链表。数组天然支持随机访问,时间复杂度为 O(1),所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素,时间复杂度为 O(n),所以不支持快速随机访问。ArrayList实现了RandomAccess接口,就表明了他具有快速随机访问功能。RandomAccess接口只是标识,并不是说ArrayList实现RandomAccess接口才具有快速随机访问功能的!

更多关于 RandomAccess接口的知识,请百度。

补充内容:双向链表和双向循环链表

双向链表:包含两个指针,一个prev指向前一个节点,一个next指向后一个节点。

推荐阅读:看图轻松理解数据结构与算法系列(双向链表)

双向循环链表:最后一个节点的 next 指向head,而 head 的prev指向最后一个节点,构成一个环。

3. ArrayList 与 Vector 区别呢?为什么要用Arraylist取代Vector呢?

Vector类的所有方法都是同步的。可以由两个线程安全地访问一个 Vector 对象,但是一个线程访问 Vector 的话代码要在同步操作上耗费大量的时间。

ArrayList不是同步的,所以不需要保证线程安全时建议使用 ArrayList。

4. ArrayList 的扩容机制

直接阅读Guide老哥的文章吧,我感觉写的很详细,我已经无法简写摘抄了,缺少一步都相当于缺少了灵魂:通过源码一步一步分析ArrayList 扩容机制

5. HashMap 和 HashTable 的区别

  1. 线程是否安全HashMap 是非线程安全的,HashTable 是线程安全的。HashTable 内部的方法基本都经过 synchronized修饰。(如果要保证线程安全,就使用 ConcurrentHashMap
  2. 效率:因为线程安全的问题,HashMap 要比 HashTable 效率高一点。另外,HashTable 基本被淘汰,不要在代码中使用它
  3. 对 Null key 和 Null value的支持HashMap中,null 可以作为键,这样的键只有一个,可以有一个或多个键所对应的值为 null。但是在HashTable中 put 中的键值只有一个 null,直接抛出 NullPointerException
  4. 初始化容量大小和每次扩充容量的大小不同: ① . 创建时如果不指定容量初始值 HashTable 默认的初试大小为11,之后每次扩容 ,容量变成原来的 2n+1;HashMap 默认的初试大小为 16,之后每次扩容,容量变成原来的2倍。 ② . 创建时如果指定了容量初始值,那么 HashTable 会直接使用给定的大小,而 HashMap 会将其扩充为2 的幂次方大小。
  5. 底层数据结构:JDK 1.8 以后的HashMap 在解决 哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8)时,将链表转换为红黑树,以减少搜索时间。HashTable 没有这样的机制。

6. HashMap 和 HashSet 的区别

HashSet 底层是基于 HashMap 实现的(HashSet 的源码非常非常少,因为除了clone()writeObject()readObject() HashSet 自己不得不实现之外,其他方法都是直接调用 HashMap 中的方法。

HashMap

HashSet

实现了Map接口

实现Set接口

存储键值对

仅存储对象

调用put()向map中添加元素

调用add()方法向map中添加元素

HashMap使用键(Key)计算Hashcode

HashSet使用成员对象来计算hashcode值,对于两个对象来说hashcode可能相同,所以equals()方法用来判断对象的相等性

7. HashSet如何检查重复

当把对象加入HashSet时,HashSet会先计算对象的HashCode值来判断对象加入的位置,同时也会与其它加入的对象的HashCode的值做比较,如果没有相符的HashCodeHashSet会假设对象没有重复出现。但是如果发现有相同的HashCode值的对象,这时会调用equals()方法来检查HashCode相等的对象是否真的相同。如果两者相同,HashSet就不会让加入操作成功。

hashcode()equals()的相关规定:

  1. 如果两个对象相等,则hashcode一定也是相同的
  2. 两个对象相等,对两个equals方法返回true
  3. 两个对象有相同的hashCode值,它们也不一定是相等的
  4. 综上,equals方法被覆盖过,则hashCode方法也必须被覆盖
  5. hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode(),则该class的两个对象无论如何都不会相等(即使这两个对象指向相同的数据)

== 与 equals 的区别

  1. ==是判断两个变量或实例是不是指向同一个内存空间 ,equals是判断两个变量或实例所指向的内存空间的值是不是相同
  2. ==是指对内存地址进行比较 equals()是对字符串的内容进行比较
  3. ==指引用是否相同 ,equals()指的是值是否相同

8. HashMap的底层实现

JDK 1.8之前

JDK 1.8之前HashMap底层是 数组和链表 结合在一起使用也就是 链表散列HashMap 通过 key 的hashCode经过扰动函数处理后得到的 hash 值,然后通过 (n - 1)& hash 判断当前元素存放的位置(这里的n指的是数组的长度),如果当前位置存在元素的话,就判断该元素与要存入的元素的 hash值,以及是key 是否相同,如果相同的话,直接覆盖,不相同就通过 拉链法解决冲突。

扰动函数指的就是 hashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法,换句话说使用扰动函数之后可以减少碰撞。

JDK 1.8 HashMap 的 hash 方法源码:

staticfinalinthash(Objectkey) {
    int h;
    // key.hashCode():返回散列值也就是hashcode
    // ^ :按位异或// j>ké无符号右移,忽略符号位,空位都以0补⻬
    return (keyWXnull) ?0 : (h=key.hashCode()) ^ (hj>k16); 
}

JDK1.7的 HashMap 的 hash 方法源码:

staticinthash(inth) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).

    h^= (hj>k20) ^ (hj>k12);
    returnh^ (hj>k7) ^ (hj>k4);
}

JDK 1.8 的 hash方法相比于 JDK 1.7 hash 方法更加简化,但是原理不变

相比于 JDK1.8 的 hash 方法,JDK 1.7 的 hash 方法的性能会稍差一点点,因为毕竟扰动了 4 次。

“拉链法”就是:将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。

JDK1.8之后相比于之前的版本, JDK1.8之后在解决哈希冲突时有了较大的变化,当链表⻓度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。

TreeMap、TreeSet以及JDK1.8之后的HashMap底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷,因为二叉查找树在某些情况下会退化成一个线性结构。

推荐阅读:《Java 8系列之重新认识HashMap》

注:本块内容后期再做整理修改

9. HashMap 的长度为什么是2的幂次方

为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀。

Hash 值 的范围值 -21474836482147483647,前后加起来大概40亿的映射空间,只要哈希函数映射得比较均匀松散,一般应用很难出现碰撞的。但问题是一个40亿长度的数组,内存是放不下的,所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算,得到的余数才能用来要存放的位置,也就是对应的数组 下标。这个数组下标的计算方法是“(n - 1)& hash”。(n代表数组⻓度),这也就解释了HashMap的⻓度为什么是2的幂次方。

那么,如何设计这个算法呢?

我们首先可能会想到采用%取余的操作来实现。但是,重点来了:“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作(也就是说 hash%lengthdehash&(length-1)的前提是 length 是2的n 次方;)。”并且采用二进制位操作 &,相对于%能够提高运算效率,这就解释了 HashMap 的⻓度为什么是2的幂次方。

10. HashMap 多线程操作导致死循环问题

主要原因在于并发下的Rehash 会造成元素之间会形成一个循环链表。不过,jdk 1.8 后解决了这个问题,但是还是不建议在多线程下使用 HashMap,因为多线程下使用 HashMap 还是会存在其他问题比如数据丢失。并发环境下推荐使用 ConcurrentHashMap

推荐阅读:疫苗:Java HashMap的死循环

11. ConcurrentHashMap 和 Hashtable 的区别

后期补上

12. ConcurrentHashMap线程安全的具体实现方式/底层具体实现

后期补上

13. comparable 和 Comparator的区别

后期补上

14. 集合框架底层数据结构总结

后期补上

15. 如何选用集合?

主要根据集合的特点来选用,比如我们需要根据键值获取到元素值时就选用Map接口下的集合,需要排序时选择TreeMap,不需要排序时就选择HashMap,需要保证线程安全就选用ConcurrentHashMap.当我们只需要存放元素值时,就选择实现Collection接口的集合,需要保证元素唯一时选择实现Set接口的集合比如TreeSetHashSet,不需要就选择实现List接口的比如ArrayListLinkedList,然后再根据实现这些接口的集合的特点来选用。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【Java面试总结】计算机网络

    我们在学习的时候,一般采用折中的办法,也就是中和 OSI 与 TCP/IP 的优点,采用一种只有五层协议的体系结构,这样既简介又能将概念阐述清楚。

    silentcow
  • 【Java面试总结】常用框架之Spring

    Spring 是一种轻量级开发框架,皆在指提高开发人员的开发效率以及系统的可维护性。

    silentcow
  • Tomcat & Servlet的学习

    silentcow
  • HashMap面试必问的6个点,你知道几个?

    针对这个问题,嗯,当然是必须看过HashMap源码。至于原理,下面那张图很清楚了:

    程序员追风
  • 【简单了解系列】从基础的使用来深挖HashMap

    说的专业一点,HashMap是常用的用于存储key-value键值对数据的一个集合,底层是基于对Map的接口实现。每一个键值对又叫Entry,这些Entry分散...

    SH的全栈笔记
  • 解读目标检测新范式:Segmentations is All You Need

    作者利用注释质量较差的边界框在困难环境中实现稳健的目标检测性能,避免了与 anchor 框或 NMS 相关的所有超参数。他们提出的模型超越了之前基于 ancho...

    机器之心
  • 解读目标检测新范式:Segmentations is All You Need

    作者利用注释质量较差的边界框在困难环境中实现稳健的目标检测性能,避免了与 anchor 框或 NMS 相关的所有超参数。他们提出的模型超越了之前基于 ancho...

    AI算法与图像处理
  • 浅谈简易端口扫描威胁感知系统的设计与实现

    一 前言: 正所谓善守者不知其所攻,善攻者不知其所守。网络攻防本来就是一场看不见硝烟的对抗。 本人设计的这套端口蜜罐检测程序,是在总结了大量的APT攻击方法和思...

    FB客服
  • 查找----基于散列表(拉链法)

    SuperHeroes
  • 如何通过冒烟测试前置来把控提测质量?

    你是否碰到过开发提测速度很快,导致项目排队,结果介入测试时,第一条用例都跑不通的情况?

    sylan215

扫码关注云+社区

领取腾讯云代金券