这些容器的泛型中全部只能使用对象,不能使用基本数据类型。
10.0 Collection Framework
java.util.Collection
- 集合中不能存放基本类型数据,而只能存放对象的引用。
Collection
的API说明文件中存在三个主要的接口List
:Set
Map
:实际上并没有继承Collection
这个接口
Java 5之后,增加了Queue体系集合,代表一种队列集合实现。
-
Collection接口
-
所有单列集合的最顶层的接口,里边定义了所有单列集合共性的方法
-
任意的单列集合都可以使用Collection接口中的方法
-
public boolean add(E e) 把给定的对象添加到当前集合中。 public void clear() 清空集合中所有的元素。 public boolean remove(E e) 把给定的对象在当前集合中册除。 public boolean contains(E e) 判断当前集合中是否包合给定的对象。 public boolean isEmpty() 判断当前集合是否为空。 public int size() 返回集合中元素的个数。 public Object[] toArray() 把集合中的元素,存储到数组中。
-
-
List接口
- 有序的集合(存储和取出顺序相同)
- 允许存储重复的元素
- 有索引,可以使用普通的for循环遍历
-
Set接口
- 不允许存储重复元素
- 没有索引,不能使用普通for循环遍历
- 无序
-
Queue接口
- 代表一种队列集合实现
10.1 List
接口:java.util.List<>
。
实现:
-
java.util.ArrayList<>
:变长数组List<Interger> = new ArrayList<>();
-
java.util.LinkedList<>
:双链表List<Interger> = new LinkedList<>();
函数:
add()
:在末尾添加一个元素clear()
:清空size()
:返回长度isEmpty()
:是否为空get(i)
:获取第i个元素set(i, val)
:将第i个元素设置为val
10.2 栈
栈是实现,是类,不是接口。
类:java.util.Stack<>
函数:
push()
:压入元素pop()
:弹出栈顶元素,并返回栈顶元素peek()
:返回栈顶元素size()
:返回长度empty()
:栈是否为空clear()
:清空
10.3 队列
接口:java.util.Queue<>
实现:
-
java.util.LinkedList<>
:双链表Queue<Integer> q = new LinkedList<>();
-
java.util.PriorityQueue<>
:优先队列- 默认是小根堆,大根堆写法:
Queue<Integer> q = new PriorityQueue<>(Collections.reverseOrder())
- 默认是小根堆,大根堆写法:
函数:
add()
:在队尾添加元素remove()
:删除并返回队头isEmpty()
:是否为空size()
:返回长度peek()
:返回队头clear()
:清空
10.4 Set
接口:java.util.Set<K>
实现:
-
java.util.HashSet<K>
:哈希表-
Set<Integer> set = new HashSet<>();
-
for(int x : set){ //遍历一个set,不一定有序 }
-
哈希表的插入、删除、查询、修改都是
O(1)
的
-
-
java.util.TreeSet<K>
:平衡树Set<Integer> set = new TreeSet<>();
- 动态维护一个有序序列——想到二分
- 效率更低一些,插入、删除、修改、查询都是
O(logn)
的
函数:
add()
:添加元素contains()
:是否包含某个元素remove()
:删除元素size()
:返回元素数isEmpty()
:是否为空clear()
:清空
java.util.TreeSet
多的函数:
- 支持二分查找操作
- 要使用下列,不能用
Set<>
接口,必须得TreeSet<Integer> set = new TreeSet<>();
ceiling(key)
:返回大于等于key的最小元素,不存在则返回nullfloor(key)
:返回小于等于key的最大元素,不存在则返回null
10.5 Map
接口:java.util.Map<K, V>
实现:
-
java.util.HashMap<K, V>
:哈希表-
增、删、改、查都是
O(1)
,但是是无序的; -
Map<String, Integer> map = new HashMap<>();
-
//遍历 for(Map.Entry<String, Integer> entry : map.entrySet()){ System.out.printf("%s %d\n", entry.getkey(), entry.getValue()); }
-
-
java.util.TreeMap<K, V>
:平衡树- 动态维护一个有序序列,但时间复杂度
O(logn)
Map<String, Integer> map = new TreeMap<>();
- 有序是按
K
来判断的,比如String
的字典序。
- 动态维护一个有序序列,但时间复杂度
函数:
put(key, value)
:添加关键字和其对应的值get(key)
:返回关键字对应的值containsKey(key)
:是否包含关键字remove(key)
:删除关键字size()
:返回元素数isEmpty()
:是否为空clear()
:清空entrySet()
:获取Map中的所有对象的集合Map.Entry<K, V>
:Map中的对象类型getKey()
:获取关键字getValue()
:获取值
java.util.TreeMap<K, V>
多的函数:
- 同样支持二分
- 要使用下列,不能用
Map<>
接口,必须得TreeMap<String, Integer> map= new TreeMap<>();
ceilingEntry(key)
:返回大于等于key的最小元素,不存在则返回nullfloorEntry(key)
:返回小于等于key的最大元素,不存在则返回null