秋招Java后端开发冲刺——基础篇5（String&集合）

一、String

1. String类是Java中字符串操作类，位于java.lang包下
2. String类型对象的底层使用字符数组char[]存储字符串，由final修饰且没有提供公共的修改方法，因此String对象是不可变的。
3. 常见方法

4. String、StringBuilder、StringBuffer

• 联系：三者都是对字符串进行操作的类
• 区别

5. 字符串常量池

• 是为了重复利用字符串字面量在JVM 中开辟的一个内存区域（堆中）
• final 关键字修饰之后的 String 会被编译器当做常量来处理

二、Java集合

（一）集合介绍
1. 框架结构
Java中集合主要是由两大接口派生而来：一个是 Collection接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。其框架结构如图所示：

2. 集合和数组

（二）实现Collection接口的集合

1. ArrayList
（1）介绍

• ArrayList是用于顺序存储元素的集合，其存储的值可以重复。
• ArrayList是非线程安全的。
  （2）常用方法

其添加、删除元素的时间复杂度均为O（n），查找元素的时间复杂度为O（1）。
（3）底层数据结构

• ArrayList 底层是一个动态数组，默认初始容量为 10。（Java7之后懒加载）
• 扩容因子：1.5。
• 扩容步骤：
  • 初始化时 elementData 为空数组。
  • 首次添加元素时，确保最小容量。
  • 当添加元素超出当前容量时，计算新的容量（1.5倍）。
  • 如果新的容量小于所需的最小容量，则调整为最小容量。
  • 如果新的容量超出最大数组大小，则进行特殊处理。
  • 使用 Arrays.copyOf 方法将旧数组内容复制到新数组。
• 扩容源码

// 默认初始容量
private static final int DEFAULT_CAPACITY = 10;

// 空数组实例，用于懒加载机制
private static final Object[] EMPTY_ELEMENTDATA = {};

// 实际存储元素的数组
transient Object[] elementData;

// ArrayList 的当前大小
private int size;
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

2. LinkedList
（1）介绍

• LinkedList是用于随机存储元素的集合，其存储的值可以重复。
• LinkedList是非线程安全的.

（2）常用方法

其添加、删除、查找元素的时间复杂度均为O（n）。

（3）底层数据结构

• LinkedList 底层使用的是双向链表（JDK1.6 之前为循环链表，JDK1.7 取消了循环）进行实现。

3. ArrayList、LinkedList、Vector之间的联系与区别

4. HashSet、LinkedHashSet 和 TreeSet的联系与区别

注：使用 Collections.synchronizedSet 方法可以创建一个线程安全的 Set 集合

Set<String> synchronizedSet = Collections.synchronizedSet(new HashSet<>());
1

5. Deque
（1）介绍

• Deque 是双端队列，在队列的两端均可以插入或删除元素。
• Deque 还提供pop（）和push（）方法用以实现栈（目前栈的实现方式）

（2）常用方法

（3）接口实现方式

• ArrayDeque：使用循环数组和双指针作为其底层数据结构。
• LinkedList :基于双向链表实现Deque。

6. PriorityQueue（力扣刷题常用）
（1）介绍

• PriorityQueue是优先级队列，是堆数据结构的主要实现方式，存在大根堆和小根堆（默认）两种。
• 大根堆：父节点的值大于等于其孩子节点的值

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a,b)->b-a);
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                // 实现大根堆的比较规则，返回负数表示 o1 比 o2 大（o1 在 o2 的前面）
                return o2.compareTo(o1);
            }
        });
1
2
3
4
5
6
7
8
9

• 小跟堆：父节点的值小于等于其孩子节点的值

PriorityQueue<Integer> maxHeap = new PriorityQueue<>();
1

• PriorityQueue是非线程安全的

（2）常用方法

（3）底层数据结构

• PriorityQueue 的底层数据结构通常采用的是二叉小顶堆（Binary Min-Heap）的数据结构，底层使用可变长的数组来存储数据。
• 二叉小顶堆：是一种完全二叉树，其中父节点的值小于或等于其任何一个子节点的值。

（三）实现Map接口的集合

1. HashMap
（1）介绍

• HashMap是基于哈希表的 Map 接口的实现，主要用于存储键值对类型数据。
• HashMap是线程不安全的
  注：HashMap的键和值都可以为NULL，但是键只能有一个为NULL，值可以多个

（2）常用函数

（3）底层数据结构

• HashMap使用的数据结构在Java8之前是：数组+链表，Java8之后是数组+链表+红黑树。
  注：当链表长度大于阈值（默认为 8）时，先判断当前数组的长度是否小于 64，小于的话选择先进行数组扩容，大于64时转换为红黑树；当红黑树的节点小于6的时候退化为链表（避免频繁的转换）。
• 初始容量为16，扩容因子0.75，2倍扩容。
• 扩容步骤：
  • 创建新数组：新的数组容量是原来数组容量的两倍
  • 重新计算哈希值：对于原来数组中的每个元素，根据新的数组容量重新计算其哈希值，从而确定其在新数组中的位置。
  • 迁移元素：将原来数组中的所有元素放到新数组中。
    注：这里不仅仅是简单地复制元素，而是需要根据新的哈希值重新分配位置。
• 扩容源码

// 在 HashMap 类中的 resize 方法
final Node<K,V>[] resize() {
    Node<K,V>[] oldTable = table;
    int oldCap = (oldTable == null) ? 0 : oldTable.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTable;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTable = (Node<K,V>[])new Node[newCap];
    table = newTable;
    if (oldTable != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTable[j]) != null) {
                oldTable[j] = null;
                if (e.next == null)
                    newTable[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTable, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTable[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTable[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTable;
}
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

（4）HashMap 的长度为什么是 2 的幂次方
向HashMap中添加元素时，需要通过计算元素的**（散列值%数组长度）来找到元素的存储位置，而当除数是2的幂次方（及数组长度为2的幂次方）时，求余的操作可以转换为&操作**，能够提高运算效率。

2. ConcurrentHashMap
（1）介绍
ConcurrentHashMap是通过加锁保证线程安全的HashMap。
注：ConcurrentHashMap 的 key 和 value 不能为 null （避免二义性）

（2）底层数据结构

• Java7之前的ConcurrentHashMap底层采用：分段的数组+链表，分段数组的长度一旦初始化就不能改变。
• Java8之后采用：数组+链表/红黑二叉树。

（3）锁机制

• Java7之前使用的是**分段锁（ReentrantLock锁）**保证线程安全
• Java8之后使用的是synchronized 和 CAS 来保证线程安全，通过CAS修改数组节点的值，然后synchronized 锁定当前链表或红黑二叉树的首节点。

3. HashMap、Hashtable、ConcurrentHashMap

（四）Collections 工具类常用方法（面试手撕算法）