精华内容
下载资源
问答
  • Java集合容器面试题(2020最新版)

    万次阅读 多人点赞 2020-03-01 11:08:34
    文章目录集合容器概述什么是集合集合的特点集合和数组的区别使用集合框架的好处常用的集合类有哪些?List,Set,Map三者的区别?...Java集合的快速失败机制 “fail-fast”?怎么确保一个集合不能被修改?Collection...

    Java面试总结(2021优化版)已发布在个人微信公众号【技术人成长之路】,优化版首先修正了读者反馈的部分答案存在的错误,同时根据最新面试总结,删除了低频问题,添加了一些常见面试题,对文章进行了精简优化,欢迎大家关注!😊😊

    【技术人成长之路】,助力技术人成长!更多精彩文章第一时间在公众号发布哦!

    文章目录

    Java面试总结汇总,整理了包括Java基础知识,集合容器,并发编程,JVM,常用开源框架Spring,MyBatis,数据库,中间件等,包含了作为一个Java工程师在面试中需要用到或者可能用到的绝大部分知识。欢迎大家阅读,本人见识有限,写的博客难免有错误或者疏忽的地方,还望各位大佬指点,在此表示感激不尽。文章持续更新中…

    序号内容链接地址
    1Java基础知识面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104390612
    2Java集合容器面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104588551
    3Java异常面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104390689
    4并发编程面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104863992
    5JVM面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104390752
    6Spring面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104397516
    7Spring MVC面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104397427
    8Spring Boot面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104397299
    9Spring Cloud面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104397367
    10MyBatis面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/101292950
    11Redis面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/103522351
    12MySQL数据库面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104778621
    13消息中间件MQ与RabbitMQ面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104588612
    14Dubbo面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104390006
    15Linux面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104588679
    16Tomcat面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104397665
    17ZooKeeper面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104397719
    18Netty面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104391081
    19架构设计&分布式&数据结构与算法面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/105870730

    集合容器概述

    什么是集合

    集合框架:用于存储数据的容器。

    集合框架是为表示和操作集合而规定的一种统一的标准的体系结构。
    任何集合框架都包含三大块内容:对外的接口、接口的实现和对集合运算的算法。

    接口:表示集合的抽象数据类型。接口允许我们操作集合时不必关注具体实现,从而达到“多态”。在面向对象编程语言中,接口通常用来形成规范。

    实现:集合接口的具体实现,是重用性很高的数据结构。

    算法:在一个实现了某个集合框架中的接口的对象身上完成某种有用的计算的方法,例如查找、排序等。这些算法通常是多态的,因为相同的方法可以在同一个接口被多个类实现时有不同的表现。事实上,算法是可复用的函数。
    它减少了程序设计的辛劳。

    集合框架通过提供有用的数据结构和算法使你能集中注意力于你的程序的重要部分上,而不是为了让程序能正常运转而将注意力于低层设计上。
    通过这些在无关API之间的简易的互用性,使你免除了为改编对象或转换代码以便联合这些API而去写大量的代码。 它提高了程序速度和质量。

    集合的特点

    集合的特点主要有如下两点:

    • 对象封装数据,对象多了也需要存储。集合用于存储对象。

    • 对象的个数确定可以使用数组,对象的个数不确定的可以用集合。因为集合是可变长度的。

    集合和数组的区别

    • 数组是固定长度的;集合可变长度的。

    • 数组可以存储基本数据类型,也可以存储引用数据类型;集合只能存储引用数据类型。

    • 数组存储的元素必须是同一个数据类型;集合存储的对象可以是不同数据类型。

    数据结构:就是容器中存储数据的方式。

    对于集合容器,有很多种。因为每一个容器的自身特点不同,其实原理在于每个容器的内部数据结构不同。

    集合容器在不断向上抽取过程中,出现了集合体系。在使用一个体系的原则:参阅顶层内容。建立底层对象。

    使用集合框架的好处

    1. 容量自增长;
    2. 提供了高性能的数据结构和算法,使编码更轻松,提高了程序速度和质量;
    3. 允许不同 API 之间的互操作,API之间可以来回传递集合;
    4. 可以方便地扩展或改写集合,提高代码复用性和可操作性。
    5. 通过使用JDK自带的集合类,可以降低代码维护和学习新API成本。

    常用的集合类有哪些?

    Map接口和Collection接口是所有集合框架的父接口:

    1. Collection接口的子接口包括:Set接口和List接口
    2. Map接口的实现类主要有:HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等
    3. Set接口的实现类主要有:HashSet、TreeSet、LinkedHashSet等
    4. List接口的实现类主要有:ArrayList、LinkedList、Stack以及Vector等

    List,Set,Map三者的区别?List、Set、Map 是否继承自 Collection 接口?List、Map、Set 三个接口存取元素时,各有什么特点?

    img

    Java 容器分为 Collection 和 Map 两大类,Collection集合的子接口有Set、List、Queue三种子接口。我们比较常用的是Set、List,Map接口不是collection的子接口。

    Collection集合主要有List和Set两大接口

    • List:一个有序(元素存入集合的顺序和取出的顺序一致)容器,元素可以重复,可以插入多个null元素,元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。
    • Set:一个无序(存入和取出顺序有可能不一致)容器,不可以存储重复元素,只允许存入一个null元素,必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet。

    Map是一个键值对集合,存储键、值和之间的映射。 Key无序,唯一;value 不要求有序,允许重复。Map没有继承于Collection接口,从Map集合中检索元素时,只要给出键对象,就会返回对应的值对象。

    Map 的常用实现类:HashMap、TreeMap、HashTable、LinkedHashMap、ConcurrentHashMap

    集合框架底层数据结构

    Collection

    1. List
    • Arraylist: Object数组
    • Vector: Object数组
    • LinkedList: 双向循环链表
    1. Set
    • HashSet(无序,唯一):基于 HashMap 实现的,底层采用 HashMap 来保存元素
    • LinkedHashSet: LinkedHashSet 继承与 HashSet,并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 Hashmap 实现一样,不过还是有一点点区别的。
    • TreeSet(有序,唯一): 红黑树(自平衡的排序二叉树。)

    Map

    • HashMap: JDK1.8之前HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突).JDK1.8以后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间
    • LinkedHashMap:LinkedHashMap 继承自 HashMap,所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外,LinkedHashMap 在上面结构的基础上,增加了一条双向链表,使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作,实现了访问顺序相关逻辑。
    • HashTable: 数组+链表组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的
    • TreeMap: 红黑树(自平衡的排序二叉树)

    哪些集合类是线程安全的?

    • vector:就比arraylist多了个同步化机制(线程安全),因为效率较低,现在已经不太建议使用。在web应用中,特别是前台页面,往往效率(页面响应速度)是优先考虑的。
    • statck:堆栈类,先进后出。
    • hashtable:就比hashmap多了个线程安全。
    • enumeration:枚举,相当于迭代器。

    Java集合的快速失败机制 “fail-fast”?

    是java集合的一种错误检测机制,当多个线程对集合进行结构上的改变的操作时,有可能会产生 fail-fast 机制。

    例如:假设存在两个线程(线程1、线程2),线程1通过Iterator在遍历集合A中的元素,在某个时候线程2修改了集合A的结构(是结构上面的修改,而不是简单的修改集合元素的内容),那么这个时候程序就会抛出 ConcurrentModificationException 异常,从而产生fail-fast机制。

    原因:迭代器在遍历时直接访问集合中的内容,并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化,就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前,都会检测modCount变量是否为expectedmodCount值,是的话就返回遍历;否则抛出异常,终止遍历。

    解决办法:

    1. 在遍历过程中,所有涉及到改变modCount值得地方全部加上synchronized。

    2. 使用CopyOnWriteArrayList来替换ArrayList

    怎么确保一个集合不能被修改?

    可以使用 Collections. unmodifiableCollection(Collection c) 方法来创建一个只读集合,这样改变集合的任何操作都会抛出 Java. lang. UnsupportedOperationException 异常。

    示例代码如下:

    List<String> list = new ArrayList<>();
    list. add("x");
    Collection<String> clist = Collections. unmodifiableCollection(list);
    clist. add("y"); // 运行时此行报错
    System. out. println(list. size());
    

    Collection接口

    List接口

    迭代器 Iterator 是什么?

    Iterator 接口提供遍历任何 Collection 的接口。我们可以从一个 Collection 中使用迭代器方法来获取迭代器实例。迭代器取代了 Java 集合框架中的 Enumeration,迭代器允许调用者在迭代过程中移除元素。

    Iterator 怎么使用?有什么特点?

    Iterator 使用代码如下:

    List<String> list = new ArrayList<>();
    Iterator<String> it = list. iterator();
    while(it. hasNext()){
      String obj = it. next();
      System. out. println(obj);
    }
    

    Iterator 的特点是只能单向遍历,但是更加安全,因为它可以确保,在当前遍历的集合元素被更改的时候,就会抛出 ConcurrentModificationException 异常。

    如何边遍历边移除 Collection 中的元素?

    边遍历边修改 Collection 的唯一正确方式是使用 Iterator.remove() 方法,如下:

    Iterator<Integer> it = list.iterator();
    while(it.hasNext()){
       *// do something*
       it.remove();
    }
    

    一种最常见的错误代码如下:

    for(Integer i : list){
       list.remove(i)
    }
    

    运行以上错误代码会报 ConcurrentModificationException 异常。这是因为当使用 foreach(for(Integer i : list)) 语句时,会自动生成一个iterator 来遍历该 list,但同时该 list 正在被 Iterator.remove() 修改。Java 一般不允许一个线程在遍历 Collection 时另一个线程修改它。

    Iterator 和 ListIterator 有什么区别?

    • Iterator 可以遍历 Set 和 List 集合,而 ListIterator 只能遍历 List。
    • Iterator 只能单向遍历,而 ListIterator 可以双向遍历(向前/后遍历)。
    • ListIterator 实现 Iterator 接口,然后添加了一些额外的功能,比如添加一个元素、替换一个元素、获取前面或后面元素的索引位置。

    遍历一个 List 有哪些不同的方式?每种方法的实现原理是什么?Java 中 List 遍历的最佳实践是什么?

    遍历方式有以下几种:

    1. for 循环遍历,基于计数器。在集合外部维护一个计数器,然后依次读取每一个位置的元素,当读取到最后一个元素后停止。

    2. 迭代器遍历,Iterator。Iterator 是面向对象的一个设计模式,目的是屏蔽不同数据集合的特点,统一遍历集合的接口。Java 在 Collections 中支持了 Iterator 模式。

    3. foreach 循环遍历。foreach 内部也是采用了 Iterator 的方式实现,使用时不需要显式声明 Iterator 或计数器。优点是代码简洁,不易出错;缺点是只能做简单的遍历,不能在遍历过程中操作数据集合,例如删除、替换。

    最佳实践:Java Collections 框架中提供了一个 RandomAccess 接口,用来标记 List 实现是否支持 Random Access。

    • 如果一个数据集合实现了该接口,就意味着它支持 Random Access,按位置读取元素的平均时间复杂度为 O(1),如ArrayList。
    • 如果没有实现该接口,表示不支持 Random Access,如LinkedList。

    推荐的做法就是,支持 Random Access 的列表可用 for 循环遍历,否则建议用 Iterator 或 foreach 遍历。

    说一下 ArrayList 的优缺点

    ArrayList的优点如下:

    • ArrayList 底层以数组实现,是一种随机访问模式。ArrayList 实现了 RandomAccess 接口,因此查找的时候非常快。
    • ArrayList 在顺序添加一个元素的时候非常方便。

    ArrayList 的缺点如下:

    • 删除元素的时候,需要做一次元素复制操作。如果要复制的元素很多,那么就会比较耗费性能。
    • 插入元素的时候,也需要做一次元素复制操作,缺点同上。

    ArrayList 比较适合顺序添加、随机访问的场景。

    如何实现数组和 List 之间的转换?

    • 数组转 List:使用 Arrays. asList(array) 进行转换。
    • List 转数组:使用 List 自带的 toArray() 方法。

    代码示例:

    // list to array
    List<String> list = new ArrayList<String>();
    list.add("123");
    list.add("456");
    list.toArray();
    
    // array to list
    String[] array = new String[]{"123","456"};
    Arrays.asList(array);
    

    ArrayList 和 LinkedList 的区别是什么?

    • 数据结构实现:ArrayList 是动态数组的数据结构实现,而 LinkedList 是双向链表的数据结构实现。
    • 随机访问效率:ArrayList 比 LinkedList 在随机访问的时候效率要高,因为 LinkedList 是线性的数据存储方式,所以需要移动指针从前往后依次查找。
    • 增加和删除效率:在非首尾的增加和删除操作,LinkedList 要比 ArrayList 效率要高,因为 ArrayList 增删操作要影响数组内的其他数据的下标。
    • 内存空间占用:LinkedList 比 ArrayList 更占内存,因为 LinkedList 的节点除了存储数据,还存储了两个引用,一个指向前一个元素,一个指向后一个元素。
    • 线程安全:ArrayList 和 LinkedList 都是不同步的,也就是不保证线程安全;

    综合来说,在需要频繁读取集合中的元素时,更推荐使用 ArrayList,而在插入和删除操作较多时,更推荐使用 LinkedList。

    补充:数据结构基础之双向链表

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。

    ArrayList 和 Vector 的区别是什么?

    这两个类都实现了 List 接口(List 接口继承了 Collection 接口),他们都是有序集合

    • 线程安全:Vector 使用了 Synchronized 来实现线程同步,是线程安全的,而 ArrayList 是非线程安全的。
    • 性能:ArrayList 在性能方面要优于 Vector。
    • 扩容:ArrayList 和 Vector 都会根据实际的需要动态的调整容量,只不过在 Vector 扩容每次会增加 1 倍,而 ArrayList 只会增加 50%。

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

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

    插入数据时,ArrayList、LinkedList、Vector谁速度较快?阐述 ArrayList、Vector、LinkedList 的存储性能和特性?

    ArrayList、LinkedList、Vector 底层的实现都是使用数组方式存储数据。数组元素数大于实际存储的数据以便增加和插入元素,它们都允许直接按序号索引元素,但是插入元素要涉及数组元素移动等内存操作,所以索引数据快而插入数据慢。

    Vector 中的方法由于加了 synchronized 修饰,因此 Vector 是线程安全容器,但性能上较ArrayList差

    LinkedList 使用双向链表实现存储,按序号索引数据需要进行前向或后向遍历,但插入数据时只需要记录当前项的前后项即可,所以 LinkedList 插入速度较快

    多线程场景下如何使用 ArrayList?

    ArrayList 不是线程安全的,如果遇到多线程场景,可以通过 Collections 的 synchronizedList 方法将其转换成线程安全的容器后再使用。例如像下面这样:

    List<String> synchronizedList = Collections.synchronizedList(list);
    synchronizedList.add("aaa");
    synchronizedList.add("bbb");
    
    for (int i = 0; i < synchronizedList.size(); i++) {
        System.out.println(synchronizedList.get(i));
    }
    

    为什么 ArrayList 的 elementData 加上 transient 修饰?

    ArrayList 中的数组定义如下:

    private transient Object[] elementData;
    

    再看一下 ArrayList 的定义:

    public class ArrayList<E> extends AbstractList<E>
         implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    

    可以看到 ArrayList 实现了 Serializable 接口,这意味着 ArrayList 支持序列化。transient 的作用是说不希望 elementData 数组被序列化,重写了 writeObject 实现:

    private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
        *// Write out element count, and any hidden stuff*
            int expectedModCount = modCount;
        s.defaultWriteObject();
        *// Write out array length*
            s.writeInt(elementData.length);
        *// Write out all elements in the proper order.*
            for (int i=0; i<size; i++)
                s.writeObject(elementData[i]);
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
    }
    

    每次序列化时,先调用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素,然后遍历 elementData,只序列化已存入的元素,这样既加快了序列化的速度,又减小了序列化之后的文件大小。

    List 和 Set 的区别

    List , Set 都是继承自Collection 接口

    List 特点:一个有序(元素存入集合的顺序和取出的顺序一致)容器,元素可以重复,可以插入多个null元素,元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。

    Set 特点:一个无序(存入和取出顺序有可能不一致)容器,不可以存储重复元素,只允许存入一个null元素,必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet。

    另外 List 支持for循环,也就是通过下标来遍历,也可以用迭代器,但是set只能用迭代,因为他无序,无法用下标来取得想要的值。

    Set和List对比

    Set:检索元素效率低下,删除和插入效率高,插入和删除不会引起元素位置改变。
    List:和数组类似,List可以动态增长,查找元素效率高,插入删除元素效率低,因为会引起其他元素位置改变

    Set接口

    说一下 HashSet 的实现原理?

    HashSet 是基于 HashMap 实现的,HashSet的值存放于HashMap的key上,HashMap的value统一为PRESENT,因此 HashSet 的实现比较简单,相关 HashSet 的操作,基本上都是直接调用底层 HashMap 的相关方法来完成,HashSet 不允许重复的值。

    HashSet如何检查重复?HashSet是如何保证数据不可重复的?

    向HashSet 中add ()元素时,判断元素是否存在的依据,不仅要比较hash值,同时还要结合equles 方法比较。
    HashSet 中的add ()方法会使用HashMap 的put()方法。

    HashMap 的 key 是唯一的,由源码可以看出 HashSet 添加进去的值就是作为HashMap 的key,并且在HashMap中如果K/V相同时,会用新的V覆盖掉旧的V,然后返回旧的V。所以不会重复( HashMap 比较key是否相等是先比较hashcode 再比较equals )。

    以下是HashSet 部分源码:

    private static final Object PRESENT = new Object();
    private transient HashMap<E,Object> map;
    
    public HashSet() {
        map = new HashMap<>();
    }
    
    public boolean add(E e) {
        // 调用HashMap的put方法,PRESENT是一个至始至终都相同的虚值
    	return map.put(e, PRESENT)==null;
    }
    

    hashCode()与equals()的相关规定

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

    ==与equals的区别

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

    HashSet与HashMap的区别

    HashMapHashSet
    实现了Map接口实现Set接口
    存储键值对仅存储对象
    调用put()向map中添加元素调用add()方法向Set中添加元素
    HashMap使用键(Key)计算HashcodeHashSet使用成员对象来计算hashcode值,对于两个对象来说hashcode可能相同,所以equals()方法用来判断对象的相等性,如果两个对象不同的话,那么返回false
    HashMap相对于HashSet较快,因为它是使用唯一的键获取对象HashSet较HashMap来说比较慢

    Queue

    BlockingQueue是什么?

    Java.util.concurrent.BlockingQueue是一个队列,在进行检索或移除一个元素的时候,它会等待队列变为非空;当在添加一个元素时,它会等待队列中的可用空间。BlockingQueue接口是Java集合框架的一部分,主要用于实现生产者-消费者模式。我们不需要担心等待生产者有可用的空间,或消费者有可用的对象,因为它都在BlockingQueue的实现类中被处理了。Java提供了集中BlockingQueue的实现,比如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue,、SynchronousQueue等。

    在 Queue 中 poll()和 remove()有什么区别?

    • 相同点:都是返回第一个元素,并在队列中删除返回的对象。
    • 不同点:如果没有元素 poll()会返回 null,而 remove()会直接抛出 NoSuchElementException 异常。

    代码示例:

    Queue<String> queue = new LinkedList<String>();
    queue. offer("string"); // add
    System. out. println(queue. poll());
    System. out. println(queue. remove());
    System. out. println(queue. size());
    

    Map接口

    说一下 HashMap 的实现原理?

    HashMap概述: HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。

    HashMap的数据结构: 在Java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。

    HashMap 基于 Hash 算法实现的

    1. 当我们往Hashmap中put元素时,利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
    2. 存储时,如果出现hash值相同的key,此时有两种情况。(1)如果key相同,则覆盖原始值;(2)如果key不同(出现冲突),则将当前的key-value放入链表中
    3. 获取时,直接找到hash值对应的下标,在进一步判断key是否相同,从而找到对应值。
    4. 理解了以上过程就不难明白HashMap是如何解决hash冲突的问题,核心就是使用了数组的存储方式,然后将冲突的key的对象放入链表中,一旦发现冲突就在链表中做进一步的对比。

    需要注意Jdk 1.8中对HashMap的实现做了优化,当链表中的节点数据超过八个之后,该链表会转为红黑树来提高查询效率,从原来的O(n)到O(logn)

    HashMap在JDK1.7和JDK1.8中有哪些不同?HashMap的底层实现

    在Java中,保存数据有两种比较简单的数据结构:数组和链表。数组的特点是:寻址容易,插入和删除困难;链表的特点是:寻址困难,但插入和删除容易;所以我们将数组和链表结合在一起,发挥两者各自的优势,使用一种叫做拉链法的方式可以解决哈希冲突。

    JDK1.8之前

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

    jdk1.7中HashMap数据结构

    JDK1.8之后

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

    jdk1.8中HashMap数据结构

    JDK1.7 VS JDK1.8 比较

    JDK1.8主要解决或优化了一下问题:

    1. resize 扩容优化
    2. 引入了红黑树,目的是避免单条链表过长而影响查询效率,红黑树算法请参考
    3. 解决了多线程死循环问题,但仍是非线程安全的,多线程时可能会造成数据丢失问题。
    不同JDK 1.7JDK 1.8
    存储结构数组 + 链表数组 + 链表 + 红黑树
    初始化方式单独函数:inflateTable()直接集成到了扩容函数resize()
    hash值计算方式扰动处理 = 9次扰动 = 4次位运算 + 5次异或运算扰动处理 = 2次扰动 = 1次位运算 + 1次异或运算
    存放数据的规则无冲突时,存放数组;冲突时,存放链表无冲突时,存放数组;冲突 & 链表长度 < 8:存放单链表;冲突 & 链表长度 > 8:树化并存放红黑树
    插入数据方式头插法(先讲原位置的数据移到后1位,再插入数据到该位置)尾插法(直接插入到链表尾部/红黑树)
    扩容后存储位置的计算方式全部按照原来方法进行计算(即hashCode ->> 扰动函数 ->> (h&length-1))按照扩容后的规律计算(即扩容后的位置=原位置 or 原位置 + 旧容量)

    HashMap的put方法的具体流程?

    当我们put的时候,首先计算 keyhash值,这里调用了 hash方法,hash方法实际是让key.hashCode()key.hashCode()>>>16进行异或操作,高16bit补0,一个数和0异或不变,所以 hash 函数大概的作用就是:高16bit不变,低16bit和高16bit做了一个异或,目的是减少碰撞。按照函数注释,因为bucket数组大小是2的幂,计算下标index = (table.length - 1) & hash,如果不做 hash 处理,相当于散列生效的只有几个低 bit 位,为了减少散列的碰撞,设计者综合考虑了速度、作用、质量之后,使用高16bit和低16bit异或来简单处理减少碰撞,而且JDK8中用了复杂度 O(logn)的树结构来提升碰撞下的性能。

    putVal方法执行流程图

    putVal方法执行流程图

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    //实现Map.put和相关方法
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 步骤①:tab为空则创建 
        // table未初始化或者长度为0,进行扩容
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 步骤②:计算index,并对null做处理  
        // (n - 1) & hash 确定元素存放在哪个桶中,桶为空,新生成结点放入桶中(此时,这个结点是放在数组中)
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        // 桶中已经存在元素
        else {
            Node<K,V> e; K k;
            // 步骤③:节点key存在,直接覆盖value 
            // 比较桶中第一个元素(数组中的结点)的hash值相等,key相等
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                    // 将第一个元素赋值给e,用e来记录
                    e = p;
            // 步骤④:判断该链为红黑树 
            // hash值不相等,即key不相等;为红黑树结点
            // 如果当前元素类型为TreeNode,表示为红黑树,putTreeVal返回待存放的node, e可能为null
            else if (p instanceof TreeNode)
                // 放入树中
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            // 步骤⑤:该链为链表 
            // 为链表结点
            else {
                // 在链表最末插入结点
                for (int binCount = 0; ; ++binCount) {
                    // 到达链表的尾部
                    
                    //判断该链表尾部指针是不是空的
                    if ((e = p.next) == null) {
                        // 在尾部插入新结点
                        p.next = newNode(hash, key, value, null);
                        //判断链表的长度是否达到转化红黑树的临界值,临界值为8
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //链表结构转树形结构
                            treeifyBin(tab, hash);
                        // 跳出循环
                        break;
                    }
                    // 判断链表中结点的key值与插入的元素的key值是否相等
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        // 相等,跳出循环
                        break;
                    // 用于遍历桶中的链表,与前面的e = p.next组合,可以遍历链表
                    p = e;
                }
            }
            //判断当前的key已经存在的情况下,再来一个相同的hash值、key值时,返回新来的value这个值
            if (e != null) { 
                // 记录e的value
                V oldValue = e.value;
                // onlyIfAbsent为false或者旧值为null
                if (!onlyIfAbsent || oldValue == null)
                    //用新值替换旧值
                    e.value = value;
                // 访问后回调
                afterNodeAccess(e);
                // 返回旧值
                return oldValue;
            }
        }
        // 结构性修改
        ++modCount;
        // 步骤⑥:超过最大容量就扩容 
        // 实际大小大于阈值则扩容
        if (++size > threshold)
            resize();
        // 插入后回调
        afterNodeInsertion(evict);
        return null;
    }
    

    ①.判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容;

    ②.根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向⑥,如果table[i]不为空,转向③;

    ③.判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是hashCode以及equals;

    ④.判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤;

    ⑤.遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;

    ⑥.插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。

    HashMap的扩容操作是怎么实现的?

    ①.在jdk1.8中,resize方法是在hashmap中的键值对大于阀值时或者初始化时,就调用resize方法进行扩容;

    ②.每次扩展的时候,都是扩展2倍;

    ③.扩展后Node对象的位置要么在原位置,要么移动到原偏移量两倍的位置。

    在putVal()中,我们看到在这个函数里面使用到了2次resize()方法,resize()方法表示的在进行第一次初始化时会对其进行扩容,或者当该数组的实际大小大于其临界值值(第一次为12),这个时候在扩容的同时也会伴随的桶上面的元素进行重新分发,这也是JDK1.8版本的一个优化的地方,在1.7中,扩容之后需要重新去计算其Hash值,根据Hash值对其进行分发,但在1.8版本中,则是根据在同一个桶的位置中进行判断(e.hash & oldCap)是否为0,重新进行hash分配后,该元素的位置要么停留在原始位置,要么移动到原始位置+增加的数组大小这个位置上

    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;//oldTab指向hash桶数组
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {//如果oldCap不为空的话,就是hash桶数组不为空
            if (oldCap >= MAXIMUM_CAPACITY) {//如果大于最大容量了,就赋值为整数最大的阀值
                threshold = Integer.MAX_VALUE;
                return oldTab;//返回
            }//如果当前hash桶数组的长度在扩容后仍然小于最大容量 并且oldCap大于默认值16
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold 双倍扩容阀值threshold
        }
        // 旧的容量为0,但threshold大于零,代表有参构造有cap传入,threshold已经被初始化成最小2的n次幂
        // 直接将该值赋给新的容量
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        // 无参构造创建的map,给出默认容量和threshold 16, 16*0.75
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // 新的threshold = 新的cap * 0.75
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        // 计算出新的数组长度后赋给当前成员变量table
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//新建hash桶数组
        table = newTab;//将新数组的值复制给旧的hash桶数组
        // 如果原先的数组没有初始化,那么resize的初始化工作到此结束,否则进入扩容元素重排逻辑,使其均匀的分散
        if (oldTab != null) {
            // 遍历新数组的所有桶下标
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    // 旧数组的桶下标赋给临时变量e,并且解除旧数组中的引用,否则就数组无法被GC回收
                    oldTab[j] = null;
                    // 如果e.next==null,代表桶中就一个元素,不存在链表或者红黑树
                    if (e.next == null)
                        // 用同样的hash映射算法把该元素加入新的数组
                        newTab[e.hash & (newCap - 1)] = e;
                    // 如果e是TreeNode并且e.next!=null,那么处理树中元素的重排
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    // e是链表的头并且e.next!=null,那么处理链表中元素重排
                    else { // preserve order
                        // loHead,loTail 代表扩容后不用变换下标,见注1
                        Node<K,V> loHead = null, loTail = null;
                        // hiHead,hiTail 代表扩容后变换下标,见注1
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        // 遍历链表
                        do {             
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    // 初始化head指向链表当前元素e,e不一定是链表的第一个元素,初始化后loHead
                                    // 代表下标保持不变的链表的头元素
                                    loHead = e;
                                else                                
                                    // loTail.next指向当前e
                                    loTail.next = e;
                                // loTail指向当前的元素e
                                // 初始化后,loTail和loHead指向相同的内存,所以当loTail.next指向下一个元素时,
                                // 底层数组中的元素的next引用也相应发生变化,造成lowHead.next.next.....
                                // 跟随loTail同步,使得lowHead可以链接到所有属于该链表的元素。
                                loTail = e;                           
                            }
                            else {
                                if (hiTail == null)
                                    // 初始化head指向链表当前元素e, 初始化后hiHead代表下标更改的链表头元素
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        // 遍历结束, 将tail指向null,并把链表头放入新数组的相应下标,形成新的映射。
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
    

    HashMap是怎么解决哈希冲突的?

    答:在解决这个问题之前,我们首先需要知道什么是哈希冲突,而在了解哈希冲突之前我们还要知道什么是哈希才行;

    什么是哈希?

    Hash,一般翻译为“散列”,也有直接音译为“哈希”的,这就是把任意长度的输入通过散列算法,变换成固定长度的输出,该输出就是散列值(哈希值);这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数

    所有散列函数都有如下一个基本特性**:根据同一散列函数计算出的散列值如果不同,那么输入值肯定也不同。但是,根据同一散列函数计算出的散列值如果相同,输入值不一定相同**。

    什么是哈希冲突?

    当两个不同的输入值,根据同一散列函数计算出相同的散列值的现象,我们就把它叫做碰撞(哈希碰撞)

    HashMap的数据结构

    在Java中,保存数据有两种比较简单的数据结构:数组和链表。数组的特点是:寻址容易,插入和删除困难;链表的特点是:寻址困难,但插入和删除容易;所以我们将数组和链表结合在一起,发挥两者各自的优势,使用一种叫做链地址法的方式可以解决哈希冲突:

    img

    这样我们就可以将拥有相同哈希值的对象组织成一个链表放在hash值所对应的bucket下,但相比于hashCode返回的int类型,我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4(即2的四次方16)要远小于int类型的范围,所以我们如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率,并且最坏情况下还会将HashMap变成一个单链表,所以我们还需要对hashCode作一定的优化

    hash()函数

    上面提到的问题,主要是因为如果使用hashCode取余,那么相当于参与运算的只有hashCode的低位,高位是没有起到任何作用的,所以我们的思路就是让hashCode取值出的高位也参与运算,进一步降低hash碰撞的概率,使得数据分布更平均,我们把这样的操作称为扰动,在JDK 1.8中的hash()函数如下:

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位进行异或运算(高低位异或)
    }
    

    这比在JDK 1.7中,更为简洁,相比在1.7中的4次位运算,5次异或运算(9次扰动),在1.8中,只进行了1次位运算和1次异或运算(2次扰动)

    JDK1.8新增红黑树

    img

    通过上面的链地址法(使用散列表)扰动函数我们成功让我们的数据分布更平均,哈希碰撞减少,但是当我们的HashMap中存在大量数据时,加入我们某个bucket下对应的链表有n个元素,那么遍历时间复杂度就为O(n),为了针对这个问题,JDK1.8在HashMap中新增了红黑树的数据结构,进一步使得遍历复杂度降低至O(logn);

    总结

    简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的:

    1. 使用链地址法(使用散列表)来链接拥有相同hash值的数据;
    2. 使用2次扰动函数(hash函数)来降低哈希冲突的概率,使得数据分布更平均;
    3. 引入红黑树进一步降低遍历的时间复杂度,使得遍历更快;

    能否使用任何类作为 Map 的 key?

    可以使用任何类作为 Map 的 key,然而在使用之前,需要考虑以下几点:

    • 如果类重写了 equals() 方法,也应该重写 hashCode() 方法。

    • 类的所有实例需要遵循与 equals() 和 hashCode() 相关的规则。

    • 如果一个类没有使用 equals(),不应该在 hashCode() 中使用它。

    • 用户自定义 Key 类最佳实践是使之为不可变的,这样 hashCode() 值可以被缓存起来,拥有更好的性能。不可变的类也可以确保 hashCode() 和 equals() 在未来不会改变,这样就会解决与可变相关的问题了。

    为什么HashMap中String、Integer这样的包装类适合作为K?

    答:String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性,能够有效的减少Hash碰撞的几率

    1. 都是final类型,即不可变性,保证key的不可更改性,不会存在获取hash值不同的情况
    2. 内部已重写了equals()hashCode()等方法,遵守了HashMap内部的规范(不清楚可以去上面看看putValue的过程),不容易出现Hash值计算错误的情况;

    如果使用Object作为HashMap的Key,应该怎么办呢?

    答:重写hashCode()equals()方法

    1. 重写hashCode()是因为需要计算存储数据的存储位置,需要注意不要试图从散列码计算中排除掉一个对象的关键部分来提高性能,这样虽然能更快但可能会导致更多的Hash碰撞;
    2. 重写equals()方法,需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值x,x.equals(null)必须返回false的这几个特性,目的是为了保证key在哈希表中的唯一性

    HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标?

    答:hashCode()方法返回的是int整数类型,其范围为-(2 ^ 31)~(2 ^ 31 - 1),约有40亿个映射空间,而HashMap的容量范围是在16(初始化默认值)~2 ^ 30,HashMap通常情况下是取不到最大值的,并且设备上也难以提供这么多的存储空间,从而导致通过hashCode()计算出的哈希值可能不在数组大小范围内,进而无法匹配存储位置;

    那怎么解决呢?

    1. HashMap自己实现了自己的hash()方法,通过两次扰动使得它自己的哈希值高低位自行进行异或运算,降低哈希碰撞概率也使得数据分布更平均;
    2. 在保证数组长度为2的幂次方的时候,使用hash()运算之后的值与运算(&)(数组长度 - 1)来获取数组下标的方式进行存储,这样一来是比取余操作更加有效率,二来也是因为只有当数组长度为2的幂次方时,h&(length-1)才等价于h%length,三来解决了“哈希值与数组大小范围不匹配”的问题;

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

    为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀,每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。

    这个算法应该如何设计呢?

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

    那为什么是两次扰动呢?

    答:这样就是加大哈希值低位的随机性,使得分布更均匀,从而提高对应数组存储下标位置的随机性&均匀性,最终减少Hash冲突,两次就够了,已经达到了高位低位同时参与运算的目的;

    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的幂次方大小。也就是说 HashMap 总是使用2的幂作为哈希表的大小,后面会介绍到为什么是2的幂次方。
    5. 底层数据结构: JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。Hashtable 没有这样的机制。
    6. 推荐使用:在 Hashtable 的类注释可以看到,Hashtable 是保留类不建议使用,推荐在单线程环境下使用 HashMap 替代,如果需要多线程使用则用 ConcurrentHashMap 替代。

    如何决定使用 HashMap 还是 TreeMap?

    对于在Map中插入、删除和定位元素这类操作,HashMap是最好的选择。然而,假如你需要对一个有序的key集合进行遍历,TreeMap是更好的选择。基于你的collection的大小,也许向HashMap中添加元素会更快,将map换为TreeMap进行有序key的遍历。

    HashMap 和 ConcurrentHashMap 的区别

    1. ConcurrentHashMap对整个桶数组进行了分割分段(Segment),然后在每一个分段上都用lock锁进行保护,相对于HashTable的synchronized锁的粒度更精细了一些,并发性能更好,而HashMap没有锁机制,不是线程安全的。(JDK1.8之后ConcurrentHashMap启用了一种全新的方式实现,利用CAS算法。)
    2. HashMap的键值对允许有null,但是ConCurrentHashMap都不允许。

    ConcurrentHashMap 和 Hashtable 的区别?

    ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

    • 底层数据结构: JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现,JDK1.8 采用的数据结构跟HashMap1.8的结构一样,数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的;
    • 实现线程安全的方式(重要): ① 在JDK1.7的时候,ConcurrentHashMap(分段锁) 对整个桶数组进行了分割分段(Segment),每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率。(默认分配16个Segment,比Hashtable效率提高16倍。) 到了 JDK1.8 的时候已经摒弃了Segment的概念,而是直接用 Node 数组+链表+红黑树的数据结构来实现,并发控制使用 synchronized 和 CAS 来操作。(JDK1.6以后 对 synchronized锁做了很多优化) 整个看起来就像是优化过且线程安全的 HashMap,虽然在JDK1.8中还能看到 Segment 的数据结构,但是已经简化了属性,只是为了兼容旧版本;② Hashtable(同一把锁) :使用 synchronized 来保证线程安全,效率非常低下。当一个线程访问同步方法时,其他线程也访问同步方法,可能会进入阻塞或轮询状态,如使用 put 添加元素,另一个线程不能使用 put 添加元素,也不能使用 get,竞争会越来越激烈效率越低。

    两者的对比图

    HashTable:

    img

    JDK1.7的ConcurrentHashMap:

    img

    JDK1.8的ConcurrentHashMap(TreeBin: 红黑二叉树节点 Node: 链表节点):

    img

    答:ConcurrentHashMap 结合了 HashMap 和 HashTable 二者的优势。HashMap 没有考虑同步,HashTable 考虑了同步的问题。但是 HashTable 在每次同步执行时都要锁住整个结构。 ConcurrentHashMap 锁的方式是稍微细粒度的。

    ConcurrentHashMap 底层具体实现知道吗?实现原理是什么?

    JDK1.7

    首先将数据分为一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据时,其他段的数据也能被其他线程访问。

    在JDK1.7中,ConcurrentHashMap采用Segment + HashEntry的方式进行实现,结构如下:

    一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和HashMap类似,是一种数组和链表结构,一个 Segment 包含一个 HashEntry 数组,每个 HashEntry 是一个链表结构的元素,每个 Segment 守护着一个HashEntry数组里的元素,当对 HashEntry 数组的数据进行修改时,必须首先获得对应的 Segment的锁。

    img

    1. 该类包含两个静态内部类 HashEntry 和 Segment ;前者用来封装映射表的键值对,后者用来充当锁的角色;
    2. Segment 是一种可重入的锁 ReentrantLock,每个 Segment 守护一个HashEntry 数组里得元素,当对 HashEntry 数组的数据进行修改时,必须首先获得对应的 Segment 锁。

    JDK1.8

    JDK1.8中,放弃了Segment臃肿的设计,取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现,synchronized只锁定当前链表或红黑二叉树的首节点,这样只要hash不冲突,就不会产生并发,效率又提升N倍。

    结构如下:

    img

    附加源码,有需要的可以看看

    插入元素过程(建议去看看源码):

    如果相应位置的Node还没有初始化,则调用CAS插入相应的数据;

    else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
        if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
            break;                   // no lock when adding to empty bin
    }
    

    如果相应位置的Node不为空,且当前该节点不处于移动状态,则对该节点加synchronized锁,如果该节点的hash不小于0,则遍历链表更新节点或插入新节点;

    if (fh >= 0) {
        binCount = 1;
        for (Node<K,V> e = f;; ++binCount) {
            K ek;
            if (e.hash == hash &&
                ((ek = e.key) == key ||
                 (ek != null && key.equals(ek)))) {
                oldVal = e.val;
                if (!onlyIfAbsent)
                    e.val = value;
                break;
            }
            Node<K,V> pred = e;
            if ((e = e.next) == null) {
                pred.next = new Node<K,V>(hash, key, value, null);
                break;
            }
        }
    }
    
    1. 如果该节点是TreeBin类型的节点,说明是红黑树结构,则通过putTreeVal方法往红黑树中插入节点;如果binCount不为0,说明put操作对数据产生了影响,如果当前链表的个数达到8个,则通过treeifyBin方法转化为红黑树,如果oldVal不为空,说明是一次更新操作,没有对元素个数产生影响,则直接返回旧值;
    2. 如果插入的是一个新节点,则执行addCount()方法尝试更新元素个数baseCount;

    辅助工具类

    Array 和 ArrayList 有何区别?

    • Array 可以存储基本数据类型和对象,ArrayList 只能存储对象。
    • Array 是指定固定大小的,而 ArrayList 大小是自动扩展的。
    • Array 内置方法没有 ArrayList 多,比如 addAll、removeAll、iteration 等方法只有 ArrayList 有。

    对于基本类型数据,集合使用自动装箱来减少编码工作量。但是,当处理固定大小的基本数据类型的时候,这种方式相对比较慢。

    如何实现 Array 和 List 之间的转换?

    • Array 转 List: Arrays. asList(array) ;
    • List 转 Array:List 的 toArray() 方法。

    comparable 和 comparator的区别?

    • comparable接口实际上是出自java.lang包,它有一个 compareTo(Object obj)方法用来排序
    • comparator接口实际上是出自 java.util 包,它有一个compare(Object obj1, Object obj2)方法用来排序

    一般我们需要对一个集合使用自定义排序时,我们就要重写compareTo方法或compare方法,当我们需要对某一个集合实现两种排序方式,比如一个song对象中的歌名和歌手名分别采用一种排序方法的话,我们可以重写compareTo方法和使用自制的Comparator方法或者以两个Comparator来实现歌名排序和歌星名排序,第二种代表我们只能使用两个参数版的Collections.sort().

    Collection 和 Collections 有什么区别?

    • java.util.Collection 是一个集合接口(集合类的一个顶级接口)。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式,其直接继承接口有List与Set。
    • Collections则是集合类的一个工具类/帮助类,其中提供了一系列静态方法,用于对集合中元素进行排序、搜索以及线程安全等各种操作。

    TreeMap 和 TreeSet 在排序时如何比较元素?Collections 工具类中的 sort()方法如何比较元素?

    TreeSet 要求存放的对象所属的类必须实现 Comparable 接口,该接口提供了比较元素的 compareTo()方法,当插入元素时会回调该方法比较元素的大小。TreeMap 要求存放的键值对映射的键必须实现 Comparable 接口从而根据键对元素进 行排 序。

    Collections 工具类的 sort 方法有两种重载的形式,

    第一种要求传入的待排序容器中存放的对象比较实现 Comparable 接口以实现元素的比较;

    第二种不强制性的要求容器中的元素必须可比较,但是要求传入第二个参数,参数是Comparator 接口的子类型(需要重写 compare 方法实现元素的比较),相当于一个临时定义的排序规则,其实就是通过接口注入比较元素大小的算法,也是对回调模式的应用(Java 中对函数式编程的支持)。

    展开全文
  • Java集合面试题

    万次阅读 多人点赞 2019-06-25 14:46:19
    Java集合面试题 Java 集合框架的基础接口有哪些? Collection ,为集合层级的根接口。一个集合代表一组对象,这些对象即为它的元素。Java 平台不提供这个接口任何直接的实现。 Set ,是一个不能包含重复元素的集合...

    Java集合面试题

    Java 集合框架的基础接口有哪些?

    • Collection ,为集合层级的根接口。一个集合代表一组对象,这些对象即为它的元素。Java 平台不提供这个接口任何直接的实现。
      • Set ,是一个不能包含重复元素的集合。这个接口对数学集合抽象进行建模,被用来代表集合,就如一副牌。
      • List ,是一个有序集合,可以包含重复元素。你可以通过它的索引来访问任何元素。List 更像长度动态变换的数组。
    • Map ,是一个将 key 映射到 value 的对象。一个 Map 不能包含重复的 key,每个 key 最多只能映射一个 value 。
    • 一些其它的接口有 Queue、Dequeue、SortedSet、SortedMap 和 ListIterator 。

    ? 为何 Collection 不从 Cloneable 和 Serializable 接口继承?

    Collection 接口指定一组对象,对象即为它的元素。

    • 如何维护这些元素由 Collection 的具体实现决定。例如,一些如 List 的 Collection 实现允许重复的元素,而其它的如 Set 就不允许。
    • 很多 Collection 实现有一个公有的 clone 方法。然而,把它放到集合的所有实现中也是没有意义的。这是因为 Collection 是一个抽象表现,重要的是实现。

    当与具体实现打交道的时候,克隆或序列化的语义和含义才发挥作用。所以,具体实现应该决定如何对它进行克隆或序列化,或它是否可以被克隆或序列化。在所有的实现中授权克隆和序列化,最终导致更少的灵活性和更多的限制,特定的实现应该决定它是否可以被克隆和序列化

    为何 Map 接口不继承 Collection 接口?

    尽管 Map 接口和它的实现也是集合框架的一部分,但 Map 不是集合,集合也不是 Map。因此,Map 继承 Collection 毫无意义,反之亦然。

    如果 Map 继承 Collection 接口,那么元素去哪儿?Map 包含 key-value 对,它提供抽取 key 或 value 列表集合( Collection )的方法,但是它不适合“一组对象”规范。

    ? 为何 Map 接口不继承 Collection 接口?

    尽管 Map 接口和它的实现也是集合框架的一部分,但 Map 不是集合,集合也不是 Map。因此,Map 继承 Collection 毫无意义,反之亦然。

    如果 Map 继承 Collection 接口,那么元素去哪儿?Map 包含 key-value 对,它提供抽取 key 或 value 列表集合( Collection )的方法,但是它不适合“一组对象”规范。

    ? Collection 和 Collections 的区别?

    • Collection ,是集合类的上级接口,继承与他的接口主要有 Set 和List 。
    • Collections ,是针对集合类的一个工具类,它提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。

    ? 集合框架里实现的通用算法有哪些?

    Java 集合框架提供常用的算法实现,比如排序和搜索。

    Collections类包含这些方法实现。大部分算法是操作 List 的,但一部分对所有类型的集合都是可用的。部分算法有排序、搜索、混编、最大最小值。

    ? 集合框架底层数据结构总结

    1)List

    • ArrayList :Object 数组。
    • Vector :Object 数组。
    • LinkedList :双向链表(JDK6 之前为循环链表,JDK7 取消了循环)。

    2)Map

    • HashMap :
      • JDK8 之前,HashMap 由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突)。
      • JDK8 以后,在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8 )时,将链表转化为红黑树,以减少搜索时间。
    • LinkedHashMap :LinkedHashMap 继承自 HashMap,所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外,LinkedHashMap 在上面结构的基础上,增加了一条双向链表,使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作,实现了访问顺序相关逻辑。详细可以查看:《LinkedHashMap 源码详细分析(JDK1.8)》
    • Hashtable :数组+链表组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的。
    • TreeMap :红黑树(自平衡的排序二叉树)。

    3)Set

    • HashSet :无序,唯一,基于 HashMap 实现的,底层采用 HashMap 来保存元素。
    • LinkedHashSet :LinkedHashSet 继承自 HashSet,并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 HashMap 实现一样,不过还是有一点点区别的。
    • TreeSet :有序,唯一,红黑树(自平衡的排序二叉树)。

    什么是迭代器(Iterator)?

    Iterator 接口,提供了很多对集合元素进行迭代的方法。每一个集合类都包含了可以返回迭代器实例的迭代方法。迭代器可以在迭代的过程中删除底层集合的元素,但是不可以直接调用集合的 #remove(Object Obj) 方法删除,可以通过迭代器的 #remove() 方法删除。

    ? Iterator 和 ListIterator 的区别是什么?

    • Iterator 可用来遍历 Set 和 List 集合,但是 ListIterator 只能用来遍历 List。
    • Iterator 对集合只能是前向遍历,ListIterator 既可以前向也可以后向。
    • ListIterator 实现了 Iterator 接口,并包含其他的功能。比如:增加元素,替换元素,获取前一个和后一个元素的索引等等。

    ? 快速失败(fail-fast)和安全失败(fail-safe)的区别是什么?

    差别在于 ConcurrentModification 异常:

    • 快速失败:当你在迭代一个集合的时候,如果有另一个线程正在修改你正在访问的那个集合时,就会抛出一个 ConcurrentModification 异常。 在 java.util 包下的都是快速失败。
    • 安全失败:你在迭代的时候会去底层集合做一个拷贝,所以你在修改上层集合的时候是不会受影响的,不会抛出 ConcurrentModification 异常。在 java.util.concurrent 包下的全是安全失败的。

    ? 如何删除 List 中的某个元素?

    有两种方式,分别如下:

    • 方式一,使用 Iterator ,顺序向下,如果找到元素,则使用 remove 方法进行移除。
    • 方式二,倒序遍历 List ,如果找到元素,则使用 remove 方法进行移除。

    ? Enumeration 和 Iterator 接口有什么不同?

    • Enumeration 跟 Iterator 相比较快两倍,而且占用更少的内存。
    • 但是,Iterator 相对于 Enumeration 更安全,因为其他线程不能修改当前迭代器遍历的集合对象。同时,Iterators 允许调用者从底层集合中移除元素,这些 Enumerations 都没法完成。

    对于很多胖友,可能并未使用过 Enumeration 类,所以可以看看 《Java Enumeration 接口》 文章。

    ? 为何 Iterator 接口没有具体的实现?

    Iterator 接口,定义了遍历集合的方法,但它的实现则是集合实现类的责任。每个能够返回用于遍历的 Iterator 的集合类都有它自己的 Iterator 实现内部类。

    这就允许集合类去选择迭代器是 fail-fast 还是 fail-safe 的。比如,ArrayList 迭代器是 fail-fast 的,而 CopyOnWriteArrayList 迭代器是 fail-safe 的。

    Comparable 和 Comparator 的区别?

    • Comparable 接口,在 java.lang 包下,用于当前对象和其它对象的比较,所以它有一个 #compareTo(Object obj) 方法用来排序,该方法只有一个参数。
    • Comparator 接口,在 java.util 包下,用于传入的两个对象的比较,所以它有一个 #compare(Object obj1, Object obj2) 方法用来排序,该方法有两个参数。

    详细的,可以看看 《Java 自定义比较器》 文章,重点是如何自己实现 Comparable 和 Comparator 的方法。

    ? compareTo 方法的返回值表示的意思?

    • 大于 0 ,表示对象大于参数对象。
    • 小于 0 ,表示对象小于参数对象
    • 等于 0 ,表示两者相等。

    ? 如何对 Object 的 List 排序?

    • Object[] 数组进行排序时,我们可以用 Arrays#sort(...) 方法。
    • List<Object> 数组进行排序时,我们可以用 Collections#sort(...) 方法。

    有哪些关于 Java 集合框架的最佳实践?

    • 基于应用的需求来选择使用正确类型的集合,这对性能来说是非常重要的。例如,如果元素的大小是固定的,并且知道优先级,我们将会使用一个 Array ,而不是 ArrayList 。
    • 一些集合类允许我们指定他们的初始容量。因此,如果我们知道存储数据的大概数值,就可以避免重散列或者大小的调整。
    • 总是使用泛型来保证类型安全,可靠性和健壮性。同时,使用泛型还可以避免运行时的 ClassCastException 异常。
    • 在 Map 中使用 JDK 提供的不可变类作为一个 key,这样可以避免 hashcode 的实现和我们自定义类的 equals 方法。
    • 应该依照接口而不是实现来编程。
    • 返回零长度的集合或者数组,而不是返回一个 null ,这样可以防止底层集合是空的。

    区别

    List 和 Set 区别?

    List,Set 都是继承自 Collection 接口。

    • List 特点:元素有放入顺序,元素可重复。
    • Set 特点:元素无放入顺序,元素不可重复,重复元素会覆盖掉。

    注意:元素虽然无放入顺序,但是元素在 Set 中的位置是有该元素的 hashcode 决定的,其位置其实是固定的。

    另外 List 支持 for 循环,也就是通过下标来遍历,也可以用迭代器,但是 Set 只能用迭代,因为他无序,无法用下标来取得想要的值。

    Set 和 List 对比:

    • Set:检索元素效率高,删除和插入效率低,插入和删除不会引起元素位置改变。
    • List:和数组类似,List 可以动态增长,查找元素效率低,插入删除元素效率,因为可能会引起其他元素位置改变。

    List 和 Map 区别?

    • List 是对象集合,允许对象重复。
    • Map 是键值对的集合,不允许 key 重复。

    Array 和 ArrayList 有何区别?什么时候更适合用 Array?

    • Array 可以容纳基本类型和对象,而 ArrayList 只能容纳对象。
    • Array 是指定大小的,而 ArrayList 大小是固定的,可自动扩容。
    • Array 没有提供 ArrayList 那么多功能,比如 addAll、removeAll 和 iterator 等。

    尽管 ArrayList 明显是更好的选择,但也有些时候 Array 比较好用,比如下面的三种情况。

    • 1、如果列表的大小已经指定,大部分情况下是存储和遍历它们
    • 2、对于遍历基本数据类型,尽管 Collections 使用自动装箱来减轻编码任务,在指定大小的基本类型的列表上工作也会变得很慢。
    • 3、如果你要使用多维数组,使用 [][] 比 List 会方便。

    ArrayList 与 LinkedList 区别?

    ? ArrayList

    • 优点:ArrayList 是实现了基于动态数组的数据结构,因为地址连续,一旦数据存储好了,查询操作效率会比较高(在内存里是连着放的)。
    • 缺点:因为地址连续,ArrayList 要移动数据,所以插入和删除操作效率比较低。

    ? LinkedList

    • 优点:LinkedList 基于链表的数据结构,地址是任意的,所以在开辟内存空间的时候不需要等一个连续的地址。对于新增和删除操作 add 和 remove ,LinedList 比较占优势。LinkedList 适用于要头尾操作或插入指定位置的场景。
    • 缺点:因为 LinkedList 要移动指针,所以查询操作性能比较低。

    ? 适用场景分析

    • 当需要对数据进行对随机访问的情况下,选用 ArrayList 。

    • 当需要对数据进行多次增加删除修改时,采用 LinkedList 。

      如果容量固定,并且只会添加到尾部,不会引起扩容,优先采用 ArrayList 。

    • 当然,绝大数业务的场景下,使用 ArrayList 就够了。主要是,注意好避免 ArrayList 的扩容,以及非顺序的插入。

    ? ArrayList 是如何扩容的?

    直接看 《ArrayList 动态扩容详解》 文章,很详细。主要结论如下:

    • 如果通过无参构造的话,初始数组容量为 0 ,当真正对数组进行添加时,才真正分配容量。每次按照 1.5 倍(位运算)的比率通过 copeOf 的方式扩容。
    • 在 JKD6 中实现是,如果通过无参构造的话,初始数组容量为10,每次通过 copeOf 的方式扩容后容量为原来的 1.5 倍。

    重点是 1.5 倍扩容,这是和 HashMap 2 倍扩容不同的地方。

    ArrayList 集合加入 1 万条数据,应该怎么提高效率?

    ArrayList 的默认初始容量为 10 ,要插入大量数据的时候需要不断扩容,而扩容是非常影响性能的。因此,现在明确了 10 万条数据了,我们可以直接在初始化的时候就设置 ArrayList 的容量!

    这样就可以提高效率了~

    ArrayList 与 Vector 区别?

    ArrayList 和 Vector 都是用数组实现的,主要有这么三个区别:

    • 1、Vector 是多线程安全的,线程安全就是说多线程访问同一代码,不会产生不确定的结果,而 ArrayList 不是。这个可以从源码中看出,Vector 类中的方法很多有 synchronized 进行修饰,这样就导致了 Vector 在效率上无法与 ArrayList 相比。

      Vector 是一种老的动态数组,是线程同步的,效率很低,一般不赞成使用。

    • 2、两个都是采用的线性连续空间存储元素,但是当空间不足的时候,两个类的增加方式是不同。

    • 3、Vector 可以设置增长因子,而 ArrayList 不可以。

    适用场景分析:

    • 1、Vector 是线程同步的,所以它也是线程安全的,而 ArrayList 是线程无需同步的,是不安全的。如果不考虑到线程的安全因素,一般用 ArrayList 效率比较高。

      实际场景下,如果需要多线程访问安全的数组,使用 CopyOnWriteArrayList 。

    • 2、如果集合中的元素的数目大于目前集合数组的长度时,在集合中使用数据量比较大的数据,用 Vector 有一定的优势。

      这种情况下,使用 LinkedList 更合适。

    HashMap 和 Hashtable 的区别?

    Hashtable 是在 Java 1.0 的时候创建的,而集合的统一规范命名是在后来的 Java2.0 开始约定的,而当时其他一部分集合类的发布构成了新的集合框架。

    • Hashtable 继承 Dictionary ,HashMap 继承的是 Java2 出现的 Map 接口。
    • 2、HashMap 去掉了 Hashtable 的 contains 方法,但是加上了 containsValue 和 containsKey 方法。
    • 3、HashMap 允许空键值,而 Hashtable 不允许。
    • 【重点】4、HashTable 是同步的,而 HashMap 是非同步的,效率上比 HashTable 要高。也因此,HashMap 更适合于单线程环境,而 HashTable 适合于多线程环境。
    • 5、HashMap 的迭代器(Iterator)是 fail-fast 迭代器,HashTable的 enumerator 迭代器不是 fail-fast 的。
    • 6、HashTable 中数组默认大小是 11 ,扩容方法是 old * 2 + 1 ,HashMap 默认大小是 16 ,扩容每次为 2 的指数大小。

    一般现在不建议用 HashTable 。主要原因是两点:

    • 一是,HashTable 是遗留类,内部实现很多没优化和冗余。
    • 二是,即使在多线程环境下,现在也有同步的 ConcurrentHashMap 替代,没有必要因为是多线程而用 Hashtable 。

    ? Hashtable 的 #size() 方法中明明只有一条语句 “return count;” ,为什么还要做同步?

    同一时间只能有一条线程执行固定类的同步方法,但是对于类的非同步方法,可以多条线程同时访问。所以,这样就有问题了,可能线程 A 在执行 Hashtable 的 put 方法添加数据,线程 B 则可以正常调用 #size() 方法读取 Hashtable 中当前元素的个数,那读取到的值可能不是最新的,可能线程 A 添加了完了数据,但是没有对 count++ ,线程 B 就已经读取 count 了,那么对于线程 B 来说读取到的 count 一定是不准确的。

    而给 #size() 方法加了同步之后,意味着线程 B 调用 #size() 方法只有在线程 A 调用 put 方法完毕之后才可以调用,这样就保证了线程安全性

    HashSet 和 HashMap 的区别?

    • Set 是线性结构,值不能重复。HashSet 是 Set 的 hash 实现,HashSet 中值不能重复是用 HashMap 的 key 来实现的。

    • Map 是键值对映射,可以空键空值。HashMap 是 Map 的 hash 实现,key 的唯一性是通过 key 值 hashcode 的唯一来确定,value 值是则是链表结构。

      因为不同的 key 值,可能有相同的 hashcode ,所以 value 值需要是链表结构。

    他们的共同点都是 hash 算法实现的唯一性,他们都不能持有基本类型,只能持有对象。

    为了更好的性能,Netty 自己实现了 key 为基本类型的 HashMap ,例如 IntObjectHashMap

    HashSet 和 TreeSet 的区别?

    • HashSet 是用一个 hash 表来实现的,因此,它的元素是无序的。添加,删除和 HashSet 包括的方法的持续时间复杂度是 O(1)
    • TreeSet 是用一个树形结构实现的,因此,它是有序的。添加,删除和 TreeSet 包含的方法的持续时间复杂度是 O(logn)

    ? 如何决定选用 HashMap 还是 TreeMap?

    • 对于在 Map 中插入、删除和定位元素这类操作,HashMap 是最好的选择。
    • 然而,假如你需要对一个有序的 key 集合进行遍历, TreeMap 是更好的选择。

    基于你的 collection 的大小,也许向 HashMap 中添加元素会更快,再将 HashMap 换为 TreeMap 进行有序 key 的遍历。

    HashMap 和 ConcurrentHashMap 的区别?

    ConcurrentHashMap 是线程安全的 HashMap 的实现。主要区别如下:

    • 1、ConcurrentHashMap 对整个桶数组进行了分割分段(Segment),然后在每一个分段上都用 lock 锁进行保护,相对 于Hashtable 的 syn 关键字锁的粒度更精细了一些,并发性能更好。而 HashMap 没有锁机制,不是线程安全的。

      JDK8 之后,ConcurrentHashMap 启用了一种全新的方式实现,利用 CAS 算法。

    • 2、HashMap 的键值对允许有 null ,但是 ConCurrentHashMap 都不允许。

    队列和栈是什么,列出它们的区别?

    栈和队列两者都被用来预存储数据。

    • java.util.Queue 是一个接口,它的实现类在Java并发包中。队列允许先进先出(FIFO)检索元素,但并非总是这样。Deque 接口允许从两端检索元素。
    • 栈与队列很相似,但它允许对元素进行后进先出(LIFO)进行检索。
      • Stack 是一个扩展自 Vector 的类,而 Queue 是一个接口。

    原理

    HashMap 的工作原理是什么?

    我们知道在 Java 中最常用的两种结构是数组和模拟指针(引用),几乎所有的数据结构都可以利用这两种来组合实现,HashMap 也是如此。实际上 HashMap 是一个**“链表散列”**。

    HashMap 是基于 hashing 的原理。

    HashMap 图解

    • 我们使用 #put(key, value) 方法来存储对象到 HashMap 中,使用 get(key) 方法从 HashMap 中获取对象。
    • 当我们给 #put(key, value) 方法传递键和值时,我们先对键调用 #hashCode() 方法,返回的 hashCode 用于找到 bucket 位置来储存 Entry 对象。

    ? 当两个对象的 hashCode 相同会发生什么?

    因为 hashcode 相同,所以它们的 bucket 位置相同,“碰撞”会发生。

    因为 HashMap 使用链表存储对象,这个 Entry(包含有键值对的 Map.Entry 对象)会存储在链表中。

    ? hashCode 和 equals 方法有何重要性?

    HashMap 使用 key 对象的 #hashCode()#equals(Object obj) 方法去决定 key-value 对的索引。当我们试着从 HashMap 中获取值的时候,这些方法也会被用到。

    • 如果这两个方法没有被正确地实现,在这种情况下,两个不同 Key 也许会产生相同的 #hashCode()#equals(Object obj) 输出,HashMap 将会认为它们是相同的,然后覆盖它们,而非把它们存储到不同的地方。

    同样的,所有不允许存储重复数据的集合类都使用 #hashCode()#equals(Object obj) 去查找重复,所以正确实现它们非常重要。#hashCode()#equals(Object obj) 方法的实现,应该遵循以下规则:

    • 如果 o1.equals(o2) ,那么 o1.hashCode() == o2.hashCode() 总是为 true 的。
    • 如果 o1.hashCode() == o2.hashCode() ,并不意味 o1.equals(o2) 会为 true

    ? HashMap 默认容量是多少?

    默认容量都是 16 ,负载因子是 0.75 。就是当 HashMap 填充了 75% 的 busket 是就会扩容,最小的可能性是(16 * 0.75 = 12),一般为原内存的 2 倍。

    ? 有哪些顺序的 HashMap 实现类?

    • LinkedHashMap ,是基于元素进入集合的顺序或者被访问的先后顺序排序。
    • TreeMap ,是基于元素的固有顺序 (由 Comparator 或者 Comparable 确定)。

    ? 我们能否使用任何类作为 Map 的 key?

    我们可以使用任何类作为 Map 的 key ,然而在使用它们之前,需要考虑以下几点:

    • 1、如果类重写了 equals 方法,它也应该重写 hashcode 方法。

    • 2、类的所有实例需要遵循与 equals 和 hashcode 相关的规则。

    • 3、如果一个类没有使用 equals ,你不应该在 hashcode 中使用它。

    • 4、用户自定义 key 类的最佳实践是使之为不可变的,这样,hashcode 值可以被缓存起来,拥有更好的性能。不可变的类也可以确保hashcode 和 equals 在未来不会改变,这样就会解决与可变相关的问题了。

      比如,我有一个 类MyKey ,在 HashMap 中使用它。代码如下:

      //传递给MyKey的name参数被用于equals()和hashCode()中
      MyKey key = new MyKey('Pankaj'); //assume hashCode=1234
      myHashMap.put(key, 'Value');
      // 以下的代码会改变key的hashCode()和equals()值
      key.setName('Amit'); //assume new hashCode=7890
      //下面会返回null,因为HashMap会尝试查找存储同样索引的key,而key已被改变了,匹配失败,返回null
      myHashMap.get(new MyKey('Pankaj'));
      
      
      • 那就是为何 String 和 Integer 被作为 HashMap 的 key 大量使用。

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

    为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀,每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。

    这个算法应该如何设计呢?我们首先可能会想到采用 % 取余的操作来实现。但是,重点来了:

    • 取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作(也就是说 hash % length == hash & (length - 1) 的前提是 length 是 2 的 n 次方;)。
    • 并且,采用二进制位操作 &,相对于 % 能够提高运算效率,

    这就解释了 HashMap 的长度为什么是 2 的幂次方。

    HashSet 的工作原理是什么?

    HashSet 是构建在 HashMap 之上的 Set hashing 实现类。让我们直接撸下源码,代码如下:

    // HashSet.java
    
    private transient HashMap<E,Object> map;
    
    private static final Object PRESENT = new Object();
    
    
    • map 属性,当我们创建一个 HashMap 对象时,其内部也会创建一个 map 对象。后续 HashSet 所有的操作,实际都是基于这个 map 之上的封装。

    • PRESENT 静态属性,所有 map 中 KEY 对应的值,都是它,避免重复创建。

    • OK ,再来看一眼 add 方法,代码如下:

      // HashSet.java
      
      public boolean add(E e) {
          return map.put(e, PRESENT) == null;
      }
      
      
      • 是不是一目了然。

    ? HashSet 如何检查重复?

    艿艿:正如我们上面看到 HashSet 的实现原理,我们自然可以推导出,HashMap 也是如何检查重复滴。

    如下摘取自 《Head First Java》 第二版:

    当你把对象加入 HashSet 时,HashSet会先计算对象的hashcode值来判断对象加入的位置,同时也会与其他加入的对象的hashcode值作比较。

    • 如果没有相符的 hashcode ,HashSet会假设对象没有重复出现。
    • 但是如果发现有相同 hashcode 值的对象,这时会调用 equals 方法来检查 hashcode 相等的对象是否真的相同。
      • 如果两者相同,HashSet 就不会让加入操作成功。
      • 如果两者不同,HashSet 就会让加入操作成功

    【详细可以查看java基础系列】

    展开全文
  • java集合超详解

    万次阅读 多人点赞 2018-08-03 21:28:15
    一、集合大纲 1.集合和数组的区别: 2.Collection集合的方法: 3.常用集合的分类: Collection 接口的接口 对象的集合(单列集合) ├——-List 接口:元素按进入先后有序保存,可重复 │——...

    一、集合大纲

    常用集合大纲
    这里写图片描述
    Collection集合大纲

    1.集合和数组的区别:

    这里写图片描述

    2.Collection集合的方法:

    这里写图片描述

    3.常用集合的分类:

    Collection 接口的接口 对象的集合(单列集合)
    ├——-List 接口:元素按进入先后有序保存,可重复
    │—————-├ LinkedList 接口实现类, 链表, 插入删除, 没有同步, 线程不安全
    │—————-├ ArrayList 接口实现类, 数组, 随机访问, 没有同步, 线程不安全
    │—————-└ Vector 接口实现类 数组, 同步, 线程安全
    │ ———————-└ Stack 是Vector类的实现类
    └——-Set 接口: 仅接收一次,不可重复,并做内部排序
    ├—————-└HashSet 使用hash表(数组)存储元素
    │————————└ LinkedHashSet 链表维护元素的插入次序
    └ —————-TreeSet 底层实现为二叉树,元素排好序

    Map 接口 键值对的集合 (双列集合)
    ├———Hashtable 接口实现类, 同步, 线程安全
    ├———HashMap 接口实现类 ,没有同步, 线程不安全-
    │—————–├ LinkedHashMap 双向链表和哈希表实现
    │—————–└ WeakHashMap
    ├ ——–TreeMap 红黑树对所有的key进行排序
    └———IdentifyHashMap

    二、List和Set集合详解:

    1.list和set的区别:

    这里写图片描述

    2.List:

    (1)ArrayList:底层数据结构是数组,查询快,增删慢,线程不安全,效率高,可以存储重复元素
    (2)LinkedList 底层数据结构是链表,查询慢,增删快,线程不安全,效率高,可以存储重复元素
    (3)Vector:底层数据结构是数组,查询快,增删慢,线程安全,效率低,可以存储重复元素
    这里写图片描述
    (4小结:

    3.Set:

    (1)HashSet底层数据结构采用哈希表实现,元素无序且唯一,线程不安全,效率高,可以存储null元素,元素的唯一性是靠所存储元素类型是否重写hashCode()和equals()方法来保证的,如果没有重写这两个方法,则无法保证元素的唯一性。
    具体实现唯一性的比较过程:存储元素首先会使用hash()算法函数生成一个int类型hashCode散列值,然后已经的所存储的元素的hashCode值比较,如果hashCode不相等,则所存储的两个对象一定不相等,此时存储当前的新的hashCode值处的元素对象;如果hashCode相等,存储元素的对象还是不一定相等,此时会调用equals()方法判断两个对象的内容是否相等,如果内容相等,那么就是同一个对象,无需存储;如果比较的内容不相等,那么就是不同的对象,就该存储了,此时就要采用哈希的解决地址冲突算法,在当前hashCode值处类似一个新的链表, 在同一个hashCode值的后面存储存储不同的对象,这样就保证了元素的唯一性。
    Set的实现类的集合对象中不能够有重复元素,HashSet也一样他是使用了一种标识来确定元素的不重复,HashSet用一种算法来保证HashSet中的元素是不重复的, HashSet采用哈希算法,底层用数组存储数据。默认初始化容量16,加载因子0.75。
    Object类中的hashCode()的方法是所有子类都会继承这个方法,这个方法会用Hash算法算出一个Hash(哈希)码值返回,HashSet会用Hash码值去和数组长度取模, 模(这个模就是对象要存放在数组中的位置)相同时才会判断数组中的元素和要加入的对象的内容是否相同,如果不同才会添加进去。
    Hash算法是一种散列算法。
    Set hs=new HashSet();

    hs.add(o);
    |
    o.hashCode();
    |
    o%当前总容量 (0–15)
    |
    | 不发生冲突
    是否发生冲突—————–直接存放
    |
    | 发生冲突
    | 假(不相等)
    o1.equals(o2)——————-找一个空位添加
    |
    | 是(相等)
    不添加
    覆盖hashCode()方法的原则:
    1、一定要让那些我们认为相同的对象返回相同的hashCode值
    2、尽量让那些我们认为不同的对象返回不同的hashCode值,否则,就会增加冲突的概率。
    3、尽量的让hashCode值散列开(两值用异或运算可使结果的范围更广)
    HashSet 的实现比较简单,相关HashSet的操作,基本上都是直接调用底层HashMap的相关方法来完成,我们应该为保存到HashSet中的对象覆盖hashCode()和equals(),因为再将对象加入到HashSet中时,会首先调用hashCode方法计算出对象的hash值,接着根据此hash值调用HashMap中的hash方法,得到的值& (length-1)得到该对象在hashMap的transient Entry[] table中的保存位置的索引,接着找到数组中该索引位置保存的对象,并调用equals方法比较这两个对象是否相等,如果相等则不添加,注意:所以要存入HashSet的集合对象中的自定义类必须覆盖hashCode(),equals()两个方法,才能保证集合中元素不重复。在覆盖equals()和hashCode()方法时, 要使相同对象的hashCode()方法返回相同值,覆盖equals()方法再判断其内容。为了保证效率,所以在覆盖hashCode()方法时, 也要尽量使不同对象尽量返回不同的Hash码值。

    如果数组中的元素和要加入的对象的hashCode()返回了相同的Hash值(相同对象),才会用equals()方法来判断两个对象的内容是否相同。

    (2)LinkedHashSet底层数据结构采用链表和哈希表共同实现,链表保证了元素的顺序与存储顺序一致,哈希表保证了元素的唯一性。线程不安全,效率高。
    (3)TreeSet底层数据结构采用二叉树来实现,元素唯一且已经排好序;唯一性同样需要重写hashCode和equals()方法,二叉树结构保证了元素的有序性。根据构造方法不同,分为自然排序(无参构造)和比较器排序(有参构造),自然排序要求元素必须实现Compareable接口,并重写里面的compareTo()方法,元素通过比较返回的int值来判断排序序列,返回0说明两个对象相同,不需要存储;比较器排需要在TreeSet初始化是时候传入一个实现Comparator接口的比较器对象,或者采用匿名内部类的方式new一个Comparator对象,重写里面的compare()方法;
    (4)小结:Set具有与Collection完全一样的接口,因此没有任何额外的功能,不像前面有两个不同的List。实际上Set就是Collection,只 是行为不同。(这是继承与多态思想的典型应用:表现不同的行为。)Set不保存重复的元素。
    Set 存入Set的每个元素都必须是唯一的,因为Set不保存重复元素。加入Set的元素必须定义equals()方法以确保对象的唯一性。Set与Collection有完全一样的接口。Set接口不保证维护元素的次序。

    4.List和Set总结:

    (1)、List,Set都是继承自Collection接口,Map则不是
    (2)、List特点:元素有放入顺序,元素可重复 ,Set特点:元素无放入顺序,元素不可重复,重复元素会覆盖掉,(注意:元素虽然无放入顺序,但是元素在set中的位置是有该元素的HashCode决定的,其位置其实是固定的,加入Set 的Object必须定义equals()方法 ,另外list支持for循环,也就是通过下标来遍历,也可以用迭代器,但是set只能用迭代,因为他无序,无法用下标来取得想要的值。)
    (3).Set和List对比:
    Set:检索元素效率低下,删除和插入效率高,插入和删除不会引起元素位置改变。
    List:和数组类似,List可以动态增长,查找元素效率高,插入删除元素效率低,因为会引起其他元素位置改变。
    (4)、ArrayList与LinkedList的区别和适用场景
    Arraylist:
    优点:ArrayList是实现了基于动态数组的数据结构,因为地址连续,一旦数据存储好了,查询操作效率会比较高(在内存里是连着放的)。
    缺点:因为地址连续, ArrayList要移动数据,所以插入和删除操作效率比较低。

    LinkedList:
    优点:LinkedList基于链表的数据结构,地址是任意的,所以在开辟内存空间的时候不需要等一个连续的地址,对于新增和删除操作add和remove,LinedList比较占优势。LinkedList 适用于要头尾操作或插入指定位置的场景
    缺点:因为LinkedList要移动指针,所以查询操作性能比较低。
    适用场景分析
    当需要对数据进行对此访问的情况下选用ArrayList,当需要对数据进行多次增加删除修改时采用LinkedList。

    ArrayList与Vector的区别和适用场景
    ArrayList有三个构造方法:

    public ArrayList(int initialCapacity)//构造一个具有指定初始容量的空列表。    
    public ArrayList()      //默认构造一个初始容量为10的空列表。    
    public ArrayList(Collection<? extends E> c)//构造一个包含指定 collection 的元素的列表

    Vector有四个构造方法:

    public Vector()//使用指定的初始容量和等于0的容量增量构造一个空向量。    
    public Vector(int initialCapacity)//构造一个空向量,使其内部数据数组的大小,其标准容量增量为零。    
    public Vector(Collection<? extends E> c)//构造一个包含指定 collection 中的元素的向量    
    public Vector(int initialCapacity,int capacityIncrement)//使用指定的初始容量和容量增量构造一个空的向量    

    ArrayList和Vector都是用数组实现的,主要有这么三个区别:
    (1).Vector是多线程安全的,线程安全就是说多线程访问同一代码,不会产生不确定的结果。而ArrayList不是,这个可以从源码中看出,Vector类中的方法很多有synchronized进行修饰,这样就导致了Vector在效率上无法与ArrayList相比;
    (2)两个都是采用的线性连续空间存储元素,但是当空间不足的时候,两个类的增加方式是不同。
    *(3)*Vector可以设置增长因子,而ArrayList不可以。
    *(4)*Vector是一种老的动态数组,是线程同步的,效率很低,一般不赞成使用。
    适用场景分析
    1.Vector是线程同步的,所以它也是线程安全的,而ArrayList是线程异步的,是不安全的。如果不考虑到线程的安全因素,一般用ArrayList效率比较高。
    2.如果集合中的元素的数目大于目前集合数组的长度时,在集合中使用数据量比较大的数据,用Vector有一定的优势。

    .TreeSet 是二差树(红黑树的树据结构)实现的,Treeset中的数据是自动排好序的,不允许放入null值
    2.HashSet 是哈希表实现的,HashSet中的数据是无序的,可以放入null,但只能放入一个null,两者中的值都不能重复,就如数据库中唯一约束
    3.HashSet要求放入的对象必须实现HashCode()方法,放入的对象,是以hashcode码作为标识的,而具有相同内容的String对象,hashcode是一样,所以放入的内容不能重复。但是同一个类的对象可以放入不同的实例

    适用场景分析:HashSet是基于Hash算法实现的,其性能通常都优于TreeSet。为快速查找而设计的Set,我们通常都应该使用HashSet,在我们需要排序的功能时,我们才使用TreeSet。
    (5)何时使用:
    这里写图片描述

    三、Map详解:

    Map用于保存具有映射关系的数据,Map里保存着两组数据:key和value,它们都可以使任何引用类型的数据,但key不能重复。所以通过指定的key就可以取出对应的value。

    (1)、请注意!!!, Map 没有继承 Collection 接口, Map 提供 key 到 value 的映射,你可以通过“键”查找“值”。一个 Map 中不能包含相同的 key ,每个 key 只能映射一个 value 。 Map 接口提供 3 种集合的视图, Map 的内容可以被当作一组 key 集合,一组 value 集合,或者一组 key-value 映射。
    (2)Map:
    这里写图片描述
    (3)HashMap和HashTable的比较:
    这里写图片描述
    (4)TreeMap:
    这里写图片描述
    (5)Map的其它类:
    IdentityHashMapHashMap的具体区别,IdentityHashMap使用 == 判断两个key是否相等,而HashMap使用的是equals方法比较key值。有什么区别呢?
    对于==,如果作用于基本数据类型的变量,则直接比较其存储的 “值”是否相等; 如果作用于引用类型的变量,则比较的是所指向的对象的地址。
    对于equals方法,注意:equals方法不能作用于基本数据类型的变量
    如果没有对equals方法进行重写,则比较的是引用类型的变量所指向的对象的地址;
    诸如String、Date等类对equals方法进行了重写的话,比较的是所指向的对象的内容。
    这里写图片描述
    (6)小结:
    HashMap 非线程安全
    HashMap:基于哈希表实现。使用HashMap要求添加的键类明确定义了hashCode()和equals()[可以重写hashCode()和equals()],为了优化HashMap空间的使用,您可以调优初始容量和负载因子。

    TreeMap:非线程安全基于红黑树实现。TreeMap没有调优选项,因为该树总处于平衡状态。

    适用场景分析:
    HashMap和HashTable:HashMap去掉了HashTable的contains方法,但是加上了containsValue()和containsKey()方法。HashTable同步的,而HashMap是非同步的,效率上比HashTable要高。HashMap允许空键值,而HashTable不允许。

    HashMap:适用于Map中插入、删除和定位元素。
    Treemap:适用于按自然顺序或自定义顺序遍历键(key)。

    5.线程安全集合类与非线程安全集合类
    LinkedList、ArrayList、HashSet是非线程安全的,Vector是线程安全的;
    HashMap是非线程安全的,HashTable是线程安全的;
    StringBuilder是非线程安全的,StringBuffer是线程安全的。

    数据结构
    ArrayXxx:底层数据结构是数组,查询快,增删慢
    LinkedXxx:底层数据结构是链表,查询慢,增删快
    HashXxx:底层数据结构是哈希表。依赖两个方法:hashCode()和equals()
    TreeXxx:底层数据结构是二叉树。两种方式排序:自然排序和比较器排序

    各种集合对比
    List和Set对比总结

    展开全文
  • Java集合中List,Set以及Map等集合体系详解(史上最全)

    万次阅读 多人点赞 2018-06-12 14:09:24
    Java集合中List,Set以及Map等集合体系详解(史上最全) 概述: List , Set, Map都是接口,前两个继承至Collection接口,Map为独立接口 Set下有HashSet,LinkedHashSet,TreeSet List下有ArrayList,Vector,...

    转载请注明出处:Java集合中List,Set以及Map等集合体系详解(史上最全)

    概述:

    • List , Set, Map都是接口,前两个继承至Collection接口,Map为独立接口
    • Set下有HashSet,LinkedHashSet,TreeSet
    • List下有ArrayList,Vector,LinkedList
    • Map下有Hashtable,LinkedHashMap,HashMap,TreeMap
    • Collection接口下还有个Queue接口,有PriorityQueue类

    这里写图片描述

    注意:

    • Queue接口与List、Set同一级别,都是继承了Collection接口。
      看图你会发现,LinkedList既可以实现Queue接口,也可以实现List接口.只不过呢, LinkedList实现了Queue接口。Queue接口窄化了对LinkedList的方法的访问权限(即在方法中的参数类型如果是Queue时,就完全只能访问Queue接口所定义的方法 了,而不能直接访问 LinkedList的非Queue的方法),以使得只有恰当的方法才可以使用。

    • SortedSet是个接口,它里面的(只有TreeSet这一个实现可用)中的元素一定是有序的。

    总结:

    Connection接口:

    List 有序,可重复

    • ArrayList
      优点: 底层数据结构是数组,查询快,增删慢。
      缺点: 线程不安全,效率高
    • Vector
      优点: 底层数据结构是数组,查询快,增删慢。
      缺点: 线程安全,效率低
    • LinkedList
      优点: 底层数据结构是链表,查询慢,增删快。
      缺点: 线程不安全,效率高

    Set 无序,唯一

    • HashSet
      底层数据结构是哈希表。(无序,唯一)
      如何来保证元素唯一性?
      1.依赖两个方法:hashCode()和equals()

    • LinkedHashSet
      底层数据结构是链表和哈希表。(FIFO插入有序,唯一)
      1.由链表保证元素有序
      2.由哈希表保证元素唯一

    • TreeSet
      底层数据结构是红黑树。(唯一,有序)
      1. 如何保证元素排序的呢?
      自然排序
      比较器排序
      2.如何保证元素唯一性的呢?
      根据比较的返回值是否是0来决定

    针对Collection集合我们到底使用谁呢?(掌握)

    唯一吗?

    是:Set

    排序吗?

    是:TreeSet或LinkedHashSet
    否:HashSet
    如果你知道是Set,但是不知道是哪个Set,就用HashSet。

    否:List

    要安全吗?

    是:Vector
    否:ArrayList或者LinkedList

    查询多:ArrayList
    增删多:LinkedList
    如果你知道是List,但是不知道是哪个List,就用ArrayList。

    如果你知道是Collection集合,但是不知道使用谁,就用ArrayList。
    如果你知道用集合,就用ArrayList。

    说完了Collection,来简单说一下Map.

    Map接口:

    上图:
    这里写图片描述

    Map接口有三个比较重要的实现类,分别是HashMap、TreeMap和HashTable。

    • TreeMap是有序的,HashMap和HashTable是无序的。
    • Hashtable的方法是同步的,HashMap的方法不是同步的。这是两者最主要的区别。

    这就意味着:

    • Hashtable是线程安全的,HashMap不是线程安全的。
    • HashMap效率较高,Hashtable效率较低。
      如果对同步性或与遗留代码的兼容性没有任何要求,建议使用HashMap。 查看Hashtable的源代码就可以发现,除构造函数外,Hashtable的所有 public 方法声明中都有 synchronized关键字,而HashMap的源码中则没有。
    • Hashtable不允许null值,HashMap允许null值(key和value都允许)
    • 父类不同:Hashtable的父类是Dictionary,HashMap的父类是AbstractMap

    重点问题重点分析:

    (一).TreeSet, LinkedHashSet and HashSet 的区别

    1. 介绍

    • TreeSet, LinkedHashSet and HashSet 在java中都是实现Set的数据结构
    • TreeSet的主要功能用于排序
    • LinkedHashSet的主要功能用于保证FIFO即有序的集合(先进先出)
    • HashSet只是通用的存储数据的集合

    2. 相同点

    • Duplicates elements: 因为三者都实现Set interface,所以三者都不包含duplicate elements
    • Thread safety: 三者都不是线程安全的,如果要使用线程安全可以Collections.synchronizedSet()

    3. 不同点

    • Performance and Speed: HashSet插入数据最快,其次LinkHashSet,最慢的是TreeSet因为内部实现排序
    • Ordering: HashSet不保证有序,LinkHashSet保证FIFO即按插入顺序排序,TreeSet安装内部实现排序,也可以自定义排序规则
    • null:HashSet和LinkHashSet允许存在null数据,但是TreeSet中插入null数据时会报NullPointerException

    4. 代码比较

      public static void main(String args[]) {
            HashSet<String> hashSet = new HashSet<>();
            LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();
            TreeSet<String> treeSet = new TreeSet<>();
    
            for (String data : Arrays.asList("B", "E", "D", "C", "A")) {
                hashSet.add(data);
                linkedHashSet.add(data);
                treeSet.add(data);
            }
    
            //不保证有序
            System.out.println("Ordering in HashSet :" + hashSet);
    
            //FIFO保证安装插入顺序排序
            System.out.println("Order of element in LinkedHashSet :" + linkedHashSet);
    
            //内部实现排序
            System.out.println("Order of objects in TreeSet :" + treeSet);
    
    
        }
    

    运行结果:
    Ordering in HashSet :[A, B, C, D, E] (无顺序)
    Order of element in LinkedHashSet :[B, E, D, C, A] (FIFO插入有序)
    Order of objects in TreeSet :[A, B, C, D, E] (排序)

    (二).TreeSet的两种排序方式比较

    1.排序的引入(以基本数据类型的排序为例)

    由于TreeSet可以实现对元素按照某种规则进行排序,例如下面的例子

    public class MyClass {
    
        public static void main(String[] args) {
            // 创建集合对象
            // 自然顺序进行排序
            TreeSet<Integer> ts = new TreeSet<Integer>();
    
            // 创建元素并添加
            // 20,18,23,22,17,24,19,18,24
            ts.add(20);
            ts.add(18);
            ts.add(23);
            ts.add(22);
            ts.add(17);
            ts.add(24);
            ts.add(19);
            ts.add(18);
            ts.add(24);
    
            // 遍历
            for (Integer i : ts) {
                System.out.println(i);
            }
        }
    }
    
    

    运行结果:
    17
    18
    19
    20
    22
    23
    24

    2.如果是引用数据类型呢,比如自定义对象,又该如何排序呢?

    测试类:

    public class MyClass {
        public static void main(String[] args) {
            TreeSet<Student> ts=new TreeSet<Student>();
            //创建元素对象
            Student s1=new Student("zhangsan",20);
            Student s2=new Student("lis",22);
            Student s3=new Student("wangwu",24);
            Student s4=new Student("chenliu",26);
            Student s5=new Student("zhangsan",22);
            Student s6=new Student("qianqi",24);
    
            //将元素对象添加到集合对象中
            ts.add(s1);
            ts.add(s2);
            ts.add(s3);
            ts.add(s4);
            ts.add(s5);
            ts.add(s6);
    
            //遍历
            for(Student s:ts){
                System.out.println(s.getName()+"-----------"+s.getAge());
            }
        }
    }
    

    Student.java:

    public class Student {
        private String name;
        private int age;
    
        public Student() {
            super();
            // TODO Auto-generated constructor stub
        }
    
        public Student(String name, int age) {
            super();
            this.name = name;
            this.age = age;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public int getAge() {
            return age;
        }
    
        public void setAge(int age) {
            this.age = age;
        }
    }
    
    

    结果报错:

    这里写图片描述
    原因分析:
    由于不知道该安照那一中排序方式排序,所以会报错。
    解决方法:
    1.自然排序
    2.比较器排序

    (1).自然排序

    自然排序要进行一下操作:
    1.Student类中实现 Comparable接口
    2.重写Comparable接口中的Compareto方法

    compareTo(T o)  比较此对象与指定对象的顺序。
    
    public class Student implements Comparable<Student>{
        private String name;
        private int age;
    
        public Student() {
            super();
            // TODO Auto-generated constructor stub
        }
    
        public Student(String name, int age) {
            super();
            this.name = name;
            this.age = age;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public int getAge() {
            return age;
        }
    
        public void setAge(int age) {
            this.age = age;
        }
    
        @Override
        public int compareTo(Student s) {
            //return -1; //-1表示放在红黑树的左边,即逆序输出
            //return 1;  //1表示放在红黑树的右边,即顺序输出
            //return o;  //表示元素相同,仅存放第一个元素
            //主要条件 姓名的长度,如果姓名长度小的就放在左子树,否则放在右子树
            int num=this.name.length()-s.name.length();
            //姓名的长度相同,不代表内容相同,如果按字典顺序此 String 对象位于参数字符串之前,则比较结果为一个负整数。
            //如果按字典顺序此 String 对象位于参数字符串之后,则比较结果为一个正整数。
            //如果这两个字符串相等,则结果为 0
            int num1=num==0?this.name.compareTo(s.name):num;
            //姓名的长度和内容相同,不代表年龄相同,所以还要判断年龄
            int num2=num1==0?this.age-s.age:num1;
            return num2;
        }
    }
    
    

    运行结果:

    lis-----------22
    qianqi-----------24
    wangwu-----------24
    chenliu-----------26
    zhangsan-----------20
    zhangsan-----------22

    (2).比较器排序

    比较器排序步骤:
    1.单独创建一个比较类,这里以MyComparator为例,并且要让其继承Comparator接口
    2.重写Comparator接口中的Compare方法

    compare(T o1,T o2)      比较用来排序的两个参数。
    

    3.在主类中使用下面的 构造方法

    TreeSet(Comparator<? superE> comparator)
              构造一个新的空 TreeSet,它根据指定比较器进行排序。
    

    测试类:

    public class MyClass {
    
        public static void main(String[] args) {
            //创建集合对象
            //TreeSet(Comparator<? super E> comparator) 构造一个新的空 TreeSet,它根据指定比较器进行排序。
            TreeSet<Student> ts=new TreeSet<Student>(new MyComparator());
    
            //创建元素对象
            Student s1=new Student("zhangsan",20);
            Student s2=new Student("lis",22);
            Student s3=new Student("wangwu",24);
            Student s4=new Student("chenliu",26);
            Student s5=new Student("zhangsan",22);
            Student s6=new Student("qianqi",24);
    
            //将元素对象添加到集合对象中
            ts.add(s1);
            ts.add(s2);
            ts.add(s3);
            ts.add(s4);
            ts.add(s5);
            ts.add(s6);
    
            //遍历
            for(Student s:ts){
                System.out.println(s.getName()+"-----------"+s.getAge());
            }
        }
    }
    
    

    Student.java:

    public class Student {
        private String name;
        private int age;
    
        public Student() {
            super();
            // TODO Auto-generated constructor stub
        }
    
        public Student(String name, int age) {
            super();
            this.name = name;
            this.age = age;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public int getAge() {
            return age;
        }
    
        public void setAge(int age) {
            this.age = age;
        }
    
    }
    
    

    MyComparator类:

    public class MyComparator implements Comparator<Student> {
    
        @Override
        public int compare(Student s1,Student s2) {
            // 姓名长度
            int num = s1.getName().length() - s2.getName().length();
            // 姓名内容
            int num2 = num == 0 ? s1.getName().compareTo(s2.getName()) : num;
            // 年龄
            int num3 = num2 == 0 ? s1.getAge() - s2.getAge() : num2;
            return num3;
        }
    
    }
    

    运行结果:

    lis-----------22
    qianqi-----------24
    wangwu-----------24
    chenliu-----------26
    zhangsan-----------20
    zhangsan-----------22

    (三). 性能测试

    对象类:

    class Dog implements Comparable<Dog> {
        int size;
        public Dog(int s) {
            size = s;
        }
        public String toString() {
            return size + "";
        }
        @Override
        public int compareTo(Dog o) {
           //数值大小比较
            return size - o.size;
        }
    }
    

    主类:

    public class MyClass {
    
        public static void main(String[] args) {
    
            Random r = new Random();
            HashSet<Dog> hashSet = new HashSet<Dog>();
            TreeSet<Dog> treeSet = new TreeSet<Dog>();
            LinkedHashSet<Dog> linkedSet = new LinkedHashSet<Dog>();
    
            // start time
            long startTime = System.nanoTime();
            for (int i = 0; i < 1000; i++) {
                int x = r.nextInt(1000 - 10) + 10;
                hashSet.add(new Dog(x));
            }
    
            // end time
            long endTime = System.nanoTime();
            long duration = endTime - startTime;
            System.out.println("HashSet: " + duration);
    
            // start time
            startTime = System.nanoTime();
            for (int i = 0; i < 1000; i++) {
                int x = r.nextInt(1000 - 10) + 10;
                treeSet.add(new Dog(x));
            }
            // end time
            endTime = System.nanoTime();
            duration = endTime - startTime;
            System.out.println("TreeSet: " + duration);
    
            // start time
            startTime = System.nanoTime();
            for (int i = 0; i < 1000; i++) {
                int x = r.nextInt(1000 - 10) + 10;
                linkedSet.add(new Dog(x));
            }
    
            // end time
            endTime = System.nanoTime();
            duration = endTime - startTime;
            System.out.println("LinkedHashSet: " + duration);
        }
    
    }
    
    

    运行结果:

    HashSet: 1544313
    TreeSet: 2066049
    LinkedHashSet: 629826
    虽然测试不够准确,但能反映得出,TreeSet要慢得多,因为它是有序的。

    嘿嘿

    好了,至此完结.小伙伴有问题的话,请留言

    参考文章:
    HashSet、TreeSet和LinkedHashSet的使用区别
    Collection集合总结
    HashMap、TreeMap和HashTable的区别

    展开全文
  • java集合详解和集合面试题目

    万次阅读 多人点赞 2018-02-12 11:01:14
    一、集合与数组 数组(可以存储基本数据类型)是用来存现对象的一种容器,但是数组的长度固定,不适合在对象数量未知的情况下...Collection接口是集合类的根接口,Java中没有提供这个接口的直接的实现类。但是却...
  • Java集合 1】java集合有哪些

    千次阅读 多人点赞 2020-06-12 15:20:56
    2、JAVA集合可以存储和操作数目不固定的一组数据。 3、若程序时不知道究竟需要多少对象,需要在空间不足时自动扩增容量,则需要使用容器类库,array不适用。  注:使用相应的toArray()和Arrays.asList()方法可以...
  • Java集合类总结,详细且易懂!

    万次阅读 多人点赞 2020-09-01 00:44:34
    Java集合要从两大接口说起,一为Collection接口,二为Map接口,它们是同一个层次的。 Collection接口被List接口和Set接口继承; List接口有三个实现类,ArrayList,LinkedList,Vector; Set接口被HashSet类实现,...
  • Java集合框架关系图

    万次阅读 多人点赞 2019-03-10 18:51:45
    Java集合中实际存放的只是对象的引用,每个集合元素都是一个引用变量,实际内容都放在堆内存或者方法区里面,但是基本数据类型是在栈内存上分配空间的,栈上的数据随时就会被收回的。 集合框架图: 上述类图中...
  • Java集合估计是我们开发过程中,用的最多的API了,它位于java.util包下,同时支持多线程的集合类位于java.util.concurrent包下。 我们都知道各种数据结构最底层的组成都是数组或者链表,其实各种集合类也是基于最...
  • Java 集合的使用

    千次阅读 2018-03-31 13:03:27
    集合概述与迭代器 迭代器 ListIterator ConcurrentModification 具体的集合 数组列表 链表 散列集 树集 队列 优先级队列 映射表 LinkedHash EnumSet / EnumMap 集合框架 集合中的接口 集合中的类 视图与包装器 ...
  • Java集合源码剖析-Java集合框架

    千次阅读 2017-12-31 22:14:21
    Hi大家好,我是清和二七,今天我们来聊聊《Java集合源码剖析-Java集合框架》 一.层次关系 Java集合工具包位于Java.util包下,包含了很多常用的数据结构,如数组、链表、栈、队列、集合、哈希表等。学习Java集合...
  • Java集合有哪些?

    千次阅读 2020-07-04 09:47:14
    Java集合有哪些? java集合分三种,List、Set、Map,这三种集合适用于不同的场景 List:适用于有序,可重复的集合 Set:适用于不可重复集合 Map:适用于键值对的存储 注:通常List与Map最为常用 每个集合常用的...
  • 1.Java集合框架是什么?说出一些集合框架的优点?

    千次阅读 多人点赞 2018-09-27 20:13:38
    1.Java集合框架是什么?说出一些集合框架的优点? 每种编程语言中都有集合,最初的Java版本包含几种集合类:Vector、Stack、HashTable和Array。随着集合的广泛使用,Java1.2提出了囊括所有集合接口、实现和算法的...
  • Java集合框架是什么?说出一些集合框架的优点?

    千次阅读 多人点赞 2019-11-20 15:33:49
    随着集合的广泛使用,Java1.2提出了囊括所有集合接口、实现和算法的集合框架。在保证线程安全的情况下使用泛型和并发集合类,Java已经经历了很久。它还包括在Java并发包中,阻塞接口以及它们的实现。 1...
  • 关于JAVA集合你了解多少?

    千次阅读 多人点赞 2020-03-28 19:02:58
    1、集合框架的由来 在编程设计中,数据结构(算法)担任着不可或缺的角色,在JAVA语言中,JAVA的设计者将数据结构进行了封装,这个封装的整体就...JAVA集合框架主要由两个接口派生而出,分别是Collection接口进入Map...
  • Java集合(一):Java集合概述

    千次阅读 2016-04-12 13:57:38
    Java提供了一个丰富的集合框架,这个集合框架包含了许多接口、虚拟类和实现类。这些接口和类提供了丰富的功能,能够满足基本的聚合需求。下图就是这个框架的整体结构图: 可以看见,这个框架非常大,大到吃惊的...
  • Java 集合框架 早在 Java 2 中之前,Java 就提供了特设类。比如:Dictionary, Vector, Stack, 和 Properties 这些类用来存储和操作对象组。 虽然这些类都非常有用,但是它们缺少一个核心的,统一的主题。由于这个...
  • java集合工具类

    千次阅读 2019-05-26 21:47:25
    下面小编给大家java集合工具类:Collections,java提供了一个操作Set、List和Map等集合的工具类:Collections,该工具类里面提供了大量方法对集合元素进行排序、查询和修改等操作,还提供了对集合对象实现同步控制...
  • Java集合综合案例

    千次阅读 2018-12-13 23:46:14
    Java按照斗地主的规则,完成洗牌发牌的动作 一: 具体规则 使用54张牌打乱顺序,三个玩家参与游戏,三人交替摸牌,每人17张牌,最后三张留作底牌。 二: 分析 准备牌: 牌可以设计为一个ArrayList,每个字符串为一张牌。...
  • java集合之List集合

    千次阅读 2018-06-02 12:57:13
    关于集合以前也总结过一点,一直忘记摘录一下集合的继承关系图。核心收集接口封装了不同类型的集合,如...核心收集接口是Java集合框架的基础。正如您在下图中所看到的,核心收集接口形成了一个层次结构。如图所示:...
  • java集合框架--集合接口

    千次阅读 2018-06-29 00:43:03
    java 集合框架使程序处理集合数组的方法标准化。集合框架包含了一组标准的接口。对这些接口,提供了几个标准的实现工具(LinkedList、HashSet 和 TreeSet); 集合接口: 接口 描述 Collection 集合框架...
  • java集合系列——List集合总结(六)

    万次阅读 2017-03-02 21:46:27
    java集合系列——java集合概述(一) java集合系列——List集合之ArrayList介绍(二) java集合系列——List集合之LinkedList介绍(三) java集合系列——List集合之Vector介绍(四) java集合...
  • Java集合汇总篇

    万次阅读 多人点赞 2020-12-13 20:25:05
    Java 集合框架一些列的接口和类来实现很多常见的数据结构和算法,例如 LinkedList 就是集合框架提供的实现了双向链表的数据结构,关于这一篇文章建议大家收藏,我会不断地完善和扩充它的内容,例如最下面的系列文章...
  • JAVA集合知识点总结

    千次阅读 2020-04-09 09:01:19
    Java集合知识点总结
  • java集合常用API

    千次阅读 2018-05-17 19:30:52
    Java 集合类可以用于存储数量不等的多个对象,还可用于保存具有映射关系的关联数组,而内存中对数据进行存储和管理的“容器”有:数组,集合。但数组有一定的弊端: ①数组的长度不可变  ②数组存储的数据类型...
  • java集合提取最小的日期 我们都广泛使用了Collection类,例如List,Map及其派生版本。 每次使用它们时,我们都必须遍历它们以找到某个元素或更新这些元素,或者找到匹配某个条件的不同元素。 考虑如下所示的人员...
  • Java集合容器(介绍)

    千次阅读 2020-05-07 15:59:41
    Java集合容器的介绍
  • Java集合(一)什么是集合

    万次阅读 多人点赞 2018-06-07 17:35:32
    什么是集合 1、集合类存放于java.util包中。 2、集合类型主要有3种:set(集)、list(列表)和map(映射)。 3、集合存放的都是对象的引用,而非对象本身。所以我们称集合中的对象就是集合中对象的引用。 简单来讲...
  • Java集合递归实现通用树Tree

    千次下载 热门讨论 2010-11-28 03:27:41
    不要分,要的是人气!资源很给力的!欢迎下载!
  • Java集合判空/非空

    千次阅读 2019-09-08 21:43:56
    代码中各种同胞写的各种集合判空,很多,很杂乱。大多数是不规范的,而且可能会造成NPE,特别是业务层调DAO层查询列表时,势必会有空值返回,这个时候一个简单的 list.size()>0 就显得很无力,很bug。 2. 判空...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,219,883
精华内容 487,953
关键字:

java集合

java 订阅