Java集合框架概述

为了规范容器的行为，统一设计，JCF定义了15种容器接口(collection interfaces)，它们的关系如下图所示:

容器主要包括 Collection 和 Map 两种，Collection 存储着对象的集合，而 Map 存储着键值对(两个对象)的映射表。

上图中提供了Queue接口，却没有Stack，这是因为Stack的功能已被JDK 1.6引入的Deque取代。

Map接口没有继承自Collection接口，因为Map表示的是关联式容器而不是集合。但Java为我们提供了从Map转换到Collection的方法，可以方便的将Map切换到集合视图。

针对上面java.util.*中的接口，通用实现类如下图所示。其中有表示出接口的实现关系，类的继承关系等。另外比较重要的一块是标示出了不同实现用到的数据结构。

Java容器里只能放对象，对于基本类型(int,long, float,double等)，需要将其包装成对象类型后(Integer, Long
Float, Double等)才能放到容器里。

重点：HashMap，HashTable，ArrayList，LinkedList

1.常用的集合分类以及他们的区别?

大方向 Collection & Map 两类：

List:存储的元素是有序的、可重复的。

Set:存储的元素不可重复的。

Queue:按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。

Map: 使用键值对(key-value)存储，类似于数学上的函数 y=f(x)，”x”代表key，”y”代表 value，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到个值。

2.哪些集合类是线程安全的?

Vector、Hashtable、Stack 都是线程安全的，而像 HashMap 则是非线程安全的，不过在 JDK 1.5 之后随着 Java.util. concurrent 并发包的出现，它们也有了自己对应的线程安全类，比如 HashMap 对应的线程安全类就是 ConcurrentHashMap。

3.Java中Collection和Collections的区别

Collection 是一个集合接口，它提供了对集合对象进行基本操作的通用接口方法，所有集合都是它的子类，比如 List、Set 等。

Collections 是一个包装类，包含了很多静态方法，不能被实例化，就像一个工具类，比如提供的排序方法: Collections. sort(list)，还有swap、shuffle、reverse之类的方法。

import java.util.ArrayList;  
import java.util.Collections;  
import java.util.List;  
public class TestCollections {  
    public static void main(String args[]) {  
        //注意List是实现Collection接口的  
        List list = new ArrayList();  
        double array[] = {11,2,323,56,231,54,-3,-5};  
        for (int i = 0; i < array.length; i++) {  
            list.add(new Double(array[i]));  
        } 
        //使用工具类中的静态方法进行排序
        Collections.sort(list); 
        //输出结果，可看见得到排序的结果
        for (int i = 0; i < array.length; i++) {  
            System.out.println(list.get(i));  
        }  
    }  
}

4.List、Set、Map 之间的区别是什么?

5.什么是 fail-fast，什么是 fail-safe？

fail-safe 和 fail-fast 是多线程并发操作集合时的一种失败处理机制。

fail-fast 表示快速失败，在集合遍历过程中，一旦发现容器中的数据被修改了，会立刻抛出ConcurrentModificationException 异常，从而导致遍历失败

fail-safe 表示失败安全，也就是在这种机制下，出现集合元素的修改，不会抛出ConcurrentModificationException。

原因是采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到。

java.util.concurrent包下的容器都是安全失败的,可以在多线程下并发使用,并发修改。常见的的使用Fail-safe方式遍历的容器有ConcerrentHashMap和CopyOnWriteArrayList等。

6.集合遍历的方法有哪些?

for循环、for-Each循环、Iterator、ListIterator、forEach方法、StreamAPI与函数式

7.迭代器Iterator是什么？

Iterator 接口提供遍历任何 Collection 的接口。我们可以从一个 Collection 中使用迭代器方法来获取迭代器实例。迭代器取代了 Java 集合框架中的 Enumeration，迭代器允许调用者在迭代过程中移除元素。

这里是指调用迭代器的remove方法，是指iterator.remove方法，不会抛出异常。抛出异常，是指在遍历时，调用 fail-fast 的集合自身的 remove 方法会抛出异常，例如 list.remove()方法。

Iterator 的特点是更加安全，因为它可以确保，在当前遍历的集合元素被更改的时候，就会抛出ConcurrentModificationException 异常

List<Integer> list = new ArrayList<>();
// 方式1：直接使用集合的remove方法 - 不安全
for(Integer i : list) {
    list.remove(i);  // 可能抛出ConcurrentModificationException
}

// 方式2：使用Iterator的remove方法 - 安全
Iterator<Integer> it = list.iterator();
while(it.hasNext()) {
    Integer i = it.next();
    it.remove();  // 安全的删除方式
}

Iterator是很典型的fail-fast实现，这种机制的实现原理是：

用集合维护一个modCount计数器记录修改次数。Iterator创建时会保存当前的modCount值。每次调用next()方法时都会检查modCount是否变化，如果发现modCount变化就立即抛出异常。这与fail-safe机制(如CopyOnWriteArrayList)是不同的，因为fail-safe是在副本上进行遍历，不会检测原数据的修改，也不会抛出异常。

8.怎么确保一个集合不能被修改?

可以使用 Collections. unmodifiableCollection(Collection c)方法来创建一个只读集合，这样改变集合的任何操作都会抛出 Java.lang.UnsupportedOperationException 异常。

示例代码如下:

List<String>list =new ArrayList<>();
list.add("x");
Collection<String> clist = Collections. unmodifiableCollection(list);
clist.add("y");// 运行时此行报错
System.out.println(list.size());

Collections.unmodifiablexxx方法对原集合进行了包装，在add、remove 等方法层面保证原集合不被修改。而迭代器是感知到集合发生修改后才抛出异常，并不能阻止已经发生的集合修改。再说了，人家迭代器的作用本来就是为了遍历，保证遍历的安全性就ok了。

9.讲一下java里面List的几种实现?

Arraylist LinkedList Vector Stack

10.ArrayList 和 Array(数组)的区别?

ArrayList 默认容量为 10（或者未初始化时第一次扩容成10），存在自动扩容机制，每次扩容到原本的1.5倍，然后把之前的数据拷贝到新建的数组中去

个人认为从数据类型上开始区分记忆就好。由于ArrayList是继承Collection接口，而Array是基本数据类型之一，所以首先初始化上有区别；其次是存储对象、使用方法，再者是独特的扩容机制，最后是泛型安全性问题，分别对应6、4、5、2、3条。

11.ArrayList 和 Vector的区别是什么?

机制、性能&安全性

12.ArrayList与LinkedList 区别?

ArrayList:1.随机访问 O(1)2.尾部插入和删除 O(1)。(尾部插入也可能需要 O(n)来进行扩容，但这并不频繁)3.其它位置插入和删除 O(n)

LinkedList:1.不支持随机访问，只能顺序遍历 O(n)2.头尾插入和删除 O(1)，因为是基于双向链表实现的3.其它位置插入和删除 O(n)，因为需要顺序遍历。

LinkedList 仅在头尾插入和删除的效率上要高，其他操作都是O(n)。且比较来看，LinkedList仅在头部插入时比 ArrayList 效率要高一点。所以大部分使用LinkedList 的场景都可以使用ArrayList 代替。

13.ArrayList扩容机制

就是tm开个1.5倍的新数组，b话那么多

当然说一下，1.5的增长因子是不会变的，因为实现时写的是size+（size>>1）

14.ArrayList线程安全吗?把ArrayList变成线程安全有哪些方法?

Copy-On-Write机制以CopyOnWriteArrayList为例,它通过写时复制实现线程安全：

所有修改操作都会复制一个新数组
修改在新数组上进行
最后用新数组原子性地替换老数组这样读操作就可以完全无锁,在原数组上进行

CopyOnWriteArraylist 适用于读多写少的高并发场景，关键词是写时复制、独占锁、弱一致性的迭代器。

15.transient修饰是什么？为什么 ArrayList 的 elementData 加上 transient 修饰?

transient 是 Java 序列化机制中的关键字，表示被修饰的字段不会被序列化。让我解释一下 ArrayList 中使用它的原因：

transient 的基本作用：

被 transient 修饰的变量不会被序列化到文件中
当对象被反序列化时，这些字段会被设置为默认值（如 null）

ArrayList 中的 elementData 为什么要用 transient：
1
private transient Object[] elementData;
主要原因是为了优化序列化的性能：

elementData 是一个数组，它的容量通常会大于实际元素数量（因为要预留扩容空间）
如果直接序列化 elementData，会序列化包括那些没有使用的空间
使用 transient 后，ArrayList 可以自定义序列化逻辑，只序列化实际存储的元素

ArrayList 如何实现序列化：

private void writeObject(ObjectOutputStream out) throws IOException {
    int size = this.size;  // 实际元素个数
    out.writeInt(size);    // 写入实际元素个数
    // 只序列化实际存在的元素
    for (int i = 0; i < size; i++) {
        out.writeObject(elementData[i]);
    }
}

这样做的好处：

减少序列化后的文件大小
提高序列化和反序列化的性能
避免了空间的浪费

所以 transient 在这里的使用是一个优化手段，通过自定义序列化过程来提升性能。

16.HashMap工作原理？

HashMap的工作原理基于哈希表，这是一种使用哈希函数将键映射到存储位置的数据结构。哈希表通过计算键的哈希值，并将其转化为数组索引，从而快速定位键值对的存储位置。在理想情况下，哈希函数能将键均匀分布到哈希表中，以最小化哈希冲突。然而，当多个键哈希到同一位置时，就需要解决哈希冲突。

基于哈希表，访问速度快。进行 put 或者 get 操作，可以达到常数时间的性能0(1)。(极端情况当hash冲突比较严重时，查找元素只能去链表遍历，复杂度为0(n);如果是Java8转化成了红黑树，那平均复杂度就是O(logn))。

元素之间没有顺序性:HashMap 使用一个哈希函数将键映射到特定的桶中。这个映射过程是基于键的哈希值，并不是线性顺序，因此插入顺序与存储顺序无关，元素之间没有顺序性。

HashMap最多只允许一条记录的键Key为nul; 但允许多条记录的Value为null; 如果允许多个 null 键，哈希值就会产生冲突，从而导致存储和检索的逻辑变得复杂。

Java7:数据结构采用(数组+链表)实现。

Java8:数据结构采用(数组+链表+红黑树)实现。

非线程安全:需要保证线程安全推荐使用并发包中的ConcurrentHashMap

17.HashMap为什么不是线程安全的?

两个问题，第一个是数据覆盖问题，在java7和8问题都存在。由于线程执行顺序不可预测，使得当两个线程操作同一个bucket时，其中一个线程获取到的头结点/尾结点已经失效却不知道导致覆盖了另一个线程的执行数据。其实不光是 put()操作，删除操作、修改操作，同样都会有覆盖问题

第二个是扩容时死循环问题。简要回答:一个线程已完成扩容，此时链表倒置，另一个线程还停留在获取到原头结点及其 next 的语句处，该 next 语义失效，继续执行将导回原头结点，形成死循环。改成尾插法就能避免这一点。

18. Java8 HashMap做了哪些优化？

结构上的变化1、插入方法上的变化2、新的机制34

19.HashMap的put操作流程？

初始化–>计算索引–>插入–>判断扩容

插入时又可以细分，先判断是否是红黑树，如果不是就遍历链表，key相同就覆盖，没有相同的就尾插，然后判断是否要转换成红黑树

判断逻辑是：如果插入前的结点总数大于或等于8，则将链表转换为红黑树。

这样一看，无论总体还是细节都是秉持先插入再扩容的原则的。

20. resize()扩容条件、扩容流程？

HashMap进行扩容取决于以下两个元素: Capacity*LoadFactor

·Capacity: HashMap当前长度

·LoadFactor: 负载因子，默认值0.75f.

当Map中的元素个数(包括数组，链表和红黑树中) 超过了16*0.75=12之后开始扩容

当然内部也会有一些其他导致扩容的情况: 例如java8中，当某个链表长度达到8，并且当前数组长度小于64时，也会触发扩容。

当 put 时，如果发现目前的 bucket 占用程度已经超过了 Load Factor 所希望的比例，那么就会发生 resize。在resize 的过程，简单的说就是把 bucket 扩充为 2 倍，之后重新计算 index，把节点再放到新的 bucket 中。

然而又因为我们使用的是2 次幂的扩展(指长度扩为原来 2 倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动 2 次幂的位置。因此，我们在扩充 HashMap 的时候，不需要重新计算 hash，只需要看看原来的 hash 值新增的那个 bit 是1还是0 就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap“。

这个设计确实非常的巧妙，既省去了重新计算 hash 值的时间，而且同时，由于新增的 1bit 是0还是1 可以认为是随机的（经过了与运算），因此 resize 的过程，均匀的把之前的冲突的节点分散到新的 bucket 了。

21.HashMap 的长度为什么是 2 的幂次方？

因为我们在计算数组下标的时候，一般是采用取模的方法。例如 hash%length;但是“取模运算 %“相对于”位与运算 a&n“是更慢的，所以如果能用“位与运算”替代取模运算的话，就会带来一定的性能优化。

但是，要用“位与运算&“替代“取模运算%”，需要满足一定的条件，那就是:

只有当length为2的n次方的时候，hash%length= hash &(length-1)才成立。

这也就解释了 HashMap 的长度为什么是 2 的幂次方。

举例：

length = 16 (二进制: 10000)
length - 1 = 15 (二进制: 01111)

假设 hash = 85 (二进制: 1010101)

方式1 - 取模运算:
85 % 16 = 5

方式2 - 位与运算:
1010101 & 01111 = 00101 = 5

结果相同！

因为当长度是2的幂时(如16)：

二进制表示会是1后面跟着n个0
length-1 就会变成n个1
这样做位与运算时，相当于保留了最后n位，效果等同于取模

22.Java 8 链表转红黑树和红黑树转链表为什么是8 和 6?

23.HashMap默认负载因子为什么是 0.75 这个值呢?设太大和太小有什么问题?

24.HashMap 和 HashTable 有什么区别?

HashMap 是线程不安全的，HashTable 是线程安全的;

由于线程安全，所以 HashTable 的效率比不上 HashMap;

HashMap最多只允许一条记录的键为null，允许多条记录的值为null，而 HashTable不允许;

HashMap 默认初始化数组的大小为16，HashTable 为 11，前者扩容时，扩大两倍，后者扩大两倍+1；

HashMap 需要重新计算 hash 值，而 HashTable 直接使用对象的 hashCode。

图1为 HashMap 的 hash 值生成，先得到 hashCode()，再高十六位异或低十六位。

25.Java8 为什么这里把key的hashcode取出来，然后把它右移16位，然后取异或?

因为int是4个字节，也就是32位，大概是有40亿的空间，如果哈希函数运用的比较松散，一般是很难出现哈希碰撞的。但是现实中一个长度为40亿的数组内存是放不下的并且HashMap在扩容前的数组的默认初始值为16，因此直接拿Hashcode值来用是不现实的。因此需要做一些运算。我们右移16位也即是把高位的数据右移到低位的16位，然后与自己做异或，那就是把高位和低位的数据进行混合，以此来加大低位的随机性，同时混合后的低位掺杂了高位的特征，这样高位的信息也被变相保存了下来。这么做主要是从速度，功效和质量来考虑的。

26.HashMap, LinkedHashMap，TreeMap 有什么区别?

HashMap 参考其他问题;

LinkedHashMap 保存了记录的插入顺序，在用 Iterator 遍历时，先取到的记录肯定是先插入的;遍历比HashMap 慢;

TreeMap 实现 SortMap 接口，能够把它保存的记录根据键排序(默认按键值升序排序，也可以指定排序的比较器。

27.为什么 ConcurrentHashMap 比 HashTable 效率要高?

底层数据结构: JDK1.7 的 ConcurrentHashMap 底层采用分段的数组+链表实现，JDK1.8 采用的数据结构跟HashMap1.8 的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用数组+链表的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的;实现线程安全的方式:

在 JDK1.7 的时候，ConcurrentHashMap 对整个桶数组进行了分割分段(Segment，分段锁)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。

到了 JDK1.8 的时候，ConcurrentHashMap 已经据弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。(JDK1.6 以后 synchronized 锁做了很多优化)整个看起来就像是优化过旦线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Seqment 的数据结构，但是已经简化了属性，只是为了兼容旧版本;

Hashtable(同一把锁):使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低

总结

hashmap容量保底是16，后面每次扩容时容量****2。执行插入操作时，先判断是否初始化，再根据数据的hash值计算索引（方法是高位左移16位后异或低位），接着插入node数组。如果索引处位置没有数据，直接插入；如果有，先判断这里是不是红黑树，如果不是那么插入链表中。如果链表有相同的键，那么直接覆盖原来的值；如果没有，那么使用尾插法插入链表中（头插法可能造成死循环）。插入完成后，判断链表是否需要转换成红黑树。所有步骤完成后，再判断整个数组是否需要扩容。

数组扩容的条件是LoadFactorCapacity，或者链表长度大于等于8且数组小于64。扩容的方法是创建一个容量为原来两倍的新数组，然后将存储好的数据重新分配新的索引复制到新数组中（具体原理是2的幂次与运算等价于取模以及“原索引+oldCapacity”）。链表和红黑树转换的阈值是8和6.

为啥重写equals方法的时候需要先重写hashCode方法?

hashmap中value的查找是通过 key 的 hashcode 来查找，通过 hashcode 计算找到对象下标(桶)地址后会用 equals 比较你传入的对象和 hashmap 中的 key 对象是否相同。
所以，如果equals判断相等的对象具有不同的哈希码，它们可能会被放置在不同的桶中，从而导致查找时无法找到预期的对象，造成数据一致性问题。

就像hashcode指的是身份证，而equals指的只是一个人的姓名，hachcode范围比equals更严格

举例：

public class Student {
    private int id;
    private String name;
    
    public Student(int id, String name) {
        this.id = id;
        this.name = name;
   
    
    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Student student = (Student) obj;
        return id == student.id && name.equals(student.name);
    }
}
public static void main(String[] args) {
    HashMap<Student, String> map = new HashMap<>();
    
    Student s1 = new Student(1, "Alice");
    map.put(s1, "Grade A");
    
    Student s2 = new Student(1, "Alice");
    // s1和s2通过equals比较是相等的
    System.out.println("s1 equals s2: " + s1.equals(s2)); // 输出 true
    
    // 如果不重写hashcode查找会失败
    System.out.println("Getting value for s2: " + map.get(s2));
}

Set集合有什么特点?如何实现key无重复的?

说一下 HashSet 的实现原理?

向HashSet 中add ()元素时，判断元素是否存在的依据，不仅要比较hash值，同时还要结合equles 方法比较。
HashSet 中的add()方法会使用HashMap 的put()方法,
HashMap 的 key 是唯一的，由源码可以看出 HashSet 添加进去的值就是作为HashMap 的key，并且在HashMap中如果K/V相同时，会用新的V覆盖掉旧的V，然后返回旧的V。所以不会重复。