java 集合详解完整版（超详细）

联合整理 https://blog.csdn.net/feiyanaffection/article/details/81394745 https://www.cnblogs.com/linliquan/p/11323172.html

一、集合大纲

1、集合与数组的区别

2、集合常用方法

3、常用集合分类

Collection 接口的接口对象的集合（单列集合） ├——-List 接口：元素按进入先后有序保存，可重复 │—————-├ LinkedList 接口实现类，链表，插入删除，没有同步，线程不安全 │—————-├ ArrayList 接口实现类，数组，随机访问，没有同步，线程不安全 │—————-└ Vector 接口实现类数组，同步，线程安全 │ ———————-└ Stack 是 Vector 类的实现类 └——-Set 接口：仅接收一次，无序不可重复，并做内部排序 ├—————-└HashSet 使用 hash 表（数组）存储元素 │————————└ LinkedHashSet 链表维护元素的插入次序 └ —————-TreeSet 底层实现为二叉树，元素排好序

Map 接口键值对的集合（双列集合） ├———Hashtable 接口实现类，同步，线程安全 ├———HashMap 接口实现类，没有同步，线程不安全 - │—————–├ LinkedHashMap 双向链表和哈希表实现 │—————–└ WeakHashMap ├ ——–TreeMap 红黑树对所有的 key 进行排序 └———IdentifyHashMap

二、List 和 Set 集合详解

1、List 和 Set 的区别

2、List 实现类

ArrayList：底层数据结构是数组，查询快，增删慢，线程不安全，效率高，可以存储重复元素
LinkedList： 底层数据结构是链表，查询慢，增删快，线程不安全，效率高，可以存储重复元素
Vector: 底层数据结构是数组，查询快，增删慢，线程安全，效率低，可以存储重复元素

说明： 为什么 ArrayList 查询快增删慢，LinkedList 增删快，查询慢

3、Set 实现类

HashSet：底层数据结构采用哈希表实现，元素无序且唯一，线程不安全，效率高，可以存储 null 元素，元素的唯一性是靠所存储元素类型是否重写 hashCode() 和 equals() 方法来保证的，如果没有重写这两个方法，则无法保证元素的唯一性。

实现唯一性的比较过程：存储元素首先会使用 hash() 算法函数生成一个 int 类型 hashCode 散列值，然后和所存储的元素的 hashCode 值比较，如果 hashCode 不相等，则所存储的两个对象一定不相等，此时存储当前的新的 hashCode 值处的元素对象；如果 hashCode 相等，存储元素的对象还是不一定相等，此时会调用 equals() 方法判断两个对象的内容是否相等，如果内容相等，那么就是同一个对象，无需存储；如果比较的内容不相等，那么就是不同的对象，就该存储了，此时就要采用哈希的解决地址冲突算法，在当前 hashCode 值处类似一个新的链表，在同一个 hashCode 值的后面存储存储不同的对象，这样就保证了元素的唯一性。
Set 的实现类的集合对象中不能够有重复元素，HashSet 也一样他是使用了一种标识来确定元素的不重复，HashSet 用一种算法来保证 HashSet 中的元素是不重复的， HashSet 采用哈希算法，底层用数组存储数据。默认初始化容量 16，加载因子 0.75。
Object 类中的 hashCode() 的方法是所有子类都会继承这个方法，这个方法会用 Hash 算法算出一个 Hash（哈希）码值返回，HashSet 会用 Hash 码值去和数组长度取模，模（这个模就是对象要存放在数组中的位置）相同时才会判断数组中的元素和要加入的对象的内容是否相同，如果不同才会添加进去。 Hash 算法是一种散列算法。 Set hs=new HashSet();

LinkedHashSet：底层数据结构采用链表和哈希表共同实现，链表保证了元素的顺序与存储顺序一致，哈希表保证了元素的唯一性。线程不安全，效率高。
TreeSet：底层数据结构采用红黑树来实现，元素唯一且已经排好序；唯一性同样需要重写 hashCode 和 equals() 方法，二叉树结构保证了元素的有序性。根据构造方法不同，分为自然排序（无参构造）和比较器排序（有参构造），自然排序要求元素必须实现 Compareable 接口，并重写里面的 compareTo() 方法，元素通过比较返回的 int 值来判断排序序列，返回 0 说明两个对象相同，不需要存储；比较器排序需要在 TreeSet 初始化是时候传入一个实现 Comparator 接口的比较器对象，或者采用匿名内部类的方式 new 一个 Comparator 对象，重写里面的 compare() 方法；

4、TreeSet 的两种排序方式

基本数据类型默认按升序排序

自定义排序

（1）自然排序：实现 Comparable 接口，并重写 Compareto 方法

对引用对象进行自然排序

public class Student implements Comparable<Student>{
    private String name;
    private int age;
 
    public Student() {
        super();
        // TODO Auto-generated constructor stub
    }
 
    public Student(String name, int age) {
        super();
        this.name = name;
        this.age = age;
    }
 
    public String getName() {
        return name;
    }
 
    public void setName(String name) {
        this.name = name;
    }
 
    public int getAge() {
        return age;
    }
 
    public void setAge(int age) {
        this.age = age;
    }
 
    @Override
    public int compareTo(Student s) {
        //return -1; //-1表示放在红黑树的左边,即逆序输出
        //return 1;  //1表示放在红黑树的右边，即顺序输出
        //return o;  //表示元素相同，仅存放第一个元素
        //主要条件 姓名的长度,如果姓名长度小的就放在左子树，否则放在右子树
        int num=this.name.length()-s.name.length();
        //姓名的长度相同，不代表内容相同,如果按字典顺序此 String 对象位于参数字符串之前，则比较结果为一个负整数。
        //如果按字典顺序此 String 对象位于参数字符串之后，则比较结果为一个正整数。
        //如果这两个字符串相等，则结果为 0
        int num1=num==0?this.name.compareTo(s.name):num;
        //姓名的长度和内容相同，不代表年龄相同，所以还要判断年龄
        int num2=num1==0?this.age-s.age:num1;
        return num2;
    }
}

（2）比较器排序：重写 Comparator 接口中的 Compare 方法

对基本数据类型进行比较器排序

o1：代表当前添加的数据
o2：代表集合中已经存在的数据
0： 表示 o1 == o2
-1(逆序输出)： o1 < o2
1(正序输出): o1 > o2
1：o1 - o2（升序排列）
-1：o2 - o1 (降序排列)
 
当compare()方法返回值大于0（为true）时，交换o1和o2
 
假设Comparator接收的两个元素原始顺序为：o1→o2
默认情况下升序：return o1>o2（假设为true）时，交换为：o2→o1（o1大，在后，即升序）
改写为降序时：return o2>o1（假设为true）时，交换为：o2→o1（o1小，在后，即降序）
 
    Comparator<Integer> comp = new Comparator<Integer>() {
             @Override
             public int compare(Integer o1, Integer o2) {
                 System.out.println(o1+"--"+o2);
                 return o2 -o1; //输出53 33 10，降序排序
               //  return  0;  //只输出一个元素：33
               //   return -1; //输出53 10 33，倒序输出
              //  return 1;  //输出33 10 55
             }
         };

对引用数据类型进行比较器排序

#1.单独创建一个比较类，这里以MyComparator为例，并且要让其继承Comparator接口
    public class MyComparator implements Comparator<Student> {
 
    @Override
    #2.重写Comparator接口中的Compare方法
    public int compare(Student s1,Student s2) {
        // 姓名长度
        int num = s1.getName().length() - s2.getName().length();
        // 姓名内容
        int num2 = num == 0 ? s1.getName().compareTo(s2.getName()) : num;
        // 年龄
        int num3 = num2 == 0 ? s1.getAge() - s2.getAge() : num2;
        return num3;
    }
}
#3、指定自己写的比较类
TreeSet<Student> ts=new TreeSet<Student>(new MyComparator());

5、List 和 Set 总结

List,Set 都是继承自 Collection 接口，Map 则不是
List 特点：元素有放入顺序，元素可重复

Set 特点： 元素无放入顺序，元素不可重复，重复元素会覆盖掉，（注意：元素虽然无放入顺序，但是元素在 set 中的位置是有该元素的 HashCode 决定的，其位置其实是固定的，加入 Set 的 Object 必须定义 equals() 方法，另外 list 支持 for 循环，也就是通过下标来遍历，也可以用迭代器，但是 set 只能用迭代，因为他无序，无法用下标来取得想要的值。）

Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。 List：和数组类似，List 可以动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变。
ArrayList 与 LinkedList 的区别和适用场景

Arraylist： 优点：ArrayList 是实现了基于动态数组的数据结构, 因为地址连续，一旦数据存储好了，查询操作效率会比较高（在内存里是连着放的）。缺点：因为地址连续， ArrayList 要移动数据, 所以插入和删除操作效率比较低。

LinkedList： 优点：LinkedList 基于链表的数据结构, 地址是任意的，所以在开辟内存空间的时候不需要等一个连续的地址，对于新增和删除操作 add 和 remove，LinedList 比较占优势。LinkedList 适用于要头尾操作或插入指定位置的场景缺点：因为 LinkedList 要移动指针, 所以查询操作性能比较低。 适用场景分析： 当需要对数据进行经常访问的情况下选用 ArrayList，当需要对数据进行多次增加删除修改时采用 LinkedList。

ArrayList 与 Vector 的区别和适用场景

ArrayList 有三个构造方法：

public ArrayList(int initialCapacity)//构造一个具有指定初始容量的空列表。
public ArrayList()      //默认构造一个初始容量为10的空列表。
public ArrayList(Collection<? extends E> c)//构造一个包含指定 collection 的元素的列表

Vector 有四个构造方法：

public Vector()//使用指定的初始容量和等于0的容量增量构造一个空向量。
public Vector(int initialCapacity)//构造一个空向量，使其内部数据数组的大小，其标准容量增量为零。
public Vector(Collection<? extends E> c)//构造一个包含指定 collection 中的元素的向量
public Vector(int initialCapacity,int capacityIncrement)//使用指定的初始容量和容量增量构造一个空的向量

区别：

ArrayList 和 Vector 都是用数组实现的，主要有这么三个区别：（1）Vector 是多线程安全的，线程安全就是说多线程访问同一代码，不会产生不确定的结果。而 ArrayList 不是，这个可以从源码中看出，Vector 类中的方法很多有 synchronized 进行修饰，这样就导致了 Vector 在效率上无法与 ArrayList 相比；（2）两个都是采用的线性连续空间存储元素，但是当空间不足的时候，两个类的增加方式是不同。（3）Vector 可以设置增长因子，而 ArrayList 不可以。（4）Vector 是一种老的动态数组，是线程同步的，效率很低，一般不赞成使用。

适用场景分析： （1）Vector 是线程同步的，所以它也是线程安全的，而 ArrayList 是线程异步的，是不安全的。如果不考虑到线程的安全因素，一般用 ArrayList 效率比较高。（2）如果集合中的元素的数目大于目前集合数组的长度时，在集合中使用数据量比较大的数据，用 Vector 有一定的优势。

HashSet 和 TreeSet 的区别和适用场景

（1）TreeSet 是二叉树（红黑树的树据结构）实现的,Treeset 中的数据是自动排好序的，不允许放入 null 值（2）HashSet 是哈希表实现的,HashSet 中的数据是无序的，可以放入 null，但只能放入一个 null，两者中的值都不能重复，就如数据库中唯一约束（3）HashSet 要求放入的对象必须实现 HashCode() 方法，放入的对象，是以 hashcode 码作为标识的，而具有相同内容的 String 对象，hashcode 是一样，所以放入的内容不能重复。但是同一个类的对象可以放入不同的实例

（4）适用场景分析:HashSet 是基于 Hash 算法实现的，其性能通常都优于 TreeSet。为快速查找而设计的 Set，我们通常都应该使用 HashSet，在我们需要排序的功能时，我们才使用 TreeSet。

List 和 Set 应该怎么选？

三、Map 详解

1、Map 概念

Map 用于保存具有映射关系的数据，Map 里保存着两组数据：key 和 value，它们都可以使任何引用类型的数据，但 key 不能重复。所以通过指定的 key 就可以取出对应的 value。

Map 接口有四个比较重要的实现类，分别是 HashMap、LinkedHashMap、TreeMap 和 HashTable。

TreeMap 是有序的，HashMap 和 HashTable 是无序的。

Hashtable 的方法是同步的，HashMap 的方法不是同步的。这是两者最主要的区别。

Map 没有继承 Collection 接口， Map 提供 key 到 value 的映射，你可以通过 “键” 查找“值”。一个 Map 中不能包含相同的 key ，每个 key 只能映射一个 value 。 Map 接口提供 3 种集合的视图， Map 的内容可以被当作一组 key 集合，一组 value 集合，或者一组 key-value 映射。

2、Map 常用方法

3、HashMap 和 HashTable 的比较

HashMap 不支持线程的同步，即任一时刻可以有多个线程同时写 HashMap; 可能会导致数据的不一致。如果需要同步，可以用 Collections 的 synchronizedMap 方法使 HashMap 具有同步的能力，或者使用 ConcurrentHashMap。

4、TreeMap

5、Map 其他实现类

IdentityHashMap 和 HashMap 的具体区别，IdentityHashMap 使用 == 判断两个 key 是否相等，而 HashMap 使用的是 equals 方法比较 key 值。有什么区别呢？对于 == ，如果作用于基本数据类型的变量，则直接比较其存储的 “值” 是否相等；如果作用于引用类型的变量，则比较的是所指向的对象的地址。对于 equals 方法，注意：equals 方法不能作用于基本数据类型的变量如果没有对 equals 方法进行重写，则比较的是引用类型的变量所指向的对象的地址；诸如 String、Date 等类对 equals 方法进行了重写的话，比较的是所指向的对象的内容。

6、Map 遍历

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
 
public class Test {
 
    public static void main(String[] args) {
         Map<String, String> map = new HashMap<String, String>();
         map.put("first", "linlin");
         map.put("second", "好好学java");
         map.put("third", "sihai");
         map.put("first", "sihai2");
 
 
         // 第一种：通过Map.keySet遍历key和value
         System.out.println("===================通过Map.keySet遍历key和value:===================");
         for (String key : map.keySet()) {
             System.out.println("key= " + key + "  and  value= " + map.get(key));
         }
 
         // 第二种：通过Map.entrySet使用iterator遍历key和value
         System.out.println("===================通过Map.entrySet使用iterator遍历key和											value:===================");
         Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
         while (it.hasNext()) {
             Map.Entry<String, String> entry = it.next();
             System.out.println("key= " + entry.getKey() + "  and  value= "
                     + entry.getValue());
         }
 
         // 第三种：通过Map.entrySet遍历key和value
         System.out.println("===================通过Map.entrySet遍历key和value:===================");
         for (Map.Entry<String, String> entry : map.entrySet()) {
             System.out.println("key= " + entry.getKey() + "  and  value= "
                     + entry.getValue());
         }
 
         // 第四种：通过Map.values()遍历所有的value，但是不能遍历键key
         System.out.println("===================通过Map.values()遍历所有的value:===================");
         for (String v : map.values()) {
             System.out.println("value= " + v);
         }
     }
 }

7、小结

HashMap：非线程安全，基于哈希表实现。使用 HashMap 要求添加的键类明确定义了 hashCode() 和 equals()[可以重写 hashCode() 和 equals()]，为了优化 HashMap 空间的使用，您可以调优初始容量和负载因子。
TreeMap：非线程安全基于红黑树实现。TreeMap 没有调优选项，因为该树总处于平衡状态。

8、适用场景

HashMap 和 HashTable:HashMap 去掉了 HashTable 的 contains 方法，但是加上了 containsValue() 和 containsKey() 方法。HashTable 同步的，而 HashMap 是非同步的，效率上比 HashTable 要高。HashMap 允许空键值，而 HashTable 不允许。

在实际使用中，如果更新图时不需要保持图中元素的顺序，就使用 HashMap，如果需要保持图中元素的插入顺序或者访问顺序，就使用 LinkedHashMap，如果需要使图按照键值排序，就使用 TreeMap。

HashMap：适用于 Map 中插入、删除和定位元素。 Treemap：适用于按自然顺序或自定义顺序遍历键 (key)。

四、重点问题

（一）说说 List,Set,Map 三者的区别？

List(对付顺序的好帮手)： List 接口存储一组不唯一（可以有多个元素引用相同的对象），有序的对象
Set(注重独一无二的性质): 不允许重复的集合。不会有多个元素引用相同的对象。
Map(用 Key 来搜索的专家): 使用键值对存储。Map 会维护与 Key 有关联的值。两个 Key 可以引用相同的对象，但 Key 不能重复，典型的 Key 是 String 类型，但也可以是任何对象。

（二）Arraylist 与 LinkedList 区别?

\1. 是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
\2. 底层数据结构： Arraylist 底层使用的是 Object 数组；LinkedList 底层使用的是双向链表数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）
\3. 插入和删除是否受元素位置的影响： ① ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的 (n-i) 个元素都要执行向后位 / 向前移一位的操作。 ② LinkedList 采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似 O（1）而数组为近似 O（n）。
\4. 是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象 (对应于get(int index)方法)。
\5. 内存空间占用： ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

1.ArrayList 是实现了基于动态数组的数据结构，LinkedList 基于链表的数据结构。　　2. 对于随机访问 get 和 set，ArrayList 觉得优于 LinkedList，因为 LinkedList 要移动指针。　　3. 对于新增和删除操作 add 和 remove，LinedList 比较占优势，因为 ArrayList 要移动数据。尽量避免同时遍历和删除集合。因为这会改变集合的大小；

（三）ArrayList 与 Vector 区别呢? 为什么要用 Arraylist 取代 Vector 呢？

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

Arraylist不是同步的，所以在不需要保证线程安全时建议使用 Arraylist。

（四）说一说 ArrayList 的扩容机制吧

https://github.com/Snailclimb/JavaGuide/blob/master/docs/java/collection/ArrayList-Grow.md

（五）HashSet 与 TreeSet 与 LinkedHashSet 对比

HashSet 不能保证元素的排列顺序，顺序有可能发生变化，不是同步的，集合元素可以是 null, 但只能放入一个 null TreeSet 是 SortedSet 接口的唯一实现类，TreeSet 可以确保集合元素处于排序状态。TreeSet 支持两种排序方式，自然排序和定制排序，其中自然排序为默认的排序方式。向 TreeSet 中加入的应该是同一个类的对象。 TreeSet 判断两个对象不相等的方式是两个对象通过 equals 方法返回 false，或者通过 CompareTo 方法比较没有返回 0 自然排序 自然排序使用要排序元素的 CompareTo（Object obj）方法来比较元素之间大小关系，然后将元素按照升序排列。 定制排序 自然排序是根据集合元素的大小，以升序排列，如果要定制排序，应该使用 Comparator 接口，实现 int compare(To1,To2) 方法 LinkedHashSet 集合同样是根据元素的 hashCode 值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet 将会以元素的添加顺序访问集合的元素。 LinkedHashSet 在迭代访问 Set 中的全部元素时，性能比 HashSet 好，但是插入时性能稍微逊色于 HashSet。

（六）LinkedHashMap 和 HashMap，TreeMap 对比

Hashtable 与 HashMap 类似, 它继承自 Dictionary 类，不同的是: 它不允许记录的键或者值为空; 它支持线程的同步，即任一时刻只有一个线程能写 Hashtable, 因此也导致了 Hashtable 在写入时会比较慢。 Hashmap 是一个最常用的 Map, 它根据键的 HashCode 值存储数据, 根据键可以直接获取它的值，具有很快的访问速度，遍历时，取得数据的顺序是完全随机的。 LinkedHashMap 保存了记录的插入顺序，在用 Iterator 遍历 LinkedHashMap 时，先得到的记录肯定是先插入的. 也可以在构造时用带参数，按照应用次数排序。在遍历的时候会比 HashMap 慢，不过有种情况例外，当 HashMap 容量很大，实际数据较少时，遍历起来可能会比 LinkedHashMap 慢，因为 LinkedHashMap 的遍历速度只和实际数据有关，和容量无关，而 HashMap 的遍历速度和他的容量有关。 TreeMap 实现 SortMap 接口，能够把它保存的记录根据键排序, 默认是按键值的升序排序，也可以指定排序的比较器，当用 Iterator 遍历 TreeMap 时，得到的记录是排过序的。我们用的最多的是 HashMap,HashMap 里面存入的键值对在取出的时候是随机的, 在 Map 中插入、删除和定位元素，HashMap 是最好的选择。 TreeMap 取出来的是排序后的键值对。但如果您要按自然顺序或自定义顺序遍历键，那么 TreeMap 会更好。 LinkedHashMap 是 HashMap 的一个子类，如果需要输出的顺序和输入的相同, 那么用 LinkedHashMap 可以实现, 它还可以按读取顺序来排列，像连接池中可以应用。

（七）HashMap 和 Hashtable 的区别

线程是否安全： HashMap 是非线程安全的，HashTable 是线程安全的；HashTable 内部的方法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；
效率：因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；
对 Null key 和 Null value 的支持： HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。。但是在 HashTable 中 put 进的键值只要有一个 null，直接抛出 NullPointerException。
初始容量大小和每次扩充容量大小的不同 ： ①创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的tableSizeFor()方法保证，下面给出了源代码）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小, 后面会介绍到为什么是 2 的幂次方。
底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

（八）HashMap 和 HashSet 区别

如果你看过 HashSet 源码的话就应该知道：HashSet 底层就是基于 HashMap 实现的。（HashSet 的源码非常非常少，因为除了 clone()、writeObject()、readObject()是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

（九）HashSet 如何检查重复

当你把对象加入HashSet时，HashSet 会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相符的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用equals（）方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功。（摘自我的 Java 启蒙书《Head fist java》第二版）

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

如果两个对象相等，则 hashcode 一定也是相同的
两个对象相等, 对两个 equals 方法返回 true
两个对象有相同的 hashcode 值，它们也不一定是相等的
综上，equals 方法被覆盖过，则 hashCode 方法也必须被覆盖
hashCode() 的默认行为是对堆上的对象产生独特值。如果没有重写 hashCode()，则该 class 的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。

（十）HashMap 的底层实现

JDK1.8 之前

JDK1.8 之前 HashMap 底层是数组和链表结合在一起使用也就是链表散列。HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法换句话说使用扰动函数之后可以减少碰撞。

HashMap 实现原理（比较好的描述）：HashMap 以键值对（key-value）的形式来储存元素，但调用 put 方法时，HashMap 会通过 hash 函数来计算 key 的 hash 值，然后通过 hash 值 &(HashMap.length-1) 判断当前元素的存储位置，如果当前位置存在元素的话，就要判断当前元素与要存入的 key 是否相同，如果相同则覆盖，如果不同则通过拉链表来解决。JDk1.8 时，当链表长度大于 8 时，将链表转为红黑树。

JDK 1.8 HashMap 的 hash 方法源码:

JDK 1.8 的 hash 方法相比于 JDK 1.7 hash 方法更加简化，但是原理不变。

static final int hash(Object key) {
2       int h;
3       // key.hashCode()：返回散列值也就是hashcode
4       // ^ ：按位异或
5       // >>>:无符号右移，忽略符号位，空位都以0补齐
6       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
7   }

对比一下 JDK1.7 的 HashMap 的 hash 方法源码.

1 static int hash(int h) {
2     // This function ensures that hashCodes that differ only by
3     // constant multiples at each bit position have a bounded
4     // number of collisions (approximately 8 at default load factor).
6     h ^= (h >>> 20) ^ (h >>> 12);
7     return h ^ (h >>> 7) ^ (h >>> 4);
8 }

相比于 JDK1.8 的 hash 方法，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。

所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

JDK1.8 之后

相比于之前的版本， JDK1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间。

TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。

（十一）HashMap 的长度为什么是 2 的幂次方

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。我们上面也讲到了过了，Hash 值的范围值 - 2147483648 到 2147483647，前后加起来大概 40 亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是 “ (n - 1) & hash”。（n 代表数组长度）。这也就解释了 HashMap 的长度为什么是 2 的幂次方。

这个算法应该如何设计呢？

我们首先可能会想到采用 % 取余的操作来实现。但是，重点来了：“取余 (%) 操作中如果除数是 2 的幂次则等价于与其除数减一的与 (&) 操作（也就是说 hash%length == hash&(length-1)的前提是 length 是 2 的 n 次方；）。” 并且采用二进制位操作 &，相对于 % 能够提高运算效率，这就解释了 HashMap 的长度为什么是 2 的幂次方。

（十二）HashMap 多线程操作导致死循环问题

主要原因在于并发下的 Rehash 会造成元素之间会形成一个循环链表。不过，jdk 1.8 后解决了这个问题，但是还是不建议在多线程下使用 HashMap, 因为多线程下使用 HashMap 还是会存在其他问题比如数据丢失。并发环境下推荐使用 ConcurrentHashMap 。

Rehash：一般来说，Hash 表这个容器当有数据要插入时，都会检查容量有没有超过设定的 thredhold，如果超过，需要增大 Hash 表的尺寸，但是这样一来，整个 Hash 表里的无素都需要被重算一遍。这叫 rehash，这个成本相当的大。

（十三）ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

底层数据结构： JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组 + 链表 实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组 + 链表 / 红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组 + 链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
实现线程安全的方式（重要）： ① 在 JDK1.7 的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段 (Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。 到了 JDK1.8 的时候已经摒弃了 Segment 的概念，而是直接用 Node 数组 + 链表 + 红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后对 synchronized 锁做了很多优化）整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；② Hashtable(同一把锁) 😗* 使用 synchronized 来保证线程安全，get/put 所有相关操作都是 synchronized 的，这相当于给整个哈希表加了一把大锁,** 效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

两者的对比图：

HashTable:

JDK1.7 的 ConcurrentHashMap：

（十四）ConcurrentHashMap 线程安全的具体实现方式 / 底层具体实现

JDK1.7（上面有示意图）

首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。

ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。

Segment 实现了 ReentrantLock, 所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。

static class Segment<K,V> extends ReentrantLock implements Serializable {
}

一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和 HashMap 类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 的锁。

JDK1.8 （上面有示意图）

ConcurrentHashMap 取消了 Segment 分段锁，采用 CAS 和 synchronized 来保证并发安全。数据结构跟 HashMap1.8 的结构类似，数组 + 链表 / 红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）

synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，效率又提升 N 倍。

（十五）comparable 和 Comparator 的区别

comparable 接口实际上是出自 java.lang 包它有一个 compareTo(Object obj)方法用来排序
comparator 接口实际上是出自 java.util 包它有一个compare(Object obj1, Object obj2)方法用来排序

Map 类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 的锁。

HL🌱数字花园

探索