Java集合学习总结

概览

容器主要包括 Collection 和 Map 两种,Collection 存储着对象的集合,而 Map 存储着键值对(两个对象)的映射表。

Collection

Collection

1. Set

  • TreeSet(有序,唯一):基于红黑树实现,支持有序性操作,例如根据一个范围查找元素的操作。但是查找效率不如 HashSet,HashSet 查找的时间复杂度为 O(1),TreeSet 则为 O(logN);
  • HashSet(无序,唯一):基于 HashMap 实现,支持快速查找,但不支持有序性操作。并且失去了元素的插入顺序信息,即使用 Iterator 遍历 HashSet 得到的结果是不确定的;
  • LinkedHashSet:继承于HashSet,内部使用双向链表维护元素的插入顺序;

2. List

  • ArrayList:基于动态数组实现,支持随机访问,插入要移动数据;
  • Vector:和 ArrayList 类似,但它是线程安全的,已弃用;
  • LinkedList:基于双向链表实现,只能顺序访问,但是可以快速地在链表中间插入和删除元素。不仅如此,LinkedList 还可以用作栈、队列和双向队列;

3. Queue

  • LinkedList:可以用它来实现双向队列;
  • PriorityQueue:基于堆结构实现,可以用它来实现优先队列;

Map

Map

  • TreeMap:基于红黑树实现;
  • HashMap:JDK1.8之前HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突)。JDK1.8以后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间
  • HashTable:和 HashMap 类似,但它是线程安全的,这意味着同一时刻多个线程可以同时写入 HashTable 并且不会导致数据不一致。它是遗留类,不应该去使用它。现在可以使用 ConcurrentHashMap 来支持线程安全,并且 ConcurrentHashMap 的效率会更高,因为ConcurrentHashMap 引入了分段锁;
  • LinkedHashMap:继承自 HashMap,使用双向链表来维护元素的顺序,顺序为插入顺序或者最近最少使用(LRU)顺序;

容器中的设计模式

迭代器模式

迭代器模式

适配器模式

java.util.Arrays.asList() 可以把数组类型转换为 List 类型。

1
2
@SafeVarargs
public static <T> List<T> asList(T... a)

此处注意 asList() 的参数为泛型的变长参数,不能使用基本类型数组作为参数,只能使用相应的包装类型数组。

1
2
3
4
Integer[] arr = {1, 2, 3};
List list = Arrays.asList(arr);
//也可以使用以下方式调用 asList():
List list = Arrays.asList(1, 2, 3);

差异分析

List

ArrayList 与 LinkedList 区别

  1. 是否保证线程安全: ArrayList 和 LinkedList 都是不同步的,也就是不保证线程安全;
  2. 底层数据结构: Arraylist 底层使用的是Object数组;LinkedList 底层使用的是双向链表数据结构;
  3. 插入和删除是否受元素位置的影响
    • ① 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);
  4. 是否支持快速随机访问: LinkedList 不支持高效的随机元素访问,而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
  5. 内存空间占用: ArrayList的空 间浪费主要体现在在list列表的结尾会预留一定的容量空间,而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间(因为要存放直接后继和直接前驱以及数据);
  6. 补充内容:RandomAccess接口(仅标识实现这个接口的类具有随机访问功能)
    1
    2
    public interface RandomAccess {
    }

此处总结一下 list 的遍历方式选择:

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

ArrayList 与 Vector 区别

  • Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。
  • Arraylist不是同步的,所以在不需要保证线程安全时时建议使用Arraylist。

Map

HashMap 和 Hashtable 的区别

  1. 线程是否安全: HashMap 是非线程安全的,HashTable 是线程安全的;HashTable 内部的方法基本都经过 synchronized 修饰(现已弃用,建议使用ConcurrentHashMap);
  2. 效率: 因为线程安全的问题,HashMap 要比 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 中的tableSizeFor()方法保证,下面给出了源代码)。也就是说 HashMap 总是使用2的幂作为哈希表的大小,后面会介绍到为什么是2的幂次方;
  5. 底层数据结构: JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。Hashtable 没有这样的机制;

ConcurrentHashMap 和 Hashtable 的区别

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

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

两者的对比图:
HashTable:
HashTable

JDK1.7的ConcurrentHashMap::
JDK1.7的ConcurrentHashMap

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

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

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

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

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

HashSet 和 HashMap 区别

如果你看过 HashSet 源码的话就应该知道:HashSet 底层就是基于 HashMap 实现的。(HashSet 的源码非常非常少,因为除了 clone() 方法、writeObject()方法、readObject()方法是 HashSet 自己不得不实现之外,其他方法都是直接调用 HashMap 中的方法。)
HashSet VS HashMap

补充问题

HashSet如何检查重复

当你把对象加入HashSet时,HashSet会先计算对象的hashcode值来判断对象加入的位置,同时也会与其他加入的对象的hashcode值作比较,如果没有相符的hashcode,HashSet会假设对象没有重复出现。但是如果发现有相同hashcode值的对象,这时会调用equals()方法来检查hashcode相等的对象是否真的相同。如果两者相同,HashSet就不会让加入操作成功。(摘自我的Java启蒙书《Head fist java》第二版)

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

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

==与equals的区别

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

comparable 和 comparator的区别

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

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

如何对Object的list排序

  • 对objects数组进行排序,我们可以用Arrays.sort()方法
  • 对objects的集合进行排序,需要使用Collections.sort()方法

如何实现数组与List的相互转换

List转数组:toArray(arraylist.size()方法;数组转List:Arrays的asList(a)方法

如何求ArrayList集合的交集、并集、差集、去重复并集

需要用到List接口中定义的几个方法:

  • addAll(Collection<? extends E> c) :按指定集合的Iterator返回的顺序将指定集合中的所有元素追加到此列表的末尾 实例代码:
  • retainAll(Collection<?> c): 仅保留此列表中包含在指定集合中的元素。
  • removeAll(Collection<?> c) :从此列表中删除指定集合中包含的所有元素。

集合的选用

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

集合的常用方法

参考API,待补充

感谢您的阅读,本文由 雪释潮涯的博客~ 版权所有。如若转载,请注明出处: 雪释潮涯的博客~( https://www.xschaoya.com
一条DB2 update sql语句认知错误

推荐阅读

留下足迹