集合

什么是集合

集合就是用于存储数据的容器，只能存储引用类型，所以集合非常适合用来存储对象。而且集合是长度可变，所以对象个数不确定的时候适合使用集合

集合的特点

1、集合只能存储引用数据类型。集合用于存储对象。

2、对象的个数确定可以使用数组，对象的个数不确定的可以用集合。因为集合是可变长度的。

集合和数组的区别

1、数组是固定长度的；集合可变长度的。

2、数组可以存储基本数据类型，也可以存储引用数据类型；集合只能存储引用数据类型。

3、数组存储的元素必须是同一个数据类型；集合存储的对象可以是不同数据类型。

使用集合框架的好处

• 减少开发工作，它提供了几乎所有常见类型的集合和用于迭代和操作数据的有用方法，因此，我们可以更专注于业务逻辑，而不是设计我们的集合api
• 提高代码质量，使用经过良好测试的核心集合类可以提高我们的程序质量，提高了代码的健壮性和可用性
• 可重用性和互操作性
• 降低维护成本 通过使用JDK附带的集合类，可以降低代码维护成本

骚戴理解：其实上面的优点有归咎于使用jdk自带的集合的话我们的编码会规范一点，例如ArrayList集合，这是我们用的jdk自带的统一规范的集合，那么这个集合的方法，具体使用无论在哪里都是一样的，但是如果是我们每个人自己设计自己的集合，首先要花很多时间，其次每个人设计的集合的方法名可能不一样，那么你自己用还好，要是别人也用你这个那还要去看你的方法名对应的功能是什么，他要是也写了个跟你一样的集合，定义的方法名也不一样，那就会很乱，所以用jdk自带的集合就会统一规范，不会像上面一样这么乱七八糟

常用的集合类有哪些？

Map接口和Collection接口是所有集合框架的父接口：

Collection集合的子接口有Set、List、Queue 三种子接口

Set接口的实现类主要有：HashSet、TreeSet、LinkedHashSet等

List接口的实现类主要有：ArrayList、LinkedList、Stack以及Vector等

Queue接口的实现类主要有：BlockingQueue、Deque等

Map接口的实现类主要有：HashMap、TreeMap、Hashtable、ConcurrentHashMap等

骚戴理解：注意没有TreeList

集合框架底层数据结构

Collection集合主要有List和Set两大接口

1、List

ArrayList：ArrayList是基于数组实现的，它的底层数据结构是一个可变的数组。当插入元素时，如果数组已满，则需要扩容，扩容的方式是创建一个新的数组，将原数组中的元素复制到新数组中，然后将新元素插入到新数组中。

LinkedList：LinkedList是基于链表实现的，它的底层数据结构是一个双向链表。当插入元素时，只需要修改链表中相应的指针，不需要像ArrayList那样进行数组的复制和扩容。

Vector：Vector是线程安全的List实现类，它的底层数据结构和ArrayList类似，也是一个可变的数组。不同的是，Vector的方法都是同步的，因此可以保证线程安全。

Stack：Stack是基于Vector实现的，它是一种后进先出（LIFO）的数据结构，支持压栈和出栈操作。

骚戴理解：Vector和Stack都是线程安全的类

2、Set

HashSet（无序，唯一）：基于HashMap实现的，默认构造函数是构建一个初始容量为16，负载因子为0.75 的HashMap。封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。

LinkedHashSet： LinkedHashSet 继承 HashSet，并且其内部是通过 LinkedHashMap

来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 Hashmap 实现一样，不过还是有一点点区别的。

TreeSet（有序，唯一）： 红黑树(平衡的排序二叉树)

3、Map

HashMap： JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）.JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间

LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表来保持键值对的插入顺序。同时通过对链表进行相应的操作， 实现了访问顺序相关逻辑。

HashTable： 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的

TreeMap： 红黑树（自平衡的排序二叉树）

ConcurrentHashMap：Java中线程安全的哈希表实现，它的底层数据结构是分段锁的哈希表。具体来说，它将整个哈希表分成了多个段(segment)，每个段都是一个独立的哈希表，每个段都有自己的锁，因此可以实现多线程并发访问，提高了并发性能。

每个段的大小可以通过参数进行配置，默认是16。在ConcurrentHashMap中，每个元素被存储在一个Entry对象中，Entry对象包含了key、value和一个指向下一个Entry的指针。每个段都包含一个Entry数组，数组的每个元素都是一个链表的头结点，每个链表中存储了哈希值相同的元素。

在进行插入、查找、删除等操作时，首先需要根据key的哈希值找到对应的段，然后在该段中进行操作。由于每个段都有自己的锁，因此不同的线程可以同时访问不同的段，从而提高了并发性能。

总之，ConcurrentHashMap是Java中线程安全的哈希表实现，采用分段锁的哈希表作为底层数据结构，可以实现高效的多线程并发访问。

哪些集合类是线程安全的？哪些集合类是线程不安全的？

哪些集合类是线程安全的？

• Vector：只要是关键性的操作，方法前面都加了synchronized关键字，来保证线程的安全性
• Hashtable：使用了synchronized关键字，所以相较于Hashmap是线程安全的。
• ConcurrentHashMap:使用锁分段技术确保线性安全，是一种高效但是线程安全的集合。
• Stack：栈，也是线程安全的，继承于Vector。

哪些集合类是线程不安全的？

• Hashmap
• Arraylist
• LinkedList
• HashSet
• TreeSet
• TreeMap

线程不安全的原因

• Hashmap：HashMap在put操作的时候，如果插入的元素超过了容量（由负载因子决定）的范围就会触发扩容操作，就是resize，这个会重新将原数组的内容重新hash到新的扩容数组中，在多线程的环境下，存在同时其他的元素也在进行put操作，如果hash值相同，可能出现同时在同一数组下用链表表示，造成闭环，导致在get时会出现死循环，所以HashMap是线程不安全的。
• Arraylist： List 对象在做 add 时，执行 Arrays.copyOf 的时候，返回一个新的数组对象。当有线程 A、B… 同时进入 grow方法，多个线程都会执行 Arrays.copyOf 方法，返回多个不同的 elementData 对象，假如，A先返回，B 后返回，那么 List.elementData ==A. elementData,如果同时B也返回，那么 List.elementData ==B. elementData,所以线程B就把线程A的数据给覆盖了，导致线程A的数据被丢失。
• LinkedList：与Arraylist线程安全问题相似，线程安全问题是由多个线程同时写或同时读写同一个资源造成的。
• HashSet：底层数据存储结构采用了Hashmap，所以Hashmap会产生的线程安全问题HashSet也会产生。

Java集合的快速失败机制 “fail-fast”？

什么是快速失败机制 “fail-fast”？

fail-fast 机制，即快速失败机制，是java集合(Collection)中的一种错误检测机制。

当多个线程对同一个集合的内容进行操作时，就有可能出现在一个线程正在迭代集合的过程中，别的线程修改了这个集合的内容，这就会产生fail-fast事件，抛出 ConcurrentModificationException异常，单线程也可能会出现fail-fast事件

例如：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。但是要注意，fail-fast机制并不保证在不同步的修改下一定会抛出异常，它只是尽最大努力去抛出，所以这种机制一般仅用于检测bug

fail-fast的出现场景

在我们常见的java集合中就可能出现fail-fast机制,比如ArrayList，HashMap。在多线程和单线程环境下都有可能出现快速失败。

单线程环境下的fail-fast

public static void main(String[] args) {List<String> list = new ArrayList<>();for (int i = 0 ; i < 10 ; i++ ) {list.add(i + "");}Iterator<String> iterator = list.iterator();int i = 0 ;while(iterator.hasNext()) {if (i == 3) {list.remove(3);}System.out.println(iterator.next());i ++;}
}

该段代码定义了一个Arraylist集合，并使用迭代器遍历，在遍历过程中，刻意在某一步迭代中remove一个元素，这个时候，就会发生fail-fast。

public static void main(String[] args) {Map<String, String> map = new HashMap<>();for (int i = 0 ; i < 10 ; i ++ ) {map.put(i+"", i+"");}Iterator<Entry<String, String>> it = map.entrySet().iterator();int i = 0;while (it.hasNext()) {if (i == 3) {map.remove(3+"");}Entry<String, String> entry = it.next();System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());i++;}
}

该段代码定义了一个hashmap对象并存放了10个键值对，在迭代遍历过程中，使用map的remove方法移除了一个元素，导致抛出了 ConcurrentModificationException异常

多线程环境下

public class FailFastTest {public static List<String> list = new ArrayList<>();private static class MyThread1 extends Thread {@Overridepublic void run() {Iterator<String> iterator = list.iterator();while(iterator.hasNext()) {String s = iterator.next();System.out.println(this.getName() + ":" + s);try {Thread.sleep(1000);} catch (InterruptedException e) {e.printStackTrace();}}super.run();}}private static class MyThread2 extends Thread {int i = 0;@Overridepublic void run() {while (i < 10) {System.out.println("thread2:" + i);if (i == 2) {list.remove(i);}try {Thread.sleep(1000);} catch (InterruptedException e) {e.printStackTrace();}i ++;}}}public static void main(String[] args) {for(int i = 0 ; i < 10;i++){list.add(i+"");}MyThread1 thread1 = new MyThread1();MyThread2 thread2 = new MyThread2();thread1.setName("thread1");thread2.setName("thread2");thread1.start();thread2.start();}
}

启动两个线程，其中一个线程1对list进行迭代，另一个线程2在线程1的迭代过程中去remove一个元素，结果也是抛出了java.util.ConcurrentModificationException

上面都是讲的删除导致集合结构改变而造成快速失败的情况，如果是添加导致的集合结构改变，也是会出现快速失败的，这里就不再举例了。

实现原理分析

final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();
}

可以看出，该方法才是判断是否抛出ConcurrentModificationException异常的关键。

在该段代码中，当modCount != expectedModCount时，就会抛出该异常。但是在一开始的时候，expectedModCount初始值默认等于modCount，为什么会出现modCount != expectedModCount？

很明显expectedModCount在整个迭代过程除了一开始赋予初始值modCount外，并没有在任何地方对其进行修改操作，不可能发生改变，所以可能发生改变的就只有modCount。下面我们在通过源码来看一下什么时候“modCount 不等于 expectedModCount”，通过ArrayList的源码，来看看modCount是如何被修改的。

package java.util;
public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{...// list中容量变化时，对应的同步函数public void ensureCapacity(int minCapacity) {modCount++;int oldCapacity = elementData.length;if (minCapacity > oldCapacity) {Object oldData[] = elementData;int newCapacity = (oldCapacity * 3)/2 + 1;if (newCapacity < minCapacity)newCapacity = minCapacity;// minCapacity is usually close to size, so this is a win:elementData = Arrays.copyOf(elementData, newCapacity);}}// 添加元素到队列最后public boolean add(E e) {// 修改modCountensureCapacity(size + 1);  // Increments modCount!!elementData[size++] = e;return true;}// 添加元素到指定的位置public void add(int index, E element) {if (index > size || index < 0)throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);// 修改modCountensureCapacity(size+1);  // Increments modCount!!System.arraycopy(elementData, index, elementData, index + 1,size - index);elementData[index] = element;size++;}// 添加集合public boolean addAll(Collection<? extends E> c) {Object[] a = c.toArray();int numNew = a.length;// 修改modCountensureCapacity(size + numNew);  // Increments modCountSystem.arraycopy(a, 0, elementData, size, numNew);size += numNew;return numNew != 0;}// 删除指定位置的元素public E remove(int index) {RangeCheck(index);// 修改modCountmodCount++;E oldValue = (E) elementData[index];int numMoved = size - index - 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index, numMoved);elementData[--size] = null; // Let gc do its workreturn oldValue;}// 快速删除指定位置的元素private void fastRemove(int index) {// 修改modCountmodCount++;int numMoved = size - index - 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--size] = null; // Let gc do its work}// 清空集合public void clear() {// 修改modCountmodCount++;// Let gc do its workfor (int i = 0; i < size; i++)elementData[i] = null;size = 0;}...
}

我们发现：无论是add()、remove()，还是clear()，只要涉及到修改集合中的元素个数时，都会改变modCount的值。

接下来，我们再系统的梳理一下fail-fast是怎么产生的。步骤如下：

1、新建了一个ArrayList，名称为arrayList。

2、向arrayList中添加内容。

3、新建一个“线程a”，并在“线程a”中通过Iterator反复的读取arrayList的值。

4、新建一个“线程b”，在“线程b”中删除arrayList中的一个“节点A”。

5、这时，就会产生有趣的事件了。

• 在某一时刻，“线程a”创建了arrayList的Iterator。此时“节点A”仍然存在于arrayList中，创建arrayList时，expectedModCount = modCount(假设它们此时的值为N)。
• 在“线程a”在遍历arrayList过程中的某一时刻，“线程b”执行了，并且“线程b”删除了arrayList中的“节点A”。“线程b”执行remove()进行删除操作时，在remove()中执行了“modCount++”，此时modCount变成了N+1！
• 线程a”接着遍历，当它执行到next()函数时，调用checkForComodification()比较“expectedModCount”和“modCount”的大小；而“expectedModCount=N”，“modCount=N+1”,这样，便抛出ConcurrentModificationException异常，产生fail-fast事件。

至此，我们就完全了解了fail-fast是如何产生的！

实现原理总结

final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();
}

有一个checkForComodification方法，当多个线程对同一个集合进行操作的时候，某线程访问集合的过程中，该集合的内容被其他线程所改变(其它线程通过add、remove、clear等方法，调用这些方法modCount都会自增，也就是modCount++)，改变了modCount的值，当modCount != expectedModCount时（在一开始的时候expectedModCount初始值默认等于modCount），这时就会抛出ConcurrentModificationException异常，产生fail-fast事件。

解决办法：

1、在遍历过程中，所有涉及到改变modCount值得地方全部加上synchronized。

1、使用CopyOnWriteArrayList来替换ArrayList

怎么确保一个集合不能被修改？

可以使用 Collections. unmodifiableCollection(Collection c) 方法来创建一个只读集

合，这样改变集合的任何操作都会抛出 Java. lang. UnsupportedOperationException 异常。

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

List、Set、Map 是否继承自Collection 接口？List，Set，Map三者的区别？List、Map、Set 三个接口存取元素时，各有什么特点？

1、List、Set、Map 是否继承自Collection 接口？

Java 容器分为 Collection 和 Map 两大类，Collection集合的子接口有Set、List、Queue 三种子接口。我们比较常用的是Set、List，Map接口不是collection的子接口。 Collection集合主要有List和Set两大接口

2、List，Set，Map三者的区别

List：一个有序（元素存入集合的顺序和取出的顺序一致）容器，元素可以重复，可以插入多个null元素，元素都有索引。

List接口常用的实现类有 ArrayList、LinkedList 和 Vector。

Set：一个无序（存入和取出顺序有可能不一致）容器，不可以存储重复元素，只允许存入一个null元素，必须保证元素唯一性。

Set 接口常用实现类是 HashSet、LinkedHashSet 以及TreeSet。

Map：一个键值对集合，存储键、值和之间的映射。 Key无序，唯一；value 不要求有序，允许重复。Map没有继承于Collection接口，从Map集合中检索元素时，只要给出键对象，就会返回对应的值对象。

Map 的常用实现类：HashMap、TreeMap、HashTable、LinkedHashMap、ConcurrentHashMap

3、List、Map、Set 三个接口存取元素时，各有什么特点？

List、Map、Set 三个接口存放时

• List以特定的索引(有顺序的存放)来存放元素,可以有重复的元素
• Set存放元素是无序的,而且不可重复（用对象的equals()方法来区分元素是否重复）
• Map保存键值对的映射,映射关系可以是一对一(键值)或者多对一,需要注意到的是：键无序不可重复,值可以重复

List、Map、Set 三个接口取出时

• List取出元素for循环，foreach循环，Iterator迭代器迭代
• Set取出元素foreach循环，Iterator迭代器迭代
• Map取出元素foreach循环，Iterator迭代器迭代

遍历map集合的方式有哪些

遍历Map集合的方式有以下几种：

1. 使用Iterator迭代器遍历Map集合。通过获取Map的entrySet()方法返回的Set集合，再通过Set集合的iterator()方法获取Iterator迭代器，最后使用while循环遍历Map集合中的元素。示例代码如下：

Map<String, Integer> map = new HashMap<>();map.put("A", 1);map.put("B", 2);map.put("C", 3);Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();while (iterator.hasNext()) {Map.Entry<String, Integer> entry = iterator.next();System.out.println(entry.getKey() + " : " + entry.getValue());}

2. 使用for-each循环遍历Map集合。通过获取Map的entrySet()方法返回的Set集合，再通过for-each循环遍历Set集合中的元素。示例代码如下：

Map<String, Integer> map = new HashMap<>();map.put("A", 1);map.put("B", 2);map.put("C", 3);for (Map.Entry<String, Integer> entry : map.entrySet()) {System.out.println(entry.getKey() + " : " + entry.getValue());}

3. 遍历Map集合的键或值。通过获取Map的keySet()方法返回的Set集合，或values()方法返回的Collection集合，再通过for-each循环遍历Set或Collection集合中的元素。示例代码如下：

Map<String, Integer> map = new HashMap<>();map.put("A", 1);map.put("B", 2);map.put("C", 3);for (String key : map.keySet()) {System.out.println(key + " : " + map.get(key));}for (Integer value : map.values()) {System.out.println(value);}

总之，遍历Map集合的方式有多种，需要根据具体的需求和场景选择合适的方式。

comparable 和 comparator的区别？

comparable 和 comparator的区别？

• comparable接口实际上是出自java.lang包，它有一个 compareTo(Object obj)方法用来排序，comparator接口实际上是出自 java.util 包，它有一个compare(Object obj1, Object obj2)方法用来排序
• Comparable是排序接口，若一个类实现了Comparable接口，就意味着“该类支持排序”。而Comparator是比较器，通过一个类实现这个接口来作为一个比较器来进行排序。
• Comparable相当于“内部比较器”，而Comparator相当于“外部比较器”。

各自的优劣

• 用Comparable 简单， 只要实现Comparable 接口的对象直接就成为一个可以比较的对象，但是需要修改源代码。
• 用Comparator 的好处是不需要修改源代码， 而是另外实现一个比较器， 当某个自定义的对象需要作比较的时候，把比较器和对象一起传递过去就可以比大小了， 并且在Comparator 里面用户可以自己实现复杂的可以通用的逻辑，使其可以匹配一些比较简单的对象，那样就可以节省很多重复劳动了。

Comparable和Comparator的 介绍和实例

Comparable

Comparable是排序接口。若一个类实现了Comparable接口，就意味着该类支持排序。实现了Comparable接口的类的对象的列表或数组可以通过Collections.sort或Arrays.sort进行自动排序。此外，实现此接口的对象可以用作有序映射中的键或有序集合中的集合，无需指定比较器。该接口定义如下：

package java.lang;
import java.util.*;
public interface Comparable<T> 
{public int compareTo(T o);
}

此接口只有一个方法compareTo，比较此对象与指定对象的顺序，如果该对象小于、等于或大于指定对象，则分别返回负整数、零或正整数。

现在有两个Person类的对象，我们如何来比较二者的大小呢？我们可以通过让Person实现Comparable接口：

public class Person implements Comparable<Person>
{String name;int age;public Person(String name, int age){super();this.name = name;this.age = age;}public String getName(){return name;}public int getAge(){return age;}@Overridepublic int compareTo(Person p){return this.age-p.getAge();}public static void main(String[] args){Person[] people=new Person[]{new Person("xujian", 20),new Person("xiewei", 10)};System.out.println("排序前");for (Person person : people){System.out.print(person.getName()+":"+person.getAge());}Arrays.sort(people);System.out.println("\n排序后");for (Person person : people){System.out.print(person.getName()+":"+person.getAge());}}
}

执行结果

Comparator

Comparator是比较接口，我们如果需要控制某个类的次序，而该类本身不支持排序(即没有实现Comparable接口)，那么我们就可以建立一个“该类的比较器”来进行排序，这个“比较器”只需要实现Comparator接口即可。也就是说，我们可以通过实现Comparator来新建一个比较器，然后通过这个比较器对类进行排序。该接口定义如下：

package java.util;
public interface Comparator<T>{int compare(T o1, T o2);boolean equals(Object obj);}

注意

1、若一个类要实现Comparator接口：它一定要实现compare(T o1, T o2) 函数，但可以不实现 equals(Object obj) 函数。

2、int compare(T o1, T o2) 是“比较o1和o2的大小”。返回“负数”，意味着“o1比o2小”；返回“零”，意味着“o1等于o2”；返回“正数”，意味着“o1大于o2”。

现在假如上面的Person类没有实现Comparable接口，该如何比较大小呢？我们可以新建一个类，让其实现Comparator接口，从而构造一个“比较器"。

public class PersonCompartor implements Comparator<Person>
{@Overridepublic int compare(Person o1, Person o2){return o1.getAge()-o2.getAge();}
}
public class Person
{String name;int age;public Person(String name, int age){super();this.name = name;this.age = age;}public String getName(){return name;}public int getAge(){return age;}public static void main(String[] args){Person[] people=new Person[]{new Person("xujian", 20),new Person("xiewei", 10)};System.out.println("排序前");for (Person person : people){System.out.print(person.getName()+":"+person.getAge());}Arrays.sort(people,new PersonCompartor());System.out.println("\n排序后");for (Person person : people){System.out.print(person.getName()+":"+person.getAge());}}
}

执行结果

Collection 和 Collections 有什么区别？

Collection和Collections是Java集合框架中的两个不同的概念。

1. Collection是Java集合框架中的一个接口，它是所有集合类的根接口，提供了一些通用的方法，如添加、删除、遍历等。

2. Collections是Java集合框架中的一个工具类，提供了一系列静态方法，用于对集合进行操作，如排序、查找、替换、复制、反转等。

简而言之，Collection是一个接口，表示集合类的基本特性和行为，而Collections是一个工具类，提供了对集合进行操作的方法。

Collections 常用的方法有哪些

Collections是Java集合框架中的一个工具类，提供了一系列常用的集合操作方法，包括排序、查找、替换、复制、反转等。常用的Collections方法包括：

1. sort(List<T> list)：对List集合进行排序，排序规则为自然顺序（从小到大）。

2. sort(List<T> list, Comparator<? super T> c)：对List集合进行排序，排序规则由Comparator指定。

3. binarySearch(List<? extends Comparable<? super T>> list, T key)：在有序List集合中查找指定元素，返回元素的索引值。

4. binarySearch(List<? extends T> list, T key, Comparator<? super T> c)：在有序List集合中查找指定元素，返回元素的索引值，查找规则由Comparator指定。

5. reverse(List<?> list)：反转List集合中的元素。

6. shuffle(List<?> list)：随机打乱List集合中的元素顺序。

7. swap(List<?> list, int i, int j)：交换List集合中指定位置的两个元素。

8. fill(List<? super T> list, T obj)：将List集合中的所有元素替换为指定元素。

9. copy(List<? super T> dest, List<? extends T> src)：将src集合中的元素复制到dest集合中。

10. max(Collection<? extends T> coll)：返回Collection集合中的最大元素。

11. min(Collection<? extends T> coll)：返回Collection集合中的最小元素。

迭代器Iterator

迭代器 Iterator 是什么？

迭代器（Iterator）是Java集合框架中的一个接口，用于遍历集合中的元素。迭代器提供了一种通用的遍历方式，可以遍历任何类型的集合，包括List、Set、Map等。它可以实现集合的单向遍历，即只能从前往后遍历，不能倒着遍历。在遍历过程中，可以删除集合中的元素，但不能修改集合中的元素。

Iterator 怎么使用？

（1）Iterator（）要求容器返回一个Iterator。Iterator将准备好返回序列的第一个元素。
（2）使用next（）获得序列中的下一个元素
（3）使用hasNext（）检查序列中是否还有元素。
（4）使用remove（）删除上一次Iterator.next()方法返回的对象。

List list = new ArrayList<>();
Iterator iterator = list.iterator();//list集合实现了Iterable接口
while (iterator.hasNext()) {String string = iterator.next();//do something
}

Iterator有什么优点？

迭代器（Iterator）是Java集合框架中的一个重要接口，具有以下优点：

1. 通用性强：迭代器提供了一种通用的遍历方式，可以遍历任何类型的集合，包括List、Set、Map等。

2. 简单易用：使用迭代器遍历集合非常简单，只需要通过调用Iterator的方法，如hasNext()、next()、remove()等，即可完成遍历。

3. 安全可靠：使用迭代器遍历集合可以保证线程安全，避免了多线程环境下的并发访问问题。

4. 支持删除操作：使用迭代器遍历集合可以方便地删除集合中的元素，而不需要考虑删除元素后的索引变化问题。

5. 性能高效：使用迭代器遍历集合的性能非常高效，尤其是对于大型集合，可以避免一次性加载所有元素的问题。

Iterator有什么特点？

Iterator是Java集合框架中的一个接口，用于遍历集合中的元素。它的特点如下：

1. 可以遍历任何类型的集合，包括List、Set、Map等。

2. 可以实现集合的单向遍历，即只能从前往后遍历，不能倒着遍历。

3. 可以在遍历过程中删除集合中的元素，但不能修改集合中的元素，否则会抛出ConcurrentModificationEception的异常。

4. 可以使用泛型，避免了类型转换的麻烦。

5. Iterator必须依附于一个集合类对象而存在，Iterator本身不具有装载数据对象的功能。

如何边遍历边移除 Collection 中的元素？

边遍历边移除Collection 的唯一正确方式是使用 Iterator.remove() 方法，如下：

List list = new ArrayList<>();
Iterator<Integer> it = list.iterator();
//正确的移除方法
while(it.hasNext()){
//设置移除元素的条件it.remove();
} //一种最常见的错误代码如下
for(Integer i : list){ list.remove(i)；//报 ConcurrentModificationException 异常
}

骚戴理解：也就是只能通过迭代器实例的remove方法来移除，而不能通过集合本身的remove方法来移除，如果用集合本身的remove方法就会触发fail-fast机制产生ConcurrentModificationException 异常，因为不允许一个线程在遍历 Collection 时另一个线程修改它。

Iterator 和 ListIterator 有什么区别？

Iterator和ListIterator都是Java集合框架中的接口，用于遍历集合中的元素。它们的主要区别如下：

1. 遍历方向不同：Iterator只能向前遍历集合中的元素，而ListIterator可以向前或向后遍历集合中的元素。

2. 支持元素操作不同：Iterator只能遍历集合中的元素，不能进行添加、修改等操作，而ListIterator可以在遍历过程中添加、修改、删除集合中的元素。

3. 支持方法不同：ListIterator相对于Iterator多了一些方法，如previous()、hasPrevious()、add()、set()等，用于在遍历过程中向前遍历、添加元素、修改元素等操作。

4. 支持的集合类型不同：Iterator可以遍历任何类型的集合，包括List、Set、Map等，而ListIterator只能遍历List类型的集合。

骚戴理解：如果需要遍历List集合并支持元素操作，应该使用ListIterator；如果只需要遍历集合中的元素，可以使用Iterator。

遍历一个 List 有哪些不同的方式？每种方法的实现原理是什么？

遍历一个List集合有以下几种不同的方式：

1. for循环遍历

使用for循环遍历List集合，可以使用下标访问集合中的元素。实现原理是通过循环控制变量遍历List集合，通过下标访问集合中的元素。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
for (int i = 0; i < list.size(); i++) {String element = list.get(i);System.out.println(element);
}

讲解原理

for循环遍历List集合的实现原理是通过循环控制变量遍历List集合，通过下标访问集合中的元素。

for循环的语法格式如下：

for (初始化表达式; 布尔表达式; 更新表达式) {// 循环体
}

其中，初始化表达式用于初始化循环控制变量，布尔表达式用于判断循环是否继续执行，更新表达式用于更新循环控制变量的值。

在for循环遍历List集合时，初始化表达式通常是将循环控制变量初始化为0，布尔表达式通常是判断循环控制变量是否小于List集合的长度，更新表达式通常是将循环控制变量加1。循环体中可以通过下标访问List集合中的元素，实现遍历List集合的功能。

2. foreach循环遍历

使用foreach循环遍历List集合，可以直接访问集合中的元素。foreach循环遍历的实现原理是通过遍历List集合中的每个元素，自动获取元素的值并赋给循环变量，然后执行循环体中的语句。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
for (String element : list) {System.out.println(element);
}

讲解原理

具体来说，foreach循环首先会获取List集合的迭代器，然后使用该迭代器遍历集合中的每个元素。在遍历过程中，循环变量会自动获取元素的值，并将其赋给循环变量。然后，执行循环体中的语句，完成对List集合的遍历操作。

与for循环遍历List集合相比，foreach循环遍历List集合的语法更加简洁，不需要显式地使用下标访问集合中的元素，可以直接访问元素变量。因此，foreach循环更加易于理解和使用，是遍历List集合的常用方式之一。

3. 迭代器遍历

使用迭代器遍历List集合，可以遍历任何类型的集合，包括List、Set、Map等。实现原理是通过获取List集合的迭代器，使用hasNext()、next()方法遍历集合中的元素。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {String element = iterator.next();System.out.println(element);
}

4. ListIterator遍历

使用ListIterator遍历List集合，可以向前或向后遍历集合中的元素，并支持元素操作。实现原理是通过获取List集合的ListIterator，使用hasNext()、next()、hasPrevious()、previous()、add()、set()等方法遍历集合中的元素。

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
ListIterator<String> iterator = list.listIterator();
while (iterator.hasNext()) {String element = iterator.next();System.out.println(element);
}

集合的各种遍历方式的使用场景有哪些？

集合的各种遍历方式适用于各种场景，具体如下：

1. for循环遍历：适用于需要根据元素的下标来访问集合中的元素的场合（例如List集合），例如需要对集合中的元素进行修改或删除操作时。

2. foreach循环遍历：适用于只需要访问集合中的元素，不需要根据元素的下标来访问的场合，例如只需要对集合中的元素进行读取操作时。

3. 迭代器遍历：适用于需要对集合中的元素进行修改或删除操作的场合，因为在使用迭代器遍历集合时，可以通过迭代器的remove()方法删除集合中的元素。

4. Lambda表达式遍历：适用于需要对集合中的元素进行函数式处理的场合，例如对集合中的元素进行过滤、映射、排序等操作时。

集合的各种遍历方式的性能分析？

在遍历集合时，不同的遍历方式具有不同的性能表现，具体的性能排名取决于集合的类型、大小、元素类型等多种因素。以下是一般情况下各种遍历方式的性能排名：

1. for循环遍历：性能最好，因为使用下标访问集合中的元素速度较快。

2. 迭代器遍历：性能次之，因为迭代器可以直接访问集合中的元素，避免了每次都需要计算下标的开销。

3. foreach循环遍历：性能较差，因为使用foreach循环遍历集合时，需要先获取迭代器，然后使用迭代器遍历集合中的元素，相比于直接使用下标访问集合中的元素，速度较慢。

4. Lambda表达式遍历：性能较差，因为Lambda表达式需要编译成函数对象，而且在遍历集合时需要进行函数式处理，相比于直接访问集合中的元素，速度较慢。

5. Stream API遍历：性能最差，因为Stream API需要进行多次操作，例如过滤、映射、排序等，每次操作都需要创建新的对象，相比于直接访问集合中的元素，速度较慢。

需要注意的是，以上性能排名仅供参考，实际性能可能会受到多种因素的影响，例如集合的大小、元素类型、遍历次数等。因此，在实际开发中，需要根据具体情况选择最优的遍历方式。同时，也可以使用性能分析工具来评估不同遍历方式的性能表现。

ArrayList

说一下 ArrayList 的优缺点

ArrayList 是 Java 中常用的动态数组实现，它具有以下优缺点：

优点：

1. 随机访问速度快：ArrayList 底层使用数组实现，可以通过下标直接访问数组中的元素，因此随机访问速度快。

2. 遍历速度较快：ArrayList 支持快速遍历，因为它的底层是一个数组，可以利用 CPU 缓存来提高遍历速度。

3. 可以存储基本数据类型：ArrayList 可以存储基本数据类型和对象类型，而且可以自动装箱和拆箱。

缺点：

1. 插入和删除操作性能较差：由于 ArrayList 底层使用数组实现，因此在插入和删除元素时，需要移动其他元素，导致性能较差。

2. 不支持多线程并发访问：ArrayList 不是线程安全的，如果多个线程同时对 ArrayList 进行修改操作，可能会导致数据不一致或抛出 ConcurrentModificationException 异常。

3. 内存空间浪费：ArrayList 在创建时需要指定初始容量，如果容量不足时需要进行扩容操作，而且扩容时需要重新分配内存空间，可能会导致内存空间浪费。

骚戴理解：ArrayList 适用于随机访问和修改操作较多的场景，但是在插入和删除操作较多的场景下，LinkedList 可能更加适合。同时，在多线程并发访问的场景下，可以使用 Vector 或 CopyOnWriteArrayList 等线程安全的 List 实现。

如何实现数组和 List 之间的转换？

数组转 List：使用 Arrays. asList(array) 进行转换。

List 转数组：使用 List 自带的 toArray() 方法。

// List 转数组
List list = new ArrayList();
list.add("123");
list.add("456");
list.toArray();
// 数组转 List
listString[] array = new String[]{"123","456"};
Arrays.asList(array);

ArrayList 和 LinkedList 的区别是什么？

ArrayList 和 LinkedList 都是 Java 中常用的 List 实现，它们的区别主要体现在以下几个方面：

1. 底层实现方式不同：ArrayList 底层使用数组实现，而 LinkedList 底层使用双向链表实现。

2. 随机访问和遍历性能不同：由于 ArrayList 底层使用数组实现，因此支持快速随机访问和遍历，而且可以利用 CPU 缓存提高访问速度；而 LinkedList 的遍历速度较慢，因为需要从头节点开始遍历每个节点，而且无法利用 CPU 缓存提高访问速度。

3. 插入和删除操作性能不同：由于 ArrayList 底层使用数组实现，因此在插入和删除元素时，需要移动其他元素，导致性能较差；而 LinkedList 的插入和删除操作性能较好，因为只需要修改相邻节点的指针即可。

4. 内存空间占用不同：LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。而 ArrayList 则是使用数组实现，每个元素只需要存储数据本身就可以了，因此相对来说占用的内存空间较小。LinkedList 的每个节点都需要额外存储两个指针，因此在存储大量元素时，可能会导致内存占用较大。而 ArrayList 在创建时需要指定初始容量，如果容量不足时需要进行扩容操作，而且扩容时需要重新分配内存空间，可能会导致内存空间浪费。

骚戴理解：ArrayList 适用于随机访问和修改操作较多的场景，但是在插入和删除操作较多的场景下，LinkedList 可能更加适合。

双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

ArrayList 和 Vector 的区别是什么？

这两个类都实现了 List 接口（List 接口继承了 Collection 接口），他们都是有序集合

1、线程安全：Vector 使用了 Synchronized 来实现线程同步，是线程安全的，而 ArrayList 是非线程安全的。

2、性能：ArrayList 在性能方面要优于 Vector。Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。

3、扩容：当 ArrayList 需要扩容时，它会创建一个新的数组，并将原数组中的元素复制到新数组中，新数组的大小是原数组的 1.5 倍。而 Vector 扩容时会创建一个新的数组，并将原数组中的元素复制到新数组中，新数组的大小是原数组的 2 倍。因此，Vector 的扩容比 ArrayList 更加消耗内存，但是相对来说 Vector 的性能更稳定，因为它的扩容次数相对较少。

骚戴理解：Vector 是线程安全的，而 ArrayList 不是线程安全的，如果需要在多线程环境中使用 ArrayList，需要进行同步处理。

插入数据时，ArrayList、LinkedList、Vector谁速度较快？

在插入数据时，LinkedList 的速度相对较快，因为它的底层是一个链表结构，插入一个元素只需要修改相邻节点的指针即可，时间复杂度为 O(1)。而 ArrayList 和 Vector 的底层是一个数组结构，插入一个元素需要将后面的元素向后移动一位，时间复杂度为 O(n)，其中 n 是数组的长度。因此在插入数据时，LinkedList 的性能比 ArrayList 和 Vector 更好。Vector 中的方法由于加了 synchronized 修饰，因此 Vector是线程安全容器，性能上较ArrayList差。

插入速度快到慢排序：LinkedList>ArrayList>Vector

多线程场景下如何使用 ArrayList？

ArrayList 不是线程安全的，如果遇到多线程场景，可以通过 Collections 的synchronizedList 方法将其转换成线程安全的容后再使用。

    List<String> list = new ArrayList<>();List<String> synchronizedList = Collections.synchronizedList(list);synchronizedList.add("aaa");synchronizedList.add("bbb");for(int i =0; i < synchronizedList.size(); i++){	System.out.println(synchronizedList.get(i));}

为什么 ArrayList 的 elementData 加上 transient 修饰？

为什么 ArrayList 的 elementData 加上 transient 修饰？

ArrayList中将elementData修饰成transient是为了节省空间，ArrayList的自动扩容机制，elementData数组相当于容器，当容器不足时就会再扩充容量，但是容器的容量往往都是大于或者等于ArrayList所存元素的个数。所以ArrayList的设计者将elementData设计为transient，这样这个数组就不会被序列化，然后在writeObject方法中手动将其序列化，并且只序列化了实际存储的那些元素，而不是整个elementData数组。

比如，现在实际有了8个元素，那么elementData数组的容量可能是8x1.5=12，如果直接序列化elementData数组，那么就会浪费4个元素的空间，特别是当元素个数非常多时，这种浪费是非常不合算的。

序列化和反序列化的定义

Java序列化就是指把Java对象转换为字节序列的过程

Java反序列化就是指把字节序列恢复为Java对象的过程。

transient关键字

被transient修饰的成员变量不会被序列化。

代码解析

ArrayList 中的数组定义如下：

private transient Object[] elementData;

再 看 一 下 ArrayList 的 定 义 ：

public class ArrayList<E>extends AbstractList<E>implementsList<E>, RandomAccess, Cloneable, java.io.Serializable

可以看到 ArrayList 实现了 Serializable 接口，这意味着 ArrayList 支持序列化。

transient 的作用是希望 elementData 数组不被序列化

重写了 writeObject 实现：

private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException{int expectedModCount = modCount;s.defaultWriteObject();s.writeInt(elementData.length);for(int i=0; i<size; i++)s.writeObject(elementData[i]);if(modCount != expectedModCount){thrownewConcurrentModificationException();}}

骚戴理解：从源码中，可以观察到 循环时是使用i<size而不是 i<elementData.length，说明序列化时，只需实际存储的那些元素，而不是整个数组。

Array （数组）和 ArrayList 有何区别？

• Array 可以存储基本数据类型和引用类型，ArrayList 只能存储引用类型。
• Array 是指定固定大小的，而 ArrayList 大小是自动扩展的。
• Array 内置方法没有 ArrayList 多，比如 addAll、removeAll、iteration 等方法只有ArrayList 有。
• Array 数组存储的元素必须是同一个数据类型；ArrayList 存储的对象可以是不同数据类型。

CopyOnWriteArrayList 是什么，可以用于什么应用场景？有哪些优缺点？

什么是CopyOnWrite ？

CopyOnWrite 容器即写时复制的容器。通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行 Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。这样做的好处是我们可以对 CopyOnWrite 容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。所以 CopyOnWrite 容器也是一种读写分离的思想，读和写不同的容器。

CopyOnWriteArrayList 是什么？

CopyOnWriteArrayList 是线程安全的集合，它的实现方式是在写操作时创建一个新的数组，并将原数组中的元素复制到新数组中，然后在新数组中进行写操作，最后将新数组替换为原数组。

读操作则直接在原数组中进行，因此读操作不需要进行同步处理，可以实现读写分离。由于每次写操作都会创建一个新的数组，因此 CopyOnWriteArrayList 的写操作相对较慢，但是读操作的性能很高。

需要注意的是，CopyOnWriteArrayList 的迭代器是弱一致性的，也就是说，在迭代过程中，如果有其他线程对 List 进行了修改，迭代器不会抛出 ConcurrentModificationException 异常，但是不保证迭代器能够遍历到所有的元素。CopyOnWriteArrayList 的使用场景是合适读多写少的场景。

骚戴理解：不能保证迭代器能够遍历到所有元素是为什么呢？例如我有个集合，里面有十个元素，我已经遍历了五个，这个时候我在前五个元素之间添加了一个新元素，但是由于已经遍历到第五个了，所以只会往后继续遍历，而遍历之前的改变就无法遍历到！

CopyOnWriteArrayList 有什么优点？

CopyOnWriteArrayList 的优点主要包括以下几点：

1. 线程安全：CopyOnWriteArrayList 是线程安全的 List 实现，可以在多线程环境中使用，无需进行额外的同步处理。

2. 读写分离：CopyOnWriteArrayList 的读操作和写操作是分离的，读操作直接在原数组中进行，不需要进行同步处理，因此读操作的性能很高。

3. 弱一致性迭代器：CopyOnWriteArrayList 的迭代器是弱一致性的，可以在迭代过程中进行修改，不会抛出 ConcurrentModificationException 异常。

4. 适用于读多写少的场景：由于每次写操作都需要创建一个新的数组，因此适用于读多写少的场景，如果写操作比较频繁，可能会导致性能下降。

需要注意的是，CopyOnWriteArrayList 的写操作相对较慢，因为每次写操作都需要创建一个新的数组，因此适用于读多写少的场景。如果读写操作的频率相当，或者写操作比较频繁，可能会导致性能下降。此外，由于每次写操作都会创建一个新的数组，因此会占用较多的内存空间，需要根据具体的场景和需求进行选择。

CopyOnWriteArrayList 的缺点是什么？

CopyOnWriteArrayList 的缺点主要包括以下几点：

1. 内存占用较高：由于每次写操作都会创建一个新的数组，因此会占用较多的内存空间。

2. 写操作性能较低：由于每次写操作都需要创建一个新的数组，因此写操作的性能较低，适用于读多写少的场景。

3. 数据一致性问题：由于 CopyOnWriteArrayList 的迭代器是弱一致性的，也就是说，在迭代过程中，如果有其他线程对 List 进行了修改，迭代器不会抛出 ConcurrentModificationException 异常，但是不保证迭代器能够遍历到所有的元素。

4. 不适用于实时性要求高的场景：由于每次写操作都需要创建一个新的数组，因此不适用于实时性要求高的场景，可能会导致写操作的延迟

CopyOnWriteArrayList 是如何保证写时线程安全的？

CopyOnWriteArrayList 是通过“写时复制”（Copy-On-Write）策略来保证写时线程安全的。当一个线程需要进行写操作时，CopyOnWriteArrayList 会先创建一个新的数组，然后将原数组中的元素复制到新数组中。由于创建新数组时只有当前线程能够访问，因此不需要进行同步处理。在新数组中进行写操作时，其他线程仍然可以访问原数组，不会被当前线程的写操作所影响。当写操作完成后，CopyOnWriteArrayList 将新数组替换为原数组，从而保证写操作的线程安全性。

Set

List 和 Set 的区别

List 和 Set 都是 Java 集合框架中的接口，它们的主要区别在于以下几个方面：

1. 元素的顺序：List 中的元素是按照插入顺序排列的，可以根据索引访问元素；而 Set 中的元素是无序的，不能根据索引访问元素。

2. 元素的唯一性：List 中的元素可以重复，可以插入多个null元素。而 Set 中的元素不能重复，每个元素只能出现一次，只允许存入一个null元素，必须保证元素唯一性

3. 实现方式：List 的常见实现方式有 ArrayList、LinkedList 等；而 Set 的常见实现方式有 HashSet、TreeSet、LinkedHashSet 等。

4. 应用场景：List 适用于需要按照插入顺序访问元素的场景，如需要维护一个有序的列表；而 Set 适用于需要保证元素唯一性的场景，如去重、查找等。

骚戴理解：如果需要按照插入顺序访问元素，可以选择 List；如果需要保证元素唯一性，可以选择 Set。

说一下 HashSet 的实现原理？

HashSet 的底层其实就是HashMap，默认构造函数是构建一个初始容量为16，负载因子为0.75 的HashMap。封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。

HashSet如何检查重复？HashSet是如何保证数据不可重复的？

当向HashSet 中添加一个对象的时候（底层就是把这个对象存到HashMap的 key中），会调用hashCode方法得到一个hash值，然后看有没有发生hash冲突，如果没有发生hash冲突，那就是直接插入，如果发生了hash冲突，那就调用equals方法进一步判断，如果这两个的hashCode()返回值相等，通过equals比较也返回true的话（说明加入的是重复的对象）那就放弃添加这个重复的元素，这也就满足了Set中元素不重复的特性。如果发生了hash冲突但是equals方法返回结果是false那就把新加入的这个对象散列到其他的位置上去。这样我们就大大减少了 equals 的次数，相应就大大提高了执行速度。如果不用hashcode函数的话那就要遍历set中所有元素然后调用equals方法一个个的去比较是否相同，很明显，这需要大量调用equals方法

骚戴理解：不同对象的hashCode方法执行的结果可能会相同，也就是所谓的hash冲突，但是不同对象调用equals后返回的结果一定是false，只有两个相同的对象的hashCode()返回值相等，通过equals比较也返回true

hashCode（）与equals（）的相关规定

hashCode() 和 equals() 是 Object 类中定义的两个方法，它们在 Java 中被广泛使用，用于判断对象是否相等。在使用这两个方法时，需要注意以下规定：

1. 如果两个对象相等（equals() 方法返回 true），那么它们的 hashCode() 值必须相等。这是因为 hashCode() 方法的实现通常依赖于对象的内容，如果两个对象相等，那么它们的内容也应该相等，因此它们的 hashCode() 值也应该相等。

2. 如果两个对象的 hashCode() 值相等，它们并不一定相等（equals() 方法返回 true）。这是因为 hashCode() 方法可能存在哈希冲突，即不同的对象可能会产生相同的 hashCode() 值。因此，当 hashCode() 值相等时，还需要调用 equals() 方法进行比较，以确定它们是否相等。

3. 如果一个类重写了 equals() 方法，那么它也应该重写 hashCode() 方法，以保证上述规定的正确性。这是因为 Object 类中的 hashCode() 方法是根据对象的地址计算得到的，如果不重写 hashCode() 方法，可能会导致相等的对象具有不同的 hashCode() 值，从而违反了第一个规定。

4. 如果一个类重写了 hashCode() 方法，那么它也应该重写 equals() 方法，以保证上述规定的正确性。这是因为 hashCode() 方法可能存在哈希冲突，如果不重写 equals() 方法，可能会导致不相等的对象具有相同的 hashCode() 值，从而违反了第二个规定。

需要注意的是，hashCode() 和 equals() 的实现应该保证效率和正确性，不应该过于复杂或者耗时。此外，hashCode() 方法的返回值应该尽可能地分布均匀，以提高哈希表的性能。

HashSet与HashMap的区别

HashSet 和 HashMap 都是 Java 集合框架中的实现类，它们的主要区别在以下几个方面：

1. 存储方式：HashSet 存储的是一组唯一的、无序的元素，而 HashMap 存储的是一组键值对。

2. 底层实现：HashSet 的底层是基于 HashMap 实现的，它使用 HashMap 存储元素，只是将元素的值作为键，键对应的值为一个固定的 Object 对象；而 HashMap 则是使用哈希表实现的。

3. 元素的唯一性：HashSet 中的元素是唯一的，每个元素只能出现一次；而 HashMap 中的键是唯一的，但值可以重复。

4. 访问方式：HashSet 中的元素不能根据索引访问，只能通过迭代器进行访问；而 HashMap 中的元素可以根据键进行访问。

需要根据具体的需求选择合适的集合类型。如果需要存储一组唯一的、无序的元素，可以选择 HashSet；如果需要存储一组键值对，可以选择 HashMap。如果需要同时存储键值对并保证键的唯一性，可以选择 LinkedHashMap。

TreeMap 和 TreeSet 在排序时如何比较元素？Collections 工具类中的 sort()方法如何比较元素？

TreeMap 和 TreeSet 在排序时如何比较元素?

TreeSet 要求存放的对象所属的类必须实现 Comparable 接口，该接口提供了比较元素的compareTo()方法，当插入元素时会回调该方法比较元素的大小。

TreeMap 要求存放的键值对映射的键必须实现 Comparable 接口从而根据键对元素进行排序。

骚戴理解：都是通过实现Comparable接口来比较元素，该接口提供了比较元素的compareTo()

方法，当插入元素时会调用该方法比较元素的大小

Collections 工具类中的 sort()方法如何比较元素？

Collections 工具类的 sort 方法有两种重载的形式，

• 要求传入的待排序容器中存放的对象必须实现 Comparable 接口，该接口提供了比较元素的compareTo()方法，当插入元素时会调用该方法比较元素的大小
• 可以传入集合中的元素没有实现Comparable接口的对象，但是要求传入第二个参数，参数是Comparator 接口的子类型（需要重写 compare 方法实现元素的比较），也就是你需要定义一个比较器，然后sort()方法比较实际上就是调用这个比较器的 compare 方法来进行比较

第二点举例

Queue

BlockingQueue是什么？

BlockingQueue是什么？

BlockingQueue 是 Java 并发编程中的一个接口，它继承自 Queue 接口，表示一个支持阻塞的队列，用于在多线程之间传递数据。当队列满时，会阻塞入队的线程，直到队列不满；当队列为空时，会阻塞出队的线程，直到队列中有元素。

BlockingQueue 是线程安全的队列，它是在多线程环境下使用的，具有线程安全的特性。

BlockingQueue 的实现通常使用了同步机制，如锁、条件变量等，来保证多个线程之间的安全访问。在多线程环境下，多个线程可以同时对 BlockingQueue 进行读写操作，而不会产生数据竞争等线程安全问题。

例如，在使用 ArrayBlockingQueue 时，put() 和 take() 方法都需要先获取锁，然后在条件变量上等待或者唤醒其他线程，以保证线程安全。而在使用 LinkedBlockingQueue 时，不同的线程可以同时对队列进行读写操作，因为它使用了两个锁，一个用于入队操作，一个用于出队操作，以避免竞争和死锁问题。

需要注意的是，虽然 BlockingQueue 是线程安全的队列，但在实际使用时，仍需要注意一些细节问题，如队列容量大小、线程池大小等，以避免因为不当使用而导致的性能问题或者死锁问题。

BlockingQueue 接口提供了多种阻塞方法，包括 put()、take()、offer()、poll() 等，可以用于实现生产者-消费者模型、线程池等多种并发场景。

BlockingQueue 接口的主要特点是：当队列为空时，take() 方法会阻塞等待元素的到来；当队列已满时，put() 方法会阻塞等待队列空闲。这种阻塞等待的机制可以避免多线程之间的竞争和死锁问题，提高了程序的健壮性和可靠性。

BlockingQueue主要提供了四类方法，如下表所示：

方法	抛出异常	返回特定值	阻塞	阻塞特定时间
入队	add(e)	offer(e)	put(e)	offer(e, time, unit)
出队	remove()	poll()	take()	poll(time, unit)
获取队首元素	element()	peek()	不支持	不支持

除了抛出异常和返回特定值方法与Queue接口定义相同外，BlockingQueue还提供了两类阻塞方法：一种是当队列没有空间/元素时一直阻塞，直到有空间/有元素；另一种是在特定的时间尝试入队/出队，等待时间可以自定义。

主要实现类

BlockingQueue 接口的常见实现类包括 ArrayBlockingQueue、LinkedBlockingQueue、SynchronousQueue 等。其中，ArrayBlockingQueue 和 LinkedBlockingQueue 是基于数组和链表实现的阻塞队列，SynchronousQueue 是一种特殊的阻塞队列，它不存储元素，只是在生产者和消费者之间进行同步。

实现类	功能
ArrayBlockingQueue	基于数组的阻塞队列，使用数组存储数据，并需要指定其长度，所以是一个有界队列
LinkedBlockingQueue	基于链表的阻塞队列，使用链表存储数据，默认是一个无界队列；也可以通过构造方法中的capacity设置最大元素数量，所以也可以作为有界队列
SynchronousQueue	一种没有缓冲的队列，生产者产生的数据直接会被消费者获取并且立刻消费
PriorityBlockingQueue	基于优先级别的阻塞队列，底层基于数组实现，是一个无界队列
DelayQueue	延迟队列，其中的元素只有到了其指定的延迟时间，才能够从队列中出队

其中在日常开发中用的比较多的是ArrayBlockingQueue和LinkedBlockingQueue

在 Queue 中 poll()和 remove()有什么区别？

在 Queue 接口中，poll() 和 remove() 都是用于获取并移除队列头部元素的方法，但它们的行为略有不同。

1. poll() 方法：从队列头部获取并移除一个元素，如果队列为空，则返回 null。

2. remove() 方法：从队列头部获取并移除一个元素，如果队列为空，则抛出 NoSuchElementException 异常。

简单来说，poll() 方法在队列为空时返回 null，而 remove() 方法在队列为空时抛出异常。

因此，在使用 Queue 接口时，如果不确定队列是否为空，可以使用 poll() 方法来获取并移除队列头部元素，如果队列为空，则返回 null；如果确定队列不为空，可以使用 remove() 方法来获取并移除队列头部元素，如果队列为空，则抛出异常。

需要注意的是，在使用 remove() 方法时，如果队列为空，会抛出 NoSuchElementException 异常，因此需要进行异常处理或者使用 try-catch 语句来避免程序崩溃。

HashMap

HashMap求桶的位置

jdk1.7

在 JDK 1.7 中，HashMap 的桶位置的计算方式与 JDK 1.8 有所不同。具体地，JDK 1.7 中 HashMap 的桶位置的计算方式如下：

1. 先计算键的哈希值 `h`，使用的是 `key.hashCode()` 方法。

2. 然后通过以下公式计算桶位置 `i`：   i = (n - 1) & h

   其中，`n` 表示 `table` 数组的长度。由于在 JDK 1.7 中，`table` 的长度不一定是 2 的幂次方，因此需要使用 `n - 1` 来保证 `i` 的值在 `table` 的下标范围内。

3. 如果桶位置 `i` 上已经有元素了，那么会使用键的 `equals()` 方法来比较键是否相等。如果键相等，那么就将该键对应的值替换为新值；如果键不相等，那么就将该键值对插入到链表的末尾。

需要注意的是，在 JDK 1.7 中，HashMap 的扩容机制与 JDK 1.8 有所不同。具体来说，当 HashMap 中的元素个数超过了负载因子与容量的乘积时，HashMap 会将容量扩大为原来的两倍，并将所有元素重新分配到新的桶中。这种做法可能会导致在扩容时，多个键映射到同一个桶中，从而降低 HashMap 的性能。

jdk1.8

HashMap求桶的位置一共分为三个过程

• 求key的hashcode
• 调用hash函数得到hash值，将hashcode的高16位和低16位进行异或操作。

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// >>> 是无符号右移符号位
}

• 通过(length- 1) & hash ，将hash值与length-1进行与操作，求桶的位置（其中hash值是上面hash函数得到的值，length是table数组的长度）

 if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);

骚戴理解：不是得到hash值就知道把元素存在数组中的哪个位置，而是还要经过(length- 1) & hash之后才可以得到数组的位置，这样是为了减少hash冲突

说一下 HashMap 的实现原理？

JDK1.7

HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。（其实所谓Map其实就是保存了两个对象之间的映射关系的一种集合），其中Key 和 Value 允许为null。这些个键值对（Entry）分散存储在一个数组当中，HashMap数组每一个元素的初始值都是Null。

骚戴理解：HashMap不能保证映射的顺序，插入后的数据顺序也不能保证一直不变（如1.8以前的扩容操作会导致顺序变化）

Entry是HashMap中的一个静态内部类.

  static class Entry<K,V> implements Map.Entry<K,V> {final K key;V value;Entry<K,V> next;//存储指向下一个Entry的引用，单链表结构int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算/*** Creates new entry.*/Entry(int h, K k, V v, Entry<K,V> n) {value = v;next = n;key = k;hash = h;} 

HashMap的总体结构如下

骚戴理解：简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。

JDK1.8

JDK 1.8 中 HashMap 的底层原理是采用数组+链表+红黑树的结构实现的，主要包括以下几个方面：

1. 数组：HashMap 内部维护了一个数组，用于存储键值对。数组的长度是固定的，且必须是 2 的幂次方。

2. 链表：数组中的每个元素都是一个链表的头结点，用于存储哈希值相同的键值对。当链表长度超过8(TREEIFY_THRESHOLD - 阈值)时，链表就自行转为红黑树，以提高查找效率。

3. 红黑树：当链表长度超过一定阈值时，HashMap 会将链表转换为红黑树，以提高查找效率。红黑树是一种自平衡二叉查找树，它的查找、插入、删除等操作的时间复杂度都是 O(log n)。

4. 扩容：当 HashMap 中的元素个数超过数组长度的 75% 时，HashMap 会进行扩容操作，即将数组长度扩大一倍，并重新计算每个元素在新数组中的位置。扩容操作会导致所有元素的位置发生变化，因此需要重新计算每个元素在新数组中的位置，这个过程比较耗时。

5. hash 函数：HashMap 会使用键对象的 hashCode() 方法计算出键的哈希值，然后根据哈希值计算出键值对在数组中的位置。

6. 线程安全：JDK 1.8 中的 HashMap 是线程不安全的，如果多个线程同时对 HashMap 进行写操作，可能会导致数据丢失或者出现死循环等问题。如果需要在多线程环境下使用 HashMap，可以使用 ConcurrentHashMap。

hashmap常说的桶是什么

HashMap 中的桶指的是存储键值对的数组元素，也称为哈希桶或哈希表节点。

在 HashMap 内部，键值对会被存储在一个数组中，这个数组被称为哈希表。每个数组元素都是一个桶，它可以存储一个或多个键值对。当 HashMap 中的键值对被添加到哈希表中时，会根据键的哈希值计算出该键值对应该存储在哪个桶中。如果桶中已经有一个或多个键值对，那么新的键值对会被添加到这个桶中，成为这个桶中的一个元素。

为了解决哈希冲突问题，HashMap 的每个桶不仅可以存储一个键值对，还可以存储多个键值对。当多个键值对的哈希值相同时，它们会被添加到同一个桶中，成为这个桶中的一个链表或红黑树。HashMap 会根据链表长度或红黑树的节点数来决定采用哪种数据结构来存储键值对，从而提高查找效率。

因此，桶是 HashMap 中存储键值对的基本单位，它是实现 HashMap 内部数据结构的核心。

骚戴理解：简单来说，所谓的桶指的就是entry数组的元素，每一个entry都是一个桶

HashMap的底层实现在JDK1.7和JDK1.8中有哪些不同？

HashMap 是 Java 中非常常用的一种数据结构，它可以用来存储键值对，并且可以根据键快速地查找对应的值。在 JDK 1.7 和 JDK 1.8 中，HashMap 的底层实现有以下几点不同：

1. 底层数组的初始化方式不同。在 JDK 1.7 中，底层数组的初始化是在第一次插入元素时进行的，而在 JDK 1.8 中，底层数组的初始化是在创建 HashMap 对象时进行的。

2. 扩容机制不同。在 JDK 1.7 中，当元素个数超过容量的 75% 时，HashMap 会进行扩容操作，即将容量扩大为原来的两倍，并将所有元素重新计算位置。这种扩容策略可能会导致大量元素在同一个桶中，从而导致链表过长，查询效率降低。而在 JDK 1.8 中，当某个桶中的链表长度大于等于 8 时，会判断当前的 HashMap 的容量是否大于等于 64。如果小于 64，则会进行 2 倍扩容；如果大于等于 64，则将链表转换为红黑树，以提高查询效率。

3. hash 函数的计算方式不同。在 JDK 1.7 中，HashMap 的 hash 函数直接使用键对象的 hashCode() 方法计算出键的哈希值，然后根据哈希值计算出键值对在数组中的位置。这种计算方式可能会导致哈希冲突，即不同的键对象计算出的哈希值相同，从而导致元素存储在同一个桶中，链表过长，查询效率降低。而在 JDK 1.8 中，HashMap 的 hash 函数进行了优化。它首先调用键对象的 hashCode() 方法计算出键的哈希值，然后将哈希值的高 16 位和低 16 位进行异或操作，得到一个 int 类型的哈希值。这种计算方式可以避免只靠低位数据来计算哈希时导致的冲突，计算结果由高低位结合决定，使元素分布更均匀。

4. 在 JDK 1.8 中，当发生哈希冲突时，采用的是尾插法，即将新的节点插入到链表的尾部。这样做可以保持链表中节点的顺序，使得链表的遍历顺序和插入顺序一致，从而提高了查询效率。在扩容时，1.8 会保持原链表的顺序，即将链表中的节点按照插入顺序重新排列，而不是颠倒链表的顺序。在 JDK 1.7 中，当发生哈希冲突时，采用的是头插法，即将新的节点插入到链表的头部。这样做可以保证在遍历链表时，先遍历到最近插入的节点，从而提高了查询效率。在扩容时，1.7 会颠倒链表的顺序，即将链表中的节点按照相反的顺序重新排列。

5. 在 JDK 1.8 中，HashMap 会在元素插入后检测是否需要扩容，即先插入元素，再检测是否需要扩容。而在 JDK 1.7 中，HashMap 会在元素插入前检测是否需要扩容，即先检测是否需要扩容，再插入元素。这样做的目的是为了避免在插入元素时频繁地进行扩容操作，从而提高了插入元素的效率。

HashMap的put方法的具体流程？

putVal方法执行流程图

①.判断数组table是否为空或length=0，是的话就执行resize()进行扩容；

②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；

③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；

④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；

⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中 执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value 即可；

⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

HashMap的扩容操作是怎么实现的？

JDK1.7扩容机制

当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)*loadFactor时（即HashMap.Size > Capacity * LoadFactor ，LoadFactor 是负载因子）就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过16*0.75=12（这个值就是代码中的threshold值，也叫做临界值）的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置。HashMap的默认初始容量为16，负载因子0.75；当我们通过HashMap的有参构造自定义一个初始容量时，给定的值必须是2的幂次方值；

根据加载因子规则，当 时，hashMap会进行一次扩容操作；一次扩容流程可划分为两个步骤：

• resize ： 创建一个新的Entry空数组，长度是原数组的2倍
• transfer：旧数组中元素往新数组中迁移

HashMap中扩容是调用resize()方法

void resize(int newCapacity) {Entry[] oldTable = table;int oldCapacity = oldTable.length;//如果当前的数组长度已经达到最大值，则不在进行调整if (oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return;}//根据传入参数的长度定义新的数组Entry[] newTable = new Entry[newCapacity];//按照新的规则，将旧数组中的元素转移到新数组中transfer(newTable);table = newTable;//更新临界值threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

代码中可以看到，如果原有table长度已经达到了上限，就不再扩容了。没有达到就以原来数组的两倍进行扩容

transfer方法的作用是把原table的Node放到新的table中，jdk1.7使用的是头插法，也就是说，新table中链表的顺序和旧列表中是相反的，在HashMap线程不安全的情况下，这种头插法可能会导致环状节点。

//旧数组中元素往新数组中迁移
void transfer(Entry[] newTable) {//旧数组Entry[] src = table;//新数组长度int newCapacity = newTable.length;//遍历旧数组for (int j = 0; j < src.length; j++) {Entry<K,V> e = src[j];if (e != null) {src[j] = null;do {Entry<K,V> next = e.next;int i = indexFor(e.hash, newCapacity);//放在新数组中的index位置e.next = newTable[i];//实现链表结构，新加入的放在链头，之前的的数据放在链尾newTable[i] = e;e = next;} while (e != null);}}
}

其中的while循环描述了头插法的过程

JDK1.8扩容

HashMap触发扩容条件

• hashMap默认的负载因子是0.75，即如果hashmap中的元素个数超过了总容量75%，则会触发扩容
• 在 JDK 1.8 中，当某个桶中的链表长度大于等于 8 时，会判断当前的 HashMap 的容量是否大于等于 64。如果小于 64，则会进行 2 倍扩容；如果大于等于 64，则将链表转换为红黑树，以提高查询效率。

jdk1.8的HashMap求桶的位置

HashMap求桶的位置一共分为三个过程

• 求key的hashcode
• 调用hash函数得到hash值，将hashcode的高16位和低16位进行异或操作。

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

• 通过(length- 1) & hash ，将hash值与length-1进行与操作，求桶的位置（其中hash值是上面hash函数得到的值，length是table数组的长度）

if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);

注意：不是得到hash值就知道把元素存在数组中的哪个位置，而是还要经过(length- 1) & hash之后才可以得到数组的位置，这样是为了减少hash冲突

无论是JDK7还是JDK8，HashMap的扩容都是每次扩容为原来的两倍，即会产生一个新的数组newtable，JDK1.8和1.7的扩容其实差不多，只是把原来数组中的元素全部放到新的只不过元素求桶的位置的方法不太一样。

在JDK7中就是按照上述写的三个步骤重新对元素求桶的位置，但是第三步与的值是新的数组的长度-1，也就是newCap-1。

if (e.next == null)newTab[e.hash & (newCap - 1)] = e;//插入新值

但是JDK8中就不是和newCap，而是直接与oldCap，也就是将hash值与旧数组的长度（oldCap）进行与操作。

if ((e.hash & oldCap) == 0) {
newTab[j] = loHead;
}else{newTab[j + oldCap] = hiHead;
}

• 如果与oldCap与的结果是0，那么就代表当前元素的桶位置不变。
• 如果结果为1，那么桶的位置就是原位置+原数组长度（oldCap）

骚戴理解：需要注意的是，虽然 JDK 8 中重新计算元素在新数组中的位置时，与旧数组的长度进行与操作的方式不同于 JDK 7 中的取模运算，但它们的本质是相同的，都是为了保证元素在新数组中的位置能够均匀地分布，避免哈希冲突。

为什么HashMap的负载因子为0.75呢？

负载因子是一个比例值，表示 HashMap 中元素的数量与容量的比值。负载因子越大，填充因子越小，就越能减少空间浪费，但是会增加哈希冲突的概率。负载因子越小，填充因子越大，就越能减少哈希冲突的概率，但是会增加空间浪费。

在 JDK 1.8 中，HashMap 的默认负载因子为 0.75。这个值是经过实验和优化得出的。当负载因子为 0.75 时，HashMap 的空间利用率比较高，同时哈希冲突的概率也比较低，可以达到较好的性能表现。如果负载因子设置得太小，会导致 HashMap 频繁地进行扩容操作，降低性能；如果负载因子设置得太大，会导致哈希冲突的概率增加，也会降低性能。

需要注意的是，在实际应用中，负载因子的选择应该根据具体情况来确定。如果应用中哈希冲突较少，可以适当提高负载因子，以减少空间浪费；如果哈希冲突较多，可以适当降低负载因子，以提高性能。

HashMap是怎么解决哈希冲突的？

简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的

• 使用链地址法（使用散列表）来链接拥有相同hash值的数据；
• 使用2次扰动函数（hash函数）来降低哈希冲突的概率，使得数据分布更平均；
• 引入红黑树进一步降低遍历的时间复杂度，使得遍历更快；

什么是哈希？

Hash，一般翻译为“散列”，也有直接音译为“哈希”的，这就是把任意长度的输入通过散列算法，变换成固定长度的输出，该输出就是散列值（哈希值）；这种转换是一种压缩映射，也就是散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

所有散列函数都有如下一个基本特性：

根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。

什么是哈希冲突？

当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象，我们就把它叫做碰撞（哈希碰撞）。

HashMap的数据结构

在Java中，保存数据有两种比较简单的数据结构：数组和链表。

数组的特点是：寻址容易，插入和删除困难；

链表的特点是：寻址困难，但插入和删除容易；

所以我们将数组和链表结合在一起，发挥两者各自的优势，使用一种叫做链地址法的方式可以解决哈希冲突：

这样我们就可以将拥有相同哈希值的对象组织成一个链表放在hash值所对应的bucket下， 但相比于hashCode返回的int类型，我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4（即2的四次方16）要远小于int类型的范围，所以我们如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率，并且最坏情况下还会将HashMap变成一个单链表（就是一直发生冲突，然后就最后成为了一条单链表），所以我们还需要对hashCode作一定的优化

hash()函数

上面提到的问题，主要是因为如果使用hashCode取余，那么相当于参与运算的只有hashCode的低位，高位是没有起到任何作用的，所以我们的思路就是让hashCode取值 出的高位也参与运算，进一步降低hash碰撞的概率，使得数据分布更平均，我们把这样的操作称为扰动，在JDK 1.8中的hash()函数如下：

static final int hashCode(Object key){int h;//与自己右移16位进行异或运算（高低位异或）return (key==null)? 0 : (h==key.hashCode()) ^ (h>>>16)//
}

这比在JDK 1.7中，更为简洁，相比在1.7中的4次位运算，5次异或运算（9次扰动），在1.8中，只进行了1次位运算和1次异或运算（2次扰动）；

JDK1.8新增红黑树

通过上面的链地址法（使用散列表）和扰动函数我们成功让我们的数据分布更平均，哈希 碰撞减少，但是当我们的HashMap中存在大量数据时，加入我们某个bucket下对应的链表有n个元素，那么遍历时间复杂度就为O(n)，为了针对这个问题，JDK1.8在HashMap中新增了红黑树的数据结构，进一步使得遍历复杂度降低至O(logn)；

简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的

• 使用链地址法（使用散列表）来链接拥有相同hash值的数据；
• 使用2次扰动函数（hash函数）来降低哈希冲突的概率，使得数据分布更平均；
• 引入红黑树进一步降低遍历的时间复杂度，使得遍历更快；

通常hash冲突的四种解决方法

• 链地址法：将哈希表的每个单元作为链表的头结点，所有哈希地址为 i 的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部。
• 开放定址法：即发生冲突时，去寻找下一个空的哈希地址。只要哈希表足够大，总能找到空的哈希地址。
• 再哈希法：即发生冲突时，由其他的函数再计算一次哈希值。
• 建立公共溢出区：将哈希表分为基本表和溢出表，发生冲突时，将冲突的元素放入溢出表。

能否使用任何类作为 Map 的 key？

在 Java 中，可以使用任何类作为 Map 的 key，只要该类正确地实现了 `hashCode()` 和 `equals()` 方法。`hashCode()` 方法用于计算对象的哈希码，`equals()` 方法用于判断两个对象是否相等。

在使用自定义类作为 Map 的 key 时，需要确保该类正确地实现了 `hashCode()` 和 `equals()` 方法。如果没有正确实现这两个方法，可能会导致 HashMap 中的元素无法正确地存储和检索，甚至会导致 HashMap 出现死循环等问题。

在实现 `hashCode()` 和 `equals()` 方法时，需要遵循以下原则：

- 如果两个对象相等，它们的哈希码必须相等。
- 如果两个对象的哈希码相等，它们不一定相等。
- `equals()` 方法必须满足自反性、对称性、传递性和一致性。

需要注意的是，如果使用可变对象作为 Map 的 key，那么在该对象发生变化时，它的哈希码也会发生变化。这可能会导致该对象无法正确地从 HashMap 中检索出来。因此，通常建议使用不可变对象作为 Map 的 key。

为什么HashMap中String、Integer这样的包装类适合作为Key？

String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性，能够有效的减少Hash碰撞的几率

1、都是final类型，即不可变性，保证key的不可更改性，不会存在获取hash值不同的情况

2、内部已重写了equals()、hashCode()等方法，遵守了HashMap内部的规范，不容易出现Hash值计算错误的情况；

如果使用自定义对象作为HashMap的Key，应该怎么办呢？

必须同时重写hashCode()和equals()方法，同时重写这两个方法是为了保证使用自定义对象作为HashMap的key时，key是唯一的，假设现在没有重写这两个方法，然后存入两个自定义的相同对象，先调用Object的hashCode()方法，由于Object的hashCode()方法是比较的是两个不同引用地址的对象，所以自定义的两个相同对象的的hashCode的结果不一样，那就会被判定为两个不同的对象，都会存到HashMap中作为key，这就不符合key的唯一性了，其实原因和下面的Set一样

为什么重写equals时必须重写hashCode方法？

如果只重写了 equals 方法，那么默认情况下，假设存了两个自定义的内容相同的对象到Set中，Set 进行去重操作时，会先判断两个对象的 hashCode 是否相同，此时因为没有重写 hashCode 方法，所以会直接执行 Object 中的 hashCode 方法，而 Object 中的 hashCode 方法对比的是两个不同引用地址的对象，那么得到的两个Hash值是不一样的，那么 equals 方法就不会执行了，这两个对象就会被判断为不是相等的，于是就在 Set 集合中插入了两个相同的对象（这里的相同是指的内容相同）。

但是，如果在重写 equals 方法时，也重写了 hashCode 方法，那么在执行判断时会去执行重写的 hashCode 方法，此时对比的是两个对象的所有属性的 hashCode 是否相同，于是调用 hashCode 返回的结果就是 true，再去调用 equals 方法，发现两个对象确实是相等的，于是就返回 true 了，因此 Set 集合就不会存储两个一模一样的数据了，于是整个程序的执行就正常了。

总结

hashCode 和 equals 两个方法是用来协同判断两个对象是否相等的，采用这种方式的原因是可以提高程序插入和查询的速度，如果在重写 equals 时，不重写 hashCode，就会导致在某些场景下，例如将两个相等的自定义对象存储在 Set 集合时，就会出现程序执行的异常，为了保证程序的正常执行，所以我们就需要在重写 equals 时，也一并重写 hashCode 方法才行。

HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标？

在理论上，可以使用 `hashCode()` 处理后的哈希值直接作为 `table` 数组的下标，但是这种做法可能会导致哈希冲突，即不同的键可能会产生相同的哈希值，从而导致它们被映射到相同的 `table` 下标位置，这就会影响 HashMap 的性能。

为了解决这个问题，HashMap 使用了一种称为“拉链法”的解决方案。具体地，HashMap 中的每个桶都是一个链表，当多个键映射到同一个桶时，它们会被存储在该桶对应的链表中。在检索时，HashMap 会先根据键的哈希值找到对应的桶，然后再在该桶对应的链表中查找键值对。

当然，如果链表过长，会影响 HashMap 的性能。因此，在 JDK 8 中，当链表长度超过一定阈值（默认为 8）时，HashMap 会将链表转换为红黑树，以提高查找效率。这种做法可以在大部分情况下保证 HashMap 的性能。

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

因为这样可以让计算桶位置的操作更加高效。

具体来说，如果 HashMap 的长度是 2 的幂次方，那么计算桶位置时可以使用位运算来代替除法运算，从而提高计算速度。

我们都知道为了找到 KEY 的位置在哈希表的哪个槽里面，需要计算 hash(KEY) % 数组长度

HashMap为了存取高效，就要尽量减少碰撞，将数据分配均匀，那么如何分配均匀，此时主要靠将数据存入到那个链表中的算法，这个算法就是 hash(KEY) & (length - 1)。& 是按位与运算，是一个位运算，而在计算机中位运算的效率很高，% 计算比 & 慢很多,这就是不用%运算的原因,为了保证 & 的计算结果等于 % 的结果需要把 length 减 1。

hash(KEY) & (length - 1)=hash(KEY) %length

既然两个计算出的hash值是相同的那当然是用效率更高的&

我做了一个小实验：

假设现在数组的长度：2 ^ 14 = 16384

String key = "zZ1!." 的 hash 值为 115398910

public static void main(String[] args) {String key = "zZ1!.";System.out.println(key.hashCode());// 115398910
}

hash & (length - 1) = 115398910 & 16383 = 6398 （你可以使用电脑的计算机验证一下是不是对的）6398 的二进制是 ‭0001100011111110‬

hash % length = 115398910 % 16384 = 6398

这样可以大大提高计算速度，因为按位与运算比取模运算要快得多。

另外，长度为 2 的幂次方的数组也可以更好地处理哈希冲突。在使用链表解决哈希冲突时，如果数组长度是 2 的幂次方，那么每个桶的链表长度最多只有 8 个元素，这样可以保证链表的查找效率。如果数组长度不是 2 的幂次方，那么桶的数量可能不能均匀分布，从而导致某些桶的链表长度很长，影响查找效率。

因此，为了提高 HashMap 的性能，通常建议将长度设置为 2 的幂次方。

骚戴理解：如果数组长度是 2 的幂次方，每个桶的链表长度最多只有 8 个元素是因为 JDK 1.8 中 HashMap 的实现使用了一种称为“树化”的策略，当某个桶中的链表长度超过了 8 个元素时，会将该链表转换成红黑树，以提高查找效率。

树化操作的前提条件是桶中的链表长度超过了阈值（默认为 8），而如果数组长度是 2 的幂次方，那么对于任意的哈希值，它与数组长度的按位与操作的结果一定是小于数组长度的。例如，如果数组长度是 16，那么对于任意的哈希值，它与 15 的按位与操作的结果一定是在 0 到 15 之间。

因此，如果数组长度是 2 的幂次方，那么对于任意的哈希值，它与数组长度的按位与操作的结果一定是小于数组长度的，也就是说，它一定可以作为桶的下标。而由于数组长度是 2 的幂次方，因此桶的数量也是 2 的幂次方，这样就可以保证桶的数量和数组长度是一致的，从而可以保证每个桶的链表长度最多只有 8 个元素。

需要注意的是，这种情况只针对 JDK 1.8 中 HashMap 的实现，如果使用其他版本的 HashMap 或者其他哈希表实现，可能不具备这种性质。

那为什么是两次扰动呢？

答：这样就是加大哈希值低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性&均匀性，最终减少Hash冲突，两次就够了，已经达到了高位低位同时参与运算的目的；

HashMap 与 HashTable 有什么区别？

• 线程安全： HashMap 是非线程安全的，HashTable 是线程安全的；HashTable 内部的方法基本都经过 synchronized 修饰。（如果你要保证线程安全的话就使用ConcurrentHashMap 吧！）；
• 效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外， HashTable 基本被淘汰，不要在代码中使用它；
• 对Null key 和Null value的支持： HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。但是在 HashTable 中 put 进的键值只要有一个 null，直接抛NullPointerException。
• 初始容量和扩容机制：HashTable 的初始容量为 11，而 HashMap 的初始容量为 16。当 HashTable 中元素的数量超过了容量的 0.75 倍时，会自动扩容为原来的 2 倍。而 HashMap 中元素的数量超过了容量的 0.75 倍时，会自动扩容为原来的 2 倍，并且扩容后的容量一定是 2 的幂次方。
• 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

骚戴理解：在 Hashtable 的类注释可以看到，Hashtable 是保留类不建议使用， 推荐在单线程环境下使用 HashMap 替代，如果需要多线程使用则用ConcurrentHashMap 替代。

如何决定使用 HashMap 还是 TreeMap？

在选择 HashMap 还是 TreeMap 时，需要根据具体的需求和场景来决定。

1. 查找效率：如果主要是进行查找操作，而对插入和删除操作的效率要求不高，那么可以选择 TreeMap。因为 TreeMap 内部采用红黑树实现，可以保证元素有序，并且查找效率比 HashMap 更高，时间复杂度为 O(log n)。

2. 插入和删除效率：如果主要是进行插入和删除操作，而对查找操作的效率要求不高，那么可以选择 HashMap。因为 HashMap 内部采用哈希表实现，可以保证插入和删除操作的效率比 TreeMap 更高，时间复杂度为 O(1)。

3. 内存占用：如果需要对大量数据进行操作，并且内存占用是一个问题，那么可以选择 HashMap。因为 HashMap 内部采用哈希表实现，可以保证元素存储在数组中，占用的内存比 TreeMap 更小。

4. 元素有序性：如果需要对元素进行排序，那么必须选择 TreeMap。因为 TreeMap 内部采用红黑树实现，可以保证元素有序。

综上所述，如果需要进行查找操作并且对元素有序性要求较高，可以选择 TreeMap；如果需要进行插入和删除操作并且对内存占用要求较高，可以选择 HashMap。如果需要同时兼顾查找效率和插入删除效率，可以使用 LinkedHashMap，它是基于哈希表和双向链表实现的，可以保证元素有序，并且插入和删除操作的效率比 TreeMap 更高。

知识充电站

• TreeMap<K,V>的Key值是要求实现java.lang.Comparable，所以迭代的时候TreeMap默认是按照Key值升序排序的；TreeMap的实现是基于红黑树结构。适用于按自然顺序或自定义顺序遍历键（key）。
• HashMap<K,V>的Key值实现散列hashCode()，分布是散列的、均匀的，不支持排序；数据结构主要是桶(数组)，链表或红黑树。适用于在Map中插入、删除和定位元素。

HashMap是线程安全的吗？为什么呢？

HashMap是线程不安全的！

线程不安全体现在JDK.1.7时在多线程的情况下扩容可能会出现死循环或数据丢失的情况，主要是在于扩容的transfer方法采用的头插法，头插法会把链表的顺序给颠倒过来，这是引起死循环的关键。在JDK1.8时在多线程的情况下扩容会可能会出现数据覆盖的情况，例如有两个线程A、B都在进行put操作（对HashMap进行put操作实际上是调用了putVal()方法），并且这两个线程hash函数计算出的插入下标是相同的，当线程A执行完putVal（）方法中的一句用于判断有没有发生hash碰撞的代码后（下面源代码的15行），由于时间片耗尽导致被挂起（注意这个时候线程A的判断结果是没有发生hash碰撞，保存了这个判断结果，但是还没有执行下一句插入元素代码，这个时候被挂起了），而线程B得到时间片后也是调用putVal（）方法插入元素，由于两个线程hash函数计算出的下标是一样的，并且前面线程A因为时间片到了还没来得及插入元素就被挂起了，所以这个时候线程B判断结果也是没有hash碰撞，直接在该下标处插入了元素，完成了正常的插入，然后线程A获得时间片，由于之前已经进行了hash碰撞的判断，所有此时不会再进行判断，而是直接进行插入，这就导致了线程B插入的数据被线程A覆盖了，所以HashMap是线程不安全。

原因：

• JDK1.7 中HashMap线程不安全体现在多线程扩容导致死循环、数据丢失

void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;for (Entry<K,V> e : table) {while(null != e) {Entry<K,V> next = e.next;if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}int i = indexFor(e.hash, newCapacity);e.next = newTable[i];  //线程A执行完这句后因为时间片耗尽就被挂起了newTable[i] = e;e = next;}}
}

HashMap的扩容就是调用上面的transfer方法来实现的，扩容后要采用头插法将元素迁移到新数组中，头插法会将链表的顺序翻转，这也是形成死循环的关键点。

上面的代码主要看下面的四句代码

//重新定义下标
Entry<K,V> next = e.next;
//下面三句就是头插法的实现e.next = newTable[i];newTable[i] = e;e = next;

模拟扩容造成死循环和数据丢失

假设现在有两个线程A、B同时对下面这个HashMap进行扩容操作：

正常扩容后的结果是下面这样的：

但是当线程A执行完上面transfer函数的第10行代码时，CPU时间片耗尽，线程A被挂起。即如下图中位置所示：

解析：线程A中：e=3、next=7、e.next=null，可以看到图1的链表中第一个是3，下一个是7，所以transfer函数第一次执行中e=3，next=7，本来根据图1的情况应该是e.next=7，但是线程A在transfer函数中执行到了 e.next = newTable[i]; 这句，而newTable[i]由于是刚扩容的所以是为null，所以执行这句后 e.next =null

线程A挂起后，此时线程B得到时间片后正常执行，并完成resize扩容操作，结果如下：

线程B完成扩容后，此时主内存中newTable和table都是最新的

也就是说主内存中7.next=3和3.next=null（这里我一开始就疑惑为什么线程B都扩容完了线程A拿到时间片后还要扩容？其实是因为线程A压根就不知道线程B已经扩容完了，线程A也不管你扩容完了没，反正就是继续执行自己之前没有执行完的代码，由于是根据线程B扩容完后存放在内存中的数据继续扩容的，所以线程A才会出现下面的数据丢失和死循环）

随后线程A获得CPU时间片继续执行newTable[i] = e和e = next;这两句代码，线程A在挂起之前的数据是e=3、next=7、e.next=null，执行这两句后结果是newTable[3] =3，e=7，执行完此轮循环后线程A的情况如下

解析：newTable[3] =3，e=7（这里的newTable[3] =3可以理解为指针，其实就是newTable[3] 是个数组，那它的值就是指向3这个节点，e=7的e可以理解为指针，从原本的指向3到指向7）

接着继续执行下一轮循环，此时e=7，从主内存中读取e.next时发现主内存中7.next=3，此时next=3，并将7采用头插法的方式放入新数组中，并继续执行完此轮循环

//此时e=7，内存中7.next=3、3.next=null，newTable[3] =3，e=7
//JMM中规定所有的变量都存储在主内存中每条线程都有自己的工作内存，
//线程的工作内存中保存了该线程所使用的变量的从主内存中拷贝的副本。
//线程对于变量的读、写都必须在工作内存中进行，而不能直接读、写主内存中的变量。
//同时，本线程的工作内存的变量也无法被其他线程直接访问，必须通过主内存完成。
Entry<K,V> next = e.next;------->next=7.next=3; 
//下面三句就是头插法的实现e.next = newTable[i];----------》e.next=3;//注意这里的e还是7，这句就是7的指针指向3newTable[i] = e; --------------》newTable[3]=e=7; e = next;----------------------》e=next=3;

注意：JMM中规定所有的变量都存储在主内存（Main Memory）中，每条线程都有自己的工作内存（Work Memory），线程的工作内存中保存了该线程所使用的变量的从主内存中拷贝的副本。线程对于变量的读、写都必须在工作内存中进行，而不能直接读、写主内存中的变量。同时，本线程的工作内存的变量也无法被其他线程直接访问，必须通过主内存完成。

所以上面线程B执行后它的工作内存存储自己的执行结果7.next=3和3.next=null，然后主内存同步过去，最后线程A去主内存复制过来到自己的工作内存中

执行完此轮循环后结果如下

注意：当e=3时3.next=null这个是线程B执行后主内存中的结果

解析：这里唯一要注意的地方就是上面在执行 e.next = newTable[i];的时候结果是e.next=3;而这其中的e是7不是3！这句是把7和3连接起来，从7指向3。这里我一开始就把e.next=3;作为下一次循环的数据依据，然后就觉得应该是下面的图示情况，其实应该是当e=3的时候e.next=null作为数据依据

这种是错误的！

上轮next=3，e=3，执行下一次循环可以发现，3.next=null，所以此轮循环将会是最后一轮循环。

//此时e=3，内存中next=3，newTable[3]=7，e=3，e.next=null
//任何一个线程的执行情况应该是放在内存中的，所以并发的时候才会出问题
//例如这个线程A去内存中拿的数据是线程B执行后的数据，已经不是线程A之前存的数据了
Entry<K,V> next = e.next;------->next=null; 
//下面三句就是头插法的实现e.next = newTable[i];----------》e.next=7;newTable[i] = e; --------------》newTable[3]=3; e = next;----------------------》e=3;

执行完此轮循环后结果如下

当执行完上面的循环后发现next=null后，将不会进行下一轮循环。到此线程A、B的扩容操作完成，很明显当线程A执行完后，HashMap中出现了环形结构，当在以后对该HashMap进行操作时会出现死循环。并且从上图可以发现，元素5在扩容期间被莫名的丢失了，这就发生了数据丢失的问题。

• JDK1.8 中HashMap线程不安全主要体现在数据覆盖

如果有两个线程A、B都在进行put操作（对HashMap进行put操作实际上是调用了putVal()方法），并且这两个线程hash函数计算出的插入下标是相同的，当线程A执行完putVal（）方法中的一句用于判断有没有发生hash碰撞的代码后（下面源代码的15行），由于时间片耗尽导致被挂起（注意这个时候线程A的判断结果是没有发生hash碰撞，保存了这个判断结果，但是还没有执行下一句插入元素代码，这个时候被挂起了），而线程B得到时间片后也是调用putVal（）方法插入元素，由于两个线程hash函数计算出的下标是一样的，并且前面线程A因为时间片到了还没来得及插入元素就被挂起了，所以这个时候线程B判断结果也是没有hash碰撞，直接在该下标处插入了元素，完成了正常的插入，然后线程A获得时间片，由于之前已经进行了hash碰撞的判断，所有此时不会再进行判断，而是直接进行插入，这就导致了线程B插入的数据被线程A覆盖了，从而线程不安全。

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab;Node<K,V> p; int n, i;//如果当前map中无数据，执行resize方法。并且返回nif ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//判断有没有发生hash碰撞，没有就直接插入if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);//否则的话，说明这上面有元素else {Node<K,V> e; K k;//如果这个元素的key与要插入的一样，那么就替换一下，也完事。if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;//1.如果当前节点是TreeNode类型的数据，执行putTreeVal方法else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//还是遍历这条链子上的数据，跟jdk7没什么区别for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);//2.完成了操作后多做了一件事情，判断，并且可能执行treeifyBin方法if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null) //true || --e.value = value;//3.afterNodeAccess(e);return oldValue;}}++modCount;//判断阈值，决定是否扩容if (++size > threshold)resize();//4.afterNodeInsertion(evict);return null;}

通常解决hash冲突的方法有4种

1）开放定址法，也称为线性探测法，就是从发生冲突的那个位置开始，按照一定的次序从hash表中找到一个空闲的位置，然后把发生冲突的元素存入到这个空闲位置中。ThreadLocal就用到了线性探测法来解决hash冲突的。

像这样一种情况

在hash表索引1的位置存了一个key=name，当再次添加key=hobby时，hash计算得到的索引也是1，这个就是hash冲突。

使用开放定址法，就是按顺序向前找到一个空闲的位置来存储冲突的key，也就是如果这个冲突的位置的右边一个位置没有存放数据那就存放这个冲突的位置，如果存放了数据还是冲突了那就继续往右边推一个位置，直到可以存放这个数据，例如上面冲突后就应该放到索引2的位置，然后索引2的位置没有数据所以就直接存放，有数据还是冲突那就放索引3的位置，以此类推，直到存放了这个数据到Hash表

（2）链式寻址法，这是一种非常常见的方法，简单理解就是把存在hash冲突的key，以单向链表的方式来存储，比如HashMap就是采用链式寻址法来实现的。

像这样一种情况

存在冲突的key直接以单向链表的方式进行存储。

（3）再hash法，就是当通过某个hash函数计算的key存在冲突时，再用另外一个hash函数对这个key做hash，一直运算直到不再产生冲突。这种方式会增加计算时间，性能影响较大。

（4）建立公共溢出区， 就是把hash表分为基本表和溢出表两个部分，凡是存在冲突的元素，一律放入到溢出表中。

补充：HashMap在JDK1.8版本中，通过链式寻址法+红黑树的方式来解决hash冲突问题，其中红黑树是为了优化Hash表链表过长导致时间复杂度增加的问题。当链表长度大于8并且hash表的容量大于64的时候，再向链表中添加元素就会触发转化。

HashMap不是线程安全的，如果要保证线程安全怎么办呢？可以用什么？

（1）使用HashTable（不推荐使用）

private Map map = new Hashtable<>()

HashTable源码中发现，其get/put方法均被synchronized关键词修饰（该关键词修饰代表这个方法加上了同步锁，相当于任意线程运行到该方法时，首先应检查有没有其它线程在使用该方法，有的话要等待上一个线程使用完毕后，当前线程才能使用）

正因如此，Hash Table的线程安全是基于方法级阻塞制的，它们占用共享资源，所以导致同时只能有一个线程操作get或put，并且get和put操作不能同时执行，所以这种同步的集合效率很低，一般不建议使用这个集合。

（2）使用SynchronizedMap（不推荐使用）

private Map map = Collections.synchronizedMap(newHashMap())

这种是直接使用工具类里面的方法创建synchronizedMapCollections.synchronizedMap(newHashMap())返回的synchronizedMap对象，把传入的HashMap对象进行了包装而已。

这个同步方式实现也比较简单，看出SynchronizedMap的实现方式是加了个对象锁（HashTable加的是同步锁，SynchronizedMap加的是对象锁），每次对HashMap的操作都要先获取这个mutex对象才能进入，故而性能也不会比HashTable好到哪去，也不建议使用。

    public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {return new SynchronizedMap<>(m);}private static class SynchronizedMap<K,V>implements Map<K,V>, Serializable {private static final long serialVersionUID = 1978198479659022715L;private final Map<K,V> m;     // Backing Mapfinal Object      mutex;        // Object on which to synchronizeSynchronizedMap(Map<K,V> m) {this.m = Objects.requireNonNull(m);mutex = this;}...}//SynchronizedMap的put方法，实际调用的还是HashMap自己的put方法public V put(K key, V value) {synchronized (mutex) {return m.put(key, value);}}

（3）ConcurrentHashMap（推荐使用）

private Map map = new ConcurrentHashMap<>()

这个实现结构最复杂，但同时也是效率最高最推荐使用的线程安全的Map，每个版本实现方式不一。Jdk8之前是使用分段加锁的方式，分成16个桶，每次只加锁其中一个桶，而jdk8又加入了红黑树和CAS算法来实现。

ConcurrentHashMap

什么是ConcurrentHashMap？实现原理是什么？

在多线程环境下，使用HashMap进行put操作时存在丢失数据的情况，为了避免这种bug的隐患，强烈建议使用ConcurrentHashMap代替HashMap。

HashTable是一个线程安全的类，它使用synchronized来锁住整张Hash表来实现线程安全，即每次锁住整张表让线程独占，相当于所有线程进行读写时都去竞争一把锁，导致效率非常低下。

ConcurrentHashMap可以做到读取数据不加锁，并且其内部的结构可以让其在进行写操作的时候能够将锁的粒度保持地尽量地小，允许多个修改操作并发进行，其关键在于使用了锁分段技术。它使用了多个锁来控制对hash表的不同部分进行的修改。对于JDK1.7版本的实现, ConcurrentHashMap内部使用段(Segment)来表示这些不同的部分，每个段其实就是一个小的Hashtable，它们有自己的锁。只要多个修改操作发生在不同的段上，它们就可以并发进行。JDK1.8的实现降低锁的粒度，JDK1.7版本锁的粒度是基于Segment的，包含多个HashEntry，而JDK1.8锁的粒度就是HashEntry（首节点）。

实现原理

JDK1.7

JDK1.7 中的 ConcurrentHashMap 是由 Segment 数组结构和链表数组 HashEntry 结构组成，即 ConcurrentHashMap 把哈希桶数组切分成多个段Segment ，每个Segment 有 n 个 链表数组（HashEntry）组成，也就是通过分段锁来实现的。

ConcurrentHashMap 定位一个元素的过程需要进行两次Hash操作，第一次 Hash 定位到 Segment，第二次 Hash 定位到元素所在的链表的头部，因此，这一种结构的带来的副作用是 Hash 的过程要比普通的 HashMap 要长，但是带来的好处是写操作的时候可以只对元素所在的 Segment 进行操作即可，不会影响到其他的 Segment，这样，在最理想的情况下，ConcurrentHashMap 可以最高同时支持 Segment 数量大小的写操作（刚好这些写操作都非常平均地分布在所有的 Segment上），所以，通过这一种结构，ConcurrentHashMap 的并发能力可以大大的提高

如下图所示，首先将数据分为一段一段(Segment)的存储，然后给每一段(Segment)数据配一把锁，当一个线程占用锁访问其中一段数据时，其他段的数据也能被其他线程访问，实现了真正的并发访问。

Segment 是 ConcurrentHashMap 的一个内部类，主要的组成如下：

Segment 继承了 ReentrantLock，所以 Segment 是一种可重入锁，扮演锁的角色。Segment 默认为 16，也就是并发度为 16。

存放元素的 HashEntry，也是一个静态内部类，主要的组成如下：

其中，用 volatile 修饰了 HashEntry 的数据 value 和 下一个节点 next，保证了多线程环境下数据获取时的可见性！

为什么要用二次hash

主要原因是为了构造分离锁，使得对于map的修改不会锁住整个容器，提高并发能力。当然，没有一种东西是绝对完美的，二次hash带来的问题是整个hash的过程比hashmap单次hash要长，所以，如果不是并发情形，不要使concurrentHashmap。

JAVA7之前ConcurrentHashMap主要采用分段锁机制，在对某个Segment进行操作时，将该Segment锁定，不允许对其进行非查询操作，而在JAVA8之后采用CAS无锁算法，这种乐观操作在完成前进行判断，如果符合预期结果才给予执行，对并发操作提供良好的优化.

JDK1.8

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

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

ConcurrentHashMap中变量使用final和volatile修饰有什么用呢？

在 ConcurrentHashMap 中，使用 final 和 volatile 修饰变量可以提高线程安全性和可见性，具体作用如下： 

1. final：使用 final 修饰的变量表示不可变变量，即该变量的值在初始化之后不能被修改。在 ConcurrentHashMap 中，使用 final 修饰 Node 类中的 key 和 hash 变量，可以保证它们在初始化之后不会被修改，从而避免了多线程之间的竞争和冲突。final修饰变量可以保证变量不需要同步就可以被访问和共享

2. volatile：使用 volatile 修饰的变量表示该变量是可见的，即对该变量的修改会立即被其他线程所感知。在 ConcurrentHashMap 中，使用 volatile 修饰了 Segment 类中的 count 和 modCount 变量，可以保证它们的修改对其他线程是可见的，从而避免了多线程之间的冲突和数据不一致的问题。

需要注意的是，虽然使用 final 和 volatile 修饰变量可以提高线程安全性和可见性，但是并不能完全保证线程安全和正确性。在使用 ConcurrentHashMap 时，还需要注意其他方面的线程安全问题，例如迭代器的使用、复合操作的原子性等。

JDK1.8 的CocurrentHashMap中为什么使用 synchronized替换 ReentrantLock？

在 JDK1.8 中，ConcurrentHashMap 内部对锁的实现进行了优化，使用了 CAS 操作和 synchronized 关键字来替换原来的可重入锁 ReentrantLock，主要原因如下：

1. 性能优化：使用 synchronized 关键字可以避免 ReentrantLock 中的 CAS 操作带来的性能损失，从而提高并发性能。

2.提高吞吐量：ConcurrentHashMap 是一个高并发的哈希表实现类，需要支持多个线程同时进行读写操作。使用 synchronized 关键字可以减少锁的竞争和冲突，从而提高吞吐量，提高并发性能。

3.简化代码：使用 synchronized 关键字可以避免 ReentrantLock 中需要手动加锁和解锁的复杂操作，从而简化了代码实现。这样可以减少代码的复杂度和出错的可能性，提高代码的可维护性和可读性。

需要注意的是，虽然 ConcurrentHashMap 在 JDK1.8 中使用了 synchronized 关键字来替换 ReentrantLock，但是它并不是传统意义上的 synchronized，而是使用了锁分段技术，将整个哈希表分成了多个段，每个段都有一个独立的锁，从而实现了高效的并发访问。这种锁分段技术可以避免锁的粒度过大或过小的问题，从而提高了并发性能和可伸缩性。

骚戴理解：在竞争和非竞争情况下使用 synchronized 的性能更好。因为 synchronized 关键字可以自动升级为轻量级锁、自旋锁等优化锁，避免了线程阻塞和切换的开销，从而提高了并发性能。而可重入锁 ReentrantLock 则需要进行手动加锁和解锁，需要进行 CAS 操作等复杂操作，从而导致性能损失

我们可以使用CocurrentHashMap来代替Hashtable吗？

我们知道Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好，因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable，但是HashTable提供更强的线程安全性。它们都可以用于多线程的环境，但是当Hashtable的大小增加到一定的时候，性能会急剧下降，因为迭代时需要被锁定很长的时间。因为ConcurrentHashMap引入了分割(segmentation)，不论它变得多么大，仅仅需要锁定map的某个部分，而其它的线程不需要等到迭代完成才能访问map。简而言之，在迭代的过程中，ConcurrentHashMap仅仅锁定map的某个部分，而Hashtable则会锁定整个map。

ConcurrentHashMap有什么优点和缺点吗？

优点

1. 高并发性能：ConcurrentHashMap 内部使用锁分段技术，将整个哈希表分成多个段，每个段都有一个独立的锁，从而实现了高效的并发访问。在多线程并发访问的情况下，ConcurrentHashMap 可以提供很高的并发性能和吞吐量。

2. 线程安全：ConcurrentHashMap 是一个线程安全的哈希表实现类，可以支持多个线程同时进行读写操作，而不需要额外的同步措施。在多线程并发访问的情况下，ConcurrentHashMap 可以保证数据的一致性和正确性。

3. 可伸缩性：ConcurrentHashMap 内部使用锁分段技术，可以根据实际的需求来调整锁的粒度和数量，从而实现可伸缩性。在多线程并发访问的情况下，ConcurrentHashMap 可以根据实际的并发情况来动态调整锁的数量和大小，以提供更好的并发性能。

4. 高效迭代器：ConcurrentHashMap 内部的迭代器是快速失败的迭代器，可以在迭代过程中检测到其他线程对哈希表的修改，从而避免了数据的不一致性和错误。在多线程并发访问的情况下，ConcurrentHashMap 可以提供高效的迭代器操作，以支持数据的遍历和访问。

5. 可定制性：ConcurrentHashMap 提供了很多可定制的参数和配置选项，可以根据实际的需求来调整哈希表的大小、负载因子、并发级别等参数，以实现更好的性能和可伸缩性。

缺点

1. 内存占用：ConcurrentHashMap 内部需要维护多个段和多个链表，以支持高并发的读写操作，从而导致内存占用较高。在数据量较大的情况下，可能会导致内存溢出等问题。

2. 无序性：ConcurrentHashMap 内部使用哈希表来存储数据，哈希表的特点是无序性，因此无法保证数据的顺序。如果需要按照某种顺序来访问数据，需要进行额外的排序操作。

3. 迭代器弱一致性：ConcurrentHashMap 内部的迭代器是弱一致性的，即在迭代过程中，如果其他线程对哈希表进行了修改，会导致迭代器抛出 ConcurrentModificationException 异常。因此，在使用迭代器访问 ConcurrentHashMap 时，需要注意线程安全和异常处理。

4. 扩容代价：ConcurrentHashMap 内部需要进行扩容操作，以支持更多的数据存储和更高的并发性能。但是，扩容操作需要进行数据迁移和重建哈希表等复杂操作，可能会导致性能下降和延迟增加。

ConcurrentHashMap在JDK 7和8之间的区别

ConcurrentHashMap 在 JDK 7 和 JDK 8 中都有所改进和优化，主要的区别如下：

1. 数据结构：JDK 7 中的 ConcurrentHashMap 内部使用分段锁技术实现并发访问，每个段都是一个独立的哈希表，可以独立地进行读写操作。而 JDK 8 中的 ConcurrentHashMap 则使用了 CAS 操作和链表/红黑树结构来实现并发访问，可以更好地支持高并发和大规模数据。

2. 并发性能：JDK 8 中的 ConcurrentHashMap 在并发性能方面有所提升，主要是因为它使用了 CAS 操作和链表/红黑树结构来实现并发访问，减少了锁的竞争和开销，从而提高了并发性能。JDK1.7 采用 Segment 的分段锁机制实现线程安全，其中 Segment 继承自 ReentrantLock 。JDK1.8 采用CAS+synchronized保证线程安全。

3. 内存占用：JDK 8 中的 ConcurrentHashMap 在内存占用方面有所改进，主要是因为它使用了链表/红黑树结构来存储数据，可以更好地利用内存空间，减少了内存占用。

4. 扩容策略：JDK 8 中的 ConcurrentHashMap 在扩容策略方面有所改进，主要是因为它使用了链表/红黑树结构来存储数据，可以更好地支持并发扩容，减少了数据迁移和重建哈希表的开销。

5. API 接口：JDK 8 中的 ConcurrentHashMap 增加了一些新的 API 接口，例如 forEach、reduce、search 等，可以更方便地对哈希表进行遍历和操作。

6.锁的粒度：JDK1.7 是对需要进行数据操作的 Segment 加锁，JDK1.8 调整为对红黑树的根节点或者链表的头结点进行加锁

Java 中 ConcurrentHashMap 的并发度是什么？

并发度可以理解为程序运行时能够同时更新 ConccurentHashMap且不产生锁竞争的最大线程数。在JDK1.7中，实际上就是ConcurrentHashMap中的分段锁个数，即Segment[]的数组长度，默认是16，这个值可以在构造函数中设置。

如果自己设置了并发度，ConcurrentHashMap 会使用大于等于该值的最小的2的幂指数作为实际并发度，也就是比如你设置的值是17（24<17<25），那么实际并发度是32(25)。

如果并发度设置的过小，会带来严重的锁竞争问题；如果并发度设置的过大，原本位于同一个Segment内的访问会扩散到不同的Segment中，CPU cache命中率会下降，从而引起程序性能下降。

在JDK1.8中，已经摒弃了Segment的概念，选择了Node数组+链表+红黑树结构，并发度大小依赖于数组的大小。

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

ConcurrentHashMap 的迭代器是弱一致性的，而不是强一致性的。

弱一致性的迭代器指的是迭代器在遍历过程中可以看到其他线程对哈希表的修改，但是无法保证遍历结果的一致性和正确性。如果其他线程在遍历过程中对哈希表进行了修改，可能会导致迭代器抛出 ConcurrentModificationException 异常，或者遍历到重复或丢失的元素。

这是因为 ConcurrentHashMap 内部使用分段锁技术来实现并发访问，每个段都有一个独立的锁，可以独立地进行读写操作。在遍历过程中，如果其他线程对同一个段进行了修改，就可能会导致迭代器遍历到不一致的元素。因此，ConcurrentHashMap 的迭代器只能保证最终一致性，不能保证强一致性。

为了避免迭代器的异常和错误，可以在遍历过程中使用锁或者采用其他的同步措施。也可以使用 ConcurrentHashMap 的新 API 接口 forEach、reduce、search 等，它们使用了更加安全和可靠的遍历方式，可以更好地避免迭代器的异常和错误。

ConcurrentHashMap 不支持 key 或者 value 为 null 的原因？

因为 ConcurrentHashMap 是用于多线程的 ，如果ConcurrentHashMap.get(key)得到了 null 就会有二义性，可能没有这个key或者可能有这个key但是对应的值是null

那为什么HashMap就没有这个二义性呢？

可以调用containsKey方法来判断二义性，没有这个key就返回false，有这个key但是对应的值是null就返回true，可以通过这个方法来区分上面说道的二义性问题，注意containsKey这个方法HashMap和ConcurrentHashMap中都有，之所以一个有二义性一个没二义性主要是因为一个是单线程的情况，一个是多线程的情况

public boolean containsKey(Object key) {return getNode(hash(key), key) != null;
}

ConcurrentHashMap为什么不能解决二义性问题

因为ConcurrentHashMap是线程安全的，一般使用在并发环境下，你一开始get方法获取到null之后，再去调用containsKey方法，没法确保get方法和containsKey方法之间，没有别的线程来捣乱，刚好把你要查询的key给设置了进去或者删除掉了。

SynchronizedMap 和 ConcurrentHashMap 有什么区别？

SynchronizedMap 和 ConcurrentHashMap 都是线程安全的 Map 实现类，但是它们之间有以下区别：

1. 数据结构：SynchronizedMap 是基于 Hashtable 实现的，而 ConcurrentHashMap 是基于哈希表实现的。

2. 并发性能：ConcurrentHashMap 在并发性能方面比 SynchronizedMap 更优秀，因为它使用了分段锁技术来实现并发访问，可以同时进行读写操作，而 SynchronizedMap 则需要使用同步锁来保证线程安全，因此在高并发环境下性能较差。

3. 锁粒度：ConcurrentHashMap 的锁粒度更细，可以支持更高的并发度，而 SynchronizedMap 的锁粒度更粗，只能支持单个线程的访问。

4. 扩容策略：ConcurrentHashMap 的扩容策略更优秀，可以在不影响并发性能的情况下进行扩容，而 SynchronizedMap 的扩容策略则需要使用同步锁来保证线程安全，可能会影响并发性能。

5. null 值：ConcurrentHashMap 不支持 key 或者 value 为 null，而 SynchronizedMap 则允许 key 或者 value 为 null。

综上所述，虽然 SynchronizedMap 和 ConcurrentHashMap 都是线程安全的 Map 实现类，但是在并发性能、锁粒度、扩容策略和 null 值等方面存在差异，因此在实际开发中需要根据具体的应用场景选择合适的实现类。如果需要支持高并发、大规模数据和 null 值，建议使用 ConcurrentHashMap，如果数据量较小，可以使用 SynchronizedMap。

HashMap 和 ConcurrentHashMap 的区别

HashMap 和 ConcurrentHashMap 都是哈希表实现的 Map 集合，但是它们之间有以下区别：

1. 线程安全性：HashMap 是非线程安全的，而 ConcurrentHashMap 是线程安全的。ConcurrentHashMap 使用了分段锁技术来实现并发访问，可以同时进行读写操作，而 HashMap 则需要使用同步锁来保证线程安全，因此在高并发环境下性能较差。

2. 并发性能：ConcurrentHashMap 在并发性能方面比 HashMap 更优秀，因为它使用了分段锁技术来实现并发访问，可以同时进行读写操作，而 HashMap 则需要使用同步锁来保证线程安全，因此在高并发环境下性能较差。

3. 锁粒度：ConcurrentHashMap 的锁粒度更细，可以支持更高的并发度，而 HashMap 的锁粒度更粗，只能支持单个线程的访问。

4. 扩容策略：ConcurrentHashMap 的扩容策略更优秀，可以在不影响并发性能的情况下进行扩容，而 HashMap 的扩容策略则需要使用同步锁来保证线程安全，可能会影响并发性能。

5. null 值：ConcurrentHashMap 不支持 key 或者 value 为 null，而 HashMap 则允许 key 或者 value 为 null。

综上所述，虽然 HashMap 和 ConcurrentHashMap 都是哈希表实现的 Map 集合，但是在线程安全性、并发性能、锁粒度、扩容策略和 null 值等方面存在差异，因此在实际开发中需要根据具体的应用场景选择合适的实现类。如果需要支持高并发、大规模数据，建议使用 ConcurrentHashMap，如果数据量较小，可以使用 HashMap。

ConcurrentHashMap 和 Hashtable 的区别？

ConcurrentHashMap 和 Hashtable 都是线程安全的哈希表实现类，但是它们之间有以下区别：

1. 数据结构：ConcurrentHashMap 是基于哈希表实现的，而 Hashtable 是基于同步方法实现的。

2. 并发性能：ConcurrentHashMap 在并发性能方面比 Hashtable 更优秀，因为它使用了分段锁技术来实现并发访问，可以同时进行读写操作，而 Hashtable 则需要使用同步锁来保证线程安全，因此在高并发环境下性能较差。

3. 锁粒度：ConcurrentHashMap 的锁粒度更细，可以支持更高的并发度，而 Hashtable 的锁粒度更粗，只能支持单个线程的访问。

4. 扩容策略：ConcurrentHashMap 的扩容策略更优秀，可以在不影响并发性能的情况下进行扩容，而 Hashtable 的扩容策略则需要使用同步锁来保证线程安全，可能会影响并发性能。

5. null 值：ConcurrentHashMap 不支持 key 或者 value 为 null，而 Hashtable 则允许 key 或者 value 为 null。

6. 迭代器：ConcurrentHashMap 的迭代器是弱一致性的，可以在迭代过程中进行并发修改，而 Hashtable 的迭代器是强一致性的，不允许在迭代过程中进行并发修改。

综上所述，虽然 ConcurrentHashMap 和 Hashtable 都是线程安全的哈希表实现类，但是在线程安全性、并发性能、锁粒度、扩容策略、null 值和迭代器等方面存在差异，因此在实际开发中需要根据具体的应用场景选择合适的实现类。如果需要支持高并发、大规模数据和 null 值，建议使用 ConcurrentHashMap，如果数据量较小，可以使用 Hashtable。

两者的对比图： HashTable:

JDK1.7的ConcurrentHashMap：

JDK1.8的ConcurrentHashMap（TreeBin: 红黑二叉树节点 Node: 链表节点）：

ConcurrentHashMap 结合了 HashMap 和 HashTable 二者的优势。HashMap 没有考虑同步，HashTable 考虑了同步的问题。但是 HashTable 在每次同步执行时都要锁住整个结构。 ConcurrentHashMap 锁的方式是稍微细粒度的。