欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页  >  IT编程

JAVA集合篇---详细

程序员文章站 2022-11-15 20:20:18
文章目录集合ListArrayListLinkedListVectorSetTreeSetHashSetHashSet底层原理HashSet的add方法HashSet的Remove方法Iterator迭代器底层实现原理MapHashMaplist与Set、Map区别及适用场景集合集合类的特点：提供一种存储空间可变的存储模式，存储的数据容量可以随时发生改变。　　和数组的区别：数组是存储同种数据类型、长度在定义后便不可变。[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-t...

文章目录


JAVA集合篇---详细

集合

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(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>
  1. 比较器排序(集合具备比较性)：
    让集合接收一个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

相关标签： java

上一篇： 数据结构与算法学习笔记：单向链表

下一篇： LeetCode——有效的括号（括号匹配）

推荐阅读