Java集合知识点思维笔记模板_ProcessOn思维导图、流程图

Stack

代表了栈这种数据结构，继承自Vector

所以Stack是一种基于数组来实现的栈数据结构

Vector

Vector是一种类似于ArrayList（基于数组来实现的）数据结构，有序的集合

每次扩容默认是2倍

LinkedHashMap

HashMap，LinkedHashMap，TreeMap区别

遍历HashMap，遍历的顺序，不是按照你插入的key-value的顺序来的。

遍历LinkedHashMap，是按照插入key-value对的顺序遍历出来的。

LinkedHashMap底层是基于链表来实现的，TreeMap是基于红黑树来实现顺序的

关键属性

final boolean accessOrder;

默认false，get一个key，或者是覆盖这个key的值，都不会改变他在链表里的顺序

是true的话，get一个key，或者是覆盖这个key的值，就会导致个key-value对顺序会在链表里改变，他会被挪动到链表的尾部去

特点

基于HashMap实现

TreeMap

特点

基于Map实现，底层基于红黑树，可以按照key的自然顺序来排序，和遍历。

static final class Entry<K,V> implements Map.Entry<K,V> {         K key;         V value;         Entry<K,V> left;         Entry<K,V> right;         Entry<K,V> parent;         boolean color = BLACK; }

HashSet

特点

Set都是直接基于Map来实现的，比如说HashSet就是基于HashMap来实现的，只有key是有值的，value都是null值，都是空的

里面的元素是无序的，没有重复的。

底层是有数组的，你可以在构造HashSet的时候就传入数组的大小，避免扩容的问题

LinkedHashSet

特点

底层基于LinkedHashMap实现，有顺序的set，迭代LinkedHashSet的顺序跟你插入的顺序是一样的

LinkedHashSet.add()方法，底层会调用LinkedHashMap.put()方法，记住加入元素的顺序。遍历的时候，是从LinkedHashMap里遍历元素，直接遍历维护好的链表的。

TreeSet

底层基于TreeMap来实现，默认根据插入元素的值排序的，而且可以定制Comparator，自己决定排序的算法和逻辑

fail-fast机制

定义

java集合中，迭代器在迭代的时候，会发生ConcurrentModificationException并发修改的异常，这个机制就叫做fail fast

原理

modCount实现fail fast机制，各个集合都有这个modCount的概念，只要这个集合被修改了，那么就会对modCount++

modificationCount，修改次数，只要修改一次，就会更新这个，add、remove、set

获取和初始化一个迭代器的时候，里面的expectedModCount就会被初始化为modCount，然后就不会变了

迭代过程中，对集合进行add，remove等操作，expectedModCount!=modCount了，这时就会扔出ConcurrentModificationException()并发修改冲突异常。

java集合包下的类，都是非线程安全的，所以针对并发修改集合的问题设计了fail fast机制

ArrayList

特点

查找数据快

基于数组实现，直接根据内存地址定位某个元素，随机读性能很高。

插入数据慢

数组来实现的话，要是往数组中间加一个元素，要把新增元素后面的元素全部往后面挪动一位，所以性能比较差

数组扩容的时候，会用老的大小 + 老的大小 >> 1（相当于除以2），也就是扩容大小1.5倍，再进行数组的拷贝。

所以不要频繁的往arraylist里头塞数据，导致频繁的数组扩容，避免扩容的时候，较差的性能影响了系统运行。

使用

默认构造函数会给数组一个默认初始大小10，创建的时候，最好给一个合理的初始化的数组的大小

LinkedList

特点

查找数据慢

基于双向链表实现，需要从头开始遍历链表获取元素。

源码实现

底层是一个双向队列的数据结构

如果数据在队列前半部分，从头开始遍历，在后半部分，从后开始遍历。

插入数据快

插入数据只需要挪动指针，不需要进行扩容和元素拷贝，速度很快。

HashMap

特点

JDK1.8以前

数组+链表

时间复杂度O(n)

JDK1.8以后

数组+链表+红黑树

时间复杂度在树化前是O(n)，树化之后是O(logN)

常用属性源码解析

数组

transient Node<K,V>[] table;

数组的元素是Node类型的，可组成单向链表。

数组中节点

static class Node<K,V> implements Map.Entry<K,V> {         final int hash;         final K key;         V value;         Node<K,V> next; }

代表了一个key-value对

包含了key的hash值

有一个next的指针，指向下一个Node

子主题

大小

transient int size;

有多少个key-value对

数组默认初始容量

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

负载因子（扩容用）

static final float DEFAULT_LOAD_FACTOR = 0.75f;

默认的负载因子，如果你在数组里的元素的个数达到了数组大小（16） * 负载因子（0.75f），默认是达到12个元素，就会进行数组的扩容

扩容阈值

int threshold;

capacity(默认数组的大小) * loadFactory

如果size达到threshold就开始扩容

源码实现

数据设置

过程描述

对key，进行hashCode()运算，得到hash值

再用hash值对数组的长度进行取模，根据取模结果，将key-value对方在数组中的某个元素上

源码解析

获得key的hash值

hash(key)

public V put(K key, V value) {         return putVal(hash(key), key, value, false, true); }

对key进行hash获取对应的hash值，key、value传入到putVal()方法里面去，将key-value对儿根据其hash值找到对应的数组位置

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

通过hashCode()方法，直接获取hash值。

把32位的二进制的hash值，所有的bit往右侧右移了16位

将他的高16位和低16位进行一个异或运算，同时保留高16位和低16位的特征，减少hash冲突。

对hash值进行取模运算

(n - 1) & hash

&与操作，来实现取模的效果，位运算，性能很高

数组默认初始length，以及未来每次扩容的值，都是2的n次方，保证hash % 数组.length取模的一样的效果

hash冲突

问题描述

hash值一样会导致他们放到同一个数组的索引的位置上去

或者多个key的hash值不一样，但对一个数组的length取模，获取到的这个数组的index位置，是一样的。

导致多个元素挂在数组同一索引位置上，成一个链表。

大量hash冲突会导致性能从O(1)变成O(n)

解决方法

JDK 1.8优化了HashMap的数据结构，如果一个链表长度超过8，会自动将链表转换为红黑树，查找性能，是O(logn)。

拓展知识

红黑树特性

红黑树是二叉查找树，左小右大，根据这个规则可以快速查找某个值

普通的二叉查找树，可能会出现不平衡的情况，导致查询性能变成O(n)，线性查询。

红黑树，红色和黑色两种节点，有很多条件限制，尽可能保证树是平衡的

如果插入节点的时候破坏了红黑树的规则和平衡，会自动重新平衡，变色（红 <-> 黑），旋转，左旋转，右旋转

数据扩容

2倍扩容 + rehash

newCap = oldCap << 1

JDK 1.8以后，扩容一定是2的倍数。

每个key-value对，都会基于key的hash值重新寻址找到新数组的新的位置

很多key在新数组的位置都不一样了，如果是之前冲突的这个key可能就会在新的数组里分布在不同的位置上了。

如果是一个链表里的元素的话，那么要么是直接放在新数组的原来的那个index，要么就是原来的index + oldCap