目录

Java中的集合分类

List

ArrayList实现原理

LinkedList

Vector

Iterator

Set

HashSet

Map

HashMap

并发容器ConcurrentHashMap

COW容器

队列

Java中的集合分类

List

ArrayList实现原理

java1.7 （数组初始化长度为10，扩容时乘以1.5倍）

1. ArrayList中含有两个元素，elementData（Object类型的数组）和Size（长度）
2. 在调用Arrylist的构造器时，会给elementData数组进行初始化，数组初始化长度为10。
3. 在调用add方法传递对象的时候，先调用方法ensurecapacityinteral判断是否需要将数组进行扩容，需要就将数组扩容调用grow方法，之后将元素赋值到数组的位置上，再对size进行+1操作。
4. 扩容（默认数组长度为10，每次扩容的时候都为原有长度的1.5倍，新建一个1.5倍的数组，把老数组的内容copy到新数组，把新数组指向elementData）。

Java1.8：（数组原本为空，调用add时才会扩容，新建数组长度为10）

1. 调用arraylist的构造器时，将其中的数组赋值为空数组。
2. 调用add方法后才会对数组进行扩容，调用时判断当前数组是否需要扩容，老数组默认为空，需要扩容时则新建一个长度为10的数组，将新数组copy给老数组。

LinkedList

1. LinkedList逻辑结构是由双向链表组成，物理结构是由跳转结构实现的一种链表结构的集合。
2. 在LinkedList中，分为一个个的node对象，也就是所谓的节点，节点对象中存储的有三个参数，前一个对象的地址，当前对象，最后一个对象的地址，以此来逐一指向当前节点的前面和后面的节点。
3. 在首次调用add方法传入参数时，会创建一个node节点存放传入的参数，同时将集合中的前一个节点和后一个节点都赋值为当前节点，在再次调用add方法时，会再次创建node节点，同时将前一个节点指向新添加的节点，将当前元素设置为最后一个元素，以此类推。
4. 在调用get（i）方法时，会对当前传入的int类型的参数做运算，判断这个索引是在集合的前半段还是后半段，如果是前半段，从第一个节点开始查找，如果是后半段，则从最后一个元素向前查找。

Vector

1. 有底层Object数组，int类型的长度。
2. 底层数组长度为10，每次需要扩容时，将数组扩容为2倍长度。
3. 线程安全，效率低，加了Sychorized关键字修饰。

Iterator

Arraylist方法中的Iterator方法：

1. Iterator中有两个方法，next和hasNext，有两个变量course（循环到哪个下标了）和lastRet（返回哪个下标）
2. 调用hasNext方法，会将course变量和当前集合的size对比，如果不一致则代表有下一个元素。

     3 调用next方法，会每次将course变量每次做加一操作，模拟指针，指向下一个下标的元素，之后将集合中的数组copy到方法内部，返回数组中第【lastRet】个元素。若要在循环时对集合进行操作，需要由迭代器完成。

Set

HashSet

        假设放入Integer，调用包装类的Hash方法，计算出放入值的的Hash值，再通过表达式和hash值计算在数组中存放的位置，放入时通过包装类的equals方法对比元素是否一致。若要放入自定义类型，需要重写自定义类型的hasCode方法和equals方法。

Map

HashMap

        在java7中，HashMap是由数组+链表的形式存储数据的，在java8中，HashMap是由数组+链表+红黑树形式存储数据的。

        在调用hashMap的put方法时，会先把当前的key传入到HashMap的hash方法之中，利用hashmap的hash算法，计算出一个值，这个值就是元素在数组中的位置，然后再把key和value存储在一个entry对象中，判断当前的数组中是否存在元素，若存在元素了，再判断当前key的原始值和存在元素的元素值，若一致则覆盖，不一致则将元素放入链表的尾部存储。

        同样的，在调用hashmao的get方法时，也会先利用hashmap的hash算法，将key传入，然后计算出元素的下标，去对应的数组位置中取元素，若当前的位置以链表的形式存储了很多元素，那么会挨个去链表中寻找hash计算后值相同并且equals后也相等的元素，此时会比较消耗时间，这个时候时间复杂度就会大大增加，所以java8引入了红黑树的存储方式，当链表大于一定长度时，会将现有的链表结构转化为红黑树结构存储数据，而这种转化又是十分耗时的操作,所以不能轻易转化，源码中有定义一个值：TREEIFY_THRESHOLD，也就是说链表的个数超过8个元素时，才会进行转化操作，至于为什么是8，通过源码的注释和搜索一些资料得知：这个值出现频率不能太高，所以源码设计者在设计时通过一系列的计算(泊松分布)得出，这个值是最合适的答案。

HashMap扩容：new的时候会遇到一个带参数的构造方法，initialCapacity代表初始容量，是数组的大小，loadFactor代表装载因子，是一个0-1之间的系数，默认0.75，当map中包含的Entry的数量大于等于threshold = 容量 * 装载因子 的时候，触发扩容机制，将其容量扩大为2倍，就是新建一个数组，将原有数组中的元素copy到新数组之中。

数组：常用的数据存储结构，是一串连续的储存单元。

链表：key、value形式储存数据的数据结构，在HashMap中存在一个node对象，里面由key和value以及next这三个元素，key、value代表键值对，next代表指的向下个元素。

红黑树：是一个平衡的二叉树的存储结构，所以效率比链表高。

特性 1. 每个节点或者是黑色，或者是红色。

2. 根节点是黑色。

3. 每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]

4. 如果一个节点是红色的，则它的子节点必须是黑色的。

5. 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。（确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。）

我个人的理解就是，红黑树就是一个平衡二叉树，在原来的二叉树结构上进行了着色、为了满足 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点的特性，从而增加了一些黑色为null的叶子节点，并且再每次的新增和删除时都会进行旋转和着色操作，以满足其特性。

然后再深入一点的知识，就说正在看一本书《算法导论》，这部分必须背：

红黑树的查找：查找这个效率高，因为是平衡的。

红黑树的添加操作：

添加步骤：

1. 将红黑树当作一颗二叉查找树，将节点插入；

2. 将节点着色为红色；

3. 通过旋转和重新着色等方法来修正该树，使重新成为一颗红黑树。

添加时的处理情况：

1. 情况说明：被插入的节点是根节点时，直接把此节点涂为黑色。

2. 情况说明：被插入的节点的父节点是黑色时，什么也不需要做。节点被插入后，仍然是红黑树。

3. 情况说明：被插入的节点的父节点是红色时，细分以下情况：

红黑树的删除操作：

删除步骤：

1. 将红黑树当作一颗二叉查找树，将该节点从二叉查找树中删除；

 ① 被删除节点没有儿子，即为叶节点，直接将该节点删除就OK了。       

② 被删除节点只有一个儿子，直接删除该节点，并用该节点的唯一子节点顶替它的位置。     

③ 被删除节点有两个儿子，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给“被删除节点“之后，再将后继节点删除。这样就巧妙的将问题转换为“删除后继节点“的情况了，下面就考虑后继节点。 在“被删除节点“有两个非空子节点的情况下，它的后继节点不可能是双子非空。既然“的后继节点“不可能双子都非空，就意味着“该节点的后继节点“要么没有儿子，要么只有一个儿子。若没有儿子，则按“情况① “进行处理；若只有一个儿子，则按“情况② “进行处理。

2. 通过“旋转和重新着色“等一系列来修正该树，使之重新成为一棵红黑树。

① 情况说明：x是“红+黑”节点时，直接把x设为黑色，此时红黑树性质全部恢复。

② 情况说明：x是“黑+黑”节点，且x是根时，什么都不做，此时红黑树性质全部恢复。

③ 情况说明：x是“黑+黑”节点，且x不是根时，这种情况又可以划分为4种子情况：

Hash算法：在HashMap的方法中有一个hash方法，他是取当前传入的key的hashode方法的返回值，将其向右位移16位，然后进行位异与运算，得到一个值，例如：调用hashcode后生成一个串，向右位移16位后等于取后十六位，扰乱后16位的顺序，会较少hash冲突的概率。

Hash冲突的解决方法：

1. 在hashmap中的hash冲突解决方法是链地址法，就是有冲突的元素后就以链表的形式存储数据。

2. 开放定址法，就是在hash冲突时，当前这个位置已经有了元素了，那就继续寻找下一个为空的位置(不是随便找的，而是按照一定的计算方法来找)。

3. 再hash，准备不同的hash算法，有冲突了就继续hash，直到不再冲突为止，多次计算会影响效率。

4. 建立两块区域，基本区域和溢出区域，一般无冲突的元素放在基本区域，有冲突的放在溢出区。

并发容器ConcurrentHashMap

CurrentHashMap的底层原理：

因为hashmap非线程安全，所以在多线程环境中使用hashmap会导致数据错乱等一系列线程安全的问题，而HashTable虽然支持多线程环境使用，但是hashTbale在每个方法中都加了锁，使得在使用的时候会造成线程阻塞，导致程序性能差，而CurrentHashMap的出现正是为了解决多线程中hasmap的问题的。

ConcurrentHashMap采用了数组+链表+Segment分段锁的方式实现，ConcurrentHashMap使用分段锁技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问，ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作，第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部，Hash的过程要比普通的HashMap要长。

简单理解就是，ConcurrentHashMap 是一个 Segment 数组，Segment 通过继承 ReentrantLock 来进行加锁，所以每次需要加锁的操作锁住的是一个 segment，这样只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全

Collections.SynchronizedList方法能将集合转化为线程安全的集合，避免线程不安全。

COW容器

CopyOnWriteArrayList/CopyOnWriteArraySet

运用了一种“写时复制”的思想，通俗的理解就是当我们需要修改（增/删/改）列表中的元素时，不直接进行修改，而是先将列表Copy，然后在新的副本上进行修改，修改完成之后，在将引用从原列表指向新列表，这样做的好处是读/写是不会冲突的，可以并发进行，读操作还是在原列表，写操作在新列表。仅仅当有多个线程同时进行写操作时，才会进行同步。

适用读多写少的场景：比如白名单，黑名单，商品类目的访问和更新场景，假如我们有一个搜索网站，用户在这个网站的搜索框中，输入关键字搜索内容，但是某些关键字不允许被搜索。这些不能被搜索的关键字会被放在一个黑名单当中，黑名单每天晚上更新一次。当用户搜索时，会检查当前关键字在不在黑名单当中，如果在，则提示不能搜索。

队列

1. ArrayBlockingQueue ：由数组结构组成的有界阻塞队列。 2. LinkedBlockingQueue ：由链表结构组成的有界阻塞队列。 3. PriorityBlockingQueue ：支持优先级排序的无界阻塞队列。 4. DelayQueue：使用优先级队列实现的无界阻塞队列。 5. SynchronousQueue：不存储元素的阻塞队列。 6. LinkedTransferQueue：由链表结构组成的无界阻塞队列。 7. LinkedBlockingDeque：由链表结构组成的双向阻塞队列

ArrayBlockingQueue（公平、非公平）

用数组实现的有界阻塞队列。此队列按照先进先出（FIFO）的原则对元素进行排序。默认情况下不保证访问者公平的访问队列，所谓公平访问队列是指阻塞的所有生产者线程或消费者线程，当队列可用时，可以按照阻塞的先后顺序访问队列，即先阻塞的生产者线程，可以先往队列里插入元素，先阻塞的消费者线程，可以先从队列里获取元素。通常情况下为了保证公平性会降低吞吐量。

LinkedBlockingQueue（两个独立锁提高并发）

基于链表的阻塞队列，同 ArrayListBlockingQueue 类似，此队列按照先进先出（FIFO）的原则对元素进行排序。而 LinkedBlockingQueue 之所以能够高效的处理并发数据，还因为其对于生产者端和消费者端分别采用了独立的锁来控制数据同步，这也意味着在高并发的情况下生产者和消费者可以并行地操作队列中的数据，以此来提高整个队列的并发性能。LinkedBlockingQueue 会默认一个类似无限大小的容量（Integer.MAX_VALUE）。

PriorityBlockingQueue（compareTo 排序实现优先）

是一个支持优先级的无界队列。默认情况下元素采取自然顺序升序排列。可以自定义实现compareTo()方法来指定元素进行排序规则，或者初始化 PriorityBlockingQueue 时，指定构造参数 Comparator 来对元素进行排序。需要注意的是不能保证同优先级元素的顺序。

DelayQueue（缓存失效、定时任务

是一个支持延时获取元素的无界阻塞队列。队列使用 PriorityQueue 来实现。队列中的元素必须实现 Delayed 接口，在创建元素时可以指定多久才能从队列中获取当前元素。只有在延迟期满时才能从队列中提取元素。我们可以将 DelayQueue 运用在以下应用场景： 1. 缓存系统的设计：可以用 DelayQueue 保存缓存元素的有效期，使用一个线程循环查询DelayQueue，一旦能从 DelayQueue 中获取元素时，表示缓存有效期到了。 2. 定时任务调度：使用 DelayQueue 保存当天将会执行的任务和执行时间，一旦从DelayQueue 中获取到任务就开始执行，从比如 TimerQueue 就是使用 DelayQueue 实现的。

SynchronousQueue（不存储数据、可用于传递数据）

是一个不存储元素的阻塞队列。每一个 put 操作必须等待一个 take 操作，否则不能继续添加元素。SynchronousQueue 可以看成是一个传球手，负责把生产者线程处理的数据直接传递给消费者线程。队列本身并不存储任何元素，非常适合于传递性场景,比如在一个线程中使用的数据，传递给另外一个线程使用， SynchronousQueue 的吞吐量高于 LinkedBlockingQueue 和ArrayBlockingQueue。

LinkedTransferQueue

是一个由链表结构组成的无界阻塞 TransferQueue 队列。相对于其他阻塞队列，LinkedTransferQueue 多了 tryTransfer 和 transfer 方法。 1. transfer 方法：如果当前有消费者正在等待接收元素（消费者使用 take()方法或带时间限制的poll()方法时），transfer 方法可以把生产者传入的元素立刻 transfer（传输）给消费者。如果没有消费者在等待接收元素，transfer 方法会将元素存放在队列的 tail 节点，并等到该元素 被消费者消费了才返回。 2. tryTransfer 方法。则是用来试探下生产者传入的元素是否能直接传给消费者。如果没有消费者等待接收元素，则返回 false。和 transfer 方法的区别是 tryTransfer 方法无论消费者是否接收，方法立即返回。而 transfer 方法是必须等到消费者消费了才返回。对于带有时间限制的 tryTransfer(E e, long timeout, TimeUnit unit)方法，则是试图把生产者传入的元素直接传给消费者，但是如果没有消费者消费该元素则等待指定的时间再返回，如果超时还没消费元素，则返回 false，如果在超时时间内消费了元素，则返回 true。

LinkedBlockingDeque

是一个由链表结构组成的双向阻塞队列。所谓双向队列指的你可以从队列的两端插入和移出元素。双端队列因为多了一个操作队列的入口，在多线程同时入队时，也就减少了一半的竞争。相比其他的阻塞队列，LinkedBlockingDeque 多了 addFirst，addLast，offerFirst，offerLast， peekFirst，peekLast 等方法，以 First 单词结尾的方法，表示插入，获取（peek）或移除双端队列的第一个元素。以 Last 单词结尾的方法，表示插入，获取或移除双端队列的最后一个元素。另外插入方法 add 等同于 addLast，移除方法 remove 等效于 removeFirst。但是 take 方法却等同 于 takeFirst，不知道是不是 Jdk 的 bug，使用时还是用带有 First 和 Last 后缀的方法更清楚。在初始化 LinkedBlockingDeque 时可以设置容量防止其过渡膨胀。另外双向阻塞队列可以运用在“工作窃取”模式中。