Java教程

Java SE - 集合

本文主要是介绍Java SE - 集合,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Java 的集合体系

 Java集合可分为两大体系:Collection 和 Map

1.常见的Java集合如下

 

 

 

 

 

 

 

 

Collection接口:单列数据,定义了存取一组对象的方法的集合

  • List:元素有序(指的是存取时,与存放顺序保持一致)、可重复的集合
  • Set:元素无序、不可重复的集合

Map接口:双列数据,保存具有映射关系“key-value对”的集合,根据元素的key访问value

 

2.集合中线程安全的集合和线程不安全的集合

线程安全的:

  • Hashtable:比HashMap多了个线程安全。
  • ConcurrentHashMap:是一种高效但是线程安全的集合。
  • Vector:比Arraylist多了个同步化机制。
  • Stack:栈,也是线程安全的,继承于Vector。

线性不安全的:

  • HashMap - 数组 + 链表 + 红黑树
  • Arraylist - 数组
  • LinkedList - 双向循环链表
  • HashSet - HashjMap
  • TreeSet - 二叉树
  • TreeMap - 红黑树

3. Arraylist与 LinkedList 异同点?

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

4. ArrayList 与 Vector 区别?

  • Vector是线程安全的,ArrayList不是线程安全的。其中,Vector在关键性的方法前面都加了synchronized关键字,来保证线程的安全性。如果有多个线程会访问到集合,那最好是使用 Vector,因为不需要我们自己再去考虑和编写线程安全的代码。
  • ArrayList在底层数组不够用时在原来的基础上扩展0.5倍,Vector是扩展1倍,这样ArrayList就有利于节约内存空间。

5. Collection子接口:Set 接口

  • Set接口描述

    • Set接口是Collection的子接口,set接口没有提供额外的方法。
    • Set 集合存取元素同样是无序的。
    • Set 集合不允许包含相同的元素,如果试把两个相同的元素加入同一个Set 集合中,则添加操作失败。
    • Set 判断两个对象是否相同不是使用 == 运算符,而是根据 equals() 方法。
  • Set 实现类之一:HashSet
    • HashSet 是 Set 接口的典型实现,大多数时候使用 Set 集合时都使用这个实现类。HashSet的底层其实就是HashMap,只不过我们HashSet是实现了Set接口并且把数据作为K值,而V值一直使用一个相同的虚值来保存。
    • HashSet 按 Hash 算法来存储集合中的元素,因此具有很好的存取、查找、删除性能
    • HashSet 具有以下特点:不能保证元素的排列顺序、HashSet 不是线程安全的、集合元素可以是 null
    • HashSet 集合判断两个元素相等的标准:两个对象通过 hashCode() 方法比较相等,并且两个对象的 equals() 方法返回值也相等
    • 对于存放在Set容器中的对象,对应的类一定要重写equals()hashCode(Object obj)方法,以实现对象相等规则。即:“相等的对象必须具有相等的散列码”。

 

  • Set实现类之二:LinkedHashSet
    • LinkedHashSet 是 HashSet 的子类
    • LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置,但它同时使用双向链表维护元素的次序,这使得元素看起来是以插入顺序保存的。
    • LinkedHashSet插入性能略低于 HashSet,但在迭代访问 Set 里的全部元素时有很好的性能。
    • LinkedHashSet 不允许集合元素重复
  • Set实现类之三:TreeSet
    • TreeSet 是 SortedSet 接口的实现类,TreeSet 可以确保集合元素处于排序状态。

    • TreeSet底层使用红黑树结构存储数据
    • TreeSet 两种排序方法:自然排序和定制排序。默认情况下,TreeSet 采用自然排序。

6. Map接口

  • Map接口概述
    • Map与Collection并列存在。用于保存具有映射关系的数据:key-value
    • Map 中的 key 和 value 都可以是任何引用类型的数据
    • Map 中的 key Set方法来存放,不允许重复,即同一个 Map 对象所对应的类,须重写 hashCode()和equals() 方法
    • 常用String类作为Map的“键”
    • key值唯一,但可以为null
    • key 和 value 之间存在单向一对一关系,即通过指定的 key 总能找到唯一的、确定的 value
    • Map接口的常用实现类:HashMap、TreeMap、LinkedHashMap和Properties。其中,HashMap是 Map 接口使用频率最高的实现类

 

 

 7. Map实现类之一:HashMap

  • HashMap是 Map 接口使用频率最高的实现类。
  • 允许使用null键和null值,与HashSet一样,不保证映射的顺序。
  • 所有的key构成的集合是Set:无序的、不可重复的。所以,key所在的类要重写:equals()和hashCode()
  • 所有的value构成的集合是Collection:无序的、可以重复的。所以,value所在的类要重写:equals()
  • 一个key-value构成一个entry
  • 所有的entry构成的集合是无序的、不可重复的
  • HashMap 判断两个 key 相等的标准是:两个 key 通过 equals() 方法返回 true,hashCode 值也相等。
  • HashMap 判断两个 value相等的标准是:两个 value 通过 equals() 方法返回 true。
  • 扩容负载因子是0.75,扩容倍数:2

8. HashMap 的 底层数据结构是什么?

在JDK1.7 和JDK1.8 中有所差别:

在JDK1.7 中,由“数组+链表”组成,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的。

在JDK1.8 中,由“数组+链表+红黑树”组成。当链表过长,则会严重影响 HashMap 的性能,红黑树搜索时间复杂度是 O(logn),而链表是糟糕的 O(n)。因此,JDK1.8 对数据结构做了进一步的优化,引入了红黑树,链表和红黑树在达到一定条件会进行转换:

  • 当链表超过 8 且数据总量超过 64 才会转红黑树。

  • 将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树,以减少搜索时间。

 

 

 

9. 解决hash冲突的办法有哪些?HashMap用的哪种?

解决Hash冲突方法有:开放定址法、再哈希法、链地址法(拉链法)、建立公共溢出区。HashMap中采用的是 链地址法 。

  • 开放定址法也称为再散列法,基本思想就是,如果p=H(key)出现冲突时,则以p为基础,再次hash,p1=H(p),如果p1再次出现冲突,则以p1为基础,以此类推,直到找到一个不冲突的哈希地址pi。 因此开放定址法所需要的hash表的长度要大于等于所需要存放的元素,而且因为存在再次hash,所以只能在删除的节点上做标记,而不能真正删除节点。
  • 再哈希法(双重散列,多重散列),提供多个不同的hash函数,当R1=H1(key1)发生冲突时,再计算R2=H2(key1),直到没有冲突为止。 这样做虽然不易产生堆集,但增加了计算的时间。
  • 链地址法(拉链法),将哈希值相同的元素构成一个同义词的单链表,并将单链表的头指针存放在哈希表的第i个单元中,查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。
  • 建立公共溢出区,将哈希表分为公共表和溢出表,当溢出发生时,将所有溢出数据统一放到溢出区。

Collections工具类

  • Collections 是一个操作 Set、List 和 Map 等集合的工具类

  • Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作,
    还提供了对集合对象设置不可变、对集合对象实现同步控制等方法
  • 排序操作:(均为static方法)
    • reverse(List):反转 List 中元素的顺序
    • shuffle(List):对 List 集合元素进行随机排序
    • sort(List):根据元素的自然顺序对指定 List 集合元素按升序排序
    • sort(List,Comparator):根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
    • swap(List,int, int):将指定 list 集合中的 i 处元素和 j 处元素进行交换
  • Collections常用方法(查找、替换)

    • Object max(Collection):根据元素的自然顺序,返回给定集合中的最大元素
    • Object max(Collection,Comparator):根据 Comparator 指定的顺序,返回给定集合中的最大元素
    • Object min(Collection)
    • Object min(Collection,Comparator)
    • int frequency(Collection,Object):返回指定集合中指定元素的出现次数
    • void copy(List dest,List src):将src中的内容复制到dest中 boolean replaceAll(List list,Object oldVal,Object newVal):使用新值替换List 对象的所有旧值

 

这篇关于Java SE - 集合的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!