本文主要是介绍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
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 对数据结构做了进一步的优化,引入了红黑树,链表和红黑树在达到一定条件会进行转换:
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工具类
这篇关于Java SE - 集合的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!