集合框架知识

Java的集合类主要由两个接口派生而出：Collection和Map

Set、List和Map可以看做集合的三大类：

List集合是有序集合，集合中的元素可以重复，访问集合中的元素可以根据元素的索引来访问。

Set集合是无序集合，集合中的元素不可以重复，访问集合中的元素只能根据元素本身来访问（也是集

合里元素不允许重复的原因）。

Map集合中保存Key-value对形式的元素，访问时只能根据每项元素的key来访问其value。

ArrayList

有序可重复,允许为空非安全的初始容量为10的动态数组

ArrayList类中两个私有属性，elementData存储ArrayList内的元素，size表示它包含的元素的数量。

有序：元素是按照该 collection 的迭代器返回它们的顺序排列的。

动态扩容：int newCapacity = (oldCapacity * 3)/2 + 1;

插入元素：按照指定位置，把从指定位置开始的所有元素利用System.arraycopy方法做一个整

体的复制，向后移动一个位置（当然先要用ensureCapacity方法进行判断，加了一个元素之后数组会

不会不够大），然后指定位置的元素设置为需要插入的元素，完成了一次插入的操作，该方法的根本目的就是将index位置空出来以供新数据插入，这里需要进行数组数据的右移，如果要复制的元素很多，那么就会比较耗费性能。

删除元素：1、把指定元素后面位置的所有元素，利用System.arraycopy方法整体向前移动一个位置

2、最后一个位置的元素指定为null，这样让gc可以去回收它，如果要复制的元素很多，那么就会比较耗费性能。

访问元素：ArrayList底层以数组实现，是一种随机访问模式，再加上它实现了RandomAccess接口，因此查

找也就是get的时候非常快。基于数组实现，可以通过下标索引直接查找到指定位置的元素，因此查找效率高

ArrayList是线程非安全的，一个方法是用Collections.synchronizedList方法把你的ArrayList变成一个线程安全的List，另一个方法就是Vector，它是ArrayList的线程安全版本

LinkedList

有序可重复,允许为空非安全的初始容量为10的双向链表

LinkedList中定义了两个私有属性：size 和Entry （Entry中包含成员变量：previous, next,element）

LinkedList底层的数据结构是基于双向循环链表的，且头结点中不存放数据，数据结构——我们可以称之为节点，节点实例保存业务数据、前一个节点的位置信息和后一个节点位置信息

插入元素：改变前后Entry的引用地址

删除元素：预删除节点的前一节点的后指针指向预删除节点的后一个节点。预删除节点的后一节点的前指针指向预删除节点的前一个节点。清空预删除节点：交给gc完成资源回收，删除操作结束。与ArrayList比较而言，LinkedList的删除动作不需要“移动”很多数据，从而效率更高。

访问元素：get(int)方法首先判断位置信息是否合法（大于等于0，小于当前LinkedList实例的Size），然后遍历

到具体位置，获得节点的业务数据（element）并返回。当index小于数组大小的一半的时候（size >> 1表示size / 2，使用移位运算提升代码运行效率），从前向后查找；否则，从后向前查找。

ArrayList和LinkedList比较

（1）LinkedList做插入、删除的时候，慢在寻址，快在只需要改变前后Entry的引用地址

（2）ArrayList做插入、删除的时候，慢在数组元素的批量copy，快在寻址

HashMap

无序可重复，允许为空线程非安全的 链表的数组

构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。

无序：特别说明这个无序指的是遍历HashMap的时候，得到的元素的顺顺序

可重复：Key重复会覆盖、Value允许重复）

Key和Value都允许为空

非线程安全的

HashMap的底层主要是基于数组和链表来实现的，它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。(key 的hash值决定位置)HashMap中主要是通过key的hashCode来计算hash值的，只要

hashCode相同，计算出来的hash值就一样。

如果存储的对象对多了，就有可能不同的对象所算出来的hash值是相同的，这就出现了所谓的hash冲突。学过数据结构的同学都知道，解决hash冲突的方法有很多，HashMap底层是通过链表来解决hash冲突的。

Entry就是数组中的元素，每个 Map.Entry 其实就是一个key-value对，它持有一个指向下一个元素的引用，这就构成了链表。（previous element next）

构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap: 空间利用和查找效率最好

加载因子它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费 ; 加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.链表长度会越来越长,查找效率降低。

存储元素（读取）：先判断key是否为null，若为null，则直接

调用putForNullKey方法，将value放置在数组第一个位置上。若不为空则根据key的hashCode重新

计算hash值，然后根据hash值得到这个元素在table数组中的位置（即下标），如果table数组在该位

置处已经存放有其他元素了，则通过比较是否存在相同的key，若存在则覆盖原来key的value，否则

将该元素保存在链头（最先保存的元素放在链尾）。若table在该处没有元素，就直接将该元素放到此

数组中的该位置上。

通过比较是否存在相同的key，若存在则覆盖原来key的value：对比Key是否相同，是先比HashCode是否相同，HashCode相同再判断equals是否为true

访问元素：此时的 HashMap 具有最好的性能：当程序通过 key 取出对应 value 时，系统只要先计算出该

key 的 hashCode() 返回值，在根据该 hashCode 返回值找出该 key 在 table 数组中的索引，然后

取出该索引处的 Entry，最后返回该 key 对应的 value 即可

2的n 次方：

HashMap的table而言，数据分布需要均匀（最好每项都只有一个元素，这样就可以直接找到），不能太紧也不能太松，太紧会导致查询速度慢，太松则浪费空间。HashMap的底层数组长度总是2的n次方数据在table数组中分布较均匀，查询速度也较快。

LinkedHashMap

HashMap+LinkedList，即它既使用HashMap操作数据结构，又使用LinkedList维护插入元素的先后顺序有序可重复

HashMap迭代HashMap的顺序并不是HashMap放置的顺序，也就是无序。我们期待一个有序的Map。LinkedHashMap就闪亮登场了，它虽然增加了时间和空间上的开销，但是通过维护一个运行于所有条目的双向链表，LinkedHashMap保证了元素迭代的顺序，该迭代顺序可以是插入顺序或者是访问顺序。

利用LinkedHashMap实现LRU算法缓存

LRU：LRU即Least Recently Used，最近最少使用，也就是说，当缓存满了，会优先淘汰那些最近最不常访问的数据。比

LinkedHashMap可以实现LRU算法的缓存基于两点：

1、LinkedList首先它是一个Map，Map是基于K-V的，和缓存一致

2、LinkedList提供了一个boolean值可以让用户指定是否实现LRU

accessOrder 1）false，所有的Entry按照插入的顺序排列（2）true，所有的Entry按照访问的顺序排列

concurrentHashMap

背景: 线程不安全的HashMap 使用Hashmap进行put操作会引起死循环 ;

效率低下的HashTable容器 , 当一个线程访问HashTable的同步方法时，其他线程访问HashTable的同步方法

时，可能会进入阻塞或轮询状态。

ConcurrentHashMap的锁分段技术（数据分段存储，分段枷锁）

首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。

数据结构：

ConcurrentHashMap为了提高本身的并发能力，在内部采用了一个叫做Segment的结构，一个Segment其实就是一个类Hash Table的结构，Segment内部维护了一个链表数组。当对HashEntry数组的数据进行修改时，必须首先获得它对应的Segment锁。

高并发：ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作，第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部。在最理想的情况下，ConcurrentHashMap可以最高同时支持Segment数量大小的写操作（刚好这些写操作都非常平均地分布在所有的Segment上），所以，通过这一种结构，ConcurrentHashMap的并发能力可以大大的提高。总的Map包含了16个Segment（默认数量），每个Segment内部包含16个HashEntry（默认数量），这样对于这个key所在的Segment加锁的同时，其他15个Segmeng还能正常使用，在性能上有了大大的提升。

详细解释一下Segment里面的成员变量的意义：

count：Segment中元素的数量

modCount：对table的大小造成影响的操作的数量（比如put或者remove操作）

threshold：阈值，Segment里面元素的数量超过这个值依旧就会对Segment进行扩容

table：链表数组，数组中的每一个元素代表了一个链表的头部

loadFactor：负载因子，用于确定threshold

volatile的保证：对volatile域的写入操作happens-before于每一个后续对同一个域的读写操作。所以，每次判断count变量的时候，即使恰好其他线程改变了segment也会体现出来。

get方法没有使用锁来同步，只是判断获取的entry的value是否为null，为null时才使用加锁的方式再次去获取。

put 操作：首先对Segment的put操作是加锁完成的。因为每个HashEntry中的next也是final的，没法对链表最后一个元素增加一个后续entry所以新增一个entry的实现方式只能通过头结点来插入了。

remove 操作：先定位Segment的过程，然后确定需要删除的元素的位置， 程序就将待删除元素前面的那一些元

素全部复制一遍，然后再一个一个重新接到链表上去，