Java集合框架这个东西应该是类似于C++的STL标准库, 便于使用一些常见的数据结构:D
目录
一.Java集合框架
1. 将接口和实现分离
2. Collection接口
3. 迭代器
4. 泛型使用方法
5. 集合框架中的接口
二. 具体的集合
1. 链表LinkedList(List)
2. 数组列表ArrayList(List)
3. 散列集HashSet(Set)
4. 树集TreeSet(SortedSet)
5. 队列与双端队列Queue&Deque
6. 优先级队列PriorityQueue
三. 映射(Map)
1. 基本映射操作
2. 更新映射值
3. 映射视图
4. 弱散列映射
5. 链接散列集与映射
6. 枚举集和映射
7. 标识散列映射
四. 视图与包装器
一.Java集合框架
CoreJava中提到C++的STL提供了一种泛型算法, 现在想来的确是这样的, 还是挺好用的, 嘤嘤嘤;
本文中有一些地方出现了容器, 就是Java中集合的概念, 是我自己习惯说容器了, 呜呜;
1.将接口和实现分离
不要直接在一个类里面实现一个集合, 可以用一个支持接口的类来实现集合, 比如要实现一个队列, 既可以使用链表LinkedLIstQueue, 也可以使用循环列表CircularArrayQueue, 只需要implements queue就可以用不同的类实现一个队列接口了, 在定义一个队列的时候就可以先这样写一个接口:
然后这样去定义队列了:
Queue<People> humanity = new CircularArrayQueue<>(100);
1
表示定义一个长度为100的队列, 用循环列表来实现;
2.Collection接口
在Java中集合类的基本接口是Collection, 它提供了2个基本方法:
一个是add, 表示向集合中加入一个元素, 如果加入成功了就返回true, 否则返回false;
一个是Iterator迭代器, 用于遍历集合中的元素;
3.迭代器
迭代器就是Iterator;
可以用Iterator的next方法来遍历容器, 如果没有next就会返回一个NoSuchElementException错误, 所以调用next之前要用hasNext检查;
恕在下直言这笨比方法希望我不要多用, 尽量用for each来直接遍历容器把;
for-each循环可以和任何实现了iterable接口的对象一起工作;
在有了lambda表达式之后可以用forEachRemaining方法配合lambda表达式一起对容器内的元素做相同的操作;
java中的iterator和C++中有一个巨大的不同:
所以在调用it.remove的时候, 是删除了上一个访问过的元素, 所以如果想要删除下一个迭代器的元素, 要先用it.next访问, 然后再remove掉;
如果在使用it.remove之前没有使用it.next, 会报错IllegalStateException
这样测试一下iterator:
import java.util.*;
class test12 {
public static void main(String[] args) {
Collection<String> a = new Vector<String>();
a.add("GodV");
a.add("We1less");
for(Iterator<String>it = a.iterator();it.hasNext();){
System.out.println((String)it.next());
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
要记得最好不要太早定义iterator, 可以等到用的时候再定义, 因为一旦执行Iterator<String>it = a.iterator()就会自动把迭代器初始化到容器的第一个位置;
4. 泛型使用方法
在Collection接口中, Java提供了很多有用的方法, 列举一些如下:
在我的测试中遇到了一些问题, 先上我写的MeVector测试代码:
import java.util.*;
import java.lang.reflect.*;
class test12 {
public static void main(String[] args) {
MyVector<String> me = new MyVector<String>();
me.add("GodV");
me.add("We1less");
System.out.println(me.size());
System.out.println(me.contains("GodV"));
for(Iterator<String> it =me.iterator();it.hasNext();){
System.out.println(it.next());
}
AbstractCollection<String> s = new Vector<>();
Class<?> cl = s.getClass();
Method[] Methods = cl.getDeclaredMethods();
for(Method i : Methods){
System.out.println(i);
}
}
}
class MyVector<E> extends AbstractCollection<E>{
private Vector<E> vec;
public MyVector(){
vec = new Vector<E>();
}
@Override
public int size(){
return vec.size();
}
@Override
public Iterator<E> iterator(){
Iterator<E> it = vec.iterator();
return it;
}
public boolean add(E e){
return vec.add(e);
}
}
//output:
//2
//true
//GodV
//We1less
//public synchronized boolean java.util.Vector.add(java.lang.Object)
//private void java.util.Vector.add(java.lang.Object,java.lang.Object[],int)
//public void java.util.Vector.add(int,java.lang.Object)
//public synchronized java.lang.Object java.util.Vector.remove(int)
//public boolean java.util.Vector.remove(java.lang.Object)
//......省略一些
//void java.util.Vector.checkInvariants()
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
首先, 如果不在MyVector中重写add方法, 就会出现unsupportedoperationexception异常, 仔细寻找错误后, 我用反射找到了AbstractCollection类中的方法, 发现add方法的返回值是void, 去查询文档中的add方法是这样的:
public void add(int index, E element) {
throw new UnsupportedOperationException();
}
1
2
3
怪不得会出现这样的异常, 所以我重写了add方法;
但是其他的一些方法, 比如contains是可以正常使用的;
5. 集合框架中的接口
上一张图表示框架继承层次:
二. 具体的集合
所有的类都实现了Collection接口, 而以map结尾的类实现了Map接口;
1.链表LinkedList
链表的实现细节就不多说了, 谈谈Java中具体的链表的特点;
Collection中的iterator有next,hasNext和remove等一些方法, 但是没有add方法, previous这些方法;
因为Collection.iterator很通用, 所有对于某些无序集合比如set这些, 所以不能有add和previous这些方法, 因为不是按照下表索引序来的, 是无序的, 所以没有这些方法;
但是List是有序的, 所以现在有了ListIterator这个新的迭代器, 仅用于List, 有add, previous, hasPrevious方法, 就可以按顺序访问, 增加链表中的值, 还有get方法和set方法, 可以获取和修改指定迭代器位置的值;
使用add方法, 新加入的方法会被依次添加到迭代器当前位置之前;
要注意使用previous方法的时候, remove方法的效果和之前的有所不同, remove会删除之前操作过的那个变量, 而不是删除光标前面的那个变量;
在使用多个迭代器的时候要特别注意, 如果两个迭代器同时操作了当前的链表, 那么另一个迭代器的顺序就会发生改变, 容易出现问题, 所以CoreJava中建议, 同时最多使用一个迭代器做既读又写的操作, 其余的迭代器都只做读的工作;
Collection也有toString方法, 返回一个类似于[A, B, C, …]这样的字符串;
使用get方法, 以随机index的方法获取某个元素是效率极低的, 在Java中已经对get做了优化, 如果索引大于 size()/2 就从列表尾端开始搜索元素;
比较高效的方法是nextIndex和previousIndex方法来获取previous和next的元素的索引;
由于链表的随机访问元素效率比较低, 但是增删元素效率比较高;
所以如果经常需要随机访问元素最好就使用数组或者ArrayList;
随手测试一下:
import java.util.*;
class test13 {
public static void main(String[] args) {
List<String> me = new LinkedList<String>();
me.add("GodV");
me.add("We1less");
me.add("weishen");
me.add("mifengaaa");
ListIterator<String> aIterator = me.listIterator();
while(aIterator.hasNext()){
System.out.println((String)aIterator.next());
}
System.out.println();
aIterator.previous();aIterator.previous();
aIterator.remove();
aIterator = me.listIterator();
while(aIterator.hasNext()){
System.out.println((String)aIterator.next());
}
}
}
//output:
//GodV
//We1less
//weishen
//mifengaaa
//
//GodV
//We1less
//mifengaaa
//可见,remove会删除上一个遍历过的元素, 而不是像光标一样删除前面一个元素
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
上一些总结的常用的List和LinkedList的方法:
2.数组列表ArrayList
ArrayList应该是一个和Vector差不多的东西, 主要特点是可以动态改变大小, 区别在于:
Vector支持线程的同步, 同一时刻只有一个线程能够写Vector, 避免多线程同时写而引起的不一致性, 但实现同步需要很高的花费,所以它比ArrayList慢;
这个东西的详细使用前面写过了, 然后前面关于List的一些方法他也能用;
在这个博客里:Java基础 自学讲义 2. OOP部分特性 二.C.泛型数组列表
3.散列集HashSet
散列集, 散列表, 哈希表啥的都是这个东西;
书上讲的有点皮, 有点没看懂, 用一个比较好的散列函数是比较重要的;
这里贴一篇我以前C++里学散列表的博客, 原理都是一样的;
散列表随手测试一下:
import java.util.*;
class test14 {
public static void main(String[] args) {
Set<String> me =new HashSet<>();
me.add("ZedKing");
me.add("GodV");
me.add("Godv");
me.add("mifengaaa");
me.add("mifengaaa");
System.out.println(me.size());
for(Iterator<String>it=me.iterator();it.hasNext();){
System.out.println(it.next());
}
}
}
//output
//4
//GodV
//Godv
//ZedKing
//mifengaaa
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Set是对大小写敏感的;
HashSet的toArray方法返回的是一个Object[]对象, 所以不能用一个ArrayList去接收;
因为在HashSet建立之前, 如果能对他的大概容量和容量使用率能有一个比较准确的预估, 可以大大提升这个哈希表的效率, 所以构造方法提供了以下几种:
最后一种只有在散列表的填充百分比大于loadFactor的百分比时, 散列表才会进行再散列(rehashed);
4. 树集TreeSet
TreeSet是由红黑树实现的(Red-Black Tree), 可以实现有序集合SortedSet
相比于普通Set就是可以实现有一定的顺序;
先上一个我的TreeSet测试代码:
import java.util.*;
import java.lang.reflect.*;
class test15 {
public static void main(String[] args) {
SortedSet<item> aSet = new TreeSet<item>();
aSet.add(new item("GodV",13));
aSet.add(new item("mifengaaa",30));
aSet.add(new item("Aluka",123));
aSet.add(new item("Cpt",33));
aSet.add(new item("GodV",42));
System.out.println(aSet);
NavigableSet<item> bSet = new TreeSet<>(
Comparator.comparingInt(p->p.getNumber())
);
// 像下面这样写也可以:
// NavigableSet<item> bSet = new TreeSet<>(
// Comparator.comparingInt(item::getNumber)
// );
bSet.addAll(aSet);
System.out.println(bSet);
}
}
class item implements Comparable<item>{
private int number;
private String description;
public item(){}
public item(String description, int number){
this.number = number;
this.description = description;
}
public int getNumber(){
return this.number;
}
public String getDescription(){
return this.description;
}
@Override
public int compareTo(item u){
return this.description.compareTo(u.getDescription())==0?Integer.compare(this.number, u.getNumber()):this.description.compareTo(u.getDescription());
}
@Override
public String toString(){
return this.description+"-"+this.number;
}
}
//output
//[Aluka-123, Cpt-33, GodV-13, GodV-42, mifengaaa-30]
//[GodV-13, mifengaaa-30, Cpt-33, GodV-42, Aluka-123]
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
上面的代码中, 第一部分是我按照item类implement的Comparable接口, 重写了compareTo方法, 按照description排序的, 次关键词number排序, 所以在TreeSet中是直接按照Comparable接口实现的compareTo的方法排序的;
第二部分我查看了TreeSet的Constructor
TreeSet<item> a = new TreeSet<>();
Class<?> cl = a.getClass();
Constructor<?>[] methods = cl.getDeclaredConstructors();
for(Constructor<?> i : methods) System.out.println(i);
1
2
3
4
发现有下面几种构造器:
public java.util.TreeSet(java.util.SortedSet)
public java.util.TreeSet(java.util.Collection)
public java.util.TreeSet(java.util.Comparator)
public java.util.TreeSet()
java.util.TreeSet(java.util.NavigableMap)
1
2
3
4
5
所以也可以使用lambda表达式或者使用method reference传入一个Comparator来实现排序的指定, 这样就不会默认去调用自己的compareTo方法了;
也可以传入一个SortedSet或者Collection来Copy所有的内容;
最后上一些树集常用的方法:
也可以在这里看到:
极客学院TreeSet
还有最后一个问题, 上面我们使用到了三个接口, TreeSet, SortedSet和 NavigableSet; 这三个接口主要是支持的方法有些不一样, 需要的时候酌情选用把…
5. 队列与双端队列
ArrayDeque和LinkedList都实现了deque;
要注意的是接口也对deque提供了push pop方法, 但是我觉得最好不要用, 因为容易分不清前面和后面, 最好用addFirst addLast offerFirst offerLast和removeFirst removeLast pollFirst pollLast, 比较好区分;
给一些常用的方法:
6. 优先级队列
Java中的优先队列是用堆(heap)实现的(最小堆, 小顶堆), 当然也可以用二叉搜索树实现;
堆和二叉搜索树的区别是:
堆一定是完全二叉树, 二叉搜索树不一定是完全二叉树
名字叫PriorityQueue
有一些方法, 比如poll offer peek这种 还有isEmpty这些, 用到自然就知道了…
还有一个好像更牛逼的东西叫PriorityBlockingQueue优先级阻塞队列, 可用于并发?
三.映射
Java里的映射就是map, 提供一种 键-值 的数据结构
1.基本映射操作
Map主要有两种, HashMap和TreeMap, 一个无序一个有序的, HashMap稍微快一点;
有put, get, remove, forEach这些常见的方法, 要注意的是遍历Map的方法, 我总结了4种, CoreJava中给出的是第一种使用forEach+lambda表达式, 我认为这种方法应该是最好的;
遍历Map:
第一种可以使用Map的forEach方法加上Java8的lambda表达式:
aMap.forEach( (k,v)->{System.out.println(k+" "+v);} );
1
第二种可以使用Map.Entry来遍历Map的条目:
for(Map.Entry<String, String> it : aMap.entrySet()){
System.out.println(it.getKey()+"="+it.getValue());
System.out.println(it);
}
1
2
3
4
第三种可以使用for结合Map的keySet和values方法来遍历:
for(String a : aMap.keySet()){
System.out.println(a);
}
for(String a : aMap.values()){
System.out.println(a);
}
1
2
3
4
5
6
第四种是使用迭代器, 这种是看起来比较熟悉而且效率挺高的, 但是要注意, 不能在使用for循环访问迭代器的同时使用remove操作, javadoc说这样会发生不可预期的错误, 如果希望迭代的同时删除元素, 可以使用while来遍历:
for(Iterator<Map.Entry<String, String>> it = aMap.entrySet().iterator();it.hasNext();){
Map.Entry<String, String> itt = it.next();
System.out.println(itt.getKey()+"="+itt.getValue());
System.out.println(itt);
}
1
2
3
4
5
当然还有第五种是在遍历keySet的时候调用get方法获取对应的值, 但是这种方法太捞了, 效率很低, 不提了, 就上一段测试代码吧:
for(String i : aMap.keySet()){
System.out.println(i+"="+aMap.get(i));
}
1
2
3
测试代码如下:
import java.util.*;
class test16 {
public static void main(String[] args) {
Map<String,String> aMap = new TreeMap<>();
aMap.put("Aluka", "AluWife");
aMap.put("GodV", "mifengaaa");
aMap.put("zz", "lym");
aMap.forEach( (k,v)->{System.out.println(k+" "+v);} );
System.out.println();
aMap.remove("zz");
for(Map.Entry<String, String> it : aMap.entrySet()){
System.out.println(it.getKey()+"="+it.getValue());
System.out.println(it);
}
System.out.println();
for(String a : aMap.keySet()){
System.out.println(a);
}
for(String a : aMap.values()){
System.out.println(a);
}
System.out.println();
for(Iterator<Map.Entry<String, String>> it = aMap.entrySet().iterator();it.hasNext();){
Map.Entry<String, String> itt = it.next();
System.out.println(itt.getKey()+"="+itt.getValue());
System.out.println(itt);
}
}
}
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
输出如下:
Aluka AluWife
GodV mifengaaa
zz lym
Aluka=AluWife
Aluka=AluWife
GodV=mifengaaa
GodV=mifengaaa
Aluka
GodV
AluWife
mifengaaa
Aluka=AluWife
Aluka=AluWife
GodV=mifengaaa
GodV=mifengaaa
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
贴一些map和sortedmap的常用方法:
2.更新映射值
在Map中更新一对键值的方法啊, 比如我要用map来统计一篇文章里每个单词出现的次数, 可以这样写:
直接用put更新, 会自动顶替原来的键值;
Map<String,Integer> aMap = new HashMap<>();
//...输入一个单词
aMap.put(word, aMap.get(word)+1);
1
2
3
但是这样在第一次加入单词的时候使用get方法会获取到一个null, 所以可以用getOrDefault方法:
aMap.put(word, aMap.getOrDefault(word, 0)+1);
1
也可以用一个新的方法, 叫putIfAbsent方法:
aMap.putIfAbsent(word, 0);
aMap.put(word, aMap.get(word)+1);
1
2
然后CoreJava中最后给了一种最简单的, 是merge方法, 这个方法会在键值不存在的时候把word和1绑定为一对键值存入, 如果键值存在就会调用Integer.sum方法把word的值和1求和存入更新:
aMap.merge(word, 1, Integer::sum);
1
感觉这个merge的真正用法不应该是在这种场合… 可能在其他场合会有妙用把, 还有一些看起来烦的一比的更新键值的方法我就不贴图了0 0
3.映射视图
Map有三个视图, 分别是KeySet, values, entrySet;
KeySet是一个Set, 但不是HashSet或TreeSet;
values是一个实现了Collection的类;
entrySet也是一个Set, 里面存着键值对应条目;
可以这样使用它们(前面遍历的时候已用过了):
4.弱散列映射
WeakHashMap, 垃圾回收器会在认为某个键值不再使用的时候把它删掉;
下面是从别的博客里抄来的一段话, 不太理解, 以后再说吧:
当WeakHashMap某个键不再正常使用时，会被从WeakHashMap自动删除。更精确的说，对于一个给定的键，其映射的存在并不能阻止垃圾回收器对该键的丢弃，这就使该键称为被终止的，被终止，然后被回收，这样，这就可以认为该键值对应该被WeakHashMap删除。
5.链接散列集与映射
LinkedHashMap和LinkedHashSet, 与HashMap, HashSet的区别就是他们会保存自己插入时的顺序;
6. 枚举集和映射
EnumSet和EnumMap是是一个以枚举型Enum对象为键值的元素集;
关于这个部分的枚举集和映射的常用方法在下一小节里面贴;
7.标识散列映射
普通的Hash表都是用Object.hashCode来生成散列值的, IdentityHashMap不是这么做的, 他是用System.identityHashCode, 这个哈希值是根据对象的内存地址生成的, 所以比较IdentityHashMap的时候要用== 不要用equals;
四.视图与包装器
视图(views)的定义:
---------------------
【转载】
作者：Peiwen123
原文：https://blog.csdn.net/qq_3398223 ... 274?utm_source=copy
|
|
收藏
淘帖
踩
奈斯
