一、集合
1、集合的体系结构概念整体结构:
Collection :单例集合的根接口
1. List(有序集合,允许相同元素和null)如果是实现了List接口的集合类,则具备的特点:有序,可
重复。
(1)LinkedList(非同步,允许相同元素和null,遍历效率低插入和删除效率高)
LinkedList 底层是使用了链表数据结构实现的, 特点: 查询速度慢,增删快。
(2)ArrayList(非同步,允许相同元素和null,实现了动态大小的数组,遍历效率高,用的多)
ArrayList 底层是维护了一个Object数组实现的。 特点: 查询速度快,增删慢。
(3)Vector(同步,允许相同元素和null,效率低)
Vector(了解即可) 底层也是维护了一个Object的数组实现的,实现与ArrayList是一样的,
但是Vector是线程安全的,操作效率低。
(3.1)Stack(继承自Vector,实现一个后进先出的堆栈)
2. Set(无序集合,不允许相同元素,最多有一个null元素) 如果是实现了Set接口的集合类,具
备的特点: 无序,不可重复。
(1)HashSet(无序集合,不允许相同元素,最多有一个null元素)
底层是使用了哈希表来支持的,特点: 存取速度快。
(2)TreeSet 如果元素具备自然顺序 的特性,那么就按照元素自然顺序的特性进行排序存储。
3. Map(没有实现collection接口,key不能重复,value可以重复,一个key映射一个value)
(1)Hashtable(实现Map接口,同步,不允许null作为key和value,用自定义的类当作key的话要
复写hashCode和eques方法)
(2)HashMap(实现Map接口,非同步,允许null作为key和value,用的多)
(3)WeakHashMap(实现Map接口)
2、各分支概念
2.1 Collection接口Collection是最基本的集合接口,一个Collection代表一组Object,即Collection的元素(Elements)。一些Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接继承自Collection的类,Java SDK提供的类都是继承自Collection的“子接口”如List和Set。
所有实现Collection接口的类都必须提供两个标准的构造函数:无参数的构造函数用于创建一个空的Collection,有一个Collection参数的构造函数用于创建一个新的Collection,这个新的Collection与传入的Collection有相同的元素。后一个构造函数允许用户复制一个Collection。
如何遍历Collection中的每一个元素?不论Collection的实际类型如何,它都支持一个iterator()的方法,该方法返回一个迭代子,使用该迭代子即可逐一访问Collection中每一个元素。典型的用法如下:
Iterator it = collection.iterator(); // 获得一个迭代子
while(it.hasNext()) {
Object obj = it.next(); // 得到下一个元素
}
由Collection接口派生的两个接口是List和Set。
2.2 List接口
List是有序的Collection,使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引(元素在List中的位置,类似于数组下标)来访问List中的元素,这类似于Java的数组。
和下面要提到的Set不同,List允许有相同的元素。
除了具有Collection接口必备的iterator()方法外,List还提供一个listIterator()方法,返回一个ListIterator接口,和标准的Iterator接口相比,ListIterator多了一些add()之类的方法,允许添加,删除,设定元素,还能向前或向后遍历。
实现List接口的常用类有LinkedList,ArrayList,Vector和Stack。
(1)LinkedList类
LinkedList实现了List接口,允许null元素。LinkenList底层采用了双向链表来存储数据,每个节点都存储着上一个节点和下一个节点的地址以及本节点的数据。此外LinkedList提供额外的get,remove,insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈(stack),队列(queue)或双向队列(deque)。
注意:LinkedList没有同步方法。如果多个线程同时访问一个List,则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List:
List list = Collections.synchronizedList(new LinkedList(...));
(2)ArrayList类ArrayList实现了可变大小的数组。它允许所有元素,包括null。ArrayList底层采用动态数组的存储方式,便利效率非常高,ArrayList是线程不安全的。
size,isEmpty,get,set方法运行时间为常数。但是add方法开销为分摊的常数,添加n个元素需要O(n)的时间。其他的方法运行时间为线性。
每个ArrayList实例都有一个容量(Capacity),即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加,但是增长算法并没有定义。当需要插入大量元素时,在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。
(3)ArrayList和LindedList的区别:1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。
2.对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。
3.对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据。
(4)Vector类Vector非常类似ArrayList,但是Vector是同步的。由Vector创建的Iterator,虽然和ArrayList创建的Iterator是同一接口,但是,因为Vector是同步的,当一个Iterator被创建而且正在被使用,另一个线程改变了Vector的状态(例如,添加或删除了一些元素),这时调用Iterator的方法时将抛出ConcurrentModificationException,因此必须捕获该异常。
(5)Stack 类
Stack继承自Vector,实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop方法,还有peek方法得到栈顶的元素,empty方法测试堆栈是否为空,search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。
2.3 Set接口
Set是一种无序的并且不包含重复的元素的Collection,即任意的两个元素e1和e2都有e1.equals(e2)=false,Set最多有一个null元素。
很明显,Set的构造函数有一个约束条件,传入的Collection参数不能包含重复的元素。
(1)HashSet 类
是哈希表实现的,HashSet中的数据是无序的,可以放入null,但只能放入一个null,两者中的值都不能重复,因为HashSet的底层实现是HashMap,但是HashSet只使用了HashMap的key来存取数据所以HashSet存的数据不能重复。
HashSet要求放入的对象必须实现HashCode()方法,放入的对象,是以hashcode码作为标识的,而具有相同内容的 String对象,hashcode是一样,所以放入的内容不能重复。但是同一个类的对象可以放入不同的实例 。
(2)HashSet有以下特点
1 不能保证元素的排列顺序,顺序有可能发生变化
2 不是同步的
3 集合元素可以是null,但只能放入一个null
当向HashSet集合中存入一个元素时,HashSet会调用该对象的hashCode()方法来得到该对象的
hashCode值,然后根据 hashCode值来决定该对象在HashSet中存储位置。
简单的说,HashSet集合判断两个元素相等的标准是两个对象通过equals方法比较相等,并且两个
对象的hashCode()方法返回值相等
注意,如果要把一个对象放入HashSet中,重写该对象对应类的equals方法,也应该重写其
hashCode()方法。其规则是如果两个对 象通过equals方法比较返回true时,其hashCode也应该相
同。另外,对象中用作equals比较标准的属性,都应该用来计算 hashCode的值。
(3)TreeSet类
1. TreeSet是SortedSet接口的唯一实现类,TreeSet可以确保集合元素处于排序状态。TreeSet支持
两种排序方式,自然排序 和定制排序,其中自然排序为默认的排序方式。向TreeSet中加入的应
该是同一个类的对象。
2. TreeSet判断两个对象不相等的方式是两个对象通过equals方法返回false,或者通过CompareTo方
法比较没有返回0
3. 自然排序
自然排序使用要排序元素的CompareTo(Object obj)方法来比较元素之间大小关系,然后将元素
按照升序排列。
4. Java提供了一个Comparable接口,该接口里定义了一个compareTo(Object obj)方法,该方法返回
一个整数值,实现了该接口的对象就可以比较大小。
obj1.compareTo(obj2)方法如果返回0,则说明被比较的两个对象相等,如果返回一个正数,则表
明obj1大于obj2,如果是 负数,则表明obj1小于obj2。
如果我们将两个对象的equals方法总是返回true,则这两个对象的compareTo方法返回应该返回0
定制排序
自然排序是根据集合元素的大小,以升序排列,如果要定制排序,应该使用Comparator接口,实
现 int compare(T o1,T o2)方法。
(4)二者区别:
1 TreeSet 是二差树实现的,Treeset中的数据是自动排好序的,不允许放入null值。
2 HashSet 是哈希表实现的,HashSet中的数据是无序的,可以放入null,但只能放入一个null,
两者中的值都不能重复,就如数据库中唯一约束。
3 HashSet要求放入的对象必须实现HashCode()方法,放入的对象,是以hashcode码作为标识的,
而具有相同内容的 String对象,hashcode是一样,所以放入的内容不能重复。但是同一个类的对
象可以放入不同的实例 。
2.4 Map接口
Map没有继承Collection接口,Map提供key到value的映射。一个Map中不能包含相同的key,每个key只能映射一个value。Map接口提供3种集合的视图,Map的内容可以被当作一组key集合,一组value集合,或者一组key-value映射。
(1) Hashtable类
Hashtable继承Map接口,实现一个key-value映射的哈希表。任何非空(non-null)的对象都可作为key或者value。
添加数据使用put(key, value),取出数据使用get(key),这两个基本操作的时间开销为常数。
使用Hashtable的简单示例如下,将1,2,3放到Hashtable中,他们的key分别是”one”,”two”,”three”:
Hashtable numbers = new Hashtable();
numbers.put(“one”, new Integer(1));
numbers.put(“two”, new Integer(2));
numbers.put(“three”, new Integer(3));
要取出一个数,比如2,用相应的key:
Integer n = (Integer)numbers.get(“two”);
System.out.println(“two = ” + n);
由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置,因此任何作为key的对象都必须实现hashCode和equals方法。hashCode和equals方法继承自根类Object,如果你用自定义的类当作key的话,要相当小心,按照散列函数的定义,如果两个对象相同,即obj1.equals(obj2)=true,则它们的hashCode必须相同,但如果两个对象不同,则它们的hashCode不一定不同,如果两个不同对象的hashCode相同,这种现象称为冲突,冲突会导致操作哈希表的时间开销增大,所以尽量定义好的hashCode()方法,能加快哈希表的操作。
如果相同的对象有不同的hashCode,对哈希表的操作会出现意想不到的结果(期待的get方法返回null),要避免这种问题,只需要牢记一条:要同时复写equals方法和hashCode方法,而不要只写其中一个。
Hashtable是同步的。
(2) HashMap类
HashMap和Hashtable类似,不同之处在于HashMap是非同步的,并且允许null,即null value和null key,但是将HashMap视为Collection时(values()方法可返回Collection)。
WeakHashMap类
WeakHashMap是一种改进的HashMap,它对key实行“弱引用”,如果一个key不再被外部所引用,那么该key可以被GC回收。
3、集合的功能特点分析
1:集合:
(1) Collection(单列集合)
List(有序,可重复)
ArrayList
底层数据结构是数组,查询快,增删慢
线程不安全,效率高
Vector
底层数据结构是数组,查询快,增删慢
线程安全,效率低
LinkedList
底层数据结构是链表,查询慢,增删快
线程不安全,效率高
Set(无序,唯一)
HashSet
底层数据结构是哈希表。
哈希表依赖两个方法:hashCode()和equals()
执行顺序:
首先判断hashCode()值是否相同
是:继续执行equals(),看其返回值
是true:说明元素重复,不添加
是false:就直接添加到集合
否:就直接添加到集合
最终:
自动生成hashCode()和equals()即可
LinkedHashSet
底层数据结构由链表和哈希表组成。
由链表保证元素有序。
由哈希表保证元素唯一。
TreeSet
底层数据结构是红黑树。(是一种自平衡的二叉树)
如何保证元素唯一性呢?
根据比较的返回值是否是0来决定
如何保证元素的排序呢?
两种方式
自然排序(元素具备比较性)
让元素所属的类实现Comparable接口
比较器排序(集合具备比较性)
让集合接收一个Comparator的实现类对象
(2)Map(双列集合)
A:Map集合的数据结构仅仅针对键有效,与值无关。
B:存储的是键值对形式的元素,键唯一,值可重复。
HashMap
底层数据结构是哈希表。线程不安全,效率高
哈希表依赖两个方法:hashCode()和equals()
执行顺序:
首先判断hashCode()值是否相同
是:继续执行equals(),看其返回值
是true:说明元素重复,不添加
是false:就直接添加到集合
否:就直接添加到集合
最终:
自动生成hashCode()和equals()即可
LinkedHashMap
底层数据结构由链表和哈希表组成。
由链表保证元素有序。
由哈希表保证元素唯一。
Hashtable
底层数据结构是哈希表。线程安全,效率低
哈希表依赖两个方法:hashCode()和equals()
执行顺序:
首先判断hashCode()值是否相同
是:继续执行equals(),看其返回值
是true:说明元素重复,不添加
是false:就直接添加到集合
否:就直接添加到集合
最终:
自动生成hashCode()和equals()即可
TreeMap
底层数据结构是红黑树。(是一种自平衡的二叉树)
如何保证元素唯一性呢?
根据比较的返回值是否是0来决定
如何保证元素的排序呢?
两种方式
自然排序(元素具备比较性)
让元素所属的类实现Comparable接口
比较器排序(集合具备比较性)
让集合接收一个Comparator的实现类对象
2:到底使用那种集合:
看需求。
是否是键值对象形式:
是:Map
键是否需要排序:
是:TreeMap
否:HashMap
不知道,就使用HashMap。
否:Collection
元素是否唯一:
是:Set
元素是否需要排序:
是:TreeSet
否:HashSet
不知道,就使用HashSet
否:List
要安全吗:
是:Vector(其实我们也不用它,后面我们讲解了多线程以后,我在给你回顾用谁)
否:ArrayList或者LinkedList
增删多:LinkedList
查询多:ArrayList
不知道,就使用ArrayList
不知道,就使用ArrayList
3:集合的常见方法及遍历方式
Collection:
add()
remove()
contains()
iterator()
size()
遍历方式:
增强for
迭代器
|--List
get()
遍历:
普通for
|--Set
Map:
put()
remove()
containskey(),containsValue()
keySet()
get()
value()
entrySet()
size()
遍历方式:
根据键找值
根据键值对对象分别找键和值。
二、集合补充小结
1.如果涉及到堆栈,队列等操作,应该考虑用List,对于需要快速插入,删除元素,应该使用LinkedList,如果需要快速随机访问元素,应该使用ArrayList。
2.如果程序在单线程环境中,或者访问仅仅在一个线程中进行,考虑非同步的类,其效率较高,如果多个线程可能同时操作一个类,应该使用同步的类。
3.要特别注意对哈希表的操作,作为key的对象要正确复写equals和hashCode方法。
4.尽量返回接口而非实际的类型,如返回List而非ArrayList,这样如果以后需要将ArrayList换成LinkedList时,客户端代码不用改变。这就是针对抽象编程。
5.集合是储存对象的,长度可变,可以封装不同的对象。
6.迭代器: 其实就是取出元素的方式(只能判断,取出,移除,无法增加)
就是把取出方式定义在集合内部,这样取出方式就可以直接访问集合内部的元素,那么取出方式就被定义成了内部类.
二每一个容器的数据结构不同,所以取出的动作细节也不一样.但是都有共性内容判断和取出,那么可以将共性提取,这些内部类都符合一个规则Iterator。
7.HashTable和HashMap的区别
HashTable:线程安全,效率低,不允许null建和null值。
HashMap:线程不安全,效率高,允许null建和null值。
8.Collection和Collections的区别?
Collection:是单列集合的顶层接口,有子接口List和Set。
Collections:是针对集合操作的工具类,有对集合进行排序和二分查找的方法。
三、集合和数组的区别
1、数组
数组是java语言内置的数据类型,他是一个线性的序列,所有可以快速访问其他的元素,数组和其他语言不同,当你创建了一个数组时,他的容量是不变的,而且在生命周期也是不能改变的,还有JAVA数组会做边界检查,如果发现有越界现象,会报RuntimeException异常错误,当然检查边界会以效率为代价。
2、集合
JAVA提供的集合,list,map,set,他们处理对象的时候就好像这些对象没有自己的类型一样,而是直接归根于Object,这样只需要创建一个集合,把对象放进去,取出时转换成自己的类型就行了。
3、数组和集合的区别
(1)数组声明了它容纳的元素的类型,而集合不声明。
(2)数组是静态的,一个数组实例具有固定的大小,一旦创建了就无法改变容量了。而集合是可以动态扩展容量,可以根据需要动态改变大小,集合提供更多的成员方法,能满足更多的需求。
(3)数组的存放的类型只能是一种(基本类型/引用类型),集合存放的类型可以不是一种(不加泛型时添加的类型是Object)。
(4)数组是java语言中内置的数据类型,是线性排列的,执行效率或者类型检查都是最快的。
4、补充
(1) toArray()方法:是遍历用的(把集合转变为数组)
public class ToArray {
public static void main(String[] args) {
Collection c=new ArrayList();
c.add("hello");
c.add("world");
c.add("java");
Object[] obj=c.toArray();
for(int x=0;x < obj.length;x++){
System.out.println(obj[x]);
}
}
}
(2)List()方法,把数组转变为集合
//定义一个数组
//String[] s={"hello","world","java"};
//List<String> list=Arrays.asList(s);
//直接引用
List<String> list=Arrays.asList("hello","world");
for(String s1:list){
System.out.println(s1);
}
注意:虽然他可以把数组转变成集合,但是本质是数组,所以他的长度不能改变,不能增删
(3)数组长度是length方法,字符串的长度是length(),集合求长度的方法是size。
list集合特有的遍历方法:就是size和get()的结合。
本篇博文是小白我在大神的肩膀上,吸收整理出来的。衷心感谢大神们的无私奉献、厚薄积发的精神,这种品质给我们小白在技术上的成长带来了很大的帮助。
参考:
https://blog.csdn.net/xnf1991/article/details/53005368
https://blog.csdn.net/spanklebobo/article/details/52126939