Java 集合连环30问

1. 常见的集合有什么
2. 线程安全的集合有哪些？线程不安全的呢？
3. ArrayList与linkList异同点
4. ArrayList与Vector区别
5. 说一说ArrayList的扩容机制
6. Array和ArrayList有什么区别？什么时候应该用Array而不是ArrayList？
7. HashMap的底层数据结构是什么？
8. 解决Hash冲突的办法有哪些？HashMap用那种？
9. 为什么在解决Hash冲突时候不直接用红黑树？而选择先用链表，再转红黑树？
10. HashMap默认加载因子是多少？为什么是0.75,不是0.6或者0.8？
11. HashMap中的key存储索引是怎么计算的？
12. HashMap的put方法流程？
13. HashMap的扩容方式？
14. 一般用什么来做HashMap的key？
15. HashMap为什么是线程不安全的？
16. ConcurrentHashMap的实现原理是什么？
17. ConcurrentHashMap的put方法执行的逻辑是什么？
18. Concurrent的get方法是否还要加锁？
19. get方法不需要加锁与volatile修饰的哈希桶有关吗?
20. ConcurrentHashMap 不支持key或者value为null的原因？
21. ConcurrentHashMap 的并发度是多少?
22. ConcurrentHashMap 迭代器是强一致性还是弱一致性？
23. JDK1.7 与JDK1.8中 ConcurrentHashMap的区别？
24. ConcurrentHashMap 和 Hashtable 的效率哪一个比较高？
25. 说一下HashTable的锁机制？
26. 多线程下安全的操作 map还有其他方法吗？
27. HashSet 和 HashMap 区别？
28. Collection 框架中实现比较要怎么做？
29. Iterator 和 ListIterator 有什么区别？
30. 说一下快速失败（fail-fast）和安全失败（fail-safe）

1.常见的集合有哪些？

Java的集合类主要由两个根接口Collection和Map派生出来，Collection派生出了三个子接口：List、Set、Queue（java5新增加了队列），因此java集合大致分为List、Set、Queue、Map四大接口体系。

注意：Collection是一个接口，Collections是一个工具类，Map不是Collection的子接口。

Java集合框架如下：

图中，List代表了有序可重复集合，可以根据元素的索引直接来访问；Set代表无序不可重复集合，只能根据元素本身来访问；Queue是队列集合。

Map代表的是存储key-value对的集合，可以根据元素的key来访问value。

上图中淡绿色的背景覆盖的是集合体系中常用的类，分别是ArrayList、Linklist、ArrayQueue、HashSet、TreeSet、HashMap、TreeMap等实现类。

2.线程安全的集合有哪些？线程不安全的呢？

线程安全的

• HashTable： 比HashMap多了线程安全
• ConcurrentHashMap： 是一种高效但是线程安全的集合
• Vector： 比ArrayList多了同步化机制
• Stack: 栈，也是线程安全的，继承于Vector

线程不安全的:

• HashMap
• ArrayList
• LinkList
• HashSet
• TreeSet
• TreeMap。。。

3.ArrayList和Linklist异同点

• 是否为线程安全：ArrayList和linklist都是不同步的，也就是不保证线程安全的
• 底层的数据结构：ArrayList底层使用的是Object数组；LinkedLinst底层使用的是双向循环链表数据结构
• 插入删除是否受元素的位置影响：ArrayList采用数组存储，所以插入和删除元素时间复杂程度受元素位置的影响，比如执行 add(E e)方法的时候，ArrayList会默认增加在此列表的末尾，这种情况复杂度就是O（1）。但是如果要在指定的位置i插入和删除元素的话【add(int idex, E element)】时间复杂程度就为O(n-i)。因为在上述操作的时候，集合中的第i和第i元素之后的（n-i）个元素都要执行向后位/向前位移一位的操作。LinkList采用链表存储，所以插入，删除元素的时间复杂程度不受元素的位置影响，都是近似O（n）
• 是否支持随机访问： LinkList不支持高效的随机元素访问，而ArrayList实现了RandmoAccess接口，所以有了随机访问的功能。快速随机访问就是通过元素的序号快速获取元素对象（对应于 get(int indedx)方法）。
• 内存空间占用：Arralist的空间浪费主要体现在list列表的结尾会预留一定的容量空间而Linklist的空间花费则体现在它的每一个元素都需要消耗空间去存储后继和直接前驱以及数据

4.ArrayList和Vector的区别

• Vector是线程安全的，ArrayList是线程不安全的。其中vector在关键性的方法前面都加了synchronize关键字，来保证线程的安全。如果项目中用到多个线程访问的集合，最好使用Vector，不需要太关注线程安全的问题。
• ArrayList在底层数组不够用时候在原来的基础上扩展0.5倍，Vector是扩展1倍，这样来说ArrayList是比较省内存的

5.说一下ArrayList的扩容机制

ArrayList扩容的本质是计算出新的扩容数组后的size实例化，并将原有数组内容复制到新的数组中去。默认情况下新的容量会是原来容量的1.5倍。

以JDK1.8为例↓：

public boolean add(E e) {
    //判断是否可以容纳e，若能，则直接添加在末尾；若不能，则进行扩容，然后再把e添加在末尾
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //将e添加到数组末尾
    elementData[size++] = e;
    return true;
    }
// 每次在add()一个元素时，arraylist都需要对这个list的容量进行一个判断。通过ensureCapacityInternal()方法确保当前ArrayList维护的数组具有存储新元素的能力，经过处理之后将元素存储在数组elementData的尾部
private void ensureCapacityInternal(int minCapacity) {
      ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
        //如果传入的是个空数组则最小容量取默认容量与minCapacity之间的最大值
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
  private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // 若ArrayList已有的存储能力满足最低存储要求，则返回add直接添加元素；如果最低要求的存储能力>ArrayList已有的存储能力，这就表示ArrayList的存储能力不足，因此需要调用 grow();方法进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
private void grow(int minCapacity) {
        // 获取elementData数组的内存空间长度
        int oldCapacity = elementData.length;
        // 扩容至原来的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //校验容量是否够
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //若预设值大于默认的最大值，检查是否溢出
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 调用Arrays.copyOf方法将elementData数组指向新的内存空间
         //并将elementData的数据复制到新的内存空间
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

6.Array和ArrayList有什么区别？什么时候应该Array而不是ArrayList？

• Array可以包含基本类型和对象类型，而ArrayList只能包含对象类型
• Array大小是固定的，ArrayList是动态变化的
• ArrayList提供了更多的方法和特性，比如： addAll（），removeAll（），iterator（）。。。

  7.HashMap的底层数据结构是什么？

在JDK1.7和JDK1.8中有区别：
在JDK1.7中，由“数组+链表”组成，数组是HashMap的核心，链表则是为了主要解决哈希冲突而存在的。

在JDK1.8中，由“数组+链表+红黑树”组成，当链表过长，则会严重影响HashMap的性能，红黑树的搜索时间为O（logn）,而链表是糟糕的O(n)。因此JDK对数据结构做了进一步的优化，引入了红黑树。链表和红黑树在一定条件下会进行转化。

• 当链表超过8且数据量超过64才会转化红黑树
• 将链表转换为红黑树会判断，如果当前数组的长度小于64，那么会优先进行扩容，而不是转换为红黑树，以减少搜索时间

8.解决哈希冲突的方法有哪些？HashMap用那种

解决Hash冲突的方法有：开放地址法，再哈希法，链地址法，建立公共溢出区。 HashMap采用的链地址法。

• 开放地址法也称再散列法,基本的思想就是，如果p=H(key) 出现冲突时，则以P为基础，再次hash，p1=H(p)，如果p1再次冲突时候，再以p1为基础，以此类推，直到找到一个不冲突的哈希地址pi。因此开放定址所需要的hash表的长度大于等于所需要存放的元素，而且因为存在再次hash，所以只能在删除的节点上做标记，而不能真正的删除节点。
• 再哈希法（双重散列，多重散列），提供多个不同的hash函数，当R1=H1（key1）发生冲突时，再计算R2=H2（key2），直到没有冲突为止。这样做虽然不易产生堆集，但是增加了计算时间。
• 链地址法（拉链法），将哈希值相同的元素构成一个同义词的单链表，并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除只要在同义链表中进行。
• 建立公共溢出区，将哈希表分为公共表和溢出表，当溢出发生时候，将所有溢出的数据放在溢出区

9.为什么在解决hash冲突的时候，不直接用红黑树？而选择先用链表，再转红黑树？

因为红黑树需要左旋右旋变色这些操作保持平衡，而单链表不需要。当元素小于8个时候，此时做查询操作，链表结构已经能够保证查询性能了。当元素大于八个时候，红黑树的搜索时间复杂程度是O（logn），而链表是O（n），此时需要红黑树来加快查询速度，但是新增节点的效率就变慢了。

如果一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑是浪费性能。

10.HashMap默认的加载因子是多少？为什么0.75,不是0.6或者0.8？

先看一下HashMap的默认构造函数：

     int threshold;             // 容纳键值对的最大值
     final float loadFactor;    // 负载因子
     int modCount;  
     int size;

Node[] table的初始长度length（默认值为16），Load factor为负载因子（默认值为0.75），threshold是HashMap所能容纳键值对的最大值。threshold = length* loadFactor。也就是说，在数组定义好长度后，负载因子越大，所能容纳的键值对就越多。

默认的loadFactor是0.75，0.75是对空间和时间效率的一个平衡的选择，一般不要修改，除非在时间和空间比较特殊的情况下：

• 如果内存空间很多而又对时间的效率要求高，可以减低负载因子loadFactor的值
• 相反，如果内存相对紧张而时间效率要求又不高，可以增加负载因子LodaFactor的值，这个值可以大于1

可以追溯作者在源码中的注释（JDK1.7）

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

11.HashMap中的key的存储索引是怎么计算的？

首先先根据key值计算出hashcode的值，再根据hashcode计算出hash值，最后通过hash&（length-1）计算出存储的位置。看一下源码的实现

// jdk1.7
方法一：
static int hash(int h) {
    int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
    h ^= k.hashCode(); // 为第一步：取hashCode值
    h ^= (h >>> 20) ^ (h >>> 12); 
    return h ^ (h >>> 7) ^ (h >>> 4);
}
方法二：
static int indexFor(int h, int length) {  //jdk1.7的源码，jdk1.8没有这个方法，但实现原理一样
     return h & (length-1);  //第三步：取模运算
}

// jdk1.8
static final int hash(Object key) {   
     int h;
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    /*      h = key.hashCode() 为第一步：取hashCode值     h ^ (h >>> 16)  为第二步：高位参与运算    */
}

这里的Hash算法本质就是三步：取key的hashCode值，根据hashcode计算出hash值、通过取模计算下标。其中。JDK1.7和JDK1.8的不同之处，就在于第二步。接下来看详细的过程，以JDK1.8为例，n为Table的长度。

12.HashMap的put方法流程？

以JDK1.8位例，简要的流程如下

1. 首先根据key的值计算hash值，找到该元素在数组中的存储下标
2. 如果数组为空就resize初始化
3. 如果没有哈希冲突就直接放在对应数组的下标
4. 如果冲突了，且key存在，就覆盖掉value
5. 如果冲突后，发现该节点是红黑树，就将该节点挂在树上
6. 如果冲突后是链表，判断该链表是否大于8，如果大于8并且数组容量小于64就进行扩容；如果链表节点大于8并且数组的容量大于64，则将这个结构转为红黑树；否则，链表插入键值对，若key存在，就覆盖掉value。

13.HashMap的扩容方式

HashMap在容量超过负载因子所定义的容量后，就会扩容。Java的数组是无法自动扩容的，方法是将HashMap的大小扩大为原来数组的两倍，并将对象放到新的数组里面。

那么扩容的步骤是什么呢?让我们看看源码。

先看下JDK1.7的代码

void resize(int newCapacity) {   //传入新的容量
        Entry[] oldTable = table;    //引用扩容前的Entry数组
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
            threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
            return;
        }
        Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
        transfer(newTable);                         //！！将数据转移到新的Entry数组里
        table = newTable;                           //HashMap的table属性引用新的Entry数组
        threshold = (int)(newCapacity * loadFactor);//修改阈值
    }

这里就是使用了一个容量更大的数组来替代已有的容量小的数组，transfer（）方法将原有Entry数组的元素拷贝到新的Entry数组里。

void transfer(Entry[] newTable) {
        Entry[] src = table;                   //src引用了旧的Entry数组
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
            Entry<K,V> e = src[j];             //取得旧Entry数组的每个元素
            if (e != null) {
                src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
                do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
                    e.next = newTable[i]; //标记[1]
                    newTable[i] = e;      //将元素放在数组上
                    e = next;             //访问下一个Entry链上的元素
                } while (e != null);
            }
        }
    }

newTable[i]的引用赋给了e.next，也就是使用单链表的头插方式，同一位置新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到Entry链的尾部（如果发生了hash冲突的话）

JDK1.8做了两处的优化

1.resize之后，元素的位置还是在原来的位置，或者原来的位置+oldCap（原来的哈希表长度）。不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话·索引变成了“原索引+oldCap”。这个设计非常的巧妙，省去了计算hash值的时间。

如下图所示，n为table的长度，图（a）表示扩容前key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定的索引位置的示例，其中hash1是key1对应哈希与高位运算的结果。

元素在重新计算 hash 之后，因为 n 变为 2倍，那么 n-1 的 mask 范围在高位多 1 bit(红色)，因此新的index就会发生这样的变化：

2.JDK1.7 中 rehash 的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置（头插法）。JDK1.8 不会倒置，使用尾插法。

14. 一般用什么作为HashMap的key?

一般用Integer、String 这种不可变类当 HashMap 当 key，而且 String 最为常用。

• 因为字符串是不可变的，所以在它创建的时候 hashcode 就被缓存了，不需要重新计算。这就是 HashMap 中的键往往都使用字符串的原因。
• 因为获取对象的时候要用到 equals() 和 hashCode() 方法，那么键对象正确的重写这两个方法是非常重要的,这些类已经很规范的重写了 hashCode() 以及 equals() 方法。

15. HashMap为什么线程不安全？

• 多线程下扩容死循环。JDK1.7中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。
• 多线程的put可能导致元素的丢失。多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在JDK 1.7和 JDK 1.8 中都存在。
• put和get并发时，可能导致get为null。线程1执行put时，因为元素个数超出threshold而导致rehash，线程2此时执行get，有可能导致这个问题。此问题在JDK 1.7和 JDK 1.8 中都存在。

具体分析可见我的这篇文章：面试官：HashMap 为什么线程不安全？

16.ConcurrentHashMapd的实现原理是什么

ConcurrentHashMap 在1.7和1.8中的实现方式不同

先来看JDK1.7

JDK1.7中的ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成，即ConcurrentHashMap 把哈希桶切分成小数组（Segment ），每个小数组有 n 个 HashEntry 组成。

其中，Segment 继承了 ReentrantLock，所以 Segment 是一种可重入锁，扮演锁的角色；HashEntry 用于存储键值对数据。

再来看下JDK1.8

在数据结构上，JDK1.8采用ConcurrentHashMap 选择了与 HashMap 相同的数组+链表+红黑树结构；在锁的实现上，抛弃了原有的 Segment 分段锁， 采用 CAS + synchronized 实现更加低粒度的锁。

将锁的级别控制在了更细粒度的哈希桶级别，也就是说只需要锁住这个链表结点（红黑树的根节点），就不会影响到其他哈希桶元素的读写，大大提高了并发度。

17.ConcurrentHashMap 的 put 方法执行的逻辑是什么？

先看JDK1.7

首先，会尝试获取锁，如果获取失败，利用自旋获取锁；如果自旋重试次数超过64次，则改为阻塞获取锁。

获取到锁后：

1. 将当前 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry。
2. 遍历该 HashEntry， 如果不为空则判断传入的 key 和当前遍历的 key 是否相等， 相等则覆盖旧的 value。
3. 不为空则需要新建一个 HashEntry 并加入到 Segment 中，同时会先判断是否需要扩容。
4. 释放 Segment 的锁。

再来看JDK1.8

1. 根据 key 计算出 hash 值。
2. 判断是否需要初始化。
3. 定位到 Node，拿到首节点f， 判断首节点f：
   • 如果为 null ，则通过cas的方式尝试添加
   • 如果为 f.hash = MOVED = -1 ,说明其他线程在扩容，参与一起扩容
   • 如果都不满足， synchronize 锁住 f 节点，判断是链表还是红黑树， 遍历插入
4. 当在链表长度达到8的时候， 数组扩容或者将链表转为红黑树。

源码分析可看这篇文章：面试 ConcurrentHashMap ，看这一篇就够了！

18.ConcurrentHashMap 的get方法是否要加锁，为什么?

get方法不需要加锁。因为 Node 的元素 val 和指针 next 都是用 volatile 修饰的，在多线程环境下修改线程A节点的val或者新增节点的时候是对线程B可见的。

这也是它比其他并发集合比如HashTable、用 Collection.synchronizedMap() 包装的 HashMap 安全效率高的原因之一。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    //可以看到这些都用了volatile修饰
    volatile V val;
    volatile Node<K,V> next;
}

19.get方法不需要加锁与volatile修饰的哈希桶有关吗？

没有关系。哈希桶table 是用volatile修饰主要是保证在数组扩容时候保证可见性。

static final class Segment<K,V> extends ReentrantLock implements Serializable {
    // 存放数据的桶
    transient volatile HashEntry<K,V>[] table;

20.ConcurrentHashMap 不支持key或者 value 为null的原因是什么？

先来说说为什么 value 不能为null，因为 ConcurrentHashMap 是用于多线程的，如果 map.get(key) 得到了 null，无法判断，是映射的 value 为null， 还是没有找到对应的 key 而为 null，这就有了二义性。

而用于单线程状态的HashMap 却可以用 containKey(key) 去判断是否包含这个null。

至于ConcurrentHashMap 中的key为什么也不能为 null 的问题，源码就是这样写的，哈哈。如果面试官不满意，就回答因为作者Doug不喜欢 null ，所以在设计之初就不允许了 null 的key存在。想要深入了解的小伙伴，可以看这篇文章这道面试题我真不知道面试官想要的回答是什么

21.ConcurrentHashMap 的并发度是多少？

在JDK1.7中， 并发度默认是16， 这个值可以在构造函数中设置。如果自己设置了并发度，ConcurrentHashMap 会使用大于等于该值的最小2的幂指数作为实际的并发度，也就是说 如果你设置的是17 那么实际的并发度就是32

22.ConcurrentHashMap 迭代器是强一致性还是弱一致性？

与 HashMap 迭代器是强一致性不同， ConcurrentHashMap 迭代器是弱一致性的。

ConcurrentHashMap 的迭代器创建后， 就会按照哈希表结构遍历一遍，但在遍历的过程中，内部的元素可能发生变化，如果发生在已遍历过的部分，迭代器就不会反映出来， 而未遍历发生过变化的部分，迭代器就会反映出来，这个就是弱一致性。

这样迭代器线程使用原来的就数据，而写线程也可以并发发生完成的改变，更重要的，这保证了多个线程并发执行的连续性和扩展性，是性能提升的关键。

23.JDK1.7 与JDK1.8 中ConcurrentHashMap 的区别？

• 数据结构: 取消了 Segment 分段锁的数据结构，取而代之的是数组+链表+红黑树的结构
• 保证线程安全的机制：JDK1.7采用 Segment 的分段锁机制实现线程的安全， 其中 segment继承自 ReentrantLock。JDK1.8 采用CAS+Synchronize保证线程安全。
• 锁的粒度：原来是对需要进行数据操作的segment加锁， 现调整为对每个数组元素加锁（Node）
• 链表转化为红黑树：定位结点的hash算法简化会带来弊端， Hash冲突加剧，因此在链表结点的数量大于8时，会将链表转化为红黑树进行处理。
• 查询时间复杂度：从原来的遍历链表O(n)，到遍历红黑树O（logN）

24.ConcurrentHashMap 和 Hashtable 的效率那个更高？ 为什么呢？

ConcurrentHash 的效率要高于 Hashtable，因为 Hashtable给整个哈希表加了一把大锁从而实现线程的安全。而ConcurrentHashMap 的锁的粒度更低， 在JDK1.7 中采用分段锁实现线程安全， 在JDK1.8 中采用 CAS + synchronize 实现线程安全。

25.说一下Hashtable 的锁机制？

Hashtable 是使用Synchronize来实现线程安全的， 给整个哈希表加了一把大锁， 多线程访问的时候， 只有一个线程能访问或者操作该对象，那其他线程只能阻塞等待需要的锁被释放，在竞争积累的多线程场景就会性能非常的差！不推荐使用！

26.多线程下安全操作的map 还有其他方法吗？

还可以使用 Collection.synchronizedMap 方法，对方法进行加同步锁。

private static class SynchronizedMap<K,V>
        implements Map<K,V>, Serializable {
        private static final long serialVersionUID = 1978198479659022715L;
        private final Map<K,V> m;     // Backing Map
        final Object      mutex;        // Object on which to synchronize
        SynchronizedMap(Map<K,V> m) {
            this.m = Objects.requireNon null (m);
            mutex = this;
        }
        SynchronizedMap(Map<K,V> m, Object mutex) {
            this.m = m;
            this.mutex = mutex;
        }
    // 省略部分代码
    }

如果传入的是HashMap 对象，其实也是对HashMap 做的方法做了一层包装， 里面使用对象锁来保证多线程安全，本质是对 HashMap 进行全表锁。 在竞争激烈的多线程环境下 性能依然是很差，不推荐使用。

27.HashSet 和 HashMap 区别？

补充HashSet的实现：HashSet 的底层其实是HashMap，只不过我们 HashSet 是实现了 Set 接口并且将数据作为 K 值， 而 V 值一直使用相同的虚值去保存。如下图源码所示：

public boolean add(E e) {
    return map.put(e, PRESENT)==null;// 调用HashMap的put方法,PRESENT是一个至始至终都相同的虚值
}

由于 HashMap 的K值本身就是不允许重复， 并且在HashMap 中如果 K/V 相同时候，会用新的V覆盖旧的V，并返回旧的V，那么在 HashSet 中执行这句话就会返回一个false，导致插入失败，这样就保证了数据的不可重复性。

28.Collection框架中实现比较要怎么操作？

• 实现类实现Comparable接口， 并是实现 comparableTo（T t） 方法，称为内部比较器
• 创建一个外部比较器，这个比较器要实现Comparator 接口的 compare（T t1，T t2）方法

29.Iterator 和 ListInterator 有什么区别

• 遍历：使用 Iterator，可以遍历所有的集合， 如 Map，List，Set；但只能在前方向上遍历集合中的元素。使用 ListIterator，只能遍历List实现的对象，但是可以向前、后 遍历集合中的对象。
• 添加元素：Iterator无法向集合中添加对象， ListIterator 可以向集合中添加元素
• 修改元素：Iterator无法修改集合中的元素，ListIterator可以使用 set（）修改集合中的元素
• 索引：Iterator无法获取集合中的元素索引，ListIterator可以获取集合中元素的索引

30.快速失败（fail-fast）和安全失败（fail-safe）

快速失败（fail-fast）

在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象进行修改（增加，修改，删除），则会抛出 Concurrent Modification Exception

原理：迭代器在遍历时，直接访问集合中的内容，并且在遍历的过程中使用一个 modCount 变量。集合在被遍历期间内容发生变化，就会改变 modCount的值。每当迭代器使用hashNext（）/ next() 遍历下一个元素之前，都会检测 modCount 变量是否为 expectedmodCount值，是的话就返回遍历，否则抛出异常，终止遍历。

注意 ： 这里的异常抛出条件是检测到 modCount！= expectedCount 这个条件。 如果集合发生变化时修改 modCount 值刚好又设置为了 expectedmodCount值，则不会发生异常。因此不能依赖异常是否抛出而进行并发操作编程，这个异常一般只用作于检测并发修改bug。

场景： java.util 包写的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改），比如 HashMap、ArrayList 、、、这些集合

安全失败（fail-safe）

采用安全失败机制的集合容器，在遍历时候不是直接在原本集合上面操作，而是复制原有集合的内容，在拷贝的集合上进行遍历

原理： 由于迭代的时候是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所做的修改不能被迭代器检测到，所以不会触发 Concurrent Modification Exception

缺点： 基于拷贝内容的优点是避免了Concurrent Modifycation Exception ，但是同样的，迭代器不能访问到修改后的内容。就是迭代器遍历开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。

场景： java.util.concurrent 包下的容器都是安全失败的，可以在多线程下并发使用，并发修改，比如： ConcurrentHashMap