首页 > 代码库 > java集合

java集合

java集合

  • Java集合框架
  • Collection接口API
  • Iterator迭代器接口(遍历集合中的元素)
  • Collection子接口之一:Set接口
    • HashSet LinkedHashSet TreeSet
  • Collection子接口之二: List接口
    • ArrayList LinkedList Vector
  • Map接口
    • HashMap TreeMap Hashtable
  • Collections工具类

Java 集合概述

  • 一方面, 面向对象语言对事物的体现都是以对象的形式,为了方便对多个对象的操作,就要对对象进行存储。另一方面,使用Array存储对象方面具有一些弊端,而Java 集合就像一种容器,可以动态地把多个对象的引用放入容器中。
  • Java 集合类可以用于存储数量不等的多个对象,还可用于保存具有映射关系的关联数组。
  • 数组的弊端:一旦建立 长度不可变。数组中数据类型必须一致,数组中元素个数未知。
  • Java 集合可分为 Collection 和 Map 两种体系
    • Collection接口:
      • Set:元素无序、不可重复的集合 ---类似高中的"集合"
      • List:元素有序,可重复的集合 ---"动态"数组
        • Map接口:具有映射关系"key-value对"的集合 ---类似于高中的"函数"

技术分享

  • Map接口继承树

技术分享

Collection 接口

  • Collection 接口是 List、Set 和 Queue 接口的父接口,该接口里定义的方法既可用于操作 Set 集合,也可用于操作 List 和 Queue 集合。
  • JDK不提供此接口的任何直接实现,而是提供更具体的子接口(如:Set和List)实现。
  • 在 Java5 之前,Java 集合会丢失容器中所有对象的数据类型,把所有对象都当成 Object 类型处理;从 Java5 增加了泛型以后,Java 集合可以记住容器中对象的数据类型

Collection 接口的方法

技术分享

技术分享

红色部分:集合与数组间转换操作的方法:如下图

使用 Iterator 接口遍历集合元素

  • Iterator对象称为迭代器(设计模式的一种),主要用于遍历 Collection 集合中的元素。
  • 所有实现了Collection接口的集合类都有一个iterator()方法,用以返回一个实现了Iterator接口的对象。
  • Iterator 仅用于遍历集合,Iterator 本身并不提供承装对象的能力。如果需要创建 Iterator 对象,则必须有一个被迭代的集合。

技术分享

Iterator接口的方法

技术分享

技术分享

在调用it.next()方法之前必须要调用it.hasNext()进行检测。若不调用,且下一条记录无效,直接调用it.next()会抛出NoSuchElementException异常

?

while(it.hasNext()){

????…..it.next();

}

使用 foreach 循环遍历集合元素

  • ????Java 5 提供了 foreach 循环迭代访问 Collection

技术分享

List接口

  • Java中数组用来存储数据的局限性
  • List集合类中元素有序、且可重复,集合中的每个元素都有其对应的顺序索引。
  • List容器中的元素都对应一个整数型的序号记载其在容器中的位置,可以根据序号存取容器中的元素。
  • JDK API中List接口的实现类常用的有:ArrayList、LinkedList和Vector。
  • List 集合里添加了一些根据索引来操作集合元素的方法
    • void add(int index, Object ele)
    • boolean addAll(int index, Collection eles)
    • Object get(int index)
    • int indexOf(Object obj)
    • int lastIndexOf(Object obj)
    • Object remove(int index)
    • Object set(int index, Object ele)
    • List subList(int fromIndex, int toIndex)

List实现类之一:ArrayList

  • ArrayList 是 List 接口的典型实现类
  • 本质上,ArrayList是对象引用的一个变长数组
  • ArrayList 是线程不安全的,而 Vector 是线程安全的,即使为保证 List 集合线程安全,也不推荐使用Vector
  • Arrays.asList(…) 方法返回的 List 集合既不是 ArrayList 实例,也不是 Vector 实例。 Arrays.asList(…) 返回值是一个固定长度的 List 集合

List实现类之二:LinkedList

  • 对于频繁的插入或删除元素的操作,建议使用LinkedList类,效率较高
  • 新增方法:
    • void addFirst(Object obj)
    • void addLast(Object obj)????
    • Object getFirst()
    • Object getLast()
    • Object removeFirst()
    • Object removeLast()

List 实现类之三:Vector

  • Vector 是一个古老的集合,JDK1.0就有了。大多数操作与ArrayList相同,区别之处在于Vector是线程安全的。
  • 在各种list中,最好把ArrayList作为缺省选择。当插入、删除频繁时,使用LinkedList;Vector总是比ArrayList慢,所以尽量避免使用。
  • 新增方法:
    • void addElement(Object obj)
    • void insertElementAt(Object obj,int index)
    • void setElementAt(Object obj,int index)
    • void removeElement(Object obj)
    • void removeAllElements()

ListIterator接口(了解)

  • List 额外提供了一个 listIterator() 方法,该方法返回一个 ListIterator 对象, ListIterator 接口继承了 Iterator 接口,提供了专门操作 List 的方法:
    • void add()
    • boolean hasPrevious()
    • Object previous()
    • Boolean hasNext()
    • Object next()

Iterator和ListIterator主要区别(了解)

1、ListIterator和Iterator都有hasNext()和next()方法,可以实现顺序向后遍历。但是ListIterator有hasPrevious()和previous()方法,可以实现逆向(顺序向前)遍历。Iterator就不可以。

2、ListIterator可以定位当前的索引位置,nextIndex()和previousIndex()可以实现。Iterator 没有此功能。

3、ListIterator有add()方法,可以向List中插入对象,而Iterator不能。

4、都可实现删除对象,但是ListIterator可以实现对象的修改,set()方法可以实现。Iterator仅能遍历,不能修改。因为ListIterator的这些功能,可以实现对LinkedList等List数据结构的操作。

?

Set 接口

  • Set接口是Collection的子接口,set接口没有提供额外的方法
  • Set 集合不允许包含相同的元素,如果试把两个相同的元素加入同一个 Set 集合中,则添加操作失败。
  • Set 判断两个对象是否相同不是使用 == 运算符,而是根据 equals 方法

Set实现类之一:HashSet

  • HashSet 是 Set 接口的典型实现,大多数时候使用 Set 集合时都使用这个实现类。
  • HashSet 按 Hash 算法来存储集合中的元素,因此具有很好的存取和查找性能。
  • HashSet 具有以下特点:
    • 不能保证元素的排列顺序
    • HashSet 不是线程安全的
    • 集合元素可以是 null
  • 当向 HashSet 集合中存入一个元素时,HashSet 会调用该对象的 hashCode() 方法来得到该对象的 hashCode 值,然后根据 hashCode 值决定该对象在 HashSet 中的存储位置。
  • HashSet 集合判断两个元素相等的标准:两个对象通过 hashCode() 方法比较相等,并且两个对象的 equals() 方法返回值也相等。

技术分享

hashCode() 方法

  • 如果两个元素的 equals() 方法返回 true,但它们的 hashCode() 返回值不相等,hashSet 将会把它们存储在不同的位置,但依然可以添加成功。
  • 对于存放在Set容器中的对象,对应的类一定要重写equals()和hashCode(Object obj)方法,以实现对象相等规则。
  • 重写 hashCode() 方法的基本原则
    • 在程序运行时,同一个对象多次调用 hashCode() 方法应该返回相同的值
    • 当两个对象的 equals() 方法比较返回 true 时,这两个对象的 hashCode() 方法的返回值也应相等

对象中用作 equals() 方法比较的 Field,都应该用来计算 hashCode 值

Set实现类之二:LinkedHashSet

  • LinkedHashSet 是 HashSet 的子类
  • LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置,但它同时使用链表维护元素的次序,这使得元素看起来是以插入顺序保存的。
  • LinkedHashSet插入性能略低于 HashSet,但在迭代访问 Set 里的全部元素时有很好的性能。
  • LinkedHashSet 不允许集合元素重复。

技术分享

Set实现类之三:TreeSet

  • TreeSet 是 SortedSet 接口的实现类,TreeSet 可以确保集合元素处于排序状态。
    • Comparator comparator()
    • Object first()
    • Object last()
    • Object lower(Object e)
    • Object higher(Object e)
    • SortedSet subSet(fromElement, toElement)
    • SortedSet headSet(toElement)
    • SortedSet tailSet(fromElement)
  • TreeSet 两种排序方法:自然排序定制排序。默认情况下,TreeSet 采用自然排序.

    ?

排 序——自然排序 Comparable 接口

  • 自然排序:TreeSet 会调用集合元素的 compareTo(Object obj) 方法来比较元素之间的大小关系,然后将集合元素按升序排列
  • 如果试图把一个对象添加到 TreeSet 时,则该对象的类必须实现 Comparable 接口。
  • 实现 Comparable 的类必须实现 compareTo(Object obj) 方法,两个对象即通过 compareTo(Object obj) 方法的返回值来比较大小。
  • Comparable 的典型实现
    • BigDecimal、BigInteger 以及所有的数值型对应的包装类:按它们对应的数值大小进行比较
    • Character:按字符的 unicode值来进行比较
    • Boolean:true 对应的包装类实例大于 false 对应的包装类实例
    • String:按字符串中字符的 unicode 值进行比较
    • Date、Time:后边的时间、日期比前面的时间、日期大
  • 向 TreeSet 中添加元素时,只有第一个元素无须比较compareTo()方法,后面添加的所有元素都会调用compareTo()方法进行比较。
  • 因为只有相同类的两个实例才会比较大小,所以向 TreeSet 中添加的应该是同一个类的对象
  • 对于 TreeSet 集合而言,它判断两个对象是否相等的唯一标准是:两个对象通过 compareTo(Object obj) 方法比较返回值
  • 当需要把一个对象放入 TreeSet 中,重写该对象对应的 equals() 方法时,应保证该方法与 compareTo(Object obj) 方法有一致的结果:如果两个对象通过 equals() 方法比较返回 true,则通过 compareTo(Object obj) 方法比较应返回 0

?

排 序——定制排序 comparator接口

  • TreeSet的自然排序是根据集合元素的大小,进行元素升序排列。如果需要定制排序,比如降序排列,可通过Comparator接口的帮助。需要重写compare(T o1,T o2)方法。
  • 利用int compare(T o1,T o2)方法,比较o1和o2的大小:如果方法返回正整数,则表示o1大于o2;如果返回0,表示相等;返回负整数,表示o1小于o2。
  • 要实现定制排序,需要将实现Comparator接口的实例作为形参传递给TreeSet的构造器。
  • 此时,仍然只能向TreeSet中添加类型相同的对象。否则发生ClassCastException异常。
  • 使用定制排序判断两个元素相等的标准是:通过Comparator比较两个元素返回了0。

Map接口

  • Map与Collection并列存在。用于保存具有映射关系的数据:Key-Value
  • Map 中的 key 和 value 都可以是任何引用类型的数据
  • Map 中的 key 用Set来存放,不允许重复,即同一个 Map 对象所对应的类,须重写hashCode()和equals()方法。
  • 常用String类作为Map的"键"。
  • key 和 value 之间存在单向一对一关系,即通过指定的 key 总能找到唯一的、确定的 value。

技术分享

技术分享

Map实现类之一:HashMap

  • Map接口的常用实现类:HashMap、TreeMap和Properties。
  • HashMap是 Map 接口使用频率最高的实现类。
  • 允许使用null键和null值,与HashSet一样,不保证映射的顺序。
  • HashMap 判断两个 key 相等的标准是:两个 key 通过 equals() 方法返回 true,hashCode 值也相等。
  • HashMap 判断两个 value相等的标准是:两个 value 通过 equals() 方法返回 true。

Map实现类之二:LinkedHashMap

  • LinkedHashMap 是 HashMap 的子类
  • 与LinkedHashSet类似,LinkedHashMap 可以维护 Map 的迭代顺序:迭代顺序与 Key-Value 对的插入顺序一致

Map实现类之三:TreeMap

  • TreeMap存储 Key-Value 对时,需要根据 key-value 对进行排序。TreeMap 可以保证所有的 Key-Value 对处于有序状态。
  • TreeMap 的 Key 的排序:
    • 自然排序:TreeMap 的所有的 Key 必须实现 Comparable 接口,而且所有的 Key 应该是同一个类的对象,否则将会抛出 ClasssCastException
    • 定制排序:创建 TreeMap 时,传入一个 Comparator 对象,该对象负责对 TreeMap 中的所有 key 进行排序。此时不需要 Map 的 Key 实现 Comparable 接口
  • TreeMap判断两个key相等的标准:两个key通过compareTo()方法或者compare()方法返回0。

若使用自定义类作为TreeMap的key,所属类需要重写equals()和hashCode()方法,且equals()方法返回true时,compareTo()方法应返回0

Map实现类之四:Hashtable

  • Hashtable是个古老的 Map 实现类,线程安全。
  • 与HashMap不同,Hashtable 不允许使用 null 作为 key 和 value
  • 与HashMap一样,Hashtable 也不能保证其中 Key-Value 对的顺序
  • Hashtable判断两个key相等、两个value相等的标准,与hashMap一致。

Map实现类之五:Properties

  • Properties 类是 Hashtable 的子类,该对象用于处理属性文件
  • 由于属性文件里的 key、value 都是字符串类型,所以 Properties 里的 key 和 value 都是字符串类型
  • 存取数据时,建议使用setProperty(String key,String value)方法和getProperty(String key)方法

Properties pros = new Properties();

pros.load(new FileInputStream("jdbc.properties"));

String user = pros.getProperty("user");

System.out.println(user);

操作集合的工具类: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 处元素进行交换

查找、替换

  • ????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 对象的所有旧值

?

同步控制

  • Collections 类中提供了多个 synchronizedXxx() 方法,该方法可使将指定集合包装成线程同步的集合,从而可以解决多线程并发访问集合时的线程安全问题

技术分享

Enumeration(了解)

  • Enumeration 接口是 Iterator 迭代器的 "古老版本"

技术分享

Enumeration stringEnum = new StringTokenizer("a-b*c-d-e-g", "-");

????while(stringEnum.hasMoreElements()){

????????Object obj = stringEnum.nextElement();

????????System.out.println(obj);

????}

?

集合部分面试题

1 Collection 和 Collections的区别

答:Collection是集合类的上级接口,继承与他的接口主要有Set 和List.

Collections是针对集合类的一个帮助类,他提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作

?

--------------------------------------------------

2 Set里的元素是不能重复的,那么用什么方法来区分重复与否呢? 是用==还是equals()? 它们有何区别

答:Set里的元素是不能重复的,那么用iterator()方法来区分重复与否。equals()是判读两个Set是否相等

equals()和==方法决定引用值是否指向同一对象equals()在类中被覆盖,为的是当两个分离的对象的内容

和类型相配的话,返回真值

?

--------------------------------------------------

3 List, Set, Map是否继承自Collection接口

答: List,Set是,Map不是

?

--------------------------------------------------

4 两个对象值相同(x.equals(y) == true),但却可有不同的hash code,这句话对不对

答:不对,有相同的hash code

?

--------------------------------------------------

5 说出ArrayList,Vector, LinkedList的存储性能和特性

答:ArrayList和Vector都是使用数组方式存储数据,此数组元素数大于实际存储的数据以便增加和插入元素,它们都允许直接按序号索引元素,但是插入元素要涉及数组元素移动等内存操作,所以索引数据快而插入数据慢,Vector由于使用了synchronized方法(线程安全),通常性能上较ArrayList差,而LinkedList使用双向链表实现存储,按序号索引数据需要进行前向或后向遍历,但是插入数据时只需要记录本项的前后项即可,所以插入速度较快。

?

--------------------------------------------------

6 HashMap和Hashtable的区别

答:HashMap是Hashtable的轻量级实现(非线程安全的实现),他们都完成了Map接口,主要区别在于

HashMap允许空(null)键值(key),由于非线程安全,效率上可能高于Hashtable。

HashMap允许将null作为一个entry的key或者value,而Hashtable不允许。

HashMap把Hashtable的contains方法去掉了,改成containsvalue和containsKey。因为contains方法容易让人引起误解。

Hashtable继承自Dictionary类,而HashMap是Java1.2引进的Map interface的一个实现。

最大的不同是,Hashtable的方法是Synchronize的,而HashMap不是,在多个线程访问Hashtable时,不需要自己为它的方法实现同步,而HashMap 就必须为之提供外同步。

Hashtable和HashMap采用的hash/rehash算法都大概一样,所以性能不会有很大的差异。

?

--------------------------------------------------

?

7 ArrayList和Vector的区别,HashMap和Hashtable的区别

答:就ArrayList与Vector主要从二方面来说.

一.同步性:Vector是线程安全的,也就是说是同步的,而ArrayList是线程序不安全的,不是同步的

二.数据增长:当需要增长时,Vector默认增长为原来一培,而ArrayList却是原来的一半

就HashMap与HashTable主要从三方面来说。

一.历史原因:Hashtable是基于陈旧的Dictionary类的,HashMap是Java 1.2引进的Map接口的一个实现

二.同步性:Hashtable是线程安全的,也就是说是同步的,而HashMap是线程序不安全的,不是同步的

三.值:只有HashMap可以让你将空值作为一个表的条目的key或value

?

?

?

8 如何高效地判断数组中是否包含某特定值

如何检查一个未排序的数组中是否包含某个特定值,这是一个在Java中非常实用并且频繁使用的操作。检查数组中是否包含特定值可以用多种不同的方式实现,但是时间复杂度差别很大。下面,将为大家展示各种方法及其需要花费的时间。

1.检查数组中是否包含特定值的四种不同方法

1)使用List:

public static boolean useList(String[] arr, String targetValue) {

????return Arrays.asList(arr).contains(targetValue);

}

2)使用Set

1

2

3

4

public static boolean useSet(String[] arr, String targetValue) {

????Set<String> set = new HashSet<String>(Arrays.asList(arr));

????return set.contains(targetValue);

}

3)使用一个简单循环:

1

2

3

4

5

6

7

public static boolean useLoop(String[] arr, String targetValue) {

????for(String s: arr){

????????if(s.equals(targetValue))

????????????return true;

????}

????return false;

}

4)使用Arrays.binarySearch()

注:下面的代码是错误的,这样写出来仅仅为了理解方便binarySearch()只能用于已排好序的数组中。所以,你会发现下面结果很奇怪。

1

2

3

4

5

6

7

public static boolean useArraysBinarySearch(String[] arr, String targetValue) {

????int a =? Arrays.binarySearch(arr, targetValue);

????if(a > 0)

????????return true;

????else

????????return false;

}

2.时间复杂度

通过下面的这段代码可以近似比较几个方法的时间复杂度。虽然分别搜索一个大小为51K10K的数组是不够精确的,但是思路是清晰的。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

public static void main(String[] args) {

????String[] arr = new String[] {? "CD",? "BC", "EF", "DE", "AB"};

???

????//use list

????long startTime = System.nanoTime();

????for (int i = 0; i < 100000; i++) {

????????useList(arr, "A");

????}

????long endTime = System.nanoTime();

????long duration = endTime - startTime;

????System.out.println("useList:? " + duration / 1000000);

???

????//use set

????startTime = System.nanoTime();

????for (int i = 0; i < 100000; i++) {

????????useSet(arr, "A");

????}

????endTime = System.nanoTime();

????duration = endTime - startTime;

????System.out.println("useSet:? " + duration / 1000000);

???

????//use loop

????startTime = System.nanoTime();

????for (int i = 0; i < 100000; i++) {

????????useLoop(arr, "A");

????}

????endTime = System.nanoTime();

????duration = endTime - startTime;

????System.out.println("useLoop:? " + duration / 1000000);

???

????//use Arrays.binarySearch()

????startTime = System.nanoTime();

????for (int i = 0; i < 100000; i++) {

????????useArraysBinarySearch(arr, "A");

????}

????endTime = System.nanoTime();

????duration = endTime - startTime;

????System.out.println("useArrayBinary:? " + duration / 1000000);

}

结果:

1

2

3

4

useList:? 13

useSet:? 72

useLoop:? 5

useArraysBinarySearch:? 9

对于长度为1K的数组:

1

2

3

4

5

6

String[] arr = new String[1000];

???

Random s = new Random();

for(int i=0; i< 1000; i++){

????arr[i] = String.valueOf(s.nextInt());

}

结果:

1

2

3

4

useList:? 112

useSet:? 2055

useLoop:? 99

useArrayBinary:? 12

对于长度为10K的数组:

1

2

3

4

5

6

String[] arr = new String[10000];

???

Random s = new Random();

for(int i=0; i< 10000; i++){

????arr[i] = String.valueOf(s.nextInt());

}

结果:

1

2

3

4

useList:? 1590

useSet:? 23819

useLoop:? 1526

useArrayBinary:? 12

很明显,使用简单循环的方法比使用其他任何集合效率更高。许多开发者会使用第一种方法,但是它并不是高效的。将数组压入Collection类型中,需要首先将数组元素遍历一遍,然后再使用集合类做其他操作。

如果使用Arrays.binarySearch()方法,数组必须是已排序的。由于上面的数组并没有进行排序,所以该方法不可使用。

实际上,如果你需要借助数组或者集合类高效地检查数组中是否包含特定值,一个已排序的列表或树可以做到时间复杂度为O(log(n))hashset可以达到O(1)

java集合