完全零基础的朋友在学习JavaSE时，最讨厌的知识点有两个：一是集合，二是IO。因为这两章API方法巨多，内容体量又大，今天学完明天忘，简直分分钟崩溃。IO以后有机会讲，这篇主要提几点学习时需要特别注意的问题。由于工作中ArrayList和HashMap最常用，这里只重点讲这两个（面试可能会考高并发情况下HashMap的死锁以及ConcurrentHashMap）。

我们首先要明确，当我们学习集合时我们在学什么？说到集合，最主要的功能就是容器。既然作为容器，那么就和生活中的茶杯、蜂巢、葫芦一样，具备最基本的两种功能：存、取。又由于各个容器内部结构不同，可能导致存取方式不同，所以除了各个容器存、取数据的方法外，还需要关注各个容器的自身特性：比如ArrayList如何去重，如何用LinkedList模拟栈/队列结构，为什么会有并发修改异常，Hashxxx为什么可以保证元素唯一，Treexxx为什么可以给元素排序等等。也就是说，学习每一种集合时，必须搞明白3点：

  • 它如何存数据（Collection体系用add()，Map体系用put()）
  • 它如何取数据（迭代器，增强for，List系还有普通for和ListIterator）
  • 容器特性造成的一些问题

本篇重点讲下面几个问题：

  • Iterator迭代器为什么要设计成接口
  • Iterator并发修改异常的底层机制是什么
  • HashSet/TreeSet与HashMap/TreeMap之间的联系
  • Map有没有iterator()方法
  • ArrayList去重原理
  • HashMap的put()源码浅析（JDK1.7版，1.8大变动，我怂，看不懂）
  • 使用HashSet/HashMap时元素为什么要重写hashCode()和equals()

首先，我们复习下集合的体系

集合体系
Collection
    |--List
        |--ArrayList
        |--LinkedList
        |--Vector
    |--Set
        |--HashSet
        |--TreeSet
Map
    |--HashMap
    |--TreeMap

Collection：

img1.注意，这是大致分类，不是继承体系图。比如ArrayList并非直接实现List，中间还有AbstractList等。2.每个具体子类内部简略地画了底层数据结构。3.具体子类内部都实现了迭代器，虽然实现方式不同，但都有hasNext()，next()等方法，可以向上抽取。4.HashSet/TreeSet底层就是HashMap/TreeMap（见下图）

Map:

img1.Map的遍历方式一般有两种：先得到全部键的set集合，再遍历键得到值；或者直接得到键值对的set集合，从中分别得到键和值。其实也是能得到iterator()的，后面再提。2.Map系添加用put()，而Collection系添加都用add()。

Iterator迭代器为什么要设计成接口

Iterator之所以设计成接口，个人认为有两点原因

  • 各个子类底层数据结构不同导致它们的取出方式不同，只能用接口规范它，而不可直接写死

比如，我们生活中的体重计，有些是机械按压式的，有些是电子计算的，具体实现方式是不同的。但我们可以让它们遵循接口规范，都对外提供一个测量体重的方法：站上去即可测量。不论是哪种体重计，使用时我并不关心你的具体实现，但我知道，你们都有“站上去即可测量”这个方法。这其实就是多态的思想：看顶层（接口），用底层（子类具体实现）。这种抽取的好处在于，既规范子类方法，又不干涉方法的具体实现。就好比我现在命令八仙过海，那自然就是各显神通。“过海”就是对八个方法的抽取，接口里只有“过海”的方法声明，没有方法体（具体实现）。但如果我说，八仙必须都游泳过海。此时相当于“过海”这个方法有了方法体，是具体方法，要放在父类中被子类继承。这种凡人的方法，恐怕会累死各位大仙。到头来还是要重写这方法去覆盖...

img

  • 迭代器不只有一个方法。为了方便管理，最好做成具体子类的内部类

如果迭代器只有一个方法，自然不用大费周章搞个内部类。子类直接实现接口的方法，即可调用。但是一个迭代器，必须至少包含判断（hasNext()）和取出（next()）两个方法。我们回顾以往用过的返回值类型，似乎没有返回"多个方法"这种类型。但我们可以创建一个对象，把多个方法封装在对象中返回（Java中真的是万物皆对象）。Iterator接口接收具体内部类对象，这就是多态，是很常见的。以ArrayList为例：

img

Iterator并发修改异常的底层机制是什么

大家之前学习时，可能只是听说有这么个异常，但不明白底层机制。这里还是以ArrayList为例

img

在ArrayList的父类AbstractList中，有一个变量叫modCount，它是用来计数的。

img

计什么数？记录容器中元素的修改次数：每次增加、删除、修改集合内元素，都会执行modCount++。这个变量在父类AbstractList中声明，我们可以在子类ArrayList里看到它的应用。

img

我们再看迭代器中，modCount的妙用

img在ArrayList内部类Itr中，有一个checkForComodification()方法。这个方法在内部类的next()、remove()中均有调用。

expectedModCount是内部类的成员变量，在内部类对象生成时被初始化。也就是说

img

对于List来说，有两种方法可以避免并发修改异常：

  • 迭代器迭代元素，迭代器修改元素(ListIterator)
  • 集合遍历元素，集合修改元素(for)
for (int x = 0; x < list.size(); x++) {
    String s = (String) list.get(x);
    if(value.equals("hello")){
        list.add("world");
    }
}

也就是说，用集合遍历时就用集合的方法去修改，用迭代器遍历时就用迭代器的方法修改。不要在迭代器遍历时，调用集合的方法修改元素。

由于ListIterator几乎不用，这里略过，主要讨论下for循环为什么可以避免并发修改异常。

要明确两点：

首先，modCount只和增删改有关（这些方法里都有modCount++），而遍历是“查询方式”，没有modCount++。不论是迭代器还是for循环，都只是查询，不会改变modCount。

其次，可能抛异常的是check方法。

而只有调用迭代器内部的next()，remove()方法时，才会调用check方法，才可能抛异常（期间除了迭代器，没有其他方法修改modCount）。for循环是我们自己写的，没有调用check方法。压根不可能抛异常。

所以只用for循环当然没问题。

img

HashSet/TreeSet与HashMap/TreeMap之间的联系

很多初学者朋友可能和我当初一样，要过很久才能反应过来：HashSet/TreeSet与HashMap/TreeMap联系原来这么紧密！紧密到什么程度呢？它们的内部干脆就放了一个map！

img

img

甚至HashSet和TreeSet内部的很多方法实现，就是简单的调用了HashMap/TreeMap的方法

img

所以，要想弄懂HashSet为什么能实现去重，TreeSet如何实现排序，关键就是看HashMap和TreeMap，因为Hashxxx和Treexxx的底层数据结构是一样的。而学习这一块的关键又在于了解HashmMap和TreeMap的put()方法各自到底做了什么。

Map有没有iterator()方法？

我上面Map的图里，只给了两种遍历方式，似乎Map没有iterator()。但不要忘了，上面查看源码我们发现HashSet/TreeSet底层就是塞了一个HashMap/TreeMap。而Set的是有iterator()的。这个iterator()肯定从Map那“借”的！所以Map肯定也有iterator()！

imgHashSet的iterator()底层调用map.keySet().iterator()，比map的其中一种遍历方式map.keySet()深了一层

img也就是说map.keySet().iterator()，返回的是一个new KeyIterator()对象。即，HashSet.iterator()返回的是HashMap给它准备好的new KeyIterator()对象

img实际上，Map提供了三种迭代器对象：遍历键，遍历值以及遍历键值对的。由于HashSet是单列的，虽然它底层用了HashMap，却只用了其中的键，至于空下来的value，HashSet准备了一个静态的数据，用来占坑！

img眼尖的朋友，可能注意到这个为了“敷衍”HashMap而给的值，它的命名其实并不敷衍。Present这个单词，意思有很多。但这里我更愿意解释为：这是HashSet给HashMap额外赠送的“礼物”~

img

ArrayList去重原理

我们说过，ArrayList底层是可以自动扩容的数组。它的add()方法本身不具备判断该元素是否唯一的功能。但我们可以设计一个策略，使得ArrayList也像Set一样的保证元素唯一性。这里提供其中一种方法：

img

首先准备两个容器，当我们把元素放入newArray时，通过contains()判断newArray（目的地容器）中是否已经有相同元素。如果newArray中已经有同内容的元素，则不放进去。最终newArray里的元素都是唯一的。那么contains()是根据什么判断两个元素相同的呢？这很重要。比如现实生活中，根据判断标准的不同，判断结果也会不同。双胞胎如果只看脸，可能会被判断为同一人，而如果根据身份证判断，就是不同人。所以我们有必要看一下ArrayList中contains()的源码。

img

我们在上一篇JavaWeb(3)：浅谈集合（上）分析过Object类的equals()方法。

img

如果String类直接继承Object的equals()，它的判断依据是对象地址值是否相同，而不是内容是否相同，是无法去重的。具体原因在上一篇已经分析过。所以它肯定复写了equals()。我们去看一下String类关于equals()的源码。

img

通过查看String类的源码，我们发现它确实复写了从Object继承的equals()方法。它对于两个字符串元素是否相同的判断依据是：是否同类型→是否同长度→是否同内容

每一个培训机构在讲到ArrayList去重时，都会拿String和Student（自定义元素）举例子。结果是String类型的元素去重成功，而Student去重失败。根本原因在于，Student不同于String，它是我们自己写的。如果我们没有通过重写equals()方法来明确判断“元素是否相同”的规则，那么equals()默认用==判断，也就是判断对象地址值。而每一个对象，不论内容是否相同，都在堆中有自己的内存空间，地址值是不同的。所以即使同内容对象，也会被判断为不同元素，都可以加入容器，无法去重。

推荐重写equals()方法。

HashMap的put()源码浅析

img这是JDK1.7的源码，现在JDK1.8改写了HashMap，变化较大。

img

HashSet/HashMap为什么要重写hashCode()和equals()

String类由于已经重写了hashCode()方法，所以没问题。我们应该考虑：如果自定义的对象不重写hashCode()方法，会有什么后果？首先，它将直接继承Object类的hashCode()方法。

img

本地方法的实现，和具体的对象内容是无关的。此时每个Person对象，比如p1.hashCode()和p2.hashCode()返回的值都是它们各自地址值的hash映射结果。由于不同对象地址值不同，所以hashCOde()返回值基本是不一样的。

这个会发生什么情况？

学习put()源码时，我们知道，HashMap会根据hash算出一个i，根据table[i]确定元素要插入的位置。而hash和hashCode()是正相关。如果hashCode()不一样，那么hash极大概率也是不同，也就是说，每个元素插进来的位置相同的概率很低。

img

你看到这种情况，心想，那好吧，你说重写hashCode()和equals()就重写吧。

@Override
public int hashCode(){
    return 0;
}

@Override
public int equals(){
    return ....省略（总之，根据内容判断）
}

这回，会出现什么结果呢？

img

哈希表正确的做法是，重写hashCode()，使不同内容的元素尽可能返回不同的值。既要避免频繁扩容，又要避免桶过深，比较次数陡增。

img

至于怎么重写hashCode()和equals()比较合理？直接IDE快捷键生成即可！

HashMap中有个叫load factor(加载因子)的东西。如果哈希表中的元素放得太满，就必须进行rehashing(再哈希)。再哈希使哈希表元数增倍，并将原有的对象重新导入新的哈希表元中，而原始的哈希表元被删除。load factor(加载因子)决定何时要对哈希表进行再哈希。在Java中，加载因子默认值为0.75。如果0.75理解起来困难，就举个不恰当的比喻：哈希表默认大小为16，如果加载因子是0.75，16*0.75=12。当12个槽被占满时，就会再哈希扩容。如果加载因子改为0.5呢？8个槽占满就再哈希。而再哈希是比较浪费资源的。

加载因子越大，填满的元素越多。好处是，空间利用率高了，但冲突的机会加大了。反之，加载因子越小，填满的元素越少，好处是冲突的机会减小了，但空间浪费多了。
冲突的机会越大，则查找的成本越高。反之，查找的成本越小。

因此，必须在 “冲突的机会”与“空间利用率”之间寻找一种平衡与折衷。 这种平衡与折衷本质上是数据结构中有名的“时-空”矛盾的平衡与折衷。

【扩展资料】

传智播客刘意老师基础班JavaSE集合相关视频

什么是HashMap——程序员小灰（公众号）

Java集合类源码解析 - 随笔分类 - 赵计刚 - 博客园

2018-5-29 23:51:56 好累啊~写得太晚了。

经

@王大天才

提醒，jdk1.8中HashMap变化很大，已经不是单纯的数组+链表，当长度超过多少时会变成红黑树…反正我听不太懂π_π。总之，大家注意下。