Java集合

集合

java集合树

List与Set的区别

1.List、Set都继承自Collection接口；List的特点：元素有放入顺序，且可重复；Set的特点：元素无放入顺序，且不可重复（注意：元素虽然无放入顺序，但是元素在Set中的位置是由该元素的HashCode决定的，其位置是固定的）。List支持for循环，也就是通过下标来遍历，也可以用迭代器，但是Set只能用迭代器，因为他无序，无法使用下标取值；

    public static void main(String[] args) {
        Set<String> stringSet = new HashSet<>();
        stringSet.add("test1");
        stringSet.add("test2");
        stringSet.add("test3");
        stringSet.add("test1");
        //打印结果：[test2, test3, test1]
        System.out.println(stringSet);

        List<String> list = new ArrayList<>();
        list.add("item1");
        list.add("item2");
        list.add("item3");
        list.add("item1");
        //打印结果：[item1, item2, item3, item1]
        System.out.println(list);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.List接口有三个实现类：LinkedList,ArrayList,Vector。Set接口有两个实现类：HashSet（底层由HashMap实现），LinkedHashSet

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

Map

Map是一个非常复杂的集合，是通过某个键key来访问元素的。

哈希算法

hash算法有6种

1. 加法Hash；

2. 位运算Hash；

3. 乘法Hash；

4. 除法Hash；

5. 查表Hash；

6. 混合Hash。

Hash冲突

在哈希表中，不同的关键字值对应到同一个存储位置的现象。即两个不同对象的HashCode相同，这种现象称为hash冲突。

解决碰撞的方法

1.拉链法（hashmap使用该方法）

对于相同的哈希值，使用链表进行连接。（HashMap使用此法）

2.再哈希法

提供多个哈希函数，如果第一个哈希函数计算出来的key的哈希值冲突了，则使用第二个哈希函数计算key的哈希值。

3.建立公共溢出区

将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

4.开放定址法

当关键字key的哈希地址p =H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，若p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。

HashMap和HashTable区别

1. hashmap将null作为key或者value，而hashtable不行
2. hashmap线程不安全，hashtable线程安全

fail-fast和fail-safe

fail-fast：在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出 Concurrent Modification Exception。

java.util 包下的集合类都是快速失败的。

fail-safe：在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则不会抛出 Concurrent Modification Exception。fail-safe的原理是对集合的修改都是先拷贝一份副本。

java.util.concurrent包下的容器都是fail-safe，

Copy-On-Write

CopyOnWrite容器是一种读写分离的思想。读和写是不同的容器。

写时加锁复制，读时不加锁不复制。

避免fail-fast的方法

1.普通for循环

public void listRemove() {
    List < Student > students = this.getStudents();
    for (int i = 0; i < students.size(); i++) {
        if (students.get(i).getId() % 3 == 0) {
            Student student = students.get(i);
            students.remove(student);
        }
    }
}
1
2
3
4
5
6
7
8
9

2.使用迭代器循环

public void iteratorRemove() {
    List < Student > students = this.getStudents();
    Iterator < Student > stuIter = students.iterator();
    while (stuIter.hasNext()) {
        Student student = stuIter.next();
        if (student.getId() % 2 == 0) {
            //这里要使用Iterator的remove方法移除当前对象，如果使用List的remove方法，则同样会出现	ConcurrentModificationException 
            stuIter.remove();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11

3.copy一份副本

public void copyRemove() { 
  // 注意，这种方法的equals需要重写 
  List<Student> students = this.getStudents(); 
  List<Student> studentsCopy = deepclone(students); 
    for (Student stu: students) {
        if (needDel(stu)) {
            studentsCopy.remove(stu);
        }
    }
}
1
2
3
4
5
6
7
8
9
10

4.使用并发集合

public void cowRemove() {
    List <String> students = new CopyOnWriteArrayList <> (this.getStudents());
    for (Student stu: students) {
        if (needDel(stu)) {
            studentsCopy.remove(stu);
        }
    }
}
1
2
3
4
5
6
7
8

5.使用stream

stream会创建新的流出来，所以不用关系元对象的新增和修改。

public List <String> streamRemove() {
    List<String> students = this.getStudents();
    return students.stream().filter(this::needDel).collect(Collectors.toList());
}
1
2
3
4

HashMap的扩容

初始化容量为16，达到阈值进行扩容。阈值 = 最大容量 * 负载因子(0.75)，扩容每次2倍，总是2的n次方。

扩容机制：使用一个容量更大的数组替代已有的容量小的数组，transfer()方法将原有的Entry数组的元素拷贝到新的Entry数组里。

负载因子为什么是0.75

0.75是一个经验值。在0.75是时间和空间成本之间做的权衡考虑。太小会导致频繁的扩容，增加空间成本；太大，会导致哈希冲突，增加时间成本。

而且，由于hashmap容量是2的幂次方，为了保证阈值 = 最大容量 * 负载因子结果是整数，设置为0.75比较合理。

为什么JDK8中HashMap要转成红黑树？

这是因为当链表长度过长时，在查找、插入等操作上效率会变得很低。而使用红黑树可以保证这些操作的时间复杂度始终为O(log n)，从而提高了HashMap在处理大量数据时的性能。

另外，由于红黑树相比链表需要更多空间来存储额外信息（如颜色、父节点等），所以只有当桶中元素数量较多时才进行转换，避免浪费空间。

当链表长度是8时，转成红黑树；当红黑树大小是6时，转回链表。

CurrentHashMap

使用分段锁保证线程安全。

默认情况下将hash表分为16个分片，在加锁的时候，针对每个单独的分片进行加锁，其他分片不受影响。锁粒度更细，所以性能更好。

ArrayList中subList的作用

ArrayList创建子列表的主要目的是为了方便对原始列表中指定范围内元素进行操作。通过使用subList()方法，我们可以轻松地获取到一个新的视图，而不需要复制整个列表。

这种方式有以下几个优点：

1. 节省空间：如果我们只需要处理原始数组中一部分元素，那么将整个数组复制到一个新数组中会浪费大量空间。使用子列表可以避免这种情况发生。

2. 方便操作：在某些情况下，我们可能只需要处理原始数组中一部分元素。例如，在搜索、排序或过滤数据时，仅需处理特定范围内的数据即可。使用子列表可以使这些操作更加简单和高效。

3. 保持同步：由于子列表是基于原始ArrayList创建的视图，因此它们与原始ArrayList之间存在关联性。也就是说，在修改子列表时会影响到原来的ArrayList，并且反之亦然。这样做可以确保两者之间保持同步。

总之，创建一个sublist能够让我们更加灵活地操作ArrayList，并且提高代码效率和可读性。

如何将集合变成线程安全？

1. 使用synchronized或者ReentranLock加锁。

2. 使用ThreadLocal，将集合放到线程类访问。

3. 使用Collections.synchronizedXXX()。

4. 使用并发容器。