Java 的集合框架和 lang 包下的常用类

—— mio

视频链接: 无

前言

1. 为什么课表上的标题是《Java 的数据结构和 lang 包下的常用类》，而本文标题却是《Java 的集合框架和 lang 包下的常用类》？因为感觉本文的侧重点还是在于介绍 Java 的集合框架，数据结构只是其中的一部分，并且其中的数据结构知识并不完整。
2. 本文主要内容是 Java 的集合框架以及一些数据结构知识。lang 包下的常用类介绍得比较匆忙，而且仅介绍了常用方法，其余内容需要同学课后自行学习。本节课主要内容是 Java 的集合框架，lang 包下的常用类介绍得比较匆忙，而且仅介绍了常用方法，其余内容需要同学课后自行学习。
3. 笔者个人认为，以下内容较多，并涉及到一些数据结构知识，如果是第一次接触的话，记不住也没关系，不用太担心（千万不要因为觉得这节课没完全学会，下节课就不来听了呀 o(╥﹏╥)o）。作为初学者，可以先了解了解，在脑海中留个印象，建立个大致的知识体系。在日后的实际使用中，如果出现了问题，再去网上查阅即可。此外，平日里常用的集合、数据结构和方法也就那么多。正所谓熟能生巧，使用多了，自然就熟悉了，自然就掌握了。
4. 呜呜呜，很遗憾，由于一些原因，笔者无法参加本周的后端组授课，只能拜托帅气的 lifeng 学长和可爱的 feellmoose 学长代上了。

Java 的集合框架

1、为什么需要集合？

Java 作为一门面向对象的语言，就免不了处理对象，为了方便操作多个对象，我们就得把这多个对象存储起来，想要存储多个对象（变量），我们需要一个容器（集合）来装载。

这听起来是不是有点像数组？众所周知，数组可以作为容器存储元素，此外，集合也具有同样的功能。那么请大家思考下，既然有了数组了，为什么还需要集合呢？

答案是 数组的使用存在一定的缺陷：

1. 数组是静态的，一旦被定义，就无法更改其长度，所以数组无法动态的适应元素数量的变化。
2. 数组的存放的类型只能是一种。
3. 数据结构单一。
4. 数组无法保存具有映射关系的数据。

相比较，集合就优点突出：

1. 集合的长度是可变的，可以动态扩展容量，可以根据需要动态改变大小。
2. 集合存放的类型可以多种。
3. 数据结构多样。不同的集合在实现上采用了各种不同的数据结构，这使得各个集合的性能、底层实现、使用方式上存在一定的差异，可根据实际场景选用。
4. 集合可以保存具有映射关系的数据。
5. 集合提供更多的成员方法，能满足更多的需求。
6. ……

2、集合框架的架构

以上两张图为集合框架的主要结构，Java 集合类主要由两个根接口 Collection 和 Map 派生出来的。（注意，Map 并非 Collection 的子接口，切勿混淆）

Collection 根接口又派生出了三个子接口：List、Set、Queue ，因此 Java 集合大致也可分成 List、Set、Queue、Map 四种接口体系，它的主要思想与接口和多态有着密不可分的联系。

Java 集合类库将接口与实现进行分开，当我们考虑采用一种数据结构时，可以选择多种实现方式。一旦我们构造了一个集合，我们就不需要知道它用了哪种实现方法，直接使用接口类型来存放集合的引用。

以 List 接口举例，比如我们想用一个类似数组的顺序存储的结构时，我们既可以采用 ArrayList（动态数组）的实现方式，同时也可以采用 LinkedList（链表）的实现方式。

List list = new ArrayList<>();

如果我们想随时换一种实现，那只需要对构造对象的地方修改就行了。

List list = new LinkedList<>();

3、Collection 接口

Collection 接口的常用方法

以下为 Collection 接口的一些常用方法，其子接口 List、Set、Queue 均可使用。

1. 把给定的对象添加到当前集合中。添加成功则返回 true ，否则返回 false 。

   boolean add(E element);

2. 将指定集合中的所有元素添加到当前集合中。添加成功则返回 true ，否则返回 false 。

   boolean addAll(Collection<? extends E> collection);

3. 清空当前集合中的所有元素，使其变为空集合。无返回值。

void clear();

4. 判断当前集合是否包含指定的元素。如果集合包含该元素则返回 true ，否则返回 false。

   boolean contains(Object element);

5. 判断当前集合是否包含指定集合中的所有元素。如果当前集合包含指定集合中的所有元素则返回 true，否则返回 false。

   boolean containsAll(Collection<?> collection);

6. 判断当前集合是否与指定对象相等。如果两个集合相等则返回 true，否则返回 false。

   boolean equals(Object object);

7. 返回当前集合的哈希值。

   int hashCode();

8. 判断当前集合是否为空，如果为空则返回 true ，否则返回 false。

   boolean isEmpty();

9. 从当前集合中移除指定元素的单个实例。如果移除成功则返回 true ，否则返回 false。若集合中本就不包含指定元素，则会移除失败，返回 false 。

   boolean remove(Object element);

10. 从当前集合中移除与指定集合中相同的元素。如果移除成功则返回 true ，否则返回 false。

    boolean removeAll(Collection<?> collection);

11. 从当前集合中仅保留与指定集合中相同的元素，移除其他元素。如果操作成功则返回 true ，否则返回 false。

    boolean retainAll(Collection<?> collection);

12. 返回集合中的元素个数。

    int size();

13. 将集合转换为数组。返回包含当前集合中所有元素的数组。

    Object[] toArray();

Collection 接口的实现类

1. List 接口（有序，可重复，可用索引访问）

List 集合为列表类型，以线性方式存储对象。List 集合中的元素允许重复，各元素的顺序就是对象插入的顺序。类似数组，用户可以也通过索引来访问 List 集合中的元素。

除了上述 Collection 集合的方法，List 还具有如下常用方法：

1. 将元素插入调用列表，插入位置的下标由 index 传递。任何已存在的，在插入点以及插入点以后的元素将前移，因此不会覆写元素。

   void add(int index, Object element);

2. 将传递的集合中的所有元素插入到调用列表中，插入点的下标由 index 传递。成功则返回 true ，否则返回 false。

   boolean addAll(int index, Collection collection);

3. 返回指定下标的元素。

   Object get(int index);

4. 对指定下标的元素进行赋值，返回该下标位置的原始元素。

   Object set(int index, Object object);

5. 返回调用列表中对象的第一个实例的下标。如果该列表不存在，则返回 -1。

   int indexOf(Object object);

常见的 List 集合的实现类主要有 ArrayList 和 LinkedList 。

1. ArrayList 类

ArrayList 底层是数组，相当于动态数组。每个 ArrayList 都有一个容量(capacity)，表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。

与 Java 中的数组相比，它的容量能动态增长。当创建一个 ArrayList 对象时，会初始化一个初始容量（默认为 10）的数组。当添加元素时，ArrayList 会检查当前元素数量是否超过了数组的容量，如果超过了，则会按照一定的策略进行扩容。

扩容是用新数组代替旧数组，指针指向新的数组的地址，旧的数组下次垃圾回收会进行回收。（创建一个新的数组，然后将旧数据拷贝过来，然后再追加新的元素）

具体自动扩容机制和规则：

• add 操作：

  1. 空集合第一次 add 操作会触发首次扩容，扩容大小是10。
  2. 如果新 add 的元素超过 ArrayList 的容量，比如添加第11个元素，则扩容1.5倍，后面每次扩容是上次容量的1.5倍。如果1.5倍存在小数问题怎么解决？实际底层是通过右移一位来实现扩容1.5倍。

• addAll 操作：

  1. 一个空的集合第一次添加一个新的集合
     • 如果添加的元素没有超过10，默认扩容是10。
     • 如果超过10，默认是添加的元素的个数。
  2. 非空集合添加元素
     • 如果添加的元素没有超过1.5倍，则扩容1.5倍。
     • 如果超过了1.5倍，数组大小 = 数组当前元素个数 + 新增元素个数。

2. LinkedList 类

LinkedList 底层是通过双向链表实现的。

（1）链表

考虑到你们可能还没学到链表，这里先简单介绍一下。

链表，顾名思义，是像链条一样连接在一起数据结构。链表的元素叫做节点，每个节点都包含两类信息，一类是实际存储的信息，一类是指针，用于指向下一个或上一个节点。其中第一个节点被称为首节点，最后一个节点被称为尾节点。

链表是一种线性表，但是并不会按线性的顺序存储数据，而是依靠指针连接相连节点。根据节点之间的连接方式和特性，链表分为单向链表、双向链表、循环链表等等，其中循环链表又分为了单向循环链表和双向循环链表。

1. 单向链表

   

   链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而尾节点则指向一个空值。节点之间的连接是单向的，即只能从前往后遍历。

2. 双向链表

   

   每个节点除了包含实际信息外，还包含两个指针：一个指向上一个节点，而另一个指向下一个节点。特别的，首节点和尾节点分别有一个指针指向空值。节点之间的连接是双向的，既可以从前往后也可以从后往前遍历。

3. 单向循环链表

   

   在单向链表的基础上，尾节点的指针又指向了首节点，使得首尾相连，整个链表形成一个环形，达到循环的效果。

4. 双向循环链表

   

   类似于单向循环链表，双向循环链表是在双链表的基础上，首尾节点相连，整个链表形成一个环形，达到循环的效果。

5. ……

由于其独特的结构，链表的特点是插入与删除数据十分方便，但寻找与读取数据的表现欠佳。插入和删除数据时，只需要“断开”原位置的节点，再插入新节点或删除旧节点，然后将断开的前后链表拼接在一起（上述操作均只调整相邻节点的指针指向即可），并不会对前后的原链表产生任何影响。寻找与读取数据时，则只能从前向后或从后向前（只有双向链表才可以从后向前）每个节点依次遍历。

（2）LinkedList

LinkedList 底层便是通过双向链表实现，双向链表的每个节点用内部类 Node 表示，通过 first 和 last 引用分别指向链表的首节点和尾节点，不存在容量不足的问题。

由于 LinkedList 的底层是双向链表，有两种方式遍历，那么在使用中便可结合实际来选择恰当的。这里就不得不提它的一个方法 node(int index) 了，它的多个方法内部均调用了该方法来获取对应的节点。源码如下：

// 返回指定下标的非空节点
Node<E> node(int index) {
    // 断言下标未越界
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

从这个方法的源码可以看出，该方法通过比较索引值与链表 size 的一半大小来确定从链表头还是尾开始遍历。如果索引值小于 size 的一半，就从链表头开始遍历，反之从链表尾开始遍历。这样可以在较短的时间内找到目标节点，充分利用了双向链表的特性来提高效率。

3. ArrayList 和 LinkedList 的对比

1. 内部实现：
   • ArrayList 基于动态数组实现。它使用一个数组来存储元素，并可以动态增长或缩小数组的大小以适应元素的添加或删除。
   • LinkedList 基于双向链表实现。它使用一个链表结构来存储元素，每个元素都包含了对前一个元素和后一个元素的引用。
2. 随机访问性能：
   • ArrayList 可以通过索引直接访问元素，支持快速的随机访问。
   • LinkedList 访问特定位置的元素需要从链表的头部或尾部开始遍历，随机访问性能相对较差。
3. 插入和删除性能：
   • ArrayList 在列表的中间插入或删除元素时，需要将后面的元素向后移动或向前移动，因此性能较差。但在列表的末尾进行插入或删除操作时，性能较好。
   • LinkedList 只需要修改相邻元素的引用，在插入和删除元素时性能更好。
4. 内存空间：
   • ArrayList 内部使用数组，需要分配一块连续的内存来存储元素，所以通常需要更多的内存空间。
   • LinkedList 只需要存储元素的值以及对前一个和后一个元素的引用，通常需要较少的内存空间。
5. 迭代性能：
   • ArrayList 可以使用迭代器或 for-each 循环轻松遍历元素，迭代性能较好。
   • LinkedList 在遍历过程中需要跟踪节点之间的引用，迭代性能略差。

选择使用 ArrayList 还是 LinkedList 取决于你的具体需求。如果需要频繁进行随机访问操作，那么 ArrayList 可能更合适。如果需要频繁进行插入和删除操作，特别是在列表的中间位置，那么 LinkedList 可能更合适。

不过，我们在项目中一般是不会使用到 LinkedList 的，需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替，并且，性能通常会更好。就连 LinkedList 的作者约书亚 · 布洛克（Josh Bloch）自己都说从来不会使用 LinkedList 。

2. Set 接口（无序，唯一）

Set 集合没有固定的大小限制，可以动态地添加和删除元素。Set 集合中的元素都是唯一的，不会有重复的元素，即使是 null 值也只能有一个。Set 集合是无序的，不能记住元素的添加顺序，没有索引值。Set 集合中的对象不会按特定的方式排序，它只是简单地把对象放到集合中。Set 的实现类主要有 HashSet 和 TreeSet 。

1. HashSet 类

HashSet 的底层原理其实是在 HashMap 的基础上包装了一下，只不过存储的时候 value （值）是默认存储了一个 Object 的静态常量，取的时候也是只返回 key （键），所以看起来就像 List 一样。（这里或许可以先跳转到下文，学习一下什么是 [Map](#4、Map 接口（键值对，双列集合）) 和 [HashMap](#1. HashMap 类（无序）) ）它的元素可以为 null ，但最多只能有一个，不然就重复了。

HashSet 是调用的 HashMap 的 put() 方法，而 put() 方法中有这样的逻辑——如果哈希值（又叫哈希码、散列码）和 key 都一样，就会直接拿新值覆盖旧值，因此 HashSet 利用这个特性可以保证唯一性。（感觉可以了解一下什么是哈希值）

而 hashCode() 和 equals() 方法是用来判断唯一性的，所以在存放对象的时候需要重写这两个方法，以此来设置去重的规则。否则就会出现如下情况，创建的两个属性一样的对象都可以放入 HashSet 中，那么 HashSet 的元素就重复了。这是因为创建两个对象的哈希值是不一样的，所以需要自己重写 hashCode() 和 equals() 。

由于底层是 HashMap ，而存储的又是 key ，所以没有 get() 方法来直接获取元素，只能遍历获取。

HashSet 存储快。添加元素的时候，HashSet 会先调用元素的 hashCode() 方法得到元素的哈希值，然后通过元素的哈希值经过移位等运算，就可以算出该元素在哈希表中的存储位置。

• 如果算出的元素存储的位置目前没有任何元素存储，那么该元素可以直接存储在该位置上。
• 如果算出的元素的存储位置目前已经存在有其他的元素了，那么还会调用该元素的 equals() 方法
  与该位置的元素再比较一次。如果该方法返回的是 true，那么该位置上的元素视为重复元素，不允许添加；如果返回的是 false ，则允许添加。

2. TreeSet 类

TreeSet 的底层结构是红黑树。

下面简单介绍一下树以及红黑树。

（1）树

树是一种数据结构，用来模拟具有树状结构性质的数据集合。它是由 n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

1. 每个节点都只有有限个子节点或无子节点。

2. 没有父节点的节点称为根节点。

3. 每一个非根节点有且只有一个父节点。

4. 除了根节点外，每个子节点可以分为多个不相交的子树。

5. 树里面没有环路。

术语：

1. 节点的度：一个节点含有的子树的个数称为该节点的度。
2. 树的度：一棵树中，最大的节点度称为树的度。
3. 叶节点或终端节点：度为零的节点。
4. 非终端节点或分支节点：度不为零的节点。
5. 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。
6. 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点。
7. 兄弟节点：具有相同父节点的节点互称为兄弟节点。
8. 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推。
9. 深度：对于任意节点n，n的深度为从根到n的唯一路径长，根的深度为0。
10. 高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0。
11. 堂兄弟节点：父节点在同一层的节点互为堂兄弟。
12. 节点的祖先：从根到该节点所经分支上的所有节点。
13. 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
14. 森林：由m（m>=0）棵互不相交的树的集合称为森林。

种类：

1. 有序 / 无序：

   • 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树。
   • 有序树 / 搜索树 / 查找树：树中任意节点的子节点之间有顺序关系，这种树称为有序树。即树的所有节点按照一定的顺序排列，这样进行插入、删除、查找时效率就会非常高。

2. 平衡 / 不平衡：

   • 平衡树

     • 绝对平衡树：所有叶节点在同一层。
     • 非绝对平衡树

   • 不平衡树

3. 节点的分叉情况：

   • 等叉树：是每个节点的键值个数都相同、子节点个数也都相同。
     • 二叉树：每个节点最多含有两个子树的树称为二叉树。
       • 完全二叉树：对于一棵二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树。
         • 满二叉树：所有叶节点都在最底层的完全二叉树。
       • 平衡二叉树（AVL）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树。
       • 排序二叉树（也被成为二叉查找树、二叉搜索树、有序二叉树）
     • 霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
     • 多叉树
   • 不等叉树：每个节点的键值个数不一定相同、子节点个数也不一定相同
     • B树：对不等叉树的节点键值数和插入、删除逻辑添加一些特殊的要求，使其能达到绝对平衡的效果。如果某个B树上所有节点的分叉数最大值是m，则把这个B数叫做m阶B树。

（2）红黑树

红黑树是一种自平衡二叉查找树，是一种数据结构。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间。

红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

1. 节点是红色或黑色。
2. 根是黑色。
3. 所有叶子都是黑色（叶子是 NIL 节点）。
4. 每个红色节点必须有两个黑色的子节点。（或者说从每个叶子到根的所有路径上不能有两个连续的红色节点。）（或者说不存在两个相邻的红色节点，相邻指两个节点是父子关系。）（或者说红色节点的父节点和子节点均是黑色的。）
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

（3）TreeSet

类似于 HashSet 的底层是 HashMap，TreeSet 底层是基于 TreeMap 来实现的。由于 TreeMap 的底层结构是红黑树，所以 TreeSet 的底层结构也是红黑树。TreeMap 采用红黑树来保存 Map 中的的每个 Entry（键值对对象），每个 Entry 都被当做红黑树的一个节点来对待。

TreeSet 是一个有序的集合，可以对存储的值进行自动排序，排序用的是二叉树原理，它的作用是提供有序的 Set 集合。TreeSet 中的元素支持 2 种排序方式：自然排序和根据创建 TreeSet 时提供的 Comparator 进行自定义排序，如何排序取决于使用的构造方法。

TreeSet 和 HashSet 不同的是不需要重写hashCode() 和 equals() 方法，因为它去重是依靠比较器来去重。因为结构是红黑树，所以每次插入都会遍历比较来寻找节点插入位置，如果发现某个节点的值是一样的那就会直接覆盖。

TreeMap 的插入就是一个“排序二叉树”算法：每当程序添加新节点时，总是从树的根节点开始比较，即将根节点当成当前节点，如果新增节点大于当前节点且当前节点的右节点存在，则以右节点作为当前节点；如果新增节点小于当前节点且当前节点的左节点存在，则以左节点作为当前节点；如果新增节点等于当前节点，则新增节点覆盖当前节点；直到某个节点的左右节点不存在，并结束循环；将新增的节点作为该节点的子节点，如果新增的节点大于该节点，则添加成该节点的右节点;如果新增的节点小于该节点，则添加成该节点的左节点。

可能有人会产生疑问了，前面不是说 Set 集合是无序的吗，怎么这里的 TreeSet 却是有序的？

首先要明确的一点是，在 Java 中我们通常说的集合有序无序针对的是插入顺序，是指在插入元素时，插入的顺序是否保持，当遍历集合时它是否会按照插入顺序展示。像 TreeSet 和 TreeMap 这样的集合根据以上定义是无序的。然而它们实现了自动排序，其元素则具有一定顺序了。举个例子，如果向 TreeSet 中依次存入数据的顺序为：”D”，”B”，”A”，”E”，”C”，”F”。当你对集合进行遍历取出数据后，你却会发现数据的顺序变为：”A”，”B”，”C”，”D”，”E”，”F”。这便是自动排序的结果。

一般来说 TreeSet （ TreeMap ）的 key 是不能为 null 的。因为在存时，会首先判断是否存在比较器，如果创建实例时没有传入 Comparator 比较器，那么程序会对 key 进行判断，判断它是否为 null ，如果为 null ，就会抛出空指针异常。如果我们有特殊需求，是可以自己实现 Comparator 接口，并重写 compare 方法去处理掉比较对象为空值的情况，这样做也是可以实现在其中存入一个空值的元素的。

3. HashSet 和 TreeSet 的对比

1. 内部实现：

   • HashSet 基于哈希表实现。
   • TreeSet 基于红黑树实现。

2. 是否有序：

   • HashSet 无序，不维持元素顺序。
   • TreeSet 插入元素后会自动排序。元素顺序遵循排序顺序，与插入顺序无关。

3. 是否需要重写 hashCode() 和 equals() 方法：

   • HashSet 需要重写 hashCode() 和 equals() 方法。
   • TreeSet 不需要重写 hashCode() 和 equals() 方法。

4. 是否可以放入 null 值：

   • HashSet 可以放入 null 值。
   • TreeSet 通常不可以放入 null 值。不够，如果我们有特殊需求，是可以自己实现 Comparator 接口，并重写 compare 方法去处理掉比较对象为空值的情况，这样做也是可以实现在其中存入一个为 null 值的元素的。

5. 性能：

   • HashSet 速度较快。
   • TreeSet 由于在插入元素时进行排序，速度较慢。

6. 比较方式（是否相同）：

   • HashSet 依靠hashCode() 和 equals() 方法。
   • TreeSet 依靠比较器来去重。

3. Queue 接口（先进先出）

Queue 集合一般用于模拟队列这种数据结构。队列的特点是先进先出。新元素插入（offer）到队列的尾部，访问元素（poll）操作会返回队列首部的元素。通常，不允许随机访问 Queue 中的元素。Queue 不支持存放 null 元素。

主要方法：

1. 将指定的元素添加到队列的末尾，如果成功则返回 true ，如果队列已满则抛出异常。如果队列有容量限制，建议使用 offer 方法。

   boolean add(E element);

2. 将指定的元素添加到队列的末尾，如果成功则返回 true，如果队列已满则返回 false。可以用于有容量限制的队列。

   boolean offer(E element);

3. 移除并返回队列的头部元素，如果队列为空则抛出异常。

   E remove();

4. 移除并返回队列的头部元素，如果队列为空则返回 null。

   E poll();

5. 返回队列的头部元素，但不移除该元素，如果队列为空则抛出异常。

   E element();

6. 返回队列的头部元素，但不移除该元素，如果队列为空则返回 null 。

   E peek();

7. 判断队列是否为空，如果队列中没有元素则返回 true ，否则返回 false 。

   boolean isEmpty();

8. 返回队列中的元素数量。

   int size();

4、Map 接口（键值对，双列集合）

不同于 Collection 集合，Map 的每个元素叫做 Entry （键值对）， 包含了两个对象，一个对象作为 key（键），一个对象作为 value（值）。也就是说，Collection 是单列集合，Map 是双列集合。Map 是一种依照 key 存储元素的容器，key 很像下标，不同的是，List 的下标是整数，而这里 Map 的 key 可以是任意类型的对象。

Map 可以简单理解为映射的集合，这种映射就是 key-value（键值对）。每个 key 都有着唯一与之对应的 value。在数学里面的函数其实就是一种映射关系，假设自变量是 x，因变量是 y，那么这个函数就是 从 x 到 y 的映射。大家想一下，这种情况下，函数上的所有点的 x 是不是都是唯一的，不重复的，而 y 就无所谓了，可以重复，哪怕是所有 y 都相等也没关系，就比如常数函数 y = 1。而 Map 的映射是从 key 到 value 的映射，所以同样，**key 具有唯一性，不可重复，而 value 则可以重复**。

Map 接口的常用方法

1. 从此映射中移除所有映射关系。

   void clear();

2. 如果此映射包含指定 key ，则返回 true。

   boolean containsKey(Object key);

3. 如果此映射包含指定 value ，无论有一个还是多个相同的，均返回 true。

   boolean containsValue(Object value);

4. 返回此映射中包含的映射关系的 set 视图。

   Set<Map, Entry<K, V>> entrySet();

5. 比较指定的对象与此映射是否相等。

   boolean equals(Object o);

6. 返回指定 key 所映射的 value ，如果此映射不包含改 key ，则返回 nu11。

   V get(Object key);

7. 返回此映射的哈希值。

   int hashCode();

8. 如果此映射未包含 key-value 映射关系，即为空，则返回 true。

   boolean isEmpty();

9. 返回此映射中包含的 key 的 set 视图。

   Set<K> keySet();

10. 将指定的 key 与此映射中的指定 value 关联，即放入键值对。如果该 key 已存在，并且 value 不同，则会更新 value 。返回值是该 key 对应的旧 value（如果该 key 已经存在于 Map 中），如果该 key 之前不存在于 Map 中，则返回 null 。

    V put(K key, V value);

11. 从指定映射中将所有的映射关系即 key-value 复制到此映射中。

    void putAll(Map<? extends K, ? extends V> m);

12. 如果存在一个 key 的映射关系，则将其从此映射中移除。返回值是被删除 key 的 value ，如果改 key 不存在，则返回 null 。

    V remove(Object key);

13. 返回此映射中的 key-value 映射关系数。

    int size();

14. 返回此映射中包含的 value 的 Collection 视图。

    Collection<V> values();

Map 接口的实现类

这里仅介绍 HashMap ，其余的同学们课后自行了解。

1. HashMap 类（无序）

HashMap 是无序的，即不会记录插入的顺序。HashMap 允许 key 和 value 为 null ，不过 key 最多只能有一个是 null 。HashMap 根据 key 的哈希值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。

HashMap 采用了拉链法，又被称为链地址法，简单来说，就是数组加链表的结合。结构实现来讲，HashMap 是数组 + 链表 + 红黑树（JDK1.8 增加了红黑树部分）实现的，如上图所示。HashMap 内部维护一个数组，每个数组元素称为一个哈希桶（bucket）。在每个数组元素上都存储了一个链表或红黑树的头节点，默认或者说初始为链表，而 HashMap 存储的数据即键值对就存在这些链表和红黑树的节点（Node 类对象，包含了键、值以及指向下一个节点的引用）。当 HashMap 中的键值对数量超过负载因子（默认为 0.75）与数组长度的乘积时，会触发扩容操作。扩容会创建一个更大的数组，并将原有的键值对重新分配到新的数组中，这个过程称为重新哈希。

可能有人会有疑问，为什么每个数组元素上是链表或红黑树，键值对存在它们的节点上，而不是直接将键值对存在每个数组元素上（每个数组元素存且仅存一个键值对）？

答案是为了解决哈希冲突。存储键值对的时候，会先取得 key 的哈希值，然后对哈希值进行一系列操作得到哈希桶的索引位置，即数组下标，该下标即为该键值对实际存储的位置。理想情况下，哈希值不同应该意味着最终得到的存储位置不同。然而，在实际情况下，不同的哈希值可能得到相同的存储位置，这被称为哈希冲突。哈希冲突是由于哈希值的范围通常比存储桶的数量（数组长度）要大，因此不同的哈希值可能映射到相同的索引位置上。为了解决哈希冲突，即不同键值对的存储位置相同，HashMap 使用了链表和红黑树，使得同一个位置能存多个键值对。

lang 包下的常用类

java.lang 包是提供利用 Java 编程语言进行程序设计的基础类，在项目中使用的时候不需要 import。下图为其架构。

下面介绍一些 lang 包的常用类的常用方法。

1. 超类

1. Object 类

Object 类是所有类的父类，也就是说 Java 的所有类都继承了 Object，子类可以使用 Object 的所有方法。

常用方法：

1. 获取对象的运行时 class 对象。class 对象就是描述对象所属类的对象。这个方法通常是和 Java 反射机制搭配使用的。

   Class<?> getClass();

2. 获取对象的哈希值。Object 中该方法默认返回的是对象的堆内存地址。

   int hashCode();

3. 该方法用于比较两个对象，如果这两个对象引用指向的是同一个对象，那么返回 true，否则返回 false 。一般 equals() 和 == 是不一样的，但是在 Object 中两者是一样的。子类一般都要重写这个方法。

   boolean equals(Obbject o);

4. 该方法是保护方法，实现对象的浅复制，只有实现了 Cloneable 接口才可以调用该方法，否则抛出异常。

   Object clone();

5. 返回一个 String 对象，一般子类都有覆盖。默认返回格式如下：对象的 class 名称 + @ + 哈希值的十六进制字符串。

   String toString();

2. 包装类

Java 语言是一个面向对象的语言，但是 Java 中的基本数据类型却是不面向对象的，这在实际使用时存在很多的不便。为了解决这个不足，在设计类时为每个基本数据类型设计了一个对应的类进行代表，这样八个和基本数据类型对应的类统称为包装类（Wrapper Class）。如下表所示：

接下来介绍下一些常用包装类的使用方法。

1. Integer 类

1. 在数字上比较两个 Integer 对象。如果比参数小，则返回 -1；如果相等，则返回 0；如果比参数大，则返回 1。

   int compareTo(Integer anotherInteger);

2. 以 double 类型返回该 Integer 的值。

   double doubleValue();

3. 以 float 类型返回该 Integer 的值。

   float floatValue();

4. 以 long 类型返回该 Integer 的值。

   long longValue();

5. 以 int 类型返回该 Integer 的值。

   int intValue();

6. 返回一个表示该 Integer 值的 String 对象。

   String toString();

7. 返回一个表示指定的 int 值的 Integer 实例。

   static Integer valueOf(int i);

8. 返回保存指定的 String 的值的 Integer 对象。

   static Integer valueOf(String s);

2. Character 类

1. 返回此 Character 对象的值。

   char charValue();

2. 确定字符是否被定义为 Unicode 中的字符。

   static boolean isDefined(char ch);

3. 确定字符（Unicode 代码点）是否被定义为 Unicode 中的字符。

   static boolean isDefined(int codePoint);

4. 确定指定字符是否为数字。

   static boolean isDigit(char ch);

5. 确定指定字符（Unicode 代码点）是否为数字。

   static boolean isDigit(int codePoint);

6. 确定指定字符是否为字母。

   static boolean isLetter(char ch);

7. 确定指定字符（Unicode 代码点）是否为字母。

   static boolean isLetter(int codePoint);

8. 确定指定字符是否为字母或数字。

   static boolean isLetterOrDigit(char ch);

9. 确定指定字符（Unicode 代码点）是否为字母或数字。

   static boolean isLetterOrDigit(int codePoint);

10. 确定指定字符是否为小写字母。

    static boolean isLowerCase(char ch);

11. 确定指定字符是否为大写字母。

    static boolean 	isUpperCase(char ch);

12. 确定指定字符是否为 Unicode 空白字符。

    static boolean isSpaceChar(char ch);

13. 确定指定字符依据 Java 标准是否为空白字符。

    static boolean isWhitespace(char ch);

14. 返回表示此 Character 值的 String 对象。

    String toString();

15. 返回一个表示指定 char 值的 Character 实例。

    static Character valueOf(char ch);

3. Boolean 类

1. 将此 Boolean 对象的值作为基本布尔值返回。

   boolean	booleanValue();

2. 将字符串参数解析为 boolean 值。当且仅当 String 参数不是 null 且在忽略大小写时等于 "true" 时，才返回 true ，否则均返回 false 。

   static boolean	parseBoolean(String s);

3. 返回一个表示指定布尔值的 String 对象。

static String	toString(boolean b);

4. 返回一个表示指定 boolean 值的 Boolean 实例。

   static Boolean	valueOf(boolean b);

3. 字符串类

1. String 类

1. 返回指定索引处的 char 值。

   char charAt(int index);

2. 考虑大小写，按字典顺序比较两个字符串。

   int compareTo(String anotherString);

3. 不考虑大小写，按字典顺序比较两个字符串。

   int	compareToIgnoreCase(String str);

4. 将指定字符串连接到此字符串的结尾。

   String concat(String str);

5. 返回指定数组中表示该字符序列的 String。

   static String copyValueOf(char[] data);

6. 测试此字符串是否以指定的前缀开始。

   boolean	startsWith(String prefix);

7. 测试此字符串是否以指定的后缀结束。

   boolean	endsWith(String suffix);

8. 不考虑大小写，将此 String 与另一个 String 比较。

   boolean	equalsIgnoreCase(String anotherString);

9. 返回指定字符在此字符串中第一次出现处的索引。

   int	indexOf(int ch);

10. 返回指定子字符串在此字符串中第一次出现处的索引。

    int	indexOf(String str);

11. 返回指定字符在此字符串中最后一次出现处的索引。

    int	lastIndexOf(int ch);

12. 返回指定子字符串在此字符串中最右边出现处的索引。

    int	lastIndexOf(String str);

13. 返回此字符串的长度。

    int	length();

14. 只有长度为 0 时返回 true。

    boolean	isEmpty();

15. 告知此字符串是否匹配给定的正则表达式。

    boolean	matches(String regex);

16. 返回一个新的字符串，它是通过用 newChar 替换此字符串中出现的所有 oldChar 得到的。

    String	replace(char oldChar, char newChar);

17. 根据给定正则表达式的匹配拆分此字符串，返回一个字符串数组。

    String[] split(String regex);

18. 将此字符串转换为一个新的字符数组。

    char[] toCharArray();

19. 使用默认语言环境的规则将此 String 中的所有字符都转换为小写。

    String toLowerCase();

20. 使用默认语言环境的规则将此 String 中的所有字符都转换为大写。

    String toUpperCase();

2. StringBuffer 类

1. 将 char 参数的字符串表示形式追加到此序列。

   StringBuffer append(char c);

2. 将 char 数组参数的字符串表示形式追加到此序列。

   StringBuffer append(char[] str);

3. 将 int 参数的字符串表示形式追加到此序列。

   StringBuffer append(int i);

4. 追加 Object 参数的字符串表示形式。

   StringBuffer append(Object obj);

5. 将指定的字符串追加到此字符序列。

   StringBuffer append(String str);

6. 将指定的 StringBuffer 追加到此序列中。

   StringBuffer append(StringBuffer sb);

7. 返回当前容量。

   int	capacity();

8. 返回此序列中指定索引处的 char 值。

   char charAt(int index);

9. 移除此序列的子字符串中的字符。

   StringBuffer delete(int start, int end);

10. 移除此序列指定位置的 char。

    StringBuffer deleteCharAt(int index);

11. 返回第一次出现的指定子字符串在该字符串中的索引。

    int	indexOf(String str);

12. 返回最后一次出现的指定子字符串在此字符串中的索引。

    int	lastIndexOf(String str);

13. 将 char 参数的字符串表示形式插入此序列中。

    StringBuffer insert(int offset, char c);

14. 将 char 数组参数的字符串表示形式插入此序列中。

    StringBuffer insert(int offset, char[] str);

15. 返回长度（字符数）。

    int	length();

16. 使用给定 String 中的字符替换此序列的子字符串中的字符。

    StringBuffer replace(int start, int end, String str);

17. 将此字符序列用其反转形式取代。

    StringBuffer reverse();

18. 将给定索引处的字符设置为 ch 。

    void setCharAt(int index, char ch);

19. 回一个新的 String，它包含此字符序列当前所包含的字符子序列。

    String substring(int start);

20. 返回一个新的 String，它包含此序列当前所包含的字符子序列。

    String substring(int start, int end);

21. 返回此序列中数据的字符串表示形式。

    String	toString();

22. 尝试减少用于字符序列的存储空间。

    void trimToSize();

3. 运算类

1. Math 类

1. 返回 int 值的绝对值。

   static int abs(int a);

2. 返回 double 值的绝对值。

   static double abs(double a)

3. 返回 double 值的立方根。

   static double cbrt(double a);

4. 返回最小的（最接近负无穷大）double 值，该值大于等于参数，并等于某个整数。

   static double ceil(double a);

5. 返回最大的（最接近正无穷大）double 值，该值小于等于参数，并等于某个整数。

   static double floor(double a);

6. 返回 double 值的自然对数（底数是 e）。

   static double log(double a);

7. 返回 double 值的底数为 10 的对数。

   static double log10(double a);

8. 返回两个 int 值中较大的一个。

   static int max(int a, int b);

9. 返回两个 double 值中较大的一个。

   static double max(double a, double b);

10. 返回两个 int 值中较小的一个。

    static int min(int a, int b);

11. 返回两个 double 值中较小的一个。

    static double min(double a, double b);

12. 返回角的三角正弦。

    static double sin(double a);

13. 返回角的三角余弦。

    static double cos(double a);

14. 返回角的三角正切。

    static double tan(double a);

15. 将用弧度表示的角转换为近似相等的用角度表示的角。

    static double toDegrees(double angrad);

16. 将用角度表示的角转换为近似相等的用弧度表示的角。

    static double toRadians(double angdeg);

结语

1. 再次强调，本节课内容较多，并涉及到一些数据结构知识，如果是第一次接触的话，记不住也没关系，不用太担心（千万不要因为觉得这节课没完全学会，下节课就不来听了呀 o(╥﹏╥)o）。作为初学者，可以先了解了解，在脑海中留个印象，建立个大致的知识体系。在日后的实际使用中，如果出现了问题，再去网上查阅即可。此外，平日里常用的集合、数据结构和方法也就那么多。正所谓熟能生巧，使用多了，自然就熟悉了，自然就掌握了。
2. 其他请见 “前言”。