Java基础——集合框架

  Java的集合框架是Java中很重要的一环,Java平台提供了一个全新的集合框架。“集合框架”主要由一组用来操作对象的接口组成。不同接口描述一组不同数据类型。Java平台的完整集合框架如下图所示: 

  上述类图中,实线边框的是实现类,比如ArrayList,LinkedList,HashMap等,折线边框的是抽象类,比如AbstractCollection,AbstractList,AbstractMap等,而点线边框的是接口,比如Collection,Iterator,List等。

  发现一个特点,上述所有的集合Collection类,都实现了Iterator接口,(Map中并没有实现这个接口),这是一个用于遍历集合中元素的接口,主要包含hashNext(),next(),remove()三种方法。它的一个子接口ListIterator在它的基础上又添加了三种方法,分别是add(),previous(),hasPrevious()。

  • 如果是Iterator接口,那么在遍历集合中元素的时候,只能单向遍历,只能通过next()访问下一个元素,依次往后遍历,被遍历后的元素不会在遍历到。所有集合均实现了这个接口,比如HashSet,HashMap;
  • 而如果是ListIterator接口,那么在遍历集合中元素的时候,可以实现双向遍历,既可以通过next()访问下一个元素,又可以通过previous()访问前一个元素,更加灵活。但是只有List的子类才实现了这个接口,比如ArrayList。

  还有一个特点就是抽象类的使用。如果要自己实现一个集合类,去实现那些抽象的接口会非常麻烦,工作量很大。这个时候就可以使用抽象类,这些抽象类中给我们提供了许多现成的实现,我们只需要根据自己的需求重写一些方法或者添加一些方法就可以实现自己需要的集合类,工作流昂大大降低。

  将一些抽象类去掉之后的简化版如下图所示。

  下面简单介绍下每一种集合类型的特点:

  • Collection:每个“槽”只有一个元素
    • Set:每个元素必须是唯一的,不能含有重复的元素。加入Set的元素必须定义equals()方法以确保对象的唯一性。不保证维护元素的顺序。
      • HashSet***:主要的特点是:存入HashSet的元素必须定义hashCode()方法采用散列的存储方法,所以没有顺序。这里所说的没有顺序是指:元素插入的顺序与输出的顺序不一致。底层的物理结构是哈希表
        • LinkedHashSet*:主要特点是:具有HashSet的查询速度,且背部使用链表维护元素的顺序(插入的次序),存入LinkedHashSet的元素必须定义hashCode()方法,底层的物理结构是链表结合哈希表
      • TreeSet*:主要特点是是:保持次序的Set,存入TreeSet的元素必须实现Comparable接口,在加入元素时会自动进行排序。底层的物理结构是红黑树
    • List:将以特定次序存储元素,可以重复。
      • ArrayList***:主要特点是:长于随机访问元素,但是在List中间插入和移除元素时较慢,加入元素的顺序就是其存放元素的顺序。底层的物理结构是数组
      • LinkedList***:只要特点是:随机访问速度较慢,可以在任何位置进行高效地插入和删除操作的有序序列。底层的物理结构是双向链表LinkedList具有直接实现Stack(栈)的所有功能的方法,因此可以直接将LinkedList作为Stack使用。LinkedList也实现很多方法支持Quene(队列)的行为,并且其也实现了Quene接口,因此LinkedList也可以用作Quene的一种实现,可以将LinkedList向上转型为Quene。
      • Vector:主要特点是:和ArrayList功能和特点基本类似,不同的地方在于Vector是线程安全的,所以速度相对慢一些。底层的物理结构也是数组。现在基本上不怎么用了
        • Stack:现在不用了,可以用LinkedList来当做Stack.
    • Quene:先进先出的容器。从容器的一端放入事物,从另一端取出。一般用LinkedList来当做Quene.
  • Map:每个“槽”中存放的是键值对(key-value),可以使用键来查找值。
    • HashMap***:主要特点是:基于散列表的实现(取代了Hashtable)。插入和查询键值对的开销是固定的。可以通过构造器设置容量和负载因子,以调整容器性能。
      • LinkedHashMap*:类似于HashMap,但是迭代遍历时,取得的键值对的顺序是其插入的次序,或者是最近最少使用(LRU)的次序。只比HashMap慢一点,而在迭代访问时更快,因为其用链表维护内部次序,
    • TreeMap**:基于红黑树的实现。加入TreeMap的元素会被自动排序,排序次序有Comparable或Comparator决定( Comparable和Comparator的区别)。是唯一带有subMap()方法的Map,可以返回一个子树。
    • Hashtable:线程安全的,同HashMap现在基本上不用了
    • WeakedHashMap:弱键(weak key)映射,允许释放映射所指向的对象
    • IdentifyHashMap:使用==代替equals()对“键”进行比较的散列映射。

代码实例:HashSetDemo

 1 package edu.sjtu.erplab.collection;
 2 
 3 import java.util.HashSet;
 4 import java.util.Iterator;
 5 import java.util.Set;
 6 
 7 public class HashSetDemo {
 8 
 9     public static void main(String[] args) {
10         Set<String> set=new HashSet<String>();
11         
12         set.add("a");
13         set.add("b");
14         set.add("c");
15         set.add("c");
16         set.add("d");
17         
18         //使用Iterator输出集合
19         Iterator<String> iter=set.iterator();
20         while(iter.hasNext())
21         {
22             System.out.print(iter.next()+" ");
23         }
24         System.out.println();
25         //使用For Each输出结合
26         for(String e:set)
27         {
28             System.out.print(e+" ");
29         }
30         System.out.println();
31         
32         //使用toString输出集合
33         System.out.println(set);
34     }
35 }

代码实例:TreeSet

View Code

代码实例:ArrayListDemo

 1 package edu.sjtu.erplab.collection;
 2 
 3 import java.util.ArrayList;
 4 import java.util.Iterator;
 5 import java.util.List;
 6 
 7 public class ArrayListDemo {
 8     public static void main(String[] args) {
 9         List<String> arrList=new ArrayList<String>();
10         
11         arrList.add("a");
12         arrList.add("b");
13         arrList.add("c");
14         arrList.add("c");
15         arrList.add("d");
16 
17         //使用Iterator输出集合
18         Iterator<String> iter=arrList.iterator();
19         while(iter.hasNext())
20         {
21             System.out.print(iter.next()+" ");
22         }
23         System.out.println();
24         //使用For Each输出结合
25         for(String e:arrList)
26         {
27             System.out.print(e+" ");
28         }
29         System.out.println();
30         
31         //使用toString输出集合
32         System.out.println(arrList);
33     }
34 }

代码实例:LinkedListTest

 1 package edu.sjtu.erplab.collection;
 2 
 3 import java.util.ArrayList;
 4 import java.util.Iterator;
 5 import java.util.List;
 6 import java.util.ListIterator;
 7 
 8 public class LinkedListTest {
 9 
10     public static void main(String[] args) {
11 
12         List<String> a=new ArrayList<String>();
13         a.add("a");
14         a.add("b");
15         a.add("c");
16         System.out.println(a);
17         
18         List<String> b=new ArrayList<String>();
19         b.add("d");
20         b.add("e");
21         b.add("f");
22         b.add("g");
23         System.out.println(b);
24         
25         //ListIterator在Iterator基础上添加了add(),previous()和hasPrevious()方法
26         ListIterator<String> aIter=a.listIterator();
27         //普通的Iterator只有三个方法,hasNext(),next()和remove()
28         Iterator<String> bIter=b.iterator();
29         
30         //b归并入a当中,间隔交叉得插入b中的元素
31         while(bIter.hasNext())
32         {
33             if(aIter.hasNext())
34                 aIter.next();
35             aIter.add(bIter.next());
36         }
37         System.out.println(a);
38         
39         //在b中每隔两个元素删除一个
40         bIter=b.iterator();
41         
42         while(bIter.hasNext())
43         {
44             bIter.next();
45             if(bIter.hasNext())
46             {
47                 bIter.next();//remove跟next是成对出现的,remove总是删除前序
48                 bIter.remove();
49             }
50         }
51         System.out.println(b);
52         
53         //删除a中所有的b中的元素
54         a.removeAll(b);
55         System.out.println(a);
56     }
57 }

最后,看到了一些关于集合架构源码剖析的文章,有兴趣可以看一下,多了解内部原理也是挺好的。 

  各大类直接的区别可以参见:java中Map,List与Set的区别

探索equals()和hashCode()方法

Java集合框架源码剖析:HashSet 和 HashMap:

http://blog.jobbole.com/101493/

java中的HashTable,HashMap和HashSet

注意:HashMap的初始化容量为16,负载因子为0.75,然后当其中的元素个数大于16*0.75时进行扩容,每次扩容会将容量扩大两倍。

   HashSet的内部结构就是HashMap,只是每个键值对的值都确定为一个常量对象PRESENT(private static final Object PRESENT = new Object();)

Java集合框架源码剖析:LinkedHashSet 和 LinkedHashMap:

http://blog.jobbole.com/101724/

注意:LinkedHashSet 和 LinkedHashMap之间的关系和HashSet与HashMap之间的关系是一样的。只是在其中加入了双向链表的结构。插入的时候依然按照HashMap的方式插入,只是在元素之间用双向链表表示前后的顺序,所以查找和插入都很快速。

Java集合框架源码剖析:TreeSet 和 TreeMap:

http://blog.jobbole.com/102230/

java集合类TreeMap和TreeSet

注意:TreeSet 和 TreeMap之间的关系和HashSet与HashMap之间的关系是一样的。TreeMap实现了SortedMap接口,也就是说会按照key的大小顺序对Map中的元素进行排序key大小的评判可以通过其本身的自然顺序(natural ordering),也可以通过构造时传入的比较器(Comparator)。TreeMap底层通过红黑树(Red-Black tree)实现,也就意着containsKey()get()put()remove()都有着log(n)的时间复杂度。

  红黑树的原理:

http://blog.jobbole.com/103045/

《Thinking In Algorithm》07.Red-Black Trees(红黑树)

Java集合框架源码剖析:ArrayList:

http://blog.jobbole.com/101796/

ArrayList与LinkedList的区别

注意:ArrayList的初始化容量为10,然后当其中的元素个数大于16*0.75时进行扩容,每次扩容会将容量扩大原先的1.5倍,eg:第一次扩容至10+10/2=15,第二次是15+15/2 = 22,以此类推。

Java集合框架源码剖析:LinkedList:

  http://blog.jobbole.com/101830/

注意:LinkedList中定义的双向链表的Node节点如下:

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java Web

数据结构与算法(4)——优先队列和堆什么是优先队列?堆和二叉堆LeetCode相关题目整理

听这个名字就能知道,优先队列也是一种队列,只不过不同的是,优先队列的出队顺序是按照优先级来的;在有些情况下,可能需要找到元素集合中的最小或者最大元素,可以利用优...

3481
来自专栏微信公众号:Java团长

Java HashMap的工作原理

面试的时候经常会遇见诸如:“java中的HashMap是怎么工作的”,“HashMap的get和put内部的工作原理”这样的问题。本文将用一个简单的例子来解释下...

592
来自专栏大数据钻研

Java 集合框架 HashSet 和 HashMap 源码剖析

总体介绍 之所以把HashSet和HashMap放在一起讲解,是因为二者在Java里有着相同的实现,前者仅仅是对后者做了一层包装,也就是说HashSet里面有一...

3006
来自专栏Petrichor的专栏

leetcode: 100. Same Tree

1041
来自专栏Java帮帮-微信公众号-技术文章全总结

Java集合详解【面试+工作】

在说集合前我们不得不说一下数组 数组的作用: 存放一组相同的数据类型(基本或对象)的数据,从而实现对数据的管理 优势:可以快速的通过下标对数组元素进行访问,效率...

4356
来自专栏Java 源码分析

HashSet 源码分析

HashSet 源码分析 1. 在阅读源码时做了大量的注释,并且做了一些测试分析源码内的执行流程,由于博客篇幅有限,并且代码阅读起来没有 IDE 方便,所以在...

3164
来自专栏个人分享

LinkedHashMap的实现原理(复习)

   LinkedHashMap是Map接口的哈希表和链接列表实现,具有可预知的迭代顺序。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不...

1034
来自专栏于晓飞的专栏

读 Java Arrays 源码 笔记

Arrays.java是Java中用来操作数组的类。使用这个工具类可以减少平常很多的工作量。了解其实现,可以避免一些错误的用法。

912
来自专栏程序员互动联盟

读 Java Arrays 源码 笔记

Arrays.java是Java中用来操作数组的类。使用这个工具类可以减少平常很多的工作量。了解其实现,可以避免一些错误的用法。 它提供的操作包括: 排序 so...

36912
来自专栏码云1024

List Set Map比较

3424

扫码关注云+社区