JAVA集合篇---详细

文章目录

• 集合
• List
• ArrayList
• LinkedList
• Vector
• Set
• TreeSet
• HashSet
• HashSet底层原理
• HashSet的add方法
• HashSet的Remove方法
• Iterator迭代器
• 底层实现原理
• Map
• HashMap
• list与Set、Map区别及适用场景

集合

集合类的特点：提供一种存储空间可变的存储模式，存储的数据容量可以随时发生改变。　　
和数组的区别：数组是存储同种数据类型、长度在定义后便不可变。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tiReLxLY-1594887118394)(en-resource://database/819:1)]

集合分为单列集合(Collection)和双列集合（Map）
Collection集合的概述：是单列集合的顶层接口，它表示一组对象，这些对象也称为Collection的元素；JDK不提供此接口的任何直接实现，它提供更具体的子接口

List

List是java中重要的数据结构之一，元素有放入顺序，元素可重复 。
这里介绍常用的3种实现方式：ArrayList、Vector、LinkedList。

可以看到，ArrayList、Vector、LinkedList都是AbstractList的实现。而AbstractList实现了List接口，并扩展自AbstractCollection。

数组，链表都是线性顺序排列的，数组的线性顺序是由数组下标决定的，而链表的线性顺序是由各个对象的指针决定的。
数组连续存储，寻址容易，插入删除操作相对困难；而链表离散存储，寻址相对困难，而插入删除操作容易

ArrayList

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

缺点：因为地址连续， （插入数据时，这个位置后面的数据在内存中要往后移）ArrayList要移动数据,所以插入和删除操作效率比较低。

LinkedList

优点：LinkedList基于链表的数据结构（LinkedList使用的是循环双向链表）,地址是任意的，所以在开辟内存空间的时候不需要等一个连续的地址，对于新增和删除操作add和remove，LinedList比较占优势。LinkedList 适用于要头尾操作或插入指定位置的场景。

缺点：因为LinkedList要移动指针,所以查询操作性能比较低。

Vector

ArrayList和Vector都是用数组实现的，主要有这么三个区别：

• 它支持线程的同步，即某一时刻只有一个线程能够写Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的花费，因此，访问它比访问ArrayList慢。
• 两个都是采用的线性连续空间存储元素，但是当空间不足的时候，两个类的增加方式是不同。如果集合中的元素的数目大于目前集合数组的长度时，vector增长率为目前数组长度的100%,而arraylist增长率为目前数组长度的50%.如过在集合中使用数据量比较大的数据，用vector有一定的优势。
• Vector可以设置增长因子，而ArrayList不可以。

Set

元素无放入顺序，元素不可重复。

TreeSet

TreeSet是红黑树的树据结构(是一种自平衡的二叉树)实现的,Treeset中的数据是自动排好序的，不允许放入null值 。

• 如何保证元素唯一性呢?

返回0代表元素相同, 返回1代表不同

• 如何保证元素的排序呢?

两种方式：

1. 自然排序(元素具备比较性)：
   让元素所属的类实现Comparable接口

public class Student implements Comparable<Student>

2. 比较器排序(集合具备比较性)：
   让集合接收一个Comparator的实现类对象

//创建一个比较器接口的子类对象
public class MyComparator implements Comparator<Student>

 TreeSet<Student> ts = new TreeSet<Student>(new MyComparator());

HashSet

HashSet,TreeSet都是AbstractSet的实现，AbstractSet是set的实现同时扩展自AbstractCollection。

HashSet是哈希表实现的,HashSet中的数据是无序的，可以放入null，但只能放入一个null，两者中的值都不能重复。

HashSet要求放入的对象必须实现HashCode()方法，放入的对象，是以hashcode码作为标识的，而具有相同内容的String对象，hashcode是一样，所以放入的内容不能重复。

执行顺序：
                    首先判断hashCode()值是否相同
                        是：继续执行equals(),看其返回值
                            是true:说明元素重复，不添加。
                            是false:就直接添加到集合。
                        否：就直接添加到集合
                最终：
                    自动生成hashCode()和equals()即可

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

HashSet底层原理

HashSet有几个重载的构造方法：

private transient HashMap<E,Object> map; 
//默认构造器 public HashSet() { 
map = new HashMap<>(); 
} 
//将传入的集合添加到HashSet的构造器 
public HashSet(Collection<? extends E> c) { 
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16)); 
addAll(c); 
} 
//明确初始容量和装载因子的构造器 
public HashSet(int initialCapacity, float loadFactor) { 
map = new HashMap<>(initialCapacity, loadFactor);
} 
//仅明确初始容量的构造器（装载因子默认0.75） 
public HashSet(int initialCapacity) { 
map = new HashMap<>(initialCapacity);
}

发现HashSet底层是通过HashMap实现的。TreeSet也是通过TreeMap实现的

HashSet的add方法

HashSet的add方法时通过HashMap的put方法实现的，HashSet添加的元素是存放在HashMap的key位置上，而value取了默认常量PRESENT，是一个空对象。

HashSet的Remove方法

HashSet的remove方法通过HashMap的remove方法来实现，通过key找到元素在数组中的位置，在调用removeNode方法删除。

set是collection的子接口，但是具体实现是通过Map。

Iterator迭代器

迭代器是一种设计模式，是一个对象，Iterator可以不用管底层数据具体是怎样存储的，都能够遍历并选择序列中的对象。迭代器通常被称为“轻量级”对象，因为创建它的代价太小。
Java中的Iterator功能比较简单，并且只能单向移动：

1. 使用方法iterator()要求容器返回一个Iterator。第一次调用Iterator的next()方法时，它返回序列的第一个元素。注意：iterator()方法是java.lang.Iterable接口,被Collection继承。
2. 使用next()获得序列中的下一个元素。
3. 使用hasNext()检查序列中是否还有元素。
4. 使用remove()将迭代器新返回的元素删除。

import java.util.*;
public class Muster {
 
    public static void main(String[] args) {
        ArrayList list = new ArrayList();
        list.add("a");
        list.add("b");
        list.add("c");
        Iterator it = list.iterator();
        while(it.hasNext()){
            String str = (String) it.next();
            System.out.println(str);
        }
    }
}

底层实现原理

这里我们来看看Java里AbstractList实现Iterator的源代码：

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {    // List接口实现了Collection<E>, Iterable<E>
2. 
3.    protected AbstractList() { 
4.    } 
5.   
6.    ... 
7. 
8.    public Iterator<E> iterator() { 
9.    return new Itr();  // 这里返回一个迭代器
10.    } 
11. 
12.    private class Itr implements Iterator<E> {  // 内部类Itr实现迭代器
13.      
14.    int cursor = 0; 
15.    int lastRet = -1; 
16.    int expectedModCount = modCount; 
17. 
18.    public boolean hasNext() {  // 实现hasNext方法
19.            return cursor != size(); 
20.    } 
21. 
22.    public E next() {  // 实现next方法
23.            checkForComodification(); 
24.        try { 
25.        E next = get(cursor); 
26.        lastRet = cursor++; 
27.        return next; 
28.        } catch (IndexOutOfBoundsException e) { 
29.        checkForComodification(); 
30.        throw new NoSuchElementException(); 
31.        } 
32.    } 
33. 
34.    public void remove() {  // 实现remove方法
35.        if (lastRet == -1) 
36.        throw new IllegalStateException(); 
37.            checkForComodification(); 
38. 
39.        try { 
40.        AbstractList.this.remove(lastRet); 
41.        if (lastRet < cursor) 
42.            cursor--; 
43.        lastRet = -1; 
44.        expectedModCount = modCount; 
45.        } catch (IndexOutOfBoundsException e) { 
46.        throw new ConcurrentModificationException(); 
47.        } 
48.    } 
49. 
50.    final void checkForComodification() { 
51.        if (modCount != expectedModCount) 
52.        throw new ConcurrentModificationException(); 
53.    } 
54.    } 
55.}

可以看到，实现next()是通过get(cursor)，然后cursor++，通过这样实现遍历。

这部分代码不难看懂，唯一难懂的是remove操作里涉及到的expectedModCount = modCount;在网上查到说这是集合迭代中的一种“快速失败”机制，这种机制提供迭代过程中集合的安全性。从源代码里可以看到增删操作都会使modCount++，通过和expectedModCount的对比，迭代器可以快速的知道迭代过程中是否存在list.add()类似的操作，存在的话快速失败!

import java.util.*;
public class Muster {
 
    public static void main(String[] args) {
        ArrayList list = new ArrayList();
        list.add("a");
        list.add("b");
        list.add("c");
        Iterator it = list.iterator();
        while(it.hasNext()){
            String str = (String) it.next();
            System.out.println(str);
            list.add("s");        //添加一个add方法
        }
    }
}

运行结果：
a
Exception in thread "main" java.util.ConcurrentModificationException　　
at java.util.ArrayList$Itr.checkForComodification(Unknown Source)　　
at java.util.ArrayList$Itr.next(Unknown Source)　　
at com.hasse.Muster.main(Muster.java:11)

modCount记录修改此列表的次数：包括改变列表的结构，改变列表的大小，打乱列表的顺序等使正在进行迭代产生错误的结果。

我们知道的是ArrayList是线程不安全的，如果在使用迭代器的过程中有其他的线程修改了List就会抛出ConcurrentModificationException，这就是Fail-Fast机制。

Map

双列集合，包括HashMap,TreeMap,HashTable。

HashMap

HashMap：基于哈希表实现。使用HashMap要求添加的键类明确定义了hashCode()和equals()[可以重写hashCode()和equals()]，为了优化HashMap空间的使用，您可以调优初始容量和负载因子。

一、哈希冲突：

若两个不相等的 key 产生了相等的 哈希值（相等的数组下标） ，这时则需要采用 哈希冲突 。

二、拉链法：

Java 标准库的 HashMap 基本上就是用 拉链法 实现的。 拉链法 的实现比较简单，将链表和数组相结合。也就是说创建一个单向链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

三、HashMap的map.put（k，v）实现原理：

1. 将key，value封装到Node对象中。
2. 它的底层会调用key的hashCode()方法得出hash值。
3. 通过哈希表函数/哈希算法，将hash值转换成数组下标，数组下标位置上如果没有任何元素，就把Node添加到这个位置上。如果这个位置有值，判断key是否相同，相同则覆盖，不同的话采用拉链法，存储到元素对应的链表中。
4. 如果说下标对应的位置上有链表。此时，就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false，那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true，那么这个节点的value将会被覆盖。

四、HashMap的map.get（k）实现原理：

1. 先调用k的hashCode()方法得出哈希值，并通过哈希算法转换成数组的下标。
2. 在通过数组下标快速定位到某个位置上。如果这个位置上什么都没有，则返回null。如果这个位置上有单向链表，那么它就会拿着参数K和单向链表上的每一个节点的K进行equals，如果所有equals方法都返回false，则get方法返回null。如果其中一个节点的K和参数K进行equals返回true，那么此时该节点的value就是我们要找的value了，get方法最终返回这个要找的value。

五、HashMap的扩容机制：

当HashMap中的结点个数超过数组大小loadEactor*(加载因子)时，就会进行数组扩容,loadFactor的默认值为0.75.世就是说，默认情况下，数组大小为16，那么当HashMap电结点个数超过160.75=12的时候，就把数组的大小和展为216=32,即扩大一倍，然后重新计算每个元素在数组中的位置，并放进去，而这是一个非常消耗性能的操作。

六、多线程下HashMap出现的问题：

1. 多线程put操作后，get操作导致死循环导致cpu100%的现象。主要是多线程同时put时，如果同时触发了rehash操作，会导致扩容后的HashMap中的链表中出现循环节点进而使得后面get的时候，会死循环。
2. 多线程put操作，导致元素丢失，也是发生在个线程对hashmap 扩容时。

七、HashMap和HashTable的区别：

1. Hashtable 是线程安全的，方法是Synchronized 的，适合在多线程环境中使用，效率稍低: HashMap不是线程安全的，方法不是Synchronized的，效率稍高，适合在单线程环境下使用，所以在多线程场合下使用的话，需要手动同步HashMap，Collctions. synchronizedMap()。PS:HashTable的效率比较低的原因?在线程竞争激烈的情况下HashTable的效率非常低下。因为当一个线程访间HashTable的同步方法时，访问其他同步方法的线程就可能会进入阻嘉或者轮训状态。如线程1使用put进行添加元素，线程2不但不能使用put方法添加元素，并且也不能使用get方法来获取元素，所以竞争越激烈改率越低.
2. HashMap的key和value都可以为null值，HashTable 的key和value都不允许存Null值。
3. HashMap中数组的默认大小是16，而且一定是2的倍数，扩容后的数組长度是之前数组长度的2倍。HashTable中数组默认大小是11.扩容后的数组长度是之前数组长度的2倍+1。
4. HashMap去掉了HashTable的contains方法，但加上了containsValue（）和containsKey（）方法。

八、HashMap为什么无序：

无序，不可重复为什么是无序的？因为不一定挂到哪一个单向链表上的，因此加入顺序和取出也不一样。
怎么保持不可重复？使用equals方法来保证HashMap集合key不可重复，如key重复来，value就会覆盖。

九、JDK1.8

JDK8之后，如果哈希表单向链表中元素超过8个，那么单向链表这种数据结构会变成红黑树数据结构。当红黑树上的节点数量小于6个，会重新把红黑树变成单向链表数据结构。

list与Set、Map区别及适用场景

1. List,Set都是继承自Collection接口，Map则不是。

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

3. Set和List对比： Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。 List：和数组类似，List可以动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变。

4 .Map适合储存键值对的数据。

5. 线程安全集合类与非线程安全集合类
LinkedList、ArrayList、HashSet是非线程安全的，Vector是线程安全的;HashMap是非线程安全的，HashTable是线程安全的;StringBuilder是非线程安全的，StringBuffer是线程安全的。

本文地址：https://blog.csdn.net/qq_41993003/article/details/107385567