Java编程思想笔记11.容器

一年又一年，字节跳动 Lark（飞书） 研发团队又双叒叕开始招新生啦！
【内推码】：GTPUVBA
【内推链接】：https://job.toutiao.com/s/JRupWVj
【招生对象】：20年9月后~21年8月前 毕业的同学
【报名时间】：6.16-7.16（提前批简历投递只有一个月抓住机会哦！）
【画重点】：提前批和正式秋招不矛盾！面试成功，提前锁定Offer；若有失利，额外获得一次面试机会，正式秋招开启后还可再次投递。

点击进入我的博客

本章包含了Java编程思想第11章和17章的内容
我们需要在任意时刻和任意位置创建任意数量的对象，所以依靠创建需要命名的引用来持有对象已经满足不了需求。Java可以用数组和其他容器类来（List、Set、Queue、Map）来解决这个问题，不同的容器类有各自的特性，满足不同的需求。

1 范型和类型安全的容器

Java SE5之前是没有范型的，一个容器内（以List为例）可以放置任意的对象。

public class Test  {
    // 用@SuppressWarnings抑制编译器对“不受检查的异常”的警告
    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        // (1)
        List strList = new ArrayList() {
            {
                add("spider");
                add(520);
            }
        };
        // (2)
        for (Object obj : strList) {
            System.out.println(((String) obj).length());
        }
    }
}
没有范型的问题：

如上所示，(1)处的代码在编译和运行的时候都没有任何问题；但是当你在(2)处需要把Object类型强制转型成你需要的对象类型的时候，这个时候就会出现问题，因为Integer是无法转型成String类型的。

范型的好处
  1. 所以更安全的做法是，我们在创建一个容器的时候就明确它能存放的类型是什么List<String> strList = new ArrayList<>();。
  2. 编译器将阻止我们放置其他类型的对象；
  3. 而且你在从容器中取出对象的时候，也不必在强制转型，因为List知道你需要的对象类型是什么，它将会帮你自动转型。
  4. 我们可以将声明类型的子类放入该容器（即子类的向上转型）。

2 基本概念

2.1 容器类图

容器类图

Java容器类类库的用途是“保存对象”，从上述类图可以发现有两个顶层接口，并可以依次将容器划分为两个不同的概念。

  1. Collection：一个独立元素的序列。所有Collection都可以用foreach遍历。
  2. Map：一组成对的“键值对”对象，允许你使用键来查找值。

2.2 Java SE5中的新增容器

  1. Queue接口及其实现PriorityQueue和各种风格的BlockingQueue。
  2. ConcurrentMap接口及其实现ConcurrentHashMap，它们也是用于多线程机制的。
  3. CopyOnWriteArrayList和CopyOnWriteArraySet，它们也是用于多线程机制的。
  4. EnumSet和EnumMap，为使用enum而设计的Set和Map的特殊实现。
  5. Collections类中的多个便利方法。

3 容器填充元素

  1. Arrays.asList()
  2. Collections.addAll()
  3. Collections.fill()
  4. Collections.nCopies()
  5. collection.addAll()
  6. Collection的构造器可以接受一个Collection来初始化
        Collection<Integer> collection = new ArrayList<>(Arrays.asList(1, 2, 3));
        collection.addAll(Arrays.asList(new Integer[]{1, 2, 3}));

        Arrays.asList(new int[]{1, 2, 3});
        Arrays.asList(1, 2, 3);

        Collections.addAll(collection, new Integer[]{1, 2, 3});
        Collections.addAll(collection, 1, 2, 3);

4 可选操作

执行各种不同的添加和移除的方法在Collection接口中都是可选操作，对于不支持的操作会抛出UnsupportedOperationException。

  1. Arrays.asList()返回的ArrayList不可以添加元素，此ArrayList和java.util.ArrayList不是同一个类。
  2. Collections.unmodifiableCollection()也会产生不可修改的列表

5 容器的打印

  1. 如果你要打印一个数组，需要用Arrays.toString()方法，直接打印数组显示的是[I@61bbe9ba这种之前介绍过的格式。
  2. 容器由于重写了toString()方法，所以可以直接打印出可读性强的结果。
  3. 由于不同Collection或Map的子类元素放置的规则和顺序不同，所以向容器内添加相同的元素，打印的结果不一定相同。
  4. HashMap提供了最快的查找技术，没有任何明显的顺序来保存其元素；TreeMap按照比较结果的升序保存键；LinkedHashMap按照插入顺序保存键，同时还保留了HashMap的查询速度。

6 List

List是一种可修改的序列，它允许在创建之后添加、移除元素，或者自我调整尺寸。

有两种基本的List：
  1. 基本的ArrayList，它擅长随机访问元素，但是在List的中间插入和删除元素时较慢
  2. LinkedList，它通过代价较低的方式在List中进行插入和删除操作，提供了优化的顺序访问；但是随机访问方面相对较慢。

6.1 LinkedList

如前所述，LinkedList也像ArrayList一样实现了基本的List接口，但是它执行插入和移除时比ArrayList要更高效，但是在随机访问操作方面要慢。
LinkedList还添加了可以使其用作栈、队列或双端队列的方法（是Queue的子类）。

LinkedList中的相同方法
  1. 正是由于LinkedList添加了栈和队列的方法，使得内部多了一些功能相同但名称不同（为了覆盖父类）的方法
  2. getFirst() == element() ≈ peek()：都是返回第一个元素，但是在空List的时候处理不一样
  3. removeFirst() == remove() ≈ poll()：都是移除并返回列表的头，但是在空List的时候处理不一样
  4. addFirst() == addLast()：都将某个元素插入队尾

7 迭代器

迭代器是一个对象，他的工作是遍历并选择序列中的对象，而程序员不必知道该序列的底层结构，即将遍历序列的操作和序列底层的结构分离。
迭代器通常被成为轻量级对象：创建它的代价很小。

Java的迭代器Iterator
  1. Java的迭代器只能向前移动
  2. 使用方法iterator()要求容器返回一个Iterator，Iterator准备好返回序列的第一个元素
  3. 使用next()获取序列中的下一个元素
  4. 使用hasNext()检查序列中是否还有元素
  5. 使用remove()将迭代器新近返回的元素删除
更强大的迭代器 ListIterator
  1. 它是Iterator的子类型，只能用于List的访问。
  2. 它可以双向移动
  3. 它可以返回当前位置前一个元素和后一个元素的索引（即下标）
  4. 可使用时set()方法替换访问过的最近的元素
  5. 可以使用listIterator(int index)直接创建一个指向索引处的ListIterator
Collection和Iterator

Java中，实现Collection就必须提供iterator()方法，这有的时候会带来麻烦。
直接生成Iterator是将队列与消费队列的方法链接在一起耦合度最小的方式，并且与实现Collection相比，它在序列类上所施加的约束也少得多。

Foreach与迭代器
  • foreach可以用于数组和所有Collection对象，之所以能够工作，是因为Collection继承了Iterable接口。
  • 数组不是Iterable。
  • Iterable接口包含一个能够产生Iterator的iterator()方法，并且Iterable接口被foreach用来在序列中移动。换言之，任何实现了Iterable接口的类，都可以用与foreach语法。
适配器方法惯用法

如果需要多个foreach遍历一个类的方法，例如该类需要支持向前和向后遍历。这是只实现Iterable是不行的，可以编写其他返回类型为Iterable的方法来满足foreach语句。这就是编写适配器。

// 反向遍历部分代码
public class Test<E> extends ArrayList<E> {
    public Test(Collection<? extends E> c) {
        super(c);
    }

    public Iterable<E> reverse() {
        return new Iterable<E>() {
            @Override
            public Iterator<E> iterator() {
                return new Iterator<E>() {
                    int index = size() - 1;
                    @Override
                    public boolean hasNext() {
                        return index >= 0;
                    }

                    @Override
                    public E next() {
                        return get(index--);
                    }
                };
            }
        };
    }
}

8 Stack 栈

栈是一种先进后出（Last In First Out，LIFO）的容器（数据结构）。
LinkedList能实现栈所有的功能。

主要方法
  1. peek()：返回栈顶元素
  2. pop()：返回并移除栈顶元素
  3. push()：元素入栈
  4. empty()：栈是否为空

9 Set 集合

Set不保存重复的元素。
Set与Collection有完全一样的接口（方法），因此没有任何额外的功能，实际上Set就是Collection只是行为不同（这就是继承和多态思想的典型应用：体现不同的行为）。

常用的几种Set
  1. HashSet：使用的是散列函数，这也是大多数使用场景的选择
  2. TreeSet：将元素存储在红-黑树数据结构中。TreeSet默认是按照字典序排序的；初始化TreeSet的时候可以设定排序的方式，如String.CASE_INSENSITIVE_ORDER就是按照字母序排列；你也可以写一个你自己的比较器Comparator。
  3. LinkedHashSet：是HashSet的扩展，但是元素顺序是按照放插入顺序保存的。
SortedSet接口
  1. SortedSet中的元素可以保证处于排序状态。
  2. SortedSet的意思是——按照对象的比较函数对元素进行排序，而不是插入顺序。

10 Queue 队列

队列是一个典型的先进先出（First In First Out，FIFO）的容器。
队列通常被当作一种可靠的将对象从程序的一个区域传输到另一个区域的途径，尤其在并发编程中十分重要。

主要方法
  1. offer()：将元素插入队尾。
  2. add()：同offer()，但是当超出队列长度当时候抛出异常。
  3. peek()：不移除的返回队头元素；为空时返回null。
  4. element()：同peek()，为空时抛出NoSuchElementException。
  5. poll()：移除并返回队头元素，为空时返回null。
  6. remove()：同poll()，为空时抛出NoSuchElementException异常。
PriorityQueue

优先级队列：按照优先级的顺序维护的队列。
当你在PriorityQueue上调用offer()方法来插入一个对象时，这个对象会在队列中被排序。默认的排序将使用对象在队列中自然顺序，但是你可以通过提供自己的Comparator来修改这个顺序。PriorityQueue可以确保当你调用相关方法时，获取的元素将是队列中优先级最高的元素。

11 Map映射表

性能是映射表中的一个重要问题,当在get()中使用线性搜索时,执行速度回相当的慢,而这正是HashMap提高速度的地方。HashMap使用了特殊的值,称作散列码,来取代对键的缓慢搜索。散列码是“相对唯一”的、用以代表对象的int值,它是通过将该对象的某些信息进行转换搜索而成的。

11.1 Map的实现

Map子类 说明
HashMap Map基于散列表的实现(它取代了HashTable)。插入和查询“键值对”的开销是固定的。可以通过构造器设置容量和负载因子,以调整容器的性能。
LinkedHashMap 类似于HashMap，但是迭代遍历时，取得“键值对”的顺序是其插入次序，或者是最近最少使用(LRU)的次序。只比HashMap慢一点；而在迭代访问时反映更快，因为它使用的链表维护内部次序。
TreeMap 基于红黑树的实现。查看“键”或“键值对”时，它们会被排序（次序由Comparable或者Comparator决定）。TreeMap特点在于所得到的结果是经过排序的。TreeMap是唯一的带有subMap()方法的Map，它可以返回一个子树。
WeakHashMap 弱键(weak key)映射，允许释放映射所指向的对象；这是为解决某类特殊问题而设计的。如果映射之外没有引用指向某个“键”，则此“键”可以被垃圾回收器回收。
ConcurrentHashMap 一种线程安全的Map，它不涉及同步加锁。
IdentityHashMap 使用==代替equals()对“键”进行比较的散列映射。专为解决特殊问题设计的。

11.2 各种Map性能比较

  1. 除了IdentityHashMap，所有Map实现的插入操作都会随着Map尺寸的变大而明显变慢。
  2. Hashtable的性能大体上与HashMap相当。
  3. TreeMap通常比HashMap要慢。
  4. LinkedHashMap插入时比HashMap慢一点。

11.3 HashMap实现原理

HashMap实现原理及源码分析

  1. 数组并不保存键本身，而是通过键对象生成一个数字（即计算散列码），将其作为数组的下标。
  2. 由于散列码计算可能会产生冲突，所以数组并不直接保存值，而是保存值的List。
  3. Java的散列函数都使用2的整数次方来作为散列表的理想容量。对现代的处理器来说，除法和求余是最慢的动作。使用2的整数次方的散列表，可用掩码代替除法。因为get()是使用最多的操作，求余数的%操作是其开销的大部分。

11.4 HashMap的性能因子

我们可以通过手工调整HashMap来提高其性能，从而满足我们特定应用的需求。为了在调整HashMap时能理解性能的问题，某些术语是必须要了解的：

  1. 容量：表中的桶位数
  2. 初始容量：表在创建时所拥有的桶位数。HashMap和HashSet都具有允许指定初始容量的构造器——默认为16
  3. 尺寸：表中当前存储的项数
  4. 负载因子：尺寸/容量。空表的负载因子为0，而半满表的负载因子为0.5，依次类推。负载轻的表产生的冲突可能性较小，因此对于插入和查找都是最理想的（但是会减慢使用迭代器进行遍历的过程）。HashMap和HashSet都具有允许指定初始容量的构造器，当负载情况达到负载因子的水平时，容器将会自动增加容量，实现方式是容量大致加倍，并重新将现在对象分布到新的桶位中（这被称为再散列）。

HashMap使用的默认负载因子为0.75（只有当表达到四分之三满时，才会进行再散列），这个因子在时间和空间代价之间达到了平衡。更高的负载因子可以降低表所需的空间，但是会增加查找代价，这很重要，因为查找是我们在大多数时间里所进行的操作（包括get和put）。如果您知道将要在HashMap中存储多少项，那么创建一个具有恰当大小的初始容量将可以避免自动再散列的开销。

11.5 WeakHashMap

  • WeakHashMap用来保存WeakReference。它使得规范映射更易于使用，在这种映射中，每个值只保存一份实例以节省存储空间。当程序需要那个值的时候，便在映射中查询现有的对象，然后使用它。映射可将值做为其初始化的一部分，不过通常在需要的时候才生成值。
  • 这是一种节约存储空间的技术，因为WeakHashMap允许垃圾回收器自动清理键和值，所以十分便。对于WeakHashMap添加键和值的操作，则没有什么特殊要求，映射会自动使用WeakReference包装他们。

12 散列与散列码

12.1 hashCode与equals

默认的hashCode和equals

Object.equals()方法比较的是对象的地址
Object.hashCode()方法默认是使用对象的地址计算散列码

12.2 equals方法的条件

  1. 自反性：对于任何非null的引用值x，x.equals(x)=true
  2. 对称性：对于任何非null的引用x、y，x.equals(y)=true，那么y.equals(y)=true。
  3. 传递性：对于任何非null的引用x、y、z，如果x.equals(y)=true、x.equals(z)=true那么y.equals(z)=true
  4. 一致性：对于任何非null的引用x和y，只要equals的操作涉及的类信息没有改变，则x.equals(y)的结果一直不变。
  5. 对于任何为null的引用，x.equals(null)=false。

12.3 hashCode方法的约定

  1. 在一个应用程序执行期间，如果一个对象的equals方法做比较所用到的信息没有被修改的话，那么，对该对象调用hashCode方法多次，它必须始终如一地返回同一个整数。在同一个应用程序的多次执行过程中，这个整数可以不同，即这个应用程序这次执行返回的整数与下一次执行返回的整数可以不一致。
  2. 如果两个对象根据equals(Object)方法是相等的，那么调用这两个对象中任一个对象的hashCode方法必须产生同样的整数结果。因此重写了equals方法必须重写hashCode方法。
  3. 如果两个对象根据equals(Object)方法是不相等的，那么调用这两个对象中任一个对象的hashCode方法，不要求必须产生不同的整数结果。然而，程序员应该意识到这样的事实，对于不相等的对象产生截然不同的整数结果，有可能提高散列表（hash table）的性能。

12.4 覆盖hashCode注意事项

  1. 无论何时，同一个对象调用hashCode()都应该生成同样的值
  2. 不应该使hashCode()依赖于具有唯一性的对象信息，尤其是this的值。
  3. 散列码更应该关注生成速度，而不是唯一性
  4. hashCode的值的范围不重要，只要保证是int即可。

13 总结

  1. 数组将数字与对象联系起来。
  2. Collection保存单一的元素，而Map保存相关联的键值对。
  3. List也建立数字索引与对象的关联，List能够自动扩充容量。
  4. 如果要进行大量的随机访问，就使用ArrayList；如果要经常从表中间出入或删除元素，则应该使用LinkedList。
  5. 各种Queue以及栈的行为，由LinkedList提供支持。
  6. Map是一种将对象（而非数字）与对象相关联的设计。HashMap设计用来快速访问；而TreeMap保持“键”始终处于排序状态，所以没有HashMap快。LinkedHashMap保持元素插入的顺序，但是也通过散列提供了快速访问能力。
  7. Set不接受重复元素。HashSet提供最快的查询速度，而TreeSet保持元素处于排序状态，LinkedHashSet以插入顺序保存元素。
  8. 不要使用已过时的Vector、Hashtable和Stack。
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 215,634评论 6赞 497
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,951评论 3赞 391
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 161,427评论 0赞 351
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,770评论 1赞 290
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,835评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,799评论 1赞 294
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,768评论 3赞 416
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,544评论 0赞 271
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,979评论 1赞 308
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,271评论 2赞 331
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,427评论 1赞 345
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,121评论 5赞 340
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,756评论 3赞 324
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,375评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,579评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,410评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,315评论 2赞 352