概述:

集合类存放于 Java.util 包中,大致可以分为两大体系,一个是Collection,另一个是Map(映射)。

  • Collection :主要由List(列表)、Set(集)、Queue(队列) 接口组成,List代表有序、重复的集合;其中Set代表无序、不可重复的集合;Java 5 又增加了Queue体系集合,代表一种队列集合实现。
  • Map:则代表具有映射关系的键值对集合。

其中,Java 集合框架中主要封装的是典型的数据结构和算法,如动态数组、双向链表、队列、栈、Set、Map 等。可以分为以下几个部分:

数据结构
List列表、Queue队列、Deque双端队列、Set集合、Map映射

比较器
Comparator比较器、Comparable排序接口

算法
Collections常用算法类、Arrays静态数组的排序、查找算法

迭代器
Iterator通用迭代器、ListIterator针对 List 特化的迭代器

有序列表(List)

List集合的特点就是存取有序,可以存储重复的元素,可以用下标进行元素的操作

在List集合中,我们常用到ArrayList和LinkedList这两个类。(Vector、Stack以淘汰)

其中,ArrayList底层通过数组实现,随着元素的增加而动态扩容。而LinkedList底层通过链表来实现,随着元素的增加不断向链表的后端增加节点。

List包括List接口以及List接口的所有实现类。因为List接口实现了Collection接口,所以List接口拥有Collection接口提供的所有常用方法,又因为List是列表类型,所以List接口还提供了一些适合于自身的常用方法,如图所示:

原文链接:https://blog.csdn.net/ChouChou719/article/details/126048677

ArrayList (底层:数组)

ArrayList是Java集合框架中使用最多的一个类,是一个数组队列,线程不安全集合。

它继承于AbstractList,实现了List, RandomAccess, Cloneable, Serializable接口。
(1)ArrayList实现List,得到了List集合框架基础功能;
(2)ArrayList实现RandomAccess,获得了快速随机访问存储元素的功能,RandomAccess是一个标记接口,没有任何方法;
(3)ArrayList实现Cloneable,得到了clone()方法,可以实现克隆功能;
(4)ArrayList实现Serializable,表示可以被序列化,通过序列化去传输,典型的应用就是hessian协议。

它具有如下特点:

  • 容量不固定,随着容量的增加而动态扩容(阈值基本不会达到)
  • 有序集合(插入的顺序==输出的顺序)
  • 插入的元素可以为null
  • 增删改查效率更高(相对于LinkedList来说)
  • 线程不安全

LinkedList(底层:链表)

LinkedList是一个双向链表结构,在任意位置插入删除都很方便,但是不支持随机取值,每次都只能从一端开始遍历,直到找到查询的对象,然后返回;不过,它不像 ArrayList 那样需要进行内存拷贝,因此相对来说效率较高,但是因为存在额外的前驱和后继节点指针,因此占用的内存比 ArrayList 多一些。

它继承AbstractSequentialList,实现了List, Deque, Cloneable, Serializable接口。

(1)LinkedList实现List,得到了List集合框架基础功能;
(2)LinkedList实现Deque,Deque 是一个双向队列,也就是既可以先入先出,又可以先入后出,说简单些就是既可以在头部添加元素,也可以在尾部添加元素;
(3)LinkedList实现Cloneable,得到了clone()方法,可以实现克隆功能;
(4)LinkedList实现Serializable,表示可以被序列化,通过序列化去传输,典型的应用就是hessian协议。

原文链接:https://blog.csdn.net/lovedingd/article/details/110393777

Vector

Vector也是一个动态数组结构,一个元老级别的类,早在jdk1.1就引入进来类,之后在jdk1.2里引进ArrayList,ArrayList大部分的方法和Vector比较相似,两者是不同的,Vector是允许同步访问的,Vector中的操作是线程安全的,但是效率低,而ArrayList所有的操作都是异步的,执行效率高,但不安全!

关于Vector,现在用的很少了,因为里面的get、set、add等方法都加了synchronized,所以,执行效率会比较低,如果需要在多线程中使用,可以采用下面语句创建ArrayList对象

List<Object> list =Collections.synchronizedList(new ArrayList<Object>());

Stack

Stack是Vector的一个子类,本质也是一个动态数组结构,不同的是,它的数据结构是先进后出,取名叫栈!

关于Stack,现在用的也很少,因为有个ArrayDeque双端队列,可以替代Stack所有的功能,并且执行效率比它高!

集(Set)

Set集合的特点:元素不重复,存取无序,无下标;

Set继承于Collection接口,是一个不允许出现重复元素,并且无序的集合,主要有HashSet和TreeSet两大实现类。在判断重复元素的时候,Set集合会调用hashCode()和equal()方法来实现。

set集合框架结构

与List接口一样,Set接口也提供了集合操作的基本方法。但与List不同的是,Set还提供了equals(Object o)和hashCode(),供其子类重写,以实现对集合中插入重复元素的处理。

原文链接:https://blog.csdn.net/ChouChou719/article/details/126048677

HashSet(存储结构:哈希表(数组+链表+红黑树)

HashSet实现Set接口,HashSet底层由HashMap实现,为哈希表结构,插入的元素被当做是HashMap的key,根据hashCode值来确定集合中的位置,由于Set集合中并没有角标的概念,所以并没有像List一样提供get()方法,HashSet相当于一个阉割版的HashMap。当获取HashSet中某个元素时,只能通过遍历集合的方式进行equals()比较来实现。添加元素时,底层HashSet调用了HashMap的put(K key, V value)方法,当有元素插入的时候在向HashMap中添加元素时,先判断key的hashCode值是否相同,如果相同,则调用equals()、==进行判断,若相同则覆盖原有元素;如果不同,则直接向Map中添加元素。

原文链接:https://blog.csdn.net/ChouChou719/article/details/126048677

它继承于AbstractSet,实现了Set, Cloneable, Serializable接口。

  • HashSet继承AbstractSet类,获得了Set接口大部分的实现,减少了实现此接口所需的工作,实际上是又继承了AbstractCollection类;
  • HashSet实现了Set接口,获取Set接口的方法,可以自定义具体实现,也可以继承AbstractSet类中的实现;
  • HashSet实现Cloneable,得到了clone()方法,可以实现克隆功能;
  • HashSet实现Serializable,表示可以被序列化,通过序列化去传输,典型的应用就是hessian协议。

存储过程(重复依据)

  • 根据hashCode计算保存的位置,如果位置为空,直接保存,若不为空,进行第二步
  • 再执行equals方法,如果equals为true,则认为是重复,否则形成链表

存储过程:

  • 基于HashCode计算元素存放位置
  • 利用31这个质数,减少散列冲突
  • 31提高执行效率 31 * i = (i << 5) - i 转为移位操作
  • 当存入元素的哈希码相同时,会调用equals进行确认,如果结果为true,则拒绝后者存入

新建集合 HashSet hashSet = new HashSet();

添加元素 hashSet.add( );

删除元素 hashSet.remove( );

遍历操作

​ 1. 增强for for( type type : hashSet)

​ 2. 迭代器 Iterator it = hashSet.iterator( );

判断 hashSet.contains( ); hashSet.isEmpty();

原文链接:https://blog.csdn.net/ChouChou719/article/details/126048677

特点:

  • 不允许出现重复因素;
  • 允许插入Null值;
  • 元素无序(添加顺序和遍历顺序不一致);
  • 线程不安全,若2个线程同时操作HashSet,必须通过代码实现同步;

TreeSet(存储结构:红黑树)

此集合的实现和树结构有关。与HashSet集合类似,TreeSet也是基于Map来实现,具体实现TreeMap,其底层结构为红黑树(特殊的二叉查找树);

与HashSet不同的是,TreeSet具有排序功能,分为自然排序(123456)和自定义排序两类,默认是自然排序;在程序中,我们可以按照任意顺序将元素插入到集合中,等到遍历时TreeSet会按照一定顺序输出–倒序或者升序;

原文链接:https://blog.csdn.net/ChouChou719/article/details/126048677

它继承AbstractSet,实现NavigableSet, Cloneable, Serializable接口。

(1)与HashSet同理,TreeSet继承AbstractSet类,获得了Set集合基础实现操作;

(2)TreeSet实现NavigableSet接口,而NavigableSet又扩展了SortedSet接口。这两个接口主要定义了搜索元素的能力,例如给定某个元素,查找该集合中比给定元素大于、小于、等于的元素集合,或者比给定元素大于、小于、等于的元素个数;简单地说,实现NavigableSet接口使得TreeSet具备了元素搜索功能;

(3)TreeSet实现Cloneable接口,意味着它也可以被克隆;

(4)TreeSet实现了Serializable接口,可以被序列化,可以使用hessian协议来传输;

创建集合 TreeSet treeSet = new TreeSet<>()

添加元素 treeSet.add();

删除元素 treeSet.remove();

遍历 1. 增强for 2. 迭代器

判断 treeSet.contains();

Comparator 实现定制比较(比较器)

补充:TreeSet集合的使用

Comparable 可比较的

特点:

  • 基于排列顺序实现元素不重复
  • 实现SortedSet接口,对集合元素自动排序,是一个有序的集合
  • 元素对象的类型必须实现Comparable接口,指定排序规则
  • 通过CompareTo方法确定是否为重复元素
  • 允许插入Null值
  • 线程不安全

原文链接:https://blog.csdn.net/ChouChou719/article/details/126048677

在TreeSet调用add方法时,会调用到底层TreeMap的put方法,在put方法中会调用到compare(key, key)方法,进行key大小的比较;

在比较的时候,会将传入的key进行类型强转,所以当我们自定义的类进行比较的时候,自然就会抛出异常,因为该类并没有实现Comparable接口;因此需要将自定义类实现Comparable接口,再做比较。

Map(映射表)

Map 中的每个元素都使用 key——>value 的形式存储在集合中。
Map 集合:该集合存储键值对, 是 key:value 一对一对往里存, 而且要保证键的唯一性。

Map 接口的常用子类HashMap、LinkedHashMap、TreeMap

HashMap:继承自AbstractMap,底层数据结构是哈希表,允许使用 null 值和 null 键,该集合
是数据不同步的,将 hashtable 替代,jdk1.2.效率高。

LinkedHashMap:是HashMap 的子类,内部使用链表来记录插入的顺序,使得输入的记录顺序和输出的记录顺序是相同的。

LinkedHashMap与HashMap最大的不同处在于,LinkedHashMap输入的记录和输出的记录顺序是相同的!

TreeMap:底层数据结构是二叉树,线程不同步,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用 Iterator 遍历时,得到的记录是排过序的;如需使用排序的映射,建议使用 TreeMap。TreeMap实际使用非常少!

发表回复

您的电子邮箱地址不会被公开。