java集合类学习笔记

集合

1 集合框架

1.1 集合框架概述

1.1.1 容器简介

到目前为止，我们已经学习了如何创建多个不同的对象，定义了这些对象以后，我们就可以利用它们来做一些有意义的事情。

举例来说，假设要存储许多雇员，不同的雇员的区别仅在于雇员的身份证号。我们可以通过身份证号来顺序存储每个雇员，但是在内存中实现呢？是不是要准备足够的内存来存储1000个雇员，然后再将这些雇员逐一插入？如果已经插入了500条记录，这时需要插入一个身份证号较低的新雇员，该怎么办呢？是在内存中将500条记录全部下移后，再从开头插入新的记录? 还是创建一个映射来记住每个对象的位置？当决定如何存储对象的集合时，必须考虑如下问题。 对于对象集合，必须执行的操作主要以下三种：

? 添加新的对象 ? 删除对象 ? 查找对象

我们必须确定如何将新的对象添加到集合中。可以将对象添加到集合的末尾、开头或者中间的某个逻辑位置。

从集合中删除一个对象后，对象集合中现有对象会有什么影响呢？可能必须将内存移来移去，或者就在现有对象所驻留的内存位置下一个“洞”。

在内存中建立对象集合后，必须确定如何定位特定对象。可建立一种机制，利用该机制可根据某些搜索条件（例如身份证号）直接定位到目标对象；否则，便需要遍历集合中的每个对象，直到找到要查找的对象为止。

前面大家已经学习过了数组。数组的作用是可以存取一组数据。但是它却存在一些缺点，使得无法使用它来比较方便快捷的完成上述应用场景的要求。

1. 首先，在很多数情况下面，我们需要能够存储一组数据的容器，这一点虽然数组可以实现，

但是如果我们需要存储的数据的个数多少并不确定。比如说：我们需要在容器里面存储某

个应用系统的当前的所有的在线用户信息，而当前的在线用户信息是时刻都可能在变化的。 也就是说，我们需要一种存储数据的容器，它能够自动的改变这个容器的所能存放的数据数量的大小。这一点上，如果使用数组来存储的话，就显得十分的笨拙。

1

2. 我们再假设这样一种场景：假定一个购物网站，经过一段时间的运行，我们已经存储了一

系列的购物清单了，购物清单中有商品信息。如果我们想要知道这段时间里面 有多少种商品被销售出去了。那么我们就需要一个容器能够自动的过滤掉购物清单中的关于商品的重复信息。如果使用数组，这也是很难实现的。

3. 最后再想想，我们经常会遇到这种情况，我知道某个人的帐号名称，希望能够进一步了解

这个人的其他的一些信息。也就是说，我们在一个地方存放一些用户信息，我 们希望能够

通过用户的帐号来查找到对应的该用户的其他的一些信息。再举个查字典例子：假设我们希望使用一个容器来存放单词以及对于这个单词的解释，而当我 们想要查找某个单词的意思的时候，能够根据提供的单词在这个容器中找到对应的单词的解释。如果使用数组来实

现的话，就更加的困难了。

为解决这些问题，Java里面就设计了容器集合，不同的容器集合以不同的格式保存对象。

数学背景

在常见用法中，集合（collection）和数学上直观的集（set）的概念是相同的。集是一个唯一项组，也就是说组中没有重复项。实际上，“集合框架”包含了一个 Set 接口和许多具体的 Set 类。但正式的集概念却比 Java 技术提前了一个世纪，那时英国数学家 George Boole 按逻辑正式的定义了集的概念。大部分人在小学时通过我们熟悉的维恩图引入的“集的交”和“集的并”学到过一些集的理论。 集的基本属性如下：

? 集内只包含每项的一个实例

? 集可以是有限的，也可以是无限的 ? 可以定义抽象概念

集不仅是逻辑学、数学和计算机科学的基础，对于商业和系统的日常应用来说，它也很实用。“连接池”这一概念就是数据库服务器的一个开放连接集。Web 服务器必须管理客户机和连接集。文件描述符提供了操作系统中另一个集的示例。

映射是一种特别的集。它是一种对（pair）集，每个对表示一个元素到另一元素的单向映射。一些映射示例有：

? IP 地址到域名（DNS）的映射 ? 关键字到数据库记录的映射 ? 字典（词到含义的映射）

? 2 进制到 10 进制转换的映射

就像集一样，映射背后的思想比 Java 编程语言早的多，甚至比计算机科学还早。而Java中的Map 就是映射的一种表现形式。

2

1.1.2 容器的分类

既然您已经具备了一些集的理论，您应该能够更轻松的理解“集合框架”。 “集合框架”由 一组用来操作对象的接口组成。不同接口描述不同类型的组。在很大程度上，一旦您理解了接口，您就理解了框架。虽然您总要创建接口特定的实现，但访问实际集合的方法应该限制在接口方法的使用上；因此，允许您更改基本的数据结构而不必改变其它代码。框架接口层次结构如下图所示。

Java容器类类库的用途是“保存对象”，并将其划分为两个不同的概念：

1） Collection 。 一组对立的元素，通常这些元素都服从某种规则。List必须保持元素特定的顺序，而Set不能有重复元素。

2） Map 。 一组 成对的“键值对”对象。初看起来这似乎应该是一个Collection ，其元素是成对

的对象，但是这样的设计实现起来太笨拙了，于是我们将Map明确的提取出来形成一个独立的概念。另一方面，如果使用Collection 表示Map的部分内容，会便于查看此部分内容。因此Map一样容易扩展成多维Map ，无需增加新的概念，只要让Map中的键值对的每个“值”也是一个Map即可。

Collection和Map的区别在于容器中每个位置保存的元素个数。Collection 每个位置只能保存一个元素（对象）。此类容器包括：List ，它以特定的顺序保存一组元素；Set 则是元素不能重复。 Map保存的是“键值对”，就像一个小型数据库。我们可以通过“键”找到该键对应的“值”。

? Collection – 对象之间没有指定的顺序，允许重复元素。 ? Set – 对象之间没有指定的顺序，不允许重复元素

? List– 对象之间有指定的顺序，允许重复元素,并引入位置下标。

? Map – 接口用于保存关键字（Key）和数值（Value）的集合，集合中的每个对象加入时

都提供数值和关键字。Map 接口既不继承 Set 也不继承 Collection。

List、Set、Map共同的实现基础是Object数组

除了四个历史集合类外，Java 2 框架还引入了六个集合实现，如下表所示。 接口 Set List Map 实现 HashSet TreeSet 历史集合类 ArrayList Vector LinkedList Stack HashMap TreeMap Hashtable Properties 3

这里没有 Collection 接口的实现，接下来我们再来看一下下面的这张关于集合框架的大图： 这张图看起来有点吓人，熟悉之后就会发现其实只有三种容器：Map，List和Set ，它们各自有两个三个实现版本。常用的容器用黑色粗线框表示。

点线方框代表“接口”，虚线方框代表抽象类，而实线方框代表普通类（即具体类，而非抽象类）。虚线箭头指出一个特定的类实现了一个接口（在抽象类的情况下，则是“部分”实现了那个接口）。实线箭头指出一个类可生成箭头指向的那个类的对象。例如任何集合( Collection )都能产生一个迭代器( Iterator )，而一个List 除了能生成一个ListIterator （列表迭代器）外,还能生成一个普通迭代器,因为List 正是从集合继承来的.

1.2 Collection

1.2.1 常用方法

Collection 接口用于表示任何对象或元素组。想要尽可能以常规方式处理一组元素时，就使用这一接口。Collection 在前面的大图也可以看出，它是List和Set 的父类。并且它本身也是一个接口。它定义了作为集合所应该拥有的一些方法。如下： 注意:

集合必须只有对象，集合中的元素不能是基本数据类型。

Collection接口支持如添加和除去等基本操作。设法除去一个元素时，如果这个元素存在，除去的仅仅是集合中此元素的一个实例。

? boolean add(Object element) ? boolean remove(Object element) Collection 接口还支持查询操作：

? int size() ? boolean isEmpty()

? boolean contains(Object element)

? Iterator iterator()

组操作 ：Collection 接口支持的其它操作，要么是作用于元素组的任务，要么是同时作用于整个集合的任务。

? boolean containsAll(Collection collection)

4

? boolean addAll(Collection collection) ? void clear()

? void removeAll(Collection collection) ? void retainAll(Collection collection)

containsAll() 方法允许您查找当前集合是否包含了另一个集合的所有元素，即另一个集合是否是当前集合的子集。其余方法是可选的，因为特定的集合可能不支持集合更改。 addAll() 方法确保另一个集合中的所有元素都被添加到当前的集合中，通常称为并。 clear() 方法从当前集合中除去所有元素。 removeAll() 方法类似于 clear() ，但只除去了元素的一个子集。 retainAll() 方法类似于 removeAll() 方法，不过可能感到它所做的与前面正好相反：它从当前集合中除去不属于另一个集合的元素，即交。

我们看一个简单的例子，来了解一下集合类的基本方法的使用： import java.util.*;

public class CollectionToArray {

public static void main(String[] args) {

Collection collection1=new ArrayList();//创建一个集合对象 collection1.add(\);//添加对象到Collection集合中 collection1.add(\); collection1.add(\);

System.out.println(\集合collection1的大小：\+collection1.size()); System.out.println(\集合collection1的内容：\+collection1);

collection1.remove(\);//从集合collection1中移除掉 \这个对象 System.out.println(\集合collection1移除 000 后的内容：\+collection1); System.out.println(\集合collection1中是否包含000 ：\+collection1.contains(\));

System.out.println(\集合collection1中是否包含111 ：\+collection1.contains(\));

Collection collection2=new ArrayList();

collection2.addAll(collection1);//将collection1 集合中的元素全部都加到collection2中

System.out.println(\集合collection2的内容：\+collection2); collection2.clear();//清空集合 collection1 中的元素

System.out.println(\集合collection2是否为空 ：\+collection2.isEmpty()); //将集合collection1转化为数组 Object s[]= collection1.toArray();

5

for(int i=0;i

运行结果为：

集合collection1的大小：3

集合collection1的内容：[000, 111, 222] 集合collection1移除 000 后的内容：[111, 222] 集合collection1中是否包含000 ：false 集合collection1中是否包含111 ：true 集合collection2的内容：[111, 222] 集合collection2是否为空 ：true 111 222

这里需要注意的是，Collection 它仅仅只是一个接口，而我们真正使用的时候，确是创建该接口的一个实现类。做为集合的接口，它定义了所有属于集合的类所都应该具有的一些方法。 而ArrayList （列表）类是集合类的一种实现方式。

这里需要一提的是，因为Collection的实现基础是数组，所以有转换为Object数组的方法：

? Object[] toArray() ? Object[] toArray(Object[] a)

其中第二个方法Object[] toArray(Object[] a) 的参数 a 应该是集合中所有存放的对象的类的父类。

1.2.2 迭代器

任何容器类，都必须有某种方式可以将东西放进去，然后由某种方式将东西取出来。毕竟，存放事物是容器最基本的工作。对于ArrayList，add（）是插入对象的方法，而get()是取出元素的方式之一。ArrayList很灵活，可以随时选取任意的元素，或使用不同的下标一次选取多个元素。 如果从更高层的角度思考，会发现这里有一个缺点：要使用容器，必须知道其中元素的确切类型。初看起来这没有什么不好的，但是考虑如下情况：如果原本是ArrayList ，但是后来考虑到容器的

6

特点，你想换用Set ，应该怎么做？或者你打算写通用的代码，它们只是使用容器，不知道或者说不关心容器的类型，那么如何才能不重写代码就可以应用于不同类型的容器？

所以迭代器(Iterator)的概念，也是出于一种设计模式就是为达成此目的而形成的。所以Collection不提供get()方法。如果要遍历Collectin中的元素，就必须用Iterator。

迭代器（Iterator）本身就是一个对象，它的工作就是遍历并选择集合序列中的对象，而客户端的程序员不必知道或关心该序列底层的结构。此外，迭代器通常被称为“轻量级”对象，创建它的代价小。但是，它也有一些限制，例如，某些迭代器只能单向移动。

Collection 接口的 iterator() 方法返回一个 Iterator。Iterator 和您可能已经熟悉的 Enumeration 接口类似。使用 Iterator 接口方法，您可以从头至尾遍历集合，并安全的从底层 Collection 中除去元素。

下面，我们看一个对于迭代器的简单使用：

import java.util.ArrayList; import java.util.Collection; import java.util.Iterator;

public class IteratorDemo {

public static void main(String[] args) { Collection collection = new ArrayList(); collection.add(\); collection.add(\); collection.add(\);

Iterator iterator = collection.iterator();//得到一个迭代器 while (iterator.hasNext()) {//遍历 Object element = iterator.next();

System.out.println(\ + element); }

if(collection.isEmpty())

System.out.println(\); else

7

System.out.println(\+collection.size()); Iterator iterator2 = collection.iterator(); while (iterator2.hasNext()) {//移除元素 Object element = iterator2.next(); System.out.println(\+element); iterator2.remove(); }

Iterator iterator3 = collection.iterator(); if (!iterator3.hasNext()) {//察看是否还有元素 System.out.println(\还有元素\); }

if(collection.isEmpty())

System.out.println(\); //使用collection.isEmpty()方法来判断 } }

程序的运行结果为： iterator = s1 iterator = s2 iterator = s3

collection is not Empty! size=3 remove: s1 remove: s2 remove: s3 还有元素

collection is Empty!

可以看到，Java的Collection的Iterator 能够用来，：

1) 使用方法 iterator() 要求容器返回一个Iterator .第一次调用Iterator 的next() 方法时，它

返回集合序列的第一个元素。

2) 使用next() 获得集合序列的中的下一个元素。 3) 使用hasNext()检查序列中是否元素。 4) 使用remove()将迭代器新返回的元素删除。

8

需要注意的是：方法删除由next方法返回的最后一个元素，在每次调用next时，remove方法只能被调用一次 。

大家看，Java 实现的这个迭代器的使用就是如此的简单。Iterator（跌代器）虽然功能简单，但仍然可以帮助我们解决许多问题，同时针对List 还有一个更复杂更高级的ListIterator。您可以在下面的List讲解中得到进一步的介绍。

1.3 List

1.3.1 概述

前面我们讲述的Collection接口实际上并没有直接的实现类。而List是容器的一种，表示列表的意思。当我们不知道存储的数据有多少的情况，我们就可以使用List 来完成存储数据的工作。例如前面提到的一种场景。我们想要在保存一个应用系统当前的在线用户的信息。我们就可以使用一个List来存储。因为List的最大的特点就是能够自动的根据插入的数据量来动态改变容器的大小。下面我们先看看List接口的一些常用方法。 1.3.2 常用方法

List 就是列表的意思，它是Collection 的一种，即继承了 Collection 接口，以定义一个允许重复项的有序集合。该接口不但能够对列表的一部分进行处理，还添加了面向位置的操作。List 是按对象的进入顺序进行保存对象，而不做排序或编辑操作。它除了拥有Collection接口的所有的方法外还拥有一些其他的方法。

面向位置的操作包括插入某个元素或 Collection 的功能，还包括获取、除去或更改元素的功能。在 List 中搜索元素可以从列表的头部或尾部开始，如果找到元素，还将报告元素所在的位置。

? void add(int index, Object element) ：添加对象element到位置index上

? boolean addAll(int index, Collection collection) ：在index位置后添加容器collection中所有

的元素 ? Object get(int index) ：取出下标为index的位置的元素

? int indexOf(Object element) ：查找对象element 在List中第一次出现的位置 ? int lastIndexOf(Object element) ：查找对象element 在List中最后出现的位置 ? Object remove(int index) ：删除index位置上的元素

? Object set(int index, Object element) ：将index位置上的对象替换为element 并返回老的元

素。

9

先看一下下面表格： 简述 实现 操作特性 提供快速的基于索引的成员访成员要求 成员可为任意ArrayList 问，对尾部成员的增加和删除Object子类的对象

支持较好 提供基于索List 引的对成员的随机访问 对列表中任何位置的成员的增LinkedList 加和删除支持较好，但对基于成员可为任意Object子类的对象

索引的成员访问支持性能较差 在“集合框架”中有两种常规的 List 实现：ArrayList 和 LinkedList。使用两种 List 实现的哪一种取决于您特定的需要。如果要支持随机访问，而不必在除尾部的任何位置插入或除去元素，那么，ArrayList 提供了可选的集合。但如果，您要频繁的从列表的中间位置添加和除去元素，而只要顺序的访问列表元素，那么，LinkedList 实现更好。

我们以ArrayList 为例，先看一个简单的例子：

例子中，我们把12个月份存放到ArrayList 中，然后用一个循环，并使用get（）方法将列表中的对象都取出来。

而LinkedList 添加了一些处理列表两端元素的方法（下图只显示了新方法）：

使用这些新方法，您就可以轻松的把 LinkedList 当作一个堆栈、队列或其它面向端点的数据结构。

我们再来看另外一个使用LinkedList 来实现一个简单的队列的例子： import java.util.*;

public class ListExample {

public static void main(String args[]) { LinkedList queue = new LinkedList(); queue.addFirst(\); queue.addFirst(\);

10

? 如果elem不为null 的话，我们也是遍历数组elementData ，并通过调用elem对象的equals()方法来得到第一个相等的元素的位置。

这里我们可以发现，ArrayList中用来判断是否包含一个对象，调用的是各个对象自己实现的equals()方法。在前面的高级特性里面，我们可以知道：如果要判断一个类的一个实例对象是否等于另外一个对象，那么我们就需要自己覆写Object类的public boolean

equals(Object obj) 方法。如果不覆写该方法的话，那么就会调用Object的equals()方法来进行判断。这就相当于比较两个对象的内存应用地址是否相等了。

在集合框架中，不仅仅是List，所有的集合类，如果需要判断里面是否存放了的某个对象，都是调用该对象的equals()方法来进行处理的。

1.4 Map

1.4.1 概述

数学中的映射关系在Java中就是通过Map来实现的。它表示，里面存储的元素是一个对（pair）,我们通过一个对象，可以在这个映射关系中找到另外一个和这个对象相关的东西。

前面提到的我们对于根据帐号名得到对应的人员的信息，就属于这种情况的应用。我们讲一个人员的帐户名和这人员的信息作了一个映射关系，也就是说，我们把帐户名和人员信息当成了一个“键值对”，“键”就是帐户名，“值”就是人员信息。下面我们先看看Map 接口的常用方法。

1.4.2 常用方法

Map 接口不是 Collection 接口的继承。而是从自己的用于维护键-值关联的接口层次结构入手。按定义，该接口描述了从不重复的键到值的映射。

我们可以把这个接口方法分成三组操作：改变、查询和提供可选视图。

改变操作允许您从映射中添加和除去键-值对。键和值都可以为 null。但是，您不能把 Map 作为一个键或值添加给自身。

? Object put(Object key,Object value)：用来存放一个键-值对Map中

? Object remove(Object key)：根据key(键)，移除一个键-值对，并将值返回 ? void putAll(Map mapping) ：将另外一个Map中的元素存入当前的Map中 ? void clear() ：清空当前Map中的元素 查询操作允许您检查映射内容：

? Object get(Object key) ：根据key(键)取得对应的值

? boolean containsKey(Object key) ：判断Map中是否存在某键（key） ? boolean containsValue(Object value):判断Map中是否存在某值(value) ? int size():返回Map中 键-值对的个数

16

? boolean isEmpty() ：判断当前Map是否为空

最后一组方法允许您把键或值的组作为集合来处理。

? public Set keySet() ：返回所有的键（key），并使用Set容器存放

? public Collection values() ：返回所有的值（Value），并使用Collection存放

? public Set entrySet() ：返回一个实现 Map.Entry 接口的元素 Set

因为映射中键的集合必须是唯一的，就使用 Set 来支持。因为映射中值的集合可能不唯一，就使用 Collection 来支持。最后一个方法返回一个实现 Map.Entry 接口的元素 Set。 我们看看Map的常用实现类的比较，如下表： 简述 实现 操作特性 成员要求 键成员可为任意Object子类的对象，但如果覆盖了equals方法，同时注意修改hashCode方法。 HashMap 能满足用户对Map的通用需求 保存键值对成员，基于键找值Map 操作，使用compareTo或compare方法对键进行排序 TreeMap 支持对键有序地遍历，使用时建议先用HashMap增加和删除键成员要求实现成员，最后从HashMap生成Comparable接口，或者使用Comparator构TreeMap； 附加实现造TreeMap键成员一了SortedMap接口，般为同一类型。 支持子Map等要求顺序的操作 成员可为任意Object保留键的插入顺序，子类的对象，但如果覆LinkedHashMap 用equals 方法检查键盖了equals方法，同时和值的相等性 注意修改hashCode方法。 下面我们看一个简单的例子：

import java.util.*;

public class MapTest {

public static void main(String[] args) { Map map1 = new HashMap();

17

Map map2 = new HashMap(); map1.put(\,\); map1.put(\,\); map2.put(\,\); map2.put(\,\);

//根据键 \取得值：\

System.out.println(\+map1.get(\));

// 根据键 \移除键值对\

System.out.println(\+map1.remove(\)); System.out.println(\+map1.get(\)); map1.putAll(map2);//将map2全部元素放入map1中 map2.clear();//清空map2

System.out.println(\+map1.isEmpty()); System.out.println(\+map2.isEmpty());

System.out.println(\中的键值对的个数size = \+map1.size()); System.out.println(\+map1.keySet());//set System.out.println(\+map1.values());//Collection System.out.println(\+map1.entrySet());

System.out.println(\是否包含键：11 = \+map1.containsKey(\)); System.out.println(\是否包含值：aaa1 = \+map1.containsValue(\)); } }

运行输出结果为： map1.get(\ map1.remove(\ map1.get(\ map1 IsEmpty?=false map2 IsEmpty?=true

map1 中的键值对的个数size = 3 KeySet=[10, 2, 11]

values=[aaaa10, bbb2, bbbb11]

entrySet=[10=aaaa10, 2=bbb2, 11=bbbb11] map1 是否包含键：11 = true map1 是否包含值：aaa1 = false

在该例子中，我们创建一个HashMap，并使用了一下Map接口中的各个方法。

18

其中Map中的entrySet()方法先提一下，该方法返回一个实现 Map.Entry 接口的对象集合。集合中每个对象都是底层 Map 中一个特定的键-值对。

Map.Entry 接口是Map 接口中的一个内部接口，该内部接口的实现类存放的是键值对。在下面的实现原理中，我们会对这方面再作介绍，现在我们先不管这个它的具体实现。 我们再看看排序的Map是如何使用： import java.util.*;

public class MapSortExample {

public static void main(String args[]) { Map map1 = new HashMap(); Map map2 = new LinkedHashMap(); for(int i=0;i<10;i++){

double s=Math.random()*100;//产生一个随机数，并将其放入Map中 map1.put(new Integer((int) s),\第 \+i+\个放入的元素：\+s+\); map2.put(new Integer((int) s),\第 \+i+\个放入的元素：\+s+\); }

System.out.println(\未排序前HashMap：\+map1); System.out.println(\未排序前LinkedHashMap：\+map2); //使用TreeMap来对另外的Map进行重构和排序 Map sortedMap = new TreeMap(map1); System.out.println(\排序后：\+sortedMap);

System.out.println(\排序后：\+new TreeMap(map2)); } }

该程序的一次运行结果为：

未排序前HashMap：{64=第 1 个放入的元素：64.05341725531845 , 15=第 9 个放入的元素：15.249165766266382 , 2=第 4 个放入的元素：2.66794706854534 , 77=第 0 个放入的元素：77.28814965781416 , 97=第 5 个放入的元素：97.32893518378948 , 99=第 2 个放入的元素：99.99412014935982 , 60=第 8 个放入的元素：60.91451419025399 , 6=第 3 个放入的元素：6.286974058646977 , 1=第 7 个放入的元素：1.8261658496439903 , 48=第 6 个放入的元素：48.736039522423106

19

}

未排序前LinkedHashMap：{77=第 0 个放入的元素：77.28814965781416 , 64=第 1 个放入的元素：64.05341725531845 , 99=第 2 个放入的元素：99.99412014935982 , 6=第 3 个放入的元素：6.286974058646977 , 2=第 4 个放入的元素：2.66794706854534 , 97=第 5 个放入的元素：97.32893518378948 , 48=第 6 个放入的元素：48.736039522423106 , 1=第 7 个放入的元素：1.8261658496439903 , 60=第 8 个放入的元素：60.91451419025399 , 15=第 9 个放入的元素：15.249165766266382 }

排序后：{1=第 7 个放入的元素：1.8261658496439903 , 2=第 4 个放入的元素：2.66794706854534 , 6=第 3 个放入的元素：6.286974058646977 , 15=第 9 个放入的元素：15.249165766266382 , 48=第 6 个放入的元素：48.736039522423106 , 60=第 8 个放入的元素：60.91451419025399 , 64=第 1 个放入的元素：64.05341725531845 , 77=第 0 个放入的元素：77.28814965781416 , 97=第 5 个放入的元素：97.32893518378948 , 99=第 2 个放入的元素：99.99412014935982 }

排序后：{1=第 7 个放入的元素：1.8261658496439903 , 2=第 4 个放入的元素：2.66794706854534 , 6=第 3 个放入的元素：6.286974058646977 , 15=第 9 个放入的元素：15.249165766266382 , 48=第 6 个放入的元素：48.736039522423106 , 60=第 8 个放入的元素：60.91451419025399 , 64=第 1 个放入的元素：64.05341725531845 , 77=第 0 个放入的元素：77.28814965781416 , 97=第 5 个放入的元素：97.32893518378948 , 99=第 2 个放入的元素：99.99412014935982 }

从运行结果，我们可以看出，HashMap的存入顺序和输出顺序无关。而LinkedHashMap 则保留了键值对的存入顺序。TreeMap则是对Map中的元素进行排序。在实际的使用中我们也经常这

20

Collection/Map 接口 成员重复性 元素存放顺序（Ordered/Sorted） order of entries 元素中被调用的方法 hashCode() equals() hashCode() equals() compareTo() 基于那中数来实现表 Hash 表 Hashtable Map Unique keys No order TreeMap SortedMap Unique keys Sorted in key order 平衡树（Batree） 2练习

撰写一个Person class，表示一个人员的信息。令该类具备多辆Car的信息，表示一个人可以拥有的车子的数据，以及:

Certificate code： 身份证对象

name： 姓名

cash： 现金

List car; 拥有的汽车,其中存放的是Car对象 boolean buycar(car); 买车子

boolean sellcar(Person p);//把自己全部的车子卖给别人

boolean buyCar(Car car,Person p);//自动查找卖车的人p是否有买主想要买的车car，如果有就买,并返回true ,否则返回false

viod addCar(car);//把某辆车送给方法的调用者。 String toString();//得到人的信息

并撰写第二个Car class 具备的属性： String ID; //ID车牌号 cost //价格 color //颜色

Person owner; //车子的拥有者

toString();//得到汽车的信息

equals();//比较车子是否同一俩汽车，ID相同则认为相同

在另外一个Market类里面，进行车子的买卖。并保留所有交易人员的的信息到一个HashMap中，我们可以通过身份证号来查找到对应的人员的信息。同时所有的车子种类都在市场中进行注册，即车子的信息使用一个Set来保存 属性：

36

HashMap people;//存放交易人员的信息。Key为身份证号，value为Person对象 方法：

static boolean sellCar(Person p1 ,Car car1, Person p2);

//p1 将car1卖给 p2 。并在该方法中记录效益人的信息到people 中。 撰写类Certificate 表示身份证： 属性： Id;//号码

方法：

equals();//比较两个身份证是否同一个，ID相同则认为相同 hashCode();//正确编写hashCode 方法 场景：

一个叫Bob的人：身份证：310 现金：30000。

有一辆车子：ID:001,红色，价格：50000的车子; 一个叫Tom的人：身份证：210 现金：70000, 有一辆车子: 颜色：白色,ID:003, 价格：25000。 一个叫King 的人：身份证：245 现金：60000,

有2辆车子: 颜色：白色,ID:005, 价格：18000。

颜色：红色,ID:045, 价格：58000。

Tom 买了Bob的车子.他就拥有了2辆汽车 King 把ID=005的车子买给了Bob 最后各人的信息如何？

37

样做：使用HashMap或者LinkedHashMap 来存放元素，当所有的元素都存放完成后，如果使用则是需要一个经过排序的Map的话，我们再使用TreeMap来重构原来的Map对象。这样做的好处是：因为HashMap和LinkedHashMap 存储数据的速度比直接使用TreeMap 要快，存取效率要高。当完成了所有的元素的存放后，我们再对整个的Map中的元素进行排序。这样可以提高整个程序的运行的效率，缩短执行时间。

这里需要注意的是，TreeMap中是根据键（Key）进行排序的。而如果我们要使用TreeMap来进行正常的排序的话，Key 中存放的对象必须实现Comparable 接口。 我们简单介绍一下这个接口：

1.4.3 Comparable 接口

在 java.lang 包中，Comparable 接口适用于一个类有自然顺序的时候。假定对象集合是同一类型，该接口允许您把集合排序成自然顺序。

它只有一个方法：compareTo() 方 法，用来比较当前实例和作为参数传入的元素。如果排序过程中当前实例出现在参数前（当前实例比参数大），就返回某个负值。如果当前实例出现在参数后（当前 实例比参数小），则返回正值。否则，返回零。如果这里不要求零返回值表示元素相等。零返回值可以只是表示两个对象在排序的时候排在同一个位置。

上面例子中的整形的包装类：Integer 就实现了该接口。我们可以看一下这个类的源码：

可以看到compareTo 方法里面通过判断当前的Integer对象的值是否大于传入的参数的值来得到返回值的。 在 Java 2 SDK，版本 1.2 中有十四个类实现 Comparable 接口。下表展示了它们的自然排序。虽然一些类共享同一种自然排序，但只有相互可比的类才能排序。

类 BigDecimal, BigInteger, Byte, 按数字大小排序 Double, Float, Integer, Long, Short Character CollationKey Date File ObjectStreamField 按 Unicode 值的数字大小排序 按语言环境敏感的字符串排序 按年代排序 按系统特定的路径名的全限定字符的 Unicode 值排序 按名字中字符的 Unicode 值排序 排序 21

String

按字符串中字符 Unicode 值排序 这里只是简单的介绍一下排序接口，如果要详细的了解排序部分内容的话，可以参考文章最后的附录部分对于排序的更加详细的描述。

我们再回到Map中来，Java提高的API中除了上面介绍的几种Map比较常用以为还有一些Map，大家可以了解一下：

? WeakHashMap： WeakHashMap 是 Map 的一个特殊实现，它只用于存储对键的弱引用。

当映射的某个键在 WeakHashMap 的外部不再被引用时，就允许垃圾收集器收集映射中

相应的键值对。使用 WeakHashMap 有益于保持类似注册表的数据结构，其中条目的键不再能被任何线程访问时，此条目就没用了。

? IdentifyHashMap： Map的一种特性实现，关键属性的hash码不是由hashCode()

方法计算，而是由System.identityHashCode 方法计算，使用==进行比较而不是

equals()方法。

通过简单的对与Map中各个常用实现类的使用，为了更好的理解Map，下面我们再来了解一下Map的实现原理。

1.4.4 实现原理

有的人可能会认为 Map 会继承 Collection。在数学中，映射只是对（pair）的集合。但是，在“集合框架”中，接口 Map 和 Collection 在层次结构没有任何亲缘关系，它们是截然不同的。这种差别的原因与 Set 和 Map 在 Java 库中使用的方法有关。Map 的典型应用是访问按关键字存储的值。它支持一系列集合操作的全部，但操作的是键-值对，而不是单个独立的元素。因此 Map 需要支持 get() 和 put() 的基本操作，而 Set 不需要。此外，还有返回 Map 对象的 Set 视图的方法： Set set = aMap.keySet();

下面我们以HashMap为例，对Map的实现机制作一下更加深入一点的理解。

因为HashMap里面使用Hash算法，所以在理解HashMap之前，我们需要先了解一下Hash算法和Hash表。

Hash，一般翻译做“散列”，也有直接音译为\哈希\的，就是把任意长度的输入（又叫做 预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能 会散列成相同的输出，而不可能从散列值来唯一的确定输入值。

说的通俗一点，Hash算法的意义在于提供了一种快速存取数据的方法,它用一种算法建立键值与真实值之间的对应关系,(每一个真实值只能有一个键值,但是一个键值可以对应多个真实值),这样可以快速在数组等里面存取数据。

22

看下图：

我们建立一个HashTable（哈希表），该表的长度为N，然后我们分别在该表中的格子中存放不同的元素。每个格子下面存放的元素又是以链表的方式存放元素。

? 当添加一个新的元素Entry 的时候，首先我们通过一个Hash函数计算出这个Entry元素的Hash

值hashcode。通过该hashcode值，就可以直接定位出我们应该把这个Entry元素存入到Hash

表的哪个格子中，如果该格子中已经存在元素了，那么只要把新的Entry元存放到这个链表中即可。

? 如果要查找一个元素Entry的时候，也同样的方式，通过Hash函数计算出这个Entry元素的

Hash值hashcode。然后通过该hashcode值，就可以直接找到这个Entry是存放到哪个格子中的。接下来就对该格子存放的链表元素进行逐个的比较查找就可以了。 举一个比较简单的例子来说明这个算法的运算方式：

假定我们有一个长度为8的Hash表（可以理解为一个长度为8的数组）。在这个Hash表中存放数字：如下表 0 1 2 3 4 5 6 7 假定我们的Hash函数为：

Hashcode = X%8 -------- 对8 取余数

其中X就是我们需要放入Hash表中的数字，而这个函数返回的Hashcode就是Hash码。 假定我们有下面10个数字需要依次存入到这个Hash表中： 11 , 23 , 44 , 9 , 6 , 32 , 12 , 45 , 57 , 89

通过上面的Hash函数，我们可以得到分别对应的Hash码：

11――3 ; 23――7 ；44――4 ；9――1；6――6；32――0；12――4；45――5；57――1；89――1；

计算出来的Hash码分别代表，该数字应该存放到Hash表中的哪个对应数字的格子中。如果改格子中已经有数字存在了，那么就以链表的方式将数字依次存放在该格子中，如下表： 0 32 1 9 57 89 2 3 11 4 44 12 5 45 6 6 7 23 Hash表和Hash算法的特点就是它的存取速度比数组差一些，但是比起单纯的链表，在查找和存储方面却要好很多。同时数组也不利于数据的重构而排序等方面的要求。 更具体的说明，读者可以参考数据结构相关方面的书籍。

简单的了解了一下Hash算法后，我们就来看看HashMap的属性有哪些： 里面最重要的3个属性：

? transient Entry[] table: 用来存放键值对的对象

Entry数组，也就是Hash表

? transient int size：当前Map中存放的键值对的个数

23

? final float loadFactor：负载因子，用来决定什么情况下应该对Entry进行扩容 我们Entry 对象是Map接口中的一个内部接口。即是使用它来保存我们的键值对的。 我们看看这个Entry 内部接口在HashMap中的实现：

通过查看源码，我们可以看到Entry类有点类似一个单向链表。其中：

final Object key 和 Object value;存放的就是我们放入Map中的键值对。 而属性Entry next;表示当前键值对的下一个键值对是哪个Entry。

接下来，我们看看HashMap的主要的构造函数：

我们主要看看 public HashMap(int initialCapacity, float loadFactor) 因为，另外两个构造函数实行也是同样的方式进行构建一个HashMap 的。 该构造函数：

1. 首先是判断参数int initialCapacity和float loadFactor是否合法

2. 然后确定Hash表的初始化长度。确定的策略是：通过传进来的参数initialCapacity

来找出第一个大于它的2的次方的数。比如说我们传了18这样的一个initialCapacity

参数，那么真实的table数组的长度为2的5次方，即32。之所以采用这种策略来构建Hash表的长度，是因为2的次方的运算对于现代的处理器来说，可以通过一些方法得到更加好的执行效率。

3. 接下来就是得到重构因子（threshold）了，这个属性也是HashMap中的一个比较重

要的属性，它表示，当Hash表中的元素被存放了多少个之后，我们就需要对该Hash表进行重构。

4. 最后就是使用得到的初始化参数capacity 来构建Hash表：Entry[] table。

下面我们看看一个键值对是如何添加到HashMap中的。

该put方法是用来添加一个键值对（key-value）到Map中，如果Map中已经存在相同的键的键值对的话，那么就把新的值覆盖老的值，并把老的值返回给方法的调用者。如果不存在一样的键，那么就返回null 。我们看看方法的具体实现：

1. 首先我们判断如果key为null则使用一个常量来代替该key值，该行为在方法maskNull（）

终将key替换为一个非null 的对象k。

2. 计算key值的Hash码：hash

3. 通过使用Hash码来定位，我们应该把当前的键值对存放到Hash表中的哪个格子中。

indexFor()方法计算出的结果：i 就是Hash表（table）中的下标。

4. 然后遍历当前的Hash表中table[i]格中的链表。从中判断已否已经存在一样的键(Key)的键

值对。如果存在一样的key的键，那么就用新的value覆写老的value，并把老的value返回 5. 如果遍历后发现没有存在同样的键值对，那么就增加当前键值对到Hash表中的第i个格子

中的链表中。并返回null 。

24

最后我们看看一个键值对是如何添加到各个格子中的链表中的：

我们先看void addEntry(int hash, Object key, Object value, int

bucketIndex)方法，该方法的作用就用来添加一个键值对到Hash表的第bucketIndex个格子中的链表中去。这个方法作的工作就是：

1. 创建一个Entry对象用来存放键值对。 2. 添加该键值对 ---- Entry对象到链表中

3. 最后在size属性加一，并判断是否需要对当前的Hash表进行重构。如果需要就在void

resize(int newCapacity)方法中进行重构。 之所以需要重构，也是基于性能考虑。大家可以考虑这样一种情况，假定我们的Hash表只有4个格子，那么我们所有的数据都是放到这4个格子中。如果存储的数据量比较大的话，例如100。这个时候，我们就会发现，在这个Hash表中的4个格子存放的4个长长的链表。而我们每次查找元素的时候，其实相当于就是遍历链表了。这种情况下，我们用这个Hash表来存取数据的性能实际上和使用链表差不多了。

但是如果我们对这个Hash表进行重构，换为使用Hash表长度为200的表来存储这100个数据，那么平均2个格子里面才会存放一个数据。这个时候我们查找的数据的速度就会非常的快。因为基本上每个格子中存放的链表都不会很长，所以我们遍历链表的次数也就很少，这样也就加快了查找速度。但是这个时候又存在了另外的一个问题。我们使用了至少200个数据的空间来存放100个数据，这样就造成至少100个数据空间的浪费。 在速度和空间上面，我们需要找到一个适合自己的中间值。在HashMap中我们通过负载因子（loadFactor）来决定应该什么时候应该重构我们的Hash表，以达到比较好的性能状态。

我们再看看重构Hash表的方法：void resize(int newCapacity)是如何实现的： 它的实现方式比较简单：

1. 首先判断如果Hash表的长度已经达到最大值，那么就不进行重构了。因为这个时候Hash表的长度已经达到上限，已经没有必要重构了。 2. 然后就是构建新的Hash表

3. 把老的Hash表中的对象数据全部转移到新的Hash表newTable中，并设置新的重构因子

threshold

对于HashMap中的实现原理，我们就分析到这里。大家可能会发现，HashCode的计算，是用来定位我们的键值对应该放到Hash表中哪个格子中的关键属性。而这个HashCode的计算方法是调用的各个对象自己的实现的hashCode()方法。而这个方法是在Object对象中定义的，所以我们自己定义的类如果要在集合中使用的话，就需要正确的覆写hashCode() 方法。下面就介绍一下应该如何正确覆写hashCode()方法。

25

本文来源：https://www.bwwdw.com/article/atdf.html