1.collection体系原理与常用实现

1.1collection体系

collection就是一个接口
image.png

1.2collection方法

image.png
image.png

retainall

image.png

1.3list

image.png

new ArrayList(Collection)

image.png

ArrayList的第三种用法

new arraylist()可以不加参数，也可以加collection，第三种就是初始容量参数
image.png

ArrayList动态扩容(add方法解析)

在向arraylist中添加元素时，java要确保有空间能够容纳添加的元素

add方法首先调用了ensureCapacityInternal方法，传入的参数为size+1，首先确保有这么多容量。
image.png

ensurecapacityInternal方法调用了ensureExplicitCapacity方法，传入的参数又调用了calculateCapacity方法。
从ensurecapacityInternal这个方法的方法名可以知道，这个方法是用来确保明确的容量。
而calculateCapacity这个方法是计算容量的。
image.png

从calculateCapacity方法中，size+1是minCapacity，选取默认容量和size+1中较大的值作为minCapacity。
image.png

这里的minCapacity是所需要的最小容量，而elementData.length是当前的容量，意思就是当前容量小了，需要扩容，使用grow方法来扩容。
image.png

grow方法中的newCapacity是旧容量（当前元素的长度）+旧容量的一半（左移1位等于除以2），
并且最后一行新建了一个数组将旧的内容拷贝进去了。
image.png

1.4set

image.png

不能包含重复元素

image.png

自己实现简易set

image.png

hashcode

image.png
判断object是不是重复的：算出之前object的hashcode，将这个hashcode作为哈希桶的名字，将对应的object放到桶中。用名字来类比就是，姓张的全部放到一个叫张的桶中。那么要判断一个object是不是重复的，只要计算出它的hashcode，并到对应的桶中寻找是否有相同的object，这样不用一个一个对比，时间复杂度会很小。
image.png

hashset和list效率对比

image.png
image.png

hashset（hashset无序，linkedhashset有序）

image.png
image.png

2.map与常用实现

2.1map是一种从键到值的映射

map不能包含重复的键，每个键可以最多映射到一个值。

2.2map的常用方法

image.png

put

image.png
image.png

get

从map中根据key拿value
image.png

containsKey, containsValue

判断当前的map中是否包含某个key或value

keySet, values，entryset

image.png

image.png
image.png

keyset的坑

对map进行修改后，keyset()也同步会修改
2022-06-07.161735.png

hashmap

image.png

hashmap的key的set就是hashset
image.png

hashmap的扩容

和hashset一样，如果发现满了，就找一块更大的空间，将hashmap移过去

hashmap线程不安全性

image.png
在扩容的同时有多线程访问，可能会形成死循环的链表。
在多线程用concurrenthashmap来代替hashmap。

3.其他一些常用实现及原理

3.1有序集合treeset/ treemap(linkedhashset)

image.png

3.2collection工具方法

image.png

3.3collection其他实现

image.png

3.4guava

image.png