记录《疯狂Java讲义精粹》划线内容及理解（第6章-java集合概述）

第六章 java集合概述

6.1 Java集合概述

java集合，是为了解决数组的两个问题而产生

1-存储的元素个数是定长的，所以list存储的元素个数是变长的

2-数组无法存储具有一定映射关系的数据，所以map由键值对构成

        集合中只能存放对象，

        数组中可以存放对象和基本类型的数据

java集合的根接口有两个

                1.collection接口，派生出

                                set无序集合（集合)
                                queue队列
                                list有序集合（列表)

                2.map接口，派生出
                                hashmap(键值对）， 等各种形式的map，

值得注意是hashmap是线程不安全的，因为它允许valus为null

如果把队列queue看成一种特殊的list，那么集合的根接口一共扩展出来三类集合（也称容器)，

set罐子，丢入的数据不可重复，且无序，访问时根据元素本身访问

list罐子，数据可重复，系统能记住元素顺序，访问需通过元素下标访问

map罐子，value可重复，key不能重复，无序，访问通过key来访问

---

为了保存数量不确定的数据，以及保存具有映射关系的数据（也被称为关联数组），Java提供了集合类。

---

Java的集合类主要由两个接口派生而出：Collection和Map

---

我们可以把Java的所有集合分成三大类，其中

Set集合类似于一个罐子，把一个对象添加到Set集合时，Set集合无法记住添加这个元素的顺序，所以Set里的元素不能重复（否则系统无法准确识别这个元素）；

List集合非常像一个数组，它可以记住每次添加元素的顺序，只是List的长度可变。

Map集合也像一个罐子，只是它里面的每项数据都由两个值组成

6.2 Collection和Iterator接口

collection接口提供的操作集合的方法，适用于set.list.queue添加元素add

把集合中所有元素添加到另一集合中addall

清除所有元素clear

判断是否包含某个集合containsall

判断集合为空isempty

返回该集合的迭代器，用于遍历该集合iterator

值得注意该方法返回的是一个iterator对象

删除指定元素remove

与指定集合做差集removeall

做交集retainall

返回集合元素个数size

将该数组转化为数组toarray
 

---

在普通情况下，当我们把一个对象“丢进”集合中后，集合会忘记这个对象的类型——也就是说，系统把所有的集合元素都当成Object类的实例进行处理。从JDK 1.5以后，这种状态得到了改进：可以使用泛型来限制集合里元素的类型，并让集合记住所有集合元素的类型。

6.2.1 使用Iterator接口遍历集合元素

关于iterator该接口的对象必须依附于collection集合而存在，该接口提供了三个方法用于迭代遍历集合

1-判断元素是否被遍历hasnext

2-获取一个元素next

3-删除上次用next获取到的元素remove

在iteraton遍历过程中，不可改变集合元素，否则发生异常，但可以通过非常危险的操作在iterator中改变元素，原理具体细节未知

在iterator执行过程中，传入的是集合元素的值，而不是地址，这意味着无法通过iterator来改变集合元素

6.2.2 使用foreach循环遍历集合元素

foreach于iterator具有相同的两点性质，遍历过程中不可改变，接收的是元素值，

foreach语句更加便捷，只需要for(类型变量名:需要遍历的集合名)就可遍历

6.3 Set集合

set集合不接受相同的元素，set判断的标准是equals方法返回true

6.3.1 HashSet类

set的三大子类之一，hashset，采用hash算法存储元素，所以具有良好的效率，主要使用对象的hashcode方法计算hash值，关于hashset有些特点，

1-不保证元素排列顺序，

2-多线程访问hashset不同步，

3-允许值为null

hashset主要通过equals和hashcode方法来判断元素是否可以加入集合，equals用来判断元素是否相等，hashcode用来计算元素的值(存储位置)

有三种特殊情况，

1-equals和hashcode都返回true可以加入集合

2-equals返回true hashcode返回false，可以加入，将两个相同的元素存在set的不同位置

3-equals返回false hashcode返回true，可以加入，将在set的同一位置用链式存储多个对象，但这样查找是将使效率下降，而hashset最重要的价值就是hash算法的效率

重写hashcode方法的一般规则，

1-把每个要用equals比较的field计算出一个int类型的hashcode值(这个值得计算比较复杂，详情可参见表)

2-把计算出来的每个hashcode乘一个质数再相加，作为hashcode方法的返回值

-------------------------------------------

 

---

HashSet按Hash算法来存储集合中的元素，因此具有很好的存取和查找性能。

6.3.2 LinkedHashSet类

linkedhashset同样使用hashcode方法来确定元素的存储位置，但他使用链表来维护元素插入顺序，所以在插入时他的性能低于hashset，但是在遍历输出是有更好的性能（因为他的元素是有序的，输出也是按照添加时的顺序输出的)

6.3.3 TreeSet类

treeset与linkedhashset差不多，都能保证元素的有序性

但linkedhashset维护的是插入时的顺序，treeset维护的是按照对象值排列的顺序，treeset采用红黑树来存储（考研考点)，

有两种排序方式，默认为自然排序，升序排列，或者实现comparator方法自定义排序

它提供了一些方法，
1-comparator定制排序，如未定制则返回null

2-first，返回第一个元素

3-last，返回最后一个元素

4-lower，返回比指定值小的元素，

5-higher，返回比指定值大的元素，

6-subset，返回指定区间的子集(包头不包尾)

7-headset，返回小于给定值得子集，

8-tailset，返回大于等于给定值得子集

看起来很乱，其实很好记，返回值是，第一个，最后一个，前一个，后一个，三个子集，(前一个后一个中给定的值不需要存在于集合中)

默认排序时，使用的是comparable类的compareto，比较a.b两数，a大于b返回1，否则为-1，相等为0，且向treeset中添加一个对象时，该对象的类必须实现comparable类的compareto方法

有两个特殊点，
1-如果没有实现这个类，则只能向treeset插入一个值，且不能取出，否则引发异常，
2-如果向treeset添加的不是一个类的对象，也会引发异常，原因在于compareto方法要求两个比较的对象是同一类

你可以通过自定义comparable类的方法，使多个不同类加入到treeset中，但取不出来，(重写compareto方法，不强制转换类型)

为了使treeset正常使用，应该保证treeset中的对象，使用equals和compareto方法的比较结果一样，可以通过重写方法达到这一目的

在treeset中放去可变对象，将面临和hashset同样的问题，只要放入后改变值，treeset将找不到改变值得元素，顺序也会变得混乱，这是因为treeset会在加入时检查并排序，但在改变集合中元素值时不会管他，这种情况下可以删掉一个没有改值得元素，那么集合会重新索引(不是重新排序)，就能删所有元素了

在自定义排序时要提供一个compartor对象与treeset关联，且要实现他的compare方法作为比较标准，这个compartor对象要作为treeset的构造器参数传入

---

如果试图把一个对象添加到TreeSet时，则该对象的类必须实现Comparable接口

6.3.4 EnumSet类

EnumSet在内部以位向量的形式存储，这种存储形式非常紧凑、高效，

因此EnumSet对象占用内存很小，而且运行效率很好，

enumset不允许插入null，否则会报空指针，如果想测试或者删除其中的null值，会返回false

enumset没有提供构造方法，但是提供了一些静态方法用于创建对象，

1-allof用指定枚举类的所有变量创建一个集合

2-complementof，假设有一个四个枚举值得枚举类，有一个enumset使用了该类的三个值创建了集合，则将该enumset作为参数传入该方法，创建的enumset中报告剩下的那一个枚举值

3-copyof，使用普通集合创建enumset，但这个普通集合中的值要属于同一枚举类

4-copyof，传入一个enumset，将复制一个该集合

5-noneof，传入一个枚举类，创建一个元素类型为该类的空集合

6-of 创建一个由一个或多个枚举值组成的集合，这些枚举值必须是同一类的

7-range，创建一个包含枚举值1到2之间所有枚举值得集合，这个顺序关系在于他们在类中的顺序
 

---

EnumSet在内部以位向量的形式存储，这种存储形式非常紧凑、高效，因此EnumSet对象占用内存很小，而且运行效率很好

6.3.5 各Set实现类的性能分析

enumset性能最好，hashset其次（尤其对添加查询等操作有良好的性能),tteeset再其次，

如果需要维持set中的元素的排序关系，用treeset,

如果想快速遍历，用linkedhashset,

值得注意的是，collection下的enumset, hashset,treeset都是线程不安全的,

 也就是说当多个线程同时访问一个set时，这个集合中的元素将不同步，

通常使用collections工具类的synchronizedSortedSet方法来包装set,解决上述问题

6.4 List集合

list与set的不同，

1）元素有序，list按添加顺序为元素添加索引

2）元素可重复

6.4.1 List接口和ListIterator接口

list的常用方法

1）add 添加元素（到指定位置参数顺序为，（位置，元素））

2）addAll（位置，子集）将指定集合中的所有元素添加到指定位置

3）get返回指定索引位置的元素

4）indesOf返回元素在list中，第一次出现的位置（索引值）

5）lastindexOf返回元素在list中，最后一次出现的索引值

6）remove删除指定位置的元素（还会返回该元素？）

7）set（位置，元素）将指定位置的元素替换

8）sublist（开始，结束）返回从开始位置到结束位置的，list子集

9）iterator返回一个listiterator对象，用于迭代liat

6.4.2 ArrayList和Vector实现类

这两个list的实现类都是基于数组实现，他两都封装了一个object的数组，使用initialcapacity参数来设置数组的长度（默认长度为10），且这个参数会自动增加（如果数组不够用了）

1）ensureCapacity（int q）将数组长度增加q，（其实改变的就是initialCapacity的值）

2）trimToSize（）调整数组的长度为元素个数（缩减数组，减少空间占用）

vector是早期java 的一个list，之后java提供arraylist之后就很少用了，但vector是线程安全的，而arraylist不是，线程安全的好处付出的代价就是性能的下降

vector还有一个子类，Stack，可以用来模拟栈（LIFO）（太老了，不推荐，模拟栈可以用linkedlist）

注意栈和set一样，都会忘记进入数据的类型，而统一当作object，所以取出来的数据要类型转换

stack类的方法

1）peek（）返回栈的第一个元素，该元素不会出栈

2）pop（）将栈顶元素出栈

3）push（object m）将元素入栈（压入栈顶）

6.4.3 固定长度的List

操作数组的工具类arrays，有一个内部类，arraylist，他是一个固定长度的list，并且只能遍历，不能增加和删除

array类的aslist方法，可以将一个数组，或者指定个数的对象，转换为一个list，而创建的这个list，就是array的内部类arraylist的实例，

补充（2023.8.8）

使用上述方法生成的list不可改变，对该list的操作在编译期不会报错，但运行到之后会抛出  UnsupportedOperationException（不支持操作）异常。

6.5 Queue集合

queue也就是队列（FIFO，先进先出），接口中的方法有

add（元素）将指定元素加入队尾

offer（元素）将指定元素加入队尾

element（）获取队头元素，不删除

peek（）获取队头元素，不删除，如队列为空，返回null

remove（）获取对头元素，并删除

poll（）出队，为空返回null

queue是一个接口，他下面有

        1）priorityQueue实现类，

        2）Deque接口，这是一个双端队列，也可以当作栈来用，

java为Deque提供了ArrayDeque和linkedlist两个实现类

​

6.5.1 PriorityQueue实现类

这个不能说是队列，而更像是一个堆，

因为如果将元素加入队列，那么PriorityQueue会将其中的所有元素排序，如果出队时，将会弹出队列中最小的元素

priorityQueue不允许插入null

因为该实现类需要对加入的元素排序，所以priorityQueue提供了两种排序方式，

1）自然排序

如果使用这种方式，则加入该Queue的对象必须实现comparable接口，并且必须是同一个类的实例

2）定制排序

也是使用comparator作为传入对象，作为排序依据，这个前面有具体解释，不再赘述

6.5.2 Deque接口与ArrayDeque实现类

Deque接口，定义的方法

1）assFirst 将指定元素插入双端队列的开头

2）addlast 将指定元素插入双端队列的末尾

3)descendinglterator 返回对应集合的迭代器，该迭代器以逆向顺序遍历集合（队列）中的元素

4）getFirst 获取队头元素，不删除

5）getLast 获取队尾元素，不删除

6）offerFirst 将指定元素插入队头

7）offerLast 将指定元素插入队尾

8）peekFirst 获取队头元素，不删除，为空返回null

9）peekLast 获取队尾元素，不删除，为空返回null

10）pollFirst 获取对头元素，并删除，为空返回null

11）pollLast 获取队尾元素，并删除，为空返回null

12）pop 出栈

13）push 入栈

14）removeFirst 获取队头元素，并删除

15）removeLast 获取队尾元素，并删除

16）removeLastOccurrence 删除该队列最后一次出现的指定元素

Deque接口的实现类，ArrayDeque，基于数组实现的双端队列，可用numElements指定数组长度，默认为16

那么这个ArrayDeque就可以用作栈，因为包含pop和push方法

6.5.3 LinkedList实现类

linkedlist实现了两个接口，list和Deque，所以他是一个可以当作栈，或双端队列的list集合

我在测试时发现一个问题，如果用for和pop，来循环遍历list，总会出错，因为最后的几位不会被输出，

原因在于，我的for的终止条件为

for (int i = 0; i < s.size(); i++)

每次在for中pop出一个元素，size（）的长度就会减一，而i++还在增长，双向奔赴会付出代价

linkeslist，使用链表实现，插入删除时性能很好

arraylist，arrayDeque，使用数组实现，随机访问时性能很好（Vector也是数组，但为线程安全付出了代价）

6.5.4 各种线性表的性能分析

先对以上的类做数据结构的分类，

线性表list 遍历时用get

​         1）基于数组的线性表 arraylist

​         2）基于链表的线性表 linkedlist

队列queue 遍历时用iterator 插入删除性能很好

​         1）双端队列/栈 Deque

6.6 Map

MAP是一种储存映射关系的数据结构，它包含两部分，key集和对应的value集，

key集类似一个set，元素不能重复，（其实map和set的关系很深，包括底层实现，方法）

value集类似一个list，元素可以重复，可以通过下标（对应的key）来访问对应的元素

在java底层实现map时，其实封装了一个Entry内部类，来存储key-value对，

并且，从java源码来看，它先是实现了map，然后包装了一个value都为null的map，就实现了set

map也被成为字典，或关联数组

map接口定义的常用方法

1）clear 清除该map所有的键值对

2）containsKey（key） 查询map中是否包含指定key，返回布尔值

3）containsValue（value） 查询map中是否包含一个或多个value值，返回布尔值

4）entrySet（） 返回map中所有的key-value对，组成的set，key-value的表现形式是Map.Entry对象

5）get（key） 返回指定key所对应的value，如不存在返回null

6）isEmpty（） 查询map是否为空，返回布尔值

7）keySet（） 返回map中，所有key组成的set

8）put（key，value） 向map添加一个键值对，如键已存在，则会被覆盖

9）putAll（map） 将指定map的所有键值对复制到本map

10）remove（key） 删除key所对应的value，返回的是被删除的value，如key不存在返回null

11）size（） 返回map中的键值对个数

12）values（） 返回map中，所有value组成的collection（也就是集合）

map中的entry内部类封装了键值对，包含三个方法

        1）getKey（） 返回该Entry里的key

        2）getValue（） 返回该Entry里的value

        3）setValue（value） 设置该Entry的value，返回新的value值

6.6.1 HashMap和Hashtable实现类

HashMap和Hashtable，类似Arraylist和Vector的关系

Hashtable是一个古老的map类，和vector一样从jdk1开始就存在，同样，他是线程安全的，它不允许将null作为key和value

hashmap的键值可以用null来赋值，但由于key的值不能重复，所以只能有一个key为null的键值对

hashmap的tostring已经被重写了，它的返回格式总是         key1=value1

在map中如果要使用自定义类，作为key的元素对象，必须要重写hashcode（）方法和equals（）方法，

hashmap和hashtable，的key相等的判断标准

                1）两个key通过equals（）方法返回true

                2）通过hashcode（）方法也返回true

他们两的value判断标准

                1）两个value通过equals（）方法返回true

和list，已经set一样，如果已经存入的元素是可变的，在存入之后改变它，对应的存储结构将不能再准确的访问到被修改的元素

在map中，尽量不要使用可变元素作为key

6.6.2 LinkedHashMap实现类

linkedhashmap可以维护key插入时的顺序，因为它使用了双链表，所以优点是插入删除的效率高，缺点是随机访问时效率底

关于遍历map，有两种方法

                1）使用keyset来获取map的所有键值对，再用eafor循环来遍历

                2）直接使用对应map的迭代器

6.6.3 使用Properties读写属性文件

properties是hashtable的子类，它可以处理属性文件，properties类可以将map对象和属性文件关联起来，比如读取，写入

properties类提供的方法

1）getProperty（key） 获取properties中，指定属性名对应的属性值

2）getProperty（key，defaultvalue） 也是获取指定key的value值，如指定key不存在，则指定默认值

3）load（inputstream instream） 从属性文件中加载键值对，追加到properties中

4）store（outputstream out，string comments）将properties中的键值对输出到指定的属性文件中

3和4方法中的形参都是输入输出流，

6.6.4 SortedMap接口和TreeMap实现类

Map的子接口sortedMap，sortedmap接口的实现类，就是TreeMap

TreeMap使用红黑树作为存储结构，树中的每个节点就是一个键值对，树的排序依据是key值

同样有两种排序方式

1）自然排序

TreeMap中，key必须是同一个类，并且这个类要实现comparable

2）定制排序

创建TreeMap时传入一个comparator对象，它负责对树中的元素排序

TreeMap中，元素相等的判断标准，两个key通过compareTo（）方法返回0

如在TreeMap中，key为自定义类，那么需要保证compare To（）方法和equlas（）的返回结果一致

TreeMap中的方法（第一个，最后一个，前一个，后一个，截取子集）

firstEntry（） 返回该map最小的key，所对应的键值对，为空返回null

firstKey（） 返回该map中最小的key值，为空返回null

lastEntry（） 返回该map中最大的key，所对应的键值对，为空返回null

lastKey（） 返回该map中最大的key值，为空返回null

higherEntry（key） 返回该map中，位于指定key后一位的键值对

higherKey（key） 返回该map中，位于指定key后一位的key

lowerEntry（key） 返回该map中，位于指定key前一位的键值对

lowerKey（key） 返回该map中，位于指定key前一位的key

subMap（开始位置，是否包含开始，结束位置，是否包含结束） 返回该map 的一个子集

subMap（开始（包括），结束（不包括）） 返回一个该map 的子集

tailMap（值） 返回该map的一个子集，key值大于指定值

tailMap（值，是否包含值） 返回该map的一个子集，key值大于指定值

headMap（值） 返回map的一个子集，key值小于指定值

headMap（值，是否包含值） 返回map的一个子集，key值小于指定值

6.6.5 WeakHashMap实现类

WeakHashMap与HashMap类似，不同点在于，HashMap对key是强引用，但WeakHashMap只有对key实际对象的弱引用，

因此如果垃圾回收程序，回收了key所对应的实际对象之后，WeakHashMap将会自动删除该key所对应的键值对

6.6.6 IdentityHashMap实现类

IdentityHashMap与HashMap类似，但IdeatityHashMap对两个key的，相等判断更加严格，必须两个key用==相等时，它才认为两个key相等

6.6.7 EnumMap实现类

EnumMap是一个与枚举类一起使用的Map，在创建它时要指定它对应的枚举类，并且其中的key都要为枚举类中的枚举值

EnumMap的底层使用数组实现，并且它维护，基于枚举类内部，每个枚举值的顺序（称为自然顺序），来维护每个键值对的顺序

EnumKey的key不允许使用null

6.6.8 各Map实现类的性能分析

这一小节了解到的map有

        1）Hashmap，

        2）hashtable，

        3）treemap，

        4）linkedhashmap，

        5）IdentityHashMap，

        6）EnumMap，

        7）WeakHashMap

性能最好的时EnumMap

其次是HashMap，其次稍差一点的是Hahstable，因为它线程安全

treemap和linkedhashmap差不多，但treemap能保持元素有序，但在插入删除是比较慢，

linkedhashmap正好在插入删除时效率高

IdentityHashMap和WeakHashMap性能一般，只是两个比较特殊的实现类

6.7 HashSet和HashMap的性能选项

Hash能存储元素的位置，称为”桶“，如果一个”桶“存储两个元素，则在同一位置用链表，存储多个元素，

在hash表中包含如下属性，

容量，桶总数

初始容量，如表意

尺寸，当前表中已装载桶，的数量

负载因子，尺寸/容量，0表示空，1表示满

负载极限，当负载因子到达负载极限时，hash表将成倍的增加桶的容量，并重新分配桶内元素，成为rehashing

hashmap和hashset，以及hashtable，默认的负载极限是0.75，也可在调用构造器时指定负载极限

负载极限，

如果太高，表空间占用内存较少（不发生rehashing），但查询时长增加，

如果太低，增加内存开销，但查询时长缩短

推荐如果刚开始就知道hash表内的最高容量，则手动指定初始化容量

6.8 操作集合的工具类：Collections

6.8.1 排序操作

collections提供，list排序的方法（以下方法都是静态）

reverse（list）反转指定list中，元素的顺序、

shuffle（list）对指定list随机排序（洗牌，这个比喻真好）

sort（list，comparator）根据comparator的顺序，对指定list排序

swap（list，i，j）将指定list 的，下标i，j处的元素互换

rotate（list，i）

i>0，将list最后的i个元素整体移到前面

i<0，将list前面的i个元素整体移到后面

这里有一个好玩的梭哈游戏，等我补全单独记录

6.8.2 查找、替换操作（以下方法都是静态）

binarySearch（list，key）对指定list（该list要有序）使用二分搜索，获取key的索引，

max（collection） 根据元素自然顺序，返回最大元素 （这里的自然排序，对于int的整数，就是大小关系，也就是调用compareTo（）方法）

max（collection，comperator） 根据comparator指定的顺序，返回集合的最大元素

min（collection）根据自然顺序，返回集合中的最小元素

min（collection，comparator） 根据comparator指定的顺序，返回集合中的最小元素

fill（list，object）使用指定元素object替换list中的所有元素

frequency（collection，object）返回元素object在collection中出现的次数

lastIndexOfSubList（来源，目标）返回子list在父list中，第一次出现的位置，如无子list，返回-1

replaceAll（list，oldval，newval）在指定list中，使用一个新值，替换list中的所有指定旧值

6.8.3 同步控制

Vector和Hashtable，这两个古早的list和map是线程安全之外，别的几乎都是不安全的，

将集合包装成线程安全，要用到一个方法

Collections的synchronizedXxx方法

xxx的地方可以填list，map，set，collection，将这个方法的返回值赋给指定的集合类型，就可获得线程安全的实现类

6.8.4 设置不可变集合

collections有如下三个方法，来返回不可变集合

emptyXxx（） 返回一个空的，不可变的集合对象，（xxx可为，list，map，set）

singletonXxx（） 返回一个只包含指定对象/元素的，不可变的集合对象

unmodifiableXxx （） 返回指定集合对象的不可变视图（只读版本）

​

6.9 烦琐的接口：Enumeration

一个古早的迭代遍历工具，和hashtable，Vector，以及Bitset都是从JDK1.0时，就存在的

这个接口主要用来遍历上面的三个古早集合，且后面的新集合不支持该接口来遍历，

它有两个方法

hasMoreElements（）此迭代器是否还有元素

nextElement（）返回此迭代器的下一个元素，如果集合为空使用此方法，将抛出异常

在计算机行业有一条规则：加入任何规则都必须慎之又慎，因为以后无法删除规则。

删除原本的规则意味这大换血

---

死亡诗社

“医药、法律、商业、工程，这些都是高贵的理想，并且是维生的必需条件。但是诗、美、浪漫、爱，这些才是我们生存的原因。”

“Medicine, law, business, engineering — these are noble pursuits and necessary to sustain life. But poetry, beauty, romance, love — these are what we stay alive for.”