黑马程序员技术交流社区

标题: 【上海校区】Java基础 自学讲义 6.Java集合框架 [打印本页]

---

作者: 不二晨    时间: 2018-10-16 09:34
标题: 【上海校区】Java基础 自学讲义 6.Java集合框架
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

---

作者: 不二晨    时间: 2018-10-16 14:10
奈斯

---

作者: 魔都黑马少年梦    时间: 2018-10-25 14:43

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2