Java集合详解

一、集合大纲

 

0.集合的基础知识：

HashMap：

创建对象：HashMap<Integer, String> Sites = new HashMap<Integer, String>();
输出结果：{1=Google, 2=Runoob, 3=Taobao}
eg：HashMap<String, String> map = new HashMap<String, String>();
    map.put("1","yff");
    map.put("2","yll");
    System.out.println(map);
 
结果：{1=yff, 2=yll}

ArrayList：

创建对象：ArrayList<String> sites = new ArrayList<String>();
 
输出结果：[Google, Runoob, Taobao]

HashSet：

创建对象：HashSet<String> sites = new HashSet<String>();
 
输出结果：[Google, Runoob, Zhihu, Taobao]

1.集合和数组的区别：

2.Collection集合的常用方法：

备注：

​​collection和collections的区别Java中Collection和Collections的区别_行万里路，读万卷书的博客-CSDN博客_collection和collections的区别

1、Collection是一个集合接口。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供最大化的统一操作方式。

2、Collections是一个jdk 的java.util包下的类（Arrays也是）。它包含各种有关集合操作的静态多态方法。服务于Java的Collection框架。

排序(Sort)

反转(Reverse)

替换所有元素（Fill）

拷贝（copy）

返回Collections中最小元素(min)

返回Collections中最小元素(max) ​等等

集合排序：在集合框架出现，对于实现集合排序，JDK推出了集合排序的接口Comparable<T>（自然排序）和Comparator<T>（比较器排序）用于集合的排序（该集合为单列集合Collection）

Comparator与Comparable区别

博客：

java中集合排序的常用方法总结_java 集合排序_卖柴火的小伙子的博客-CSDN博客

排序算法详解及实际应用_排序算法的实际应用_keep one's resolveY的博客-CSDN博客

java集合的排序_集合排序的实现类_撸java代码的博客-CSDN博客

3.常用集合的分类：

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

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

二、List和Set集合详解：

1.list和set的区别：

2.List详解

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

3.Set详解

  (1) HashSet

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

hashCode()和equals()都是Object类的方法，hashCode()默认是通过地址来计算hash码，但是可能被重写过用内容来计算hash码，equals()默认通过地址判断两个对象是否相等，但是可能被重写用内容来比较两个对象

所以两个对象相等，他们的hashCode和equals一定相等，但是hashCode相等的两个对象未必相等，因为hashcode返回的是int类型，他的最多有2的32次方个，还是有可能会重复的。

为什么要同时重写equals方法和hashcode方法？
了解目的之后，所以我们需要重写这俩个方法，那只重写其中的一个方法可行嘛？我们来分析一下：
只重写equals方法：

比如在HashSet或HashMap中，key如果是String类型，String如果只重写了equals（）而没有重写hashcode（）的话，则两个equals()比较为true的key，因为hashcode不同导致两个key没有出现在一个索引上，就会出现map中存在两个相同的key。

只重写hashcode方法呢：在做对象之间的比较时，我们要知道：

如果equals方法相等，则他们hsahcode的hash值必然相等，俩个对象必然相等
如果equals方法不等，则他们hashcode的hash值不一定不等，俩个对象必然不等
如果hashcode的hash值不等，则俩个对象必然不等
如果hashcode的hash值相等，俩个对象不一定相等，要在判断equals是否相等来比较俩个对象是否相等。(为什么具有相同哈希码的两个对象不一定相等? 这很简单.哈希码是int整数，只有32位.现在以 Long 为例.由于它的长度为64位，其值比2 的32次方 多得多.但是依旧会有很多具有相同哈希码的值.)
所以，需要同时重写equals方法和hashcode方法。

具体实现唯一性的比较过程：存储元素首先会使用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();
 
hs.add(o);
|
o.hashCode();
|
o%当前总容量 (0–15)
|
hashCode是否冲突（与原来的hashcode进行比较）？
  不发生冲突  —————–  直接存放
|
  发生冲突则再判断
| 
  o1.equals(o2)————假（不相等）——-找一个空位添加
               ————是（相等）  ——-不添加
        
 
覆盖hashCode()方法的原则：
1、一定要让那些我们认为相同的对象返回相同的hashCode值
2、尽量让那些我们认为不同的对象返回不同的hashCode值，否则，就会增加冲突的概率。
3、尽量的让hashCode值散列开（两值用异或运算可使结果的范围更广）
HashSet 的实现比较简单，相关HashSet的操作，基本上都是直接调用底层HashMap的相关方法来完成，
我们应该为保存到HashSet中的对象覆盖hashCode()和equals()，因为再将对象加入到HashSet中时，
会首先调用hashCode方法计算出对象的hash值，接着根据此hash值调用HashMap中的hash方法，
得到的值& (length-1)得到该对象在hashMap的transient Entry[] table中的保存位置的索引，
接着找到数组中该索引位置保存的对象，并调用equals方法比较这两个对象是否相等，如果相等则不添加，
注意：所以要存入HashSet的集合对象中的自定义类必须覆盖hashCode(),equals()两个方法，
才能保证集合中元素不重复。在覆盖equals()和hashCode()方法时， 要使相同对象的hashCode()方法
返回相同值，覆盖equals()方法再判断其内容。为了保证效率，所以在覆盖hashCode()方法时， 
也要尽量使不同对象尽量返回不同的Hash码值。
 
如果数组中的元素和要加入的对象的hashCode()返回了相同的Hash值（相同对象）,
才会用equals()方法来判断两个对象的内容是否相同。

 (2) LinkedHashSet 

底层数据结构采用链表和哈希表共同实现（有排序），链表保证了元素的顺序与存储顺序一致，哈希表保证了元素的唯一性。线程不安全，效率高。
 

(3) TreeSet 

底层数据结构采用二叉树来实现（保证插入遍历顺序一致），元素唯一且已经排好序；唯一性同样需要重写hashCode和equals()方法，二叉树结构保证了元素的有序性。

根据构造方法不同，分为自然排序（无参构造）和比较器排序（有参构造）：

自然排序要求元素（实体类）必须实现Compareable接口，并重写里面的compareTo()方法，元素（实体类）通过比较返回的int值来判断排序序列，返回0说明两个对象相同，不需要存储；

比较器排需要在TreeSet初始化是时候传入一个实现Comparator接口的比较器对象，或者采用匿名内部类的方式new一个Comparator对象，重写里面的compare()方法；
 

在代码开发中会遇到，讲取到的数据list按照某个字段排序，可以直接使用Collections.sort()方法排序
 
 //排序前，要确认list 是否为空，避免空指针异常
 List <ObejectEntity> list= new arrayList<>();
 Collections.sort(list, new Comparator<ObejectEntity>() {
            @Override
            public int compare(ObejectEntity o1, ObejectEntity o2) {
            //这里使用时间字段排序 如果要用其他字段直接从bean实体中取
            return o2.getPayTime().compareTo(o1.getPayTime());
            //上面使用的是降序排序，如果正序 直接使用o1-o2即可
            }
        });
 
 
不过现在使用lambda表达式更简洁（推荐）
 
 //这里是上面的lambda变种方式
 Collections.sort(list, (o1, o2) -> o2.getPayTime().compareTo(o1.getPayTime()));
 
//如果排序后，需要取前几条，可以直接使用sublist(startIndex , endIndex)
 List<ObejectEntity> orderList=list.subList(0,10);
 

(4) 小结 

Set 存入Set的每个元素都必须是唯一的，因为Set不保存重复元素。加入Set的元素必须定义equals()方法以确保对象的唯一性。Set和Collection有完全一样的接口。Set接口不保证维护元素的次序。

4.List和Set总结

（1）、List,Set都是继承自Collection接口，Map则不是
（2）、List特点：元素有放入顺序，元素可重复 ，Set特点：元素无放入顺序，元素不可重复，重复元素会覆盖掉，（注意：元素虽然无放入顺序，但是元素在set中的位置是有该元素的HashCode决定的，其位置其实是固定的，加入Set 的Object必须定义equals()方法 ，另外list支持for循环，也就是通过下标来遍历，也可以用迭代器，但是set只能用迭代，因为他无序，无法用下标来取得想要的值。）
（3）、Set和List对比：
Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。
List：和数组类似，List可以动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变。
 （4）、常用的类的区别

---------------------------------------------------------------------
一、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有一定的优势。
 
--------------------------------------------------------------------------
三、TreeSet 和HashSet区别：
 
1.TreeSet 是二差树（红黑树的树据结构）实现的,Treeset中的数据是自动排好序的，
不允许放入null值
2.HashSet 是哈希表实现的,HashSet中的数据是无序的，可以放入null，但只能放入一个null，
两者中的值都不能重复，就如数据库中唯一约束
3.HashSet要求放入的对象必须实现HashCode()方法，放入的对象，是以hashcode码作为标识的，
而具有相同内容的String对象，hashcode是一样，所以放入的内容不能重复。
但是同一个类的对象可以放入不同的实例
 
适用场景分析:
HashSet是基于Hash算法实现的，其性能通常都优于TreeSet。为快速查找而设计的Set，
我们通常都应该使用HashSet，在我们需要排序的功能时，我们才使用TreeSet。

List和Set的核心图

Java使用不同方式获取两个集合List的交集、补集、并集(相加)、差集(相减)_java list取交集-CSDN博客

遍历list和set的方法：

1.使用for循环遍历List与Set集合

for (int i = 0; i < list.size(); i++) { System.out.println(list.get(i)); }

for (int i = 0; i < set.size()-(set.size()-1); i++) { System.out.println(set); }

--------------------------------------------------------------------------------------------------------------

2.使用foreach遍历List与Set集合

for (String str : list) { System.out.println(str); }

for(String str1:set) { System.out.println(str1); }

--------------------------------------------------------------------------------------------------------------

3.使用迭代器遍历List与Set集合

// 1.根据集合获取对应的迭代器
        Iterator<String> it = list.iterator();
        // 2.判断是否有下一个元素,如果有的话就返回true并且执行循环,
        // 如果没有,说明已经取到迭代器的末尾
        while (it.hasNext()) {
            String string = it.next();
            System.out.println(string);
        }

//根据集合获取对应的迭代器
        Iterator<String> it = set.iterator();
        while(it.hasNext()) {
            //定义一个字符串接收遍历的集合内容
            String str2=it.next();
            System.out.println(str2);
        }

--------------------------------------------------------------------------------------------------------------

4.使用lambda表达式遍历List与Set集合

list.forEach(n -> System.out.println(n));

System.out.println("=====4.使用lambda表达式遍历List集合(二)====="); list.forEach(System.out::println);

--------------------------------------------------------------------

set.forEach(n->System.out.println(n));
        //使用lambda遍历Set
        System.out.println("=========3.使用lambda遍历Set集合(二)===========");
        set.forEach(System.out::println);

移除List元素的方法：

通过迭代器的方式，进行 remove() 操作不仅会删除元素，还会对 list 集合的下标进行重新维护，因此，在删除操作时建议使用这种方式。

删除list集合中特定元素的正确姿势_斗者_2013的博客-CSDN博客_list删除指定元素

取两个集合List的交集、补集、并集、差集的几种方式_取两个list的交集-CSDN博客（重要）

三、Map详解：

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

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

（2）Map的常用方法：

（3）HashMap和HashTable的比较：

（4）TreeMap：

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

HashMap和HashTable和Treemap适用场景分析:

HashMap去掉了HashTable的contains方法，但是加上了containsValue()和containsKey()方法，
HashTable同步的，而HashMap是非同步的，效率上比HashTable要高。
HashMap允许空键值，而HashTable不允许
 
HashMap：适用于Map中插入、删除和定位元素
Treemap：适用于按自然顺序或自定义顺序遍历键(key)

遍历Map：

谈谈java中遍历Map的几种方法 
java中的map遍历有多种方法，从最早的Iterator，到java5支持的foreach,再到java8 Lambda，让我们一起来看下具体的用法以及各自的优缺点
 
先初始化一个map
public class TestMap {
  public static Map<Integer, Integer> map = new HashMap<Integer, Integer>();
}
----------------------------------------------------------------------------------
1、keySet values
如果只需要map的key或者value，用map的keySet或values方法无疑是最方便的
 
  // KeySet 获取key
  public void testKeySet() {
    for (Integer key : map.keySet()) {
      System.out.println(key);
    }
  }
  // values 获取value
  public void testValues() {
    for (Integer value : map.values()) {
      System.out.println(value);
    }
  }
----------------------------------------------------------------------------------
2、keySet get(key)
如果需要同时获取key和value，可以先获取key,然后再通过map的get(key)获取value
 
需要说明的是，该方法不是最优选择，一般不推荐使用
 
  // keySet get(key) 获取key and value
  public void testKeySetAndGetKey() {
    for (Integer key : map.keySet()) {
      System.out.println(key + ":" + map.get(key));
    }
  }
----------------------------------------------------------------------------------
3、entrySet
通过对map entrySet的遍历，也可以同时拿到key和value，一般情况下，性能上要优于上一种,这一种也是最常用的遍历方法
 
  // entrySet 获取key and value
  public void testEntry() {
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
      System.out.println(entry.getKey() + ":" + entry.getValue());
    }
  }
----------------------------------------------------------------------------------
4、Iterator
对于上面的几种foreach都可以用Iterator代替，其实foreach在java5中才被支持，foreach的写法看起来更简洁
 
但Iterator也有其优势：在用foreach遍历map时，如果改变其大小，会报错，但如果只是删除元素，可以使用Iterator的remove方法删除元素
 
  // Iterator entrySet 获取key and value
  public void testIterator() {
    Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
    while (it.hasNext()) {
      Map.Entry<Integer, Integer> entry = it.next();
      System.out.println(entry.getKey() + ":" + entry.getValue());
      // it.remove(); 删除元素
    }
  }
----------------------------------------------------------------------------------
5、Lambda
java8提供了Lambda表达式支持，语法看起来更简洁，可以同时拿到key和value，不过，经测试，性能低于entrySet,所以更推荐用entrySet的方式
 
  // Lambda 获取key and value
  public void testLambda() {
    map.forEach((key, value) -> {
      System.out.println(key + ":" + value);
    });
  }
简单性能测试
用10万条数据，做了一个简单性能测试，数据类型为Integer，map实现选取HashMap
 
  static {
    for (int i = 0; i < 100000; i++) {
      map.put(i, 1);
    }
  }
测试结果如下：
 
KeySet：           392
Values：           320
keySet get(key)：  552
entrySet：         465
entrySet Iterator：508
Lambda：           536
需要说明的是，map存储的数据类型，map的大小，以及map的不同实现方式都会影响遍历的性能，所以该测试结果仅供参考
----------------------------------------------------------------------------------
 
总结：
如果只是获取key，或者value，推荐使用keySet或者values方式
如果同时需要key和value推荐使用entrySet
如果需要在遍历过程中删除元素推荐使用Iterator
如果需要在遍历过程中增加元素，可以新建一个临时map存放新增的元素，等遍历完毕，再把临时map放到原来的map中

-----------------------------------------------------------------------------------------------------------------------------

集合线程安全集合类与非线程安全集合类

LinkedList、ArrayList、HashSet是非线程安全的，Vector是线程安全的;
HashMap是非线程安全的，HashTable是线程安全的;
StringBuilder是非线程安全的，StringBuffer是线程安全的。

集合数据结构

ArrayXxx:底层数据结构是数组，查询修改快，增删慢
LinkedXxx:底层数据结构是链表，查询修改慢，增删快
HashXxx:底层数据结构是哈希表。有数组链表的优点，依赖两个方法：hashCode()（hash表的地址）和equals()
TreeXxx:底层数据结构是二叉树。两种方式排序：自然排序和比较器排序

集合对比：

Map接口和Collection接口是所有集合框架的父接口。Collection又包含了Set、List。Set不能包含重复的元素。List是一个有序集合，可以包含重复元素，提供按索引遍历的方式。Map不能包含重复的key，但可以包含相同的value。

ArrayList
底层实现方式是数组，默认大小是10个，当指定容量大小时用指定大小的容量；当数组满了以1.5倍扩容，特点是查询快，增删改慢。
 

LinkedList
底层实现方式是双向链表，特点是查询慢，增删改快。
 

HashMap
底层实现是数组+链表+红黑树，默认大小16，当指定容量大小时，用大于该容量的最小的2的幂次方作为初始容量；当table使用了容量的0.75倍时扩容，扩容为2倍，当table容量超过64且链表数量大于8时，链表会树化。线程不安全。

HashMap的底层有数组 + 链表(红黑树)组成，数组的大小可以在构造方法时设置，
默认大小为16，数组中每一个元素就是一个链表，jdk7之前链表中的元素采用头插法插入元素，
jdk8之后采用尾插法插入元素，由于插入的元素越来越多，查找效率就变低了，
所以满足某种条件时，链表会转换成红黑树。随着元素的增加，HashMap的数组会频繁扩容，
如果构造时不赋予加载因子默认值，那么负载因子默认值为0.75,数组扩容的情况如下:
 
1:当添加某个元素后，数组的总的添加元素数大于了 数组长度 * 0.75(默认,也可自己设定),
数组长度扩容为两倍。(如开始创建HashMap集合后，数组长度为16，临界值为16 * 0.75 = 12，
当加入元素后元素个数超过12，数组长度扩容为32，临界值变为24)
 
2：在没有红黑树的条件下，添加元素后数组中某个链表的长度超过了8，数组会扩容为两倍
.(如开始创建HashMAp集合后，假设添加的元素都在一个链表中，当链表中元素为8时，
再在链表中添加一个元素，此时若数组中不存在红黑树，则数组会扩容为两倍变成32，
假设此时链表元素排列不变，再在该链表中添加一个元素，数组长度再扩容两倍，变为64，
假设此时链表元素排列还是不变，则此时链表中存在10个元素，这是HashMap链表元素数存在的最大值，
此时，再加入元素，满足了链表树化的两个条件(1:数组长度达到64, 2:该链表长度达到了8)，
该链表会转换为红黑树
————————————————
 
原文链接：https://blog.csdn.net/zhuzhianing/article/details/123962898

 

HashSet
对HashMap进行了封装，无序且不能重复，其他与HashMap一致。线程不安全。
 

HashTable
默认初始大小为11，指定大小时直接使用指定大小的容量；当使用了容量的0.75倍时扩容，扩容为2*n+1（n为扩容前容量）。不会树化。线程安全。
 

TreeMap
底层是红黑树，一种近似平衡的二叉查找树。按key的大小对元素进行排序。线程不安全。
 

TreeSet
对TreeMap进行了封装。
 

ConcurrentHashMap
1.7底层是Segment数组+HashEntry数组+链表，每个Segment继承了ReentrantLock。
1.8底层是Node数组+链表+红黑树，使用了CAS和Synchronized保证并发安全。

详细介绍

ArrayList
是顺序容器，底层通过数组实现。这里的数组是Object数组，可以容纳任何类型的对象，允许是null。因为数组内存连续性的要求，所以在申请内存的时候的时候必须指定申请的空间大小，而这个空间大小在申请后就已经固定无法变更，所以数组自己是没办法进行扩容的，只是我们人为用逻辑的方式对数组进行扩容。
扩容机制

1. ArrayList中维护了一个Object类型的数组elementData. transient Object[] elementData；
2. 当创建ArrayList对象时，如果使用的是无参构造器，则初始化elementData容量为0，第一次添加，则扩容elementData为10，如果再次扩容，则扩容elementData为1.5倍
3. 如果使用的是指定大小的构造器，则初始化elementData容量为指定大小，如果需要扩容，则直接扩容elementData为1.5倍

LinkedList
LinkedList同时实现了List接口和Deque接口，既可以看作顺序容器，也可以看作队列，同时也可以看作一个栈。没有实现同步（synchronized）
双向链表的数据结构。first和last引用分别指向链表的第一个和最后一个元素。没有哑元，当链表为空的时候first和last都指向null，链表本身就是完善线性表的内存扩容机制的数据结构，链表是一种不要求内存连续的顺序存储数据结构，它的数据节点可以分布在内存中的各个地方，节点之间是各自记录着下一个元素的指针，通过指针把所有节点串联起来组成了一条链装的结构。

HashMap
数组+链表+红黑树

两个影响HashMap性能的参数：初始容量initial capacity（指定初始table的大小）和负载系数load factor（指定自动扩容的临界值capactiy * load factor）。当entry的数量超过临界值时，容器自动扩容并重新哈希。负载系数默认为0.75，这是在时间和空间的权衡，如果为1则会导致太多的哈希冲突，底层红黑树变得异常复杂，不利于查询，降低了时间效率，如果为0.5又会浪费内存空间，原本存储1M的数据现在需要2M，降低了空间利用率。

两个特别注意的方法hashCode()和equals()。hashCode()决定了对象会被放到哪个bucket里，当多个对象的哈希值冲突时，equals()决定了这些对象是否是“同一个对象”。所以如果要将自定义对象放入，需要重载这两个方法。只重写hashCode无法保证两个对象的属性是否相同。

1. 我们往Hashmap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中
   的下标
2. 存储时，如果出现hash值相同的key，此时有两种情况。(1)如果key相同，则覆盖原始值；(2)如果
   key不同（出现冲突），则将当前的key-value放入链表中
3. 获取时，直接找到hash值对应的下标，进一步判断key是否相同，从而找到对应值。
   根据对冲突的处理方式不同，哈希表有两种实现方式：开放地址形式和冲突链表方式。
   

扩容机制
只有在第一次添加数据的时候，HashMap的容量才会确定下来。
如果没指定初始容量大小，HashMap的初始容量会初始为16。
如果指定了初始容量大小，HashMap会将其扩充为2的幂次方大小。指定为2的幂次方大小是因为为了让计算索引时hash(k)&(table.length - 1)与hash(k)%table.length相同，低位都为1，把哈希值的高位都抹掉了，即用位运算替代取模运算。

1. 添加一个元素时，先得到hash值，然后转换成索引值
2. 找到存储数据表table，看索引值位置是否有元素，如果没有则直接加入
3. 如果索引位置有元素，则会调用equals方法进行比较，如果相同就放弃添加，不相同就添加到最后
4. 如果一条链表的元素个数达到8，并且table的大小>=64，就会进行树化（红黑树），如果table不满64会先扩table。
5. table的数组扩容：第一次添加时，table数组扩容到16，临界值是160.75=12，如果table数组使用了临界值12，就会扩容到162=32，当table使用了新的临界值32*0.75=24，就会继续扩容，以此类推tempType

Java8 对 HashMap 进行了一些修改，最大的不同就是利用了红黑树，所以其由 数组+链表+红黑树 组成。
根据 Java7 HashMap 的介绍，我们知道，查找的时候，根据 hash 值我们能够快速定位到数组的具体下标，但是之后的话，需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决于链表的长度，为 O(n)。为了降低这部分的开销，在 Java8 中，当链表中的元素超过了 8 个以后，会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。

java 常见集合_lmdsoft的博客-CSDN博客_常用集合有哪些

HashSet
HashSet实现了Set接口；对HashMap进行了封装；可以存放null，但只能有一个null；不保证元素是有序的，取决于hash后，再确定索引的结果；不能有重复元素。其余与HashMap相同。

哈希表边存放的是哈希值。HashSet 存储元素的顺序并不是按照存入时的顺序（和List 显然不同） 而是按照哈希值来存的所以取数据也是按照哈希值取得。元素的哈希值是通过元素的hashcode 方法来获取的, HashSet 首先判断两个元素的哈希值，如果哈希值一样，接着会比较equals 方法 如果 equls 结果为true ，HashSet 就视为同一个元素。如果equals 为false 就不是同一个元素。

不同的对象hashcode一般都是不同的。如果hashcode相同时再equals判断。

那么如果哈希值出现重复相同，equals 为false 的元素是怎么存储呢,就是在同样的哈希值下顺延（可以认为哈希值相同的元素放在一个哈希桶中）。也就是哈希一样的存一列。如图1 表示hashCode 值不相同的情况；图2 表示hashCode 值相同，但equals 不相同的情况。

 HashSet 通过hashCode 值来确定元素在内存中的位置。一个hashCode 位置上可以存放多个元素。
 

Hashtable

1. 存放的元素是键值对：K-V
2. 键和值都不能为null
3. 使用方法和HashMap一样
4. Hashtable是线程安全的（synchronized），HashMap不是

扩容机制

1. 不指定初始容量，初始容量大小为11，到达临界值为容量*0.75时，扩容为2n+1。
2. 如果指定初始容量，直接使用给定容量大小。
3. 不会进行树化。
4. 采用头插法迁移数据。

TreeMap
底层通过红黑树实现，会按照key的大小顺序对Map中的元素进行排序。非同步。

TreeSet
对TreeMap进行了封装

ConcurrentHashMap
实现了线程安全。读操作和写操作都能有很高的性能，读操作几乎不需要加锁，写操作通过锁分段技术只对所操作的段加锁而不影响客户端对其它段的访问。到1.8的时候改成了CAS和Synchronized。
1.7底层数据结构： Segments数组+HashEntry数组+链表。
将数组分成n个Segment，每个Segment里存放的是由HashEntry组成的数组，HashEntry用于存储键值对数据。每个HashEntry之间形成冲突链表。
Segment继承了ReentrantLock。当对HashEntry数组的数据进行修改时，必须首先获得对应的Segment数组元素的锁。每次加锁的操作锁住的是一个Segment，保证了每个Segment是线程安全的。
无参构造默认有16个Segment，传入参数Segment数量为大于参数的最小的2的幂次数。Segment不可以扩容，Segment[i]可以扩容。
Segment[i] 的默认大小为 2，负载因子是 0.75，得出初始阈值为 1.5，也就是以后插入第一个元素不会触发扩容，插入第二个会进行第一次扩容。

1.8底层数据结构： Node数组+链表+红黑树，和HashMap一样，但采用CAS（Compare-and-Swap，比较并替换）和Synchronized来保证并发安全。Synchronized进行了锁升级，所以性能没有问题。