不爱吃鸭脖
jinhua
2023-07-07
目录

java集合

# java集合

# 常见的集合有哪些

  • Collection接口
    • List 接口
      • ArrayList
      • LinkedList
      • Vector
    • Set接口
      • HashSet
      • TreeSet
  • Map 接口
    • HashMap
    • TreeMap
    • HashTable

# ArrayList扩容机制

ArrayList的扩容主要发生在向ArrayList集合中添加元素的时候。当添加元素时，如果元素个数+1> 当前数组长度，就会进行扩容。扩容后的数组大小是原来的1.5倍，即 oldCapacity + (oldCapacity >> 1)。将旧数组内容通过Arrays.copyOf全部复制到新数组，此时新旧列表的size大小相同，但elementData的长度即容量不同。

举个例子，当我们创建一个无参的ArrayList对象时，底层是一个空数组。当添加第一个元素时，会进行扩容，将底层数组长度扩为10。扩容触发的条件是：存元素时，先让size+1的值判断是否大于底层elementData.length的长度，如果大于，则先扩容再添加。

# 快速失败与安全失败

快速失败（fail-fast）和安全失败（fail-safe）是Java集合中的两种机制。

快速失败机制是指在使用迭代器对集合对象进行遍历的时候，如果A线程对集合进行遍历，正好B线程对集合进行修改（增加、删除、修改），则A线程会抛出ConcurrentModificationException异常。这是因为迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext ()/next ()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。

安全失败机制是指采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，故不会抛 ConcurrentModificationException 异常。

# 为什么ArrayList不是安全的

ArrayList不是线程安全的，因为它的方法没有进行同步。这意味着如果多个线程同时访问一个ArrayList实例，并且至少有一个线程修改了列表结构，那么它必须在外部进行同步。否则，可能会导致不可预测的结果。

下面是一个简单的例子，演示了当多个线程同时访问一个ArrayList实例时可能会发生什么：

import java.util.ArrayList;
import java.util.List;

public class ArrayListExample {
    public static void main(String[] args) throws InterruptedException {
        List<Integer> numbers = new ArrayList<>();
        // 创建两个线程同时向列表中添加元素
        Thread thread1 = new Thread(() -> {
            for (int i = 0; i < 1000; i++) {
                numbers.add(i);
            }
        });
        Thread thread2 = new Thread(() -> {
            for (int i = 1000; i < 2000; i++) {
                numbers.add(i);
            }
        });
        // 启动两个线程
        thread1.start();
        thread2.start();
        // 等待两个线程执行完毕
        thread1.join();
        thread2.join();
        // 打印列表大小
        System.out.println(numbers.size());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

上面的代码中，我们创建了一个ArrayList并启动了两个线程同时向列表中添加元素。理论上，当两个线程都执行完毕后，列表的大小应该是2000。但实际上，当我们运行这段代码时，可能会发现列表的大小小于2000。这是因为两个线程同时修改了列表结构，导致其中一些添加操作丢失。

# 有哪几种实现ArrayList线程安全的方法

ArrayList不是线程安全的。如果多个线程同时访问一个ArrayList实例，并且至少有一个线程从结构上修改了列表，那么它必须在外部进行同步。这通常是通过对自然封装该列表的对象进行同步来完成的。

如果不存在这样的对象，则应使用Collections.synchronizedList方法来“包装”该列表。最好在创建时完成此操作，以防止意外的非同步访问：

List list = Collections.synchronizedList(new ArrayList(...));
1

这样返回的列表就是线程安全的。需要注意的是，迭代这个列表仍然需要手动同步，因为迭代过程中可能会发生意外的并发修改。

synchronized (list) {
    Iterator i = list.iterator();
    while (i.hasNext()) {
        // do something
    }
}
1
2
3
4
5
6

除了使用Collections.synchronizedList方法外，还可以使用并发集合类CopyOnWriteArrayList，它是一个线程安全的ArrayList变体，它在写入时复制底层数组。这种方法在读操作远多于写操作的场景中效果很好。

# CopyOnWriteArrayList怎么保证线程安全

CopyOnWriteArrayList是一个线程安全的ArrayList变体，它通过在写入时复制底层数组来实现线程安全。这意味着当我们向列表中添加、删除或修改元素时，它都会创建底层数组的一个新副本，然后在新副本上进行修改。这样，读取操作就不会被阻塞，因为它们总是在原始数组上进行。

由于CopyOnWriteArrayList在写入时复制底层数组，所以写入操作的开销比较大。但是，读取操作非常快，因为它们不需要同步。这使得CopyOnWriteArrayList在读操作远多于写操作的场景中表现很好。

下面是一个简单的例子，演示了如何使用CopyOnWriteArrayList：

import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

public class CopyOnWriteArrayListExample {
    public static void main(String[] args) {
        List<Integer> numbers = new CopyOnWriteArrayList<>();
        numbers.add(1);
        numbers.add(2);
        numbers.add(3);

        // 使用迭代器遍历列表
        for (Integer number : numbers) {
            System.out.println(number);
            // 在迭代过程中修改列表
            if (number == 2) {
                numbers.remove(number);
            }
        }

        // 再次遍历列表
        for (Integer number : numbers) {
            System.out.println(number);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

上面的代码中，我们创建了一个CopyOnWriteArrayList并添加了一些元素。然后我们使用迭代器遍历这个列表。在遍历过程中，当遇到元素2时，我们尝试从列表中删除它。由于CopyOnWriteArrayList在写入时复制底层数组，所以这不会影响我们的迭代过程。当我们再次遍历列表时，可以看到元素2已经被删除。

# Map

# HashMap的数据结构

在Java 8之前，HashMap内部使用了一个数组和链表来存储键值对。数组中的每个元素都是一个桶，每个桶都包含一个链表，用于存储具有相同哈希值的键值对。当我们向HashMap中添加一个键值对时，它会根据键的哈希值来确定应该将其存储在哪个桶中。如果该桶中已经有了具有相同哈希值的键值对，则会将新的键值对添加到该桶的链表中。

在Java 8中，HashMap的实现进行了优化。当链表长度超过一定阈值时，它会将链表转换为红黑树，以提高查找效率。

  • 如果链表长度>8 && 数组大小>=64，链表转为红黑树
  • 如果红黑树节点个数<6 ，转为链表

下面是一个简单的例子，演示了如何使用HashMap：

import java.util.HashMap;
import java.util.Map;

public class HashMapExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("one", 1);
        map.put("two", 2);
        map.put("three", 3);

        System.out.println(map.get("one"));
        System.out.println(map.get("two"));
        System.out.println(map.get("three"));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

上面的代码中，我们创建了一个HashMap并添加了一些键值对。然后我们使用get方法从HashMap中检索键值对。由于HashMap提供了快速的键值检索，所以这些操作都非常快。

# HashMap 扩容机制

是的，HashMap也有扩容的机制。当HashMap中存储的键值对数量超过了数组长度和负载因子的乘积时，它会自动进行扩容。

负载因子是一个介于0和1之间的浮点数，它表示了HashMap在进行扩容之前可以容忍的最大填充程度。默认情况下，负载因子为0.75，这意味着当HashMap中存储的键值对数量超过了数组长度的75%时，它就会自动进行扩容。

在扩容过程中，HashMap会创建一个新的数组，长度为原数组的两倍。然后它会将原数组中的所有键值对重新哈希到新数组中。这个过程可能会比较耗时，因为它需要重新计算所有键值对的哈希值并将它们重新插入到新数组中。

下面是一个简单的例子，演示了如何使用HashMap：

import java.util.HashMap;
import java.util.Map;

public class HashMapExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < 12; i++) {
            map.put("key" + i, i);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11

上面的代码中，我们创建了一个HashMap并向其中添加了12个键值对。由于默认情况下HashMap的初始容量为16，负载因子为0.75，所以当我们添加第9个键值对时，HashMap会自动进行扩容。

# HashMap 的底层原理

HashMap 是一个基于哈希表实现的 Map 接口。它的底层数据结构是一个数组，每个数组元素都是一个链表或红黑树，用于解决哈希冲突。

当您向 HashMap 中添加一个键值对时，它会使用键的哈希值来确定该键值对应该存储在数组的哪个位置。如果该位置已经有其他键值对，则会在该位置形成一个链表。当链表长度大于等于8并且数组长度超过64时，链表会转换为红黑树以提高查找效率。

# 链表是怎么插入元素的

在 JDK 1.7 中，HashMap 使用头插法来插入新节点。但是，在 JDK 1.8 中，HashMap 改为使用尾插法来插入新节点。

这种改变是为了解决在 JDK 1.7 中 HashMap 在扩容时可能出现的链表成环问题。在 JDK 1.7 中，由于使用头插法，在扩容时可能会改变链表中节点的相对顺序，从而导致链表成环。而在 JDK 1.8 中，由于使用尾插法，扩容时不会改变链表中节点的相对顺序，因此不会出现链表成环的问题。

在 JDK 1.7 中，HashMap 使用头插法来插入新节点。这种方法在扩容时可能会改变链表中节点的相对顺序，从而导致链表成环。

当 HashMap 需要扩容时，它会创建一个新的数组，并将旧数组中的所有元素重新插入到新数组中。由于使用头插法，每次插入新节点时都会将其插入到链表的头部，这会改变链表中节点的相对顺序。如果在扩容过程中，两个相邻的节点被分配到了同一个位置，则它们的相对顺序会发生改变，从而导致链表成环。

# 红黑树的插入、删除、查找的最坏时间复杂度都为 O(logn)

红黑树是一种自平衡的二叉搜索树，它能够保证在最坏情况下查找、插入和删除操作的时间复杂度都是O(log n)。

红黑树的查找操作与普通的二叉搜索树相同，时间复杂度取决于树的高度。由于红黑树是一种自平衡的二叉搜索树，它能够保证树的高度始终保持在O(log n)的数量级，因此查找操作的时间复杂度也是O(log n)。

红黑树的插入和删除操作比较复杂，因为它们需要维护红黑树的性质。当我们向红黑树中插入或删除一个节点时，它会通过旋转和重新着色来调整树的结构，以保证树仍然满足红黑树的性质。由于这些调整操作的时间复杂度都是O(1)，而最多需要进行O(log n)次调整，所以插入和删除操作的时间复杂度也是O(log n)。

# 红黑树的了解，为什么不用二叉树/平衡树？

红黑树是一种自平衡的二叉搜索树，它通过旋转和重新着色来维护树的平衡。与平衡二叉树（如AVL树）相比，红黑树在插入和删除操作时需要进行的旋转次数通常更少，代价更小。

这是因为红黑树对平衡的要求没有平衡二叉树那么严格。平衡二叉树要求任意节点的左右子树高度差不能超过1，而红黑树只要求从任意节点到其每个叶子节点的所有简单路径上的黑色节点数相同。这意味着红黑树能够容忍更多的不平衡情况，因此在插入和删除操作时需要进行的旋转次数也更少。

下面是一个简单的例子，演示了红黑树和AVL树在插入操作时需要进行的旋转次数：

import java.util.TreeMap;
import java.util.TreeSet;

public class RedBlackTreeExample {
    public static void main(String[] args) {
        // 创建一个红黑树
        TreeMap<Integer, Integer> treeMap = new TreeMap<>();
        // 向红黑树中添加元素
        for (int i = 0; i < 7; i++) {
            treeMap.put(i, i);
        }

        // 创建一个AVL树
        TreeSet<Integer> treeSet = new TreeSet<>();
        // 向AVL树中添加元素
        for (int i = 0; i < 7; i++) {
            treeSet.add(i);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

上面的代码中，我们创建了一个红黑树和一个AVL树，并向它们中分别添加了7个元素。由于这些元素是按顺序添加的，所以如果不进行旋转，它们会形成一条链。

在向红黑树中添加元素时，它只需要进行2次旋转就能保持平衡。而在向AVL树中添加元素时，它需要进行3次旋转才能保持平衡。

当然，这只是一个简单的例子，并不能完全代表所有情况。但它说明了红黑树在插入操作时通常需要进行更少的旋转。

# Hash函数的设计为什么可以降低碰撞

HashMap使用的哈希函数是通过对键的哈希码进行再哈希来设计的，它能够有效地降低哈希冲突的概率。

在Java中，每个对象都有一个哈希码，它是由对象的hashCode方法返回的一个整数。HashMap使用这个哈希码来计算键在数组中的位置。但是，直接使用对象的哈希码可能会导致哈希冲突，因为不同的对象可能具有相同的哈希码。

为了降低哈希冲突的概率，HashMap对键的哈希码进行了再哈希。具体来说，它会将键的哈希码与它自身右移16位后的值进行异或运算，然后再使用这个结果来计算键在数组中的位置。这样做能够有效地打乱键的哈希码，使得即使原始的哈希码分布不均匀，再哈希后也能得到较为均匀的分布。

下面是HashMap中计算键在数组中位置的代码：

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

static int indexFor(int h, int length) {
    return h & (length-1);
}
1
2
3
4
5
6
7
8

上面的代码中，hash方法用于对键进行再哈希，它会将键的哈希码与它自身右移16位后的值进行异或运算。indexFor方法用于根据再哈希后的值计算键在数组中的位置，它会将再哈希后的值与数组长度减1进行按位与运算。

通过这种方式，HashMap能够有效地降低哈希冲突的概率，提高查找效率。

# 解决hash冲突的方法

  • 链地址法：在冲突的位置拉一个链表，把冲突的元素放进去。
  • 开放定址法：开放定址法就是从冲突的位置再接着往下找，给冲突元素找个空位。
    • 线行探测法: 从冲突的位置开始，依次判断下一个位置是否空闲，直至找到空闲位置
    • 平方探测法: 从冲突的位置x开始，第一次增加1^2个位置，第二次增加2^2…，直至找到空闲的位置

# 阈值为什么是8

在Java 8中，当HashMap中的链表长度超过一定阈值（默认为8）时，它会将链表转换为红黑树。这个阈值是经过实验和测试确定的，它能够在保证性能的同时避免过多的空间浪费。

当链表长度较短时，使用链表进行查找的效率并不比红黑树差。但是，当链表长度超过一定阈值时，使用红黑树进行查找的效率会更高。因此，将链表转换为红黑树能够提高查找效率。

但是，红黑树需要更多的空间来存储节点之间的关系。如果我们将链表长度较短的链表也转换为红黑树，那么就会浪费大量的空间。因此，我们需要确定一个合适的阈值，使得当链表长度超过这个阈值时才将其转换为红黑树。

经过实验和测试，Java开发团队确定了这个阈值为8。这意味着当链表长度超过8时，HashMap会将其转换为红黑树。这个阈值能够在保证性能的同时避免过多的空间浪费。

# 为什么负载因子为0.75

负载因子是一个介于0和1之间的浮点数，它表示了HashMap在进行扩容之前可以容忍的最大填充程度。默认情况下，负载因子为0.75，这意味着当HashMap中存储的键值对数量超过了数组长度的75%时，它就会自动进行扩容。

负载因子的值会影响HashMap的性能和空间利用率。如果负载因子过小，那么HashMap会频繁进行扩容，这会导致性能下降。如果负载因子过大，那么HashMap中的哈希冲突会增多，这也会导致性能下降。

经过实验和测试，Java开发团队确定了默认的负载因子为0.75。这个值能够在保证性能的同时避免过多的空间浪费。

当然，根据具体应用场景的不同，我们也可以手动指定负载因子的值。例如，如果我们知道HashMap中要存储大量的键值对，那么我们可以指定一个较大的初始容量和一个较小的负载因子，以减少扩容次数和哈希冲突。

# HashMap为什么不是线程安全的

# ConcurrentHashMap为什么从分段锁变为CAS+synchronized锁

ConcurrentHashMap是Java中一种线程安全的哈希表实现，它能够在高并发环境下提供良好的性能。在Java 7及更早版本中，ConcurrentHashMap使用分段锁来实现线程安全。但是，在Java 8中，ConcurrentHashMap的内部实现发生了变化，它不再使用分段锁，而是使用CAS和synchronized来实现线程安全。

在 JDK 1.7 及之前，ConcurrentHashMap 使用分段锁（Segment）来保证线程安全。每个段都是一个独立的哈希表，只包含总容量的一部分，每个段都有自己的锁，因此不同的线程可以同时访问不同的段。这种方法在高并发场景下表现良好，但由于锁的开销和段的数量限制，它的性能随着并发度的增加而下降。

在 JDK 1.8 中，ConcurrentHashMap 改为使用 CAS（Compare And Swap）和 synchronized 来保证线程安全。这种实现方式被称为“数组+链表+红黑树”，即每个桶内部采用链表或红黑树来存储键值对，当桶内键值对数量达到一定阈值时，链表会自动转化为红黑树，以提高查找效率。每个桶内部都通过 synchronized 来实现同步，以保证线程安全性。而对于读操作，使用了无锁的 CAS 操作。

相比于分段锁，这种实现方式有以下优点：

  • 减少锁竞争：由于每个桶内部采用了 synchronized 来实现同步，不同的线程可以同时访问不同的桶，从而减少了锁竞争。
  • 更高的并发度：由于不再受限于固定数量的段，ConcurrentHashMap 可以根据需要动态调整大小，并支持更高的并发度。
  • 更好的扩展性：由于不再需要维护多个段的锁，因此在扩展时可以更容易地添加或删除桶，而不需要重构整个数据结构。
  • 更好的性能：使用 CAS 操作替代了分段锁，避免了分段锁中的自旋等待开销，提高了并发性能。

总之，在 JDK 1.8 中，ConcurrentHashMap 放弃了分段锁，采用了 CAS 和 synchronized 的方式来实现更好的并发性能。这样，在保证线程安全的同时，还能够提供更高的并发性能。

# treeMap如何实现排序的

TreeMap是Java中一种基于红黑树的有序映射实现，它能够按照键的自然顺序或者指定的比较器来排序键值对。

TreeMap是如何实现有序的呢？主要有以下两个方面：

  1. 使用红黑树作为底层数据结构：红黑树是一种自平衡的二叉搜索树，它能够保证在最坏情况下查找、插入和删除操作的时间复杂度都是O(log n)。由于红黑树是一种二叉搜索树，它能够按照键的大小顺序来存储键值对。这样，当我们遍历红黑树时，就能够按照键的有序顺序来访问键值对。

  2. 使用比较器或者可比较接口来比较键的大小：当我们向TreeMap中添加一个键值对时，它会根据键的大小来确定其在红黑树中的位置。为了比较键的大小，TreeMap可以使用两种方式：一种是使用键的自然顺序，即键必须实现Comparable接口，并且提供compareTo方法来定义其大小关系；另一种是使用指定的比较器，即在创建TreeMap时传入一个Comparator对象，并且提供compare方法来定义其大小关系。无论使用哪种方式，TreeMap都能够按照键的有序顺序来排序键值对。

下面是一个简单的例子，演示了如何使用TreeMap：

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {
        // 创建一个TreeMap，使用键的自然顺序
        Map<String, Integer> map1 = new TreeMap<>();
        map1.put("one", 1);
        map1.put("two", 2);
        map1.put("three", 3);

        // 遍历map1，按照键的字典顺序输出
        for (Map.Entry<String, Integer> entry : map1.entrySet()) {
            System.out.println(entry.getKey() + " = " + entry.getValue());
        }

        // 创建一个TreeMap，使用指定的比较器
        Map<String, Integer> map2 = new TreeMap<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                // 按照字符串长度比较
                return o1.length() - o2.length();
            }
        });
        map2.put("one", 1);
        map2.put("two", 2);
        map2.put("three", 3);

        // 遍历map2，按照字符串长度顺序输出
        for (Map.Entry<String, Integer> entry : map2.entrySet()) {
            System.out.println(entry.getKey() + " = " + entry.getValue());
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

上面的代码中，我们创建了两个TreeMap，并向它们中分别添加了一些键值对。第一个TreeMap使用了键的自然顺序，即字符串的字典顺序。第二个TreeMap使用了指定的比较器，即按照字符串长度来比较。当我们遍历这两个TreeMap时，可以看到它们都能够按照键的有序顺序来输出键值对。

# Set与Map之间的区别

Set和Map是Java中两种不同的集合类型，它们之间有一些重要的区别。

  • 存储内容不同：Set是一种集合，它用于存储一组不重复的元素。Map是一种映射，它用于存储一组键值对，其中键是唯一的。

  • 数据结构不同：Set和Map通常使用不同的数据结构来实现。例如，HashSet使用哈希表来存储元素，而TreeSet使用红黑树来存储元素。HashMap使用哈希表来存储键值对，而TreeMap使用红黑树来存储键值对。

  • 常用方法不同：Set和Map提供了不同的方法来操作集合。例如，Set提供了add、remove和contains等方法来添加、删除和查找元素。Map提供了put、get和remove等方法来添加、查找和删除键值对。

下面是一个简单的例子，演示了如何使用Set和Map：

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class SetAndMapExample {
    public static void main(String[] args) {
        // 创建一个Set并添加元素
        Set<String> set = new HashSet<>();
        set.add("one");
        set.add("two");
        set.add("three");

        // 遍历Set
        for (String s : set) {
            System.out.println(s);
        }

        // 创建一个Map并添加键值对
        Map<String, Integer> map = new HashMap<>();
        map.put("one", 1);
        map.put("two", 2);
        map.put("three", 3);

        // 遍历Map
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " = " + entry.getValue());
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

上面的代码中，我们创建了一个Set和一个Map，并向它们中分别添加了一些元素。然后我们遍历这两个集合，可以看到它们分别存储了不重复的元素和唯一的键值对。

java基础
并发编程

← 并发编程→

最近更新
01
实习技术
08-24
02
sql
07-28
03
git命令
07-26
更多文章>
Theme by Vdoing | Copyright © 2019-2023 Evan Xu | MIT License