- 标★号为重要知识点
java.util.Map接口有以下四种实现类
- HashMap：
最常用的Map，根据键的hashcode值来存储数据，根据键可以直接获得他的值（因为相同的键hashcode值相同，
在地址为hashcode值的地方存储的就是值，所以根据键可以直接获得值），具有很快的访问速度，遍历时，
取得数据的顺序是随机的，HashMap最多只允许一条记录的键为null，允许多条记录的值为null，
HashMap不支持线程同步，即任意时刻可以有多个线程同时写HashMap，这样对导致数据不一致，如果需要同步，
可以使用synchronziedMap的方法使得HashMap具有同步的能力或者使用concurrentHashMap。
- HashTable：
与HashMap类似，不同的是，它不允许记录的键或值为空，支持线程同步，即任意时刻只能有一个线程写HashTable，
因此也导致HashTable在写入时比较慢!
- LinkedHashMap：
是HahsMap的一个子类，但它保持了记录的插入顺序，遍历时先得到的肯定是先插入的，也可以在构造时带参数，
主要是利用链表维护插入顺序，再使用哈希表维护哈希位置。按照应用次数排序，在遍历时会比HahsMap慢，不过有个例外，
当HashMap的容量很大，实际数据少时，遍历起来会比LinkedHashMap慢（因为它是链啊），因为HashMap的遍历速度和它容量有关，
LinkedHashMap遍历速度只与数据多少有关
- TreeMap：
实现了sortMap接口，底层是红黑树。能够把保存的记录按照键排序（默认升序），也可以指定排序比较器，遍历时得到的数据是拍过序的。
- 常见使用：
在Map中插入，删除，定位元素：HashMap
要按照自定义顺序或自然顺序遍历：TreeMap
要求输入顺序和输出顺序相同：LinkedHashMap
需要同步的话使用：HashTable(更推荐ConcurrentHashMap)
主要有几点不同。
- 1.数据结构不同，hashMap在1.8之后采用数组、链表、红黑树的形式，hashtable采用的是数组加链表的形式。
- 2.hashMap允许null,hashtable不允许null.
- 3.数组大小不同，hashMap固定为2的次幂。
-
- 计算hash的方式不同。hashtable直接使用除留余数法，hashMap采用的是hash&size - 1.
-
- hashMap中contains方法的拆分为key和value减少歧义。
HashMap和HashTable是使用数组+链表结构实现，根据Hash和table长度计算数组的下标index做操作，hashMap默认数组长度为16，
hashMap对null值的key都放在table[0]的位置，table[index]形成1个链表，当然在新版jdk中链表节点数>8会变成红黑树结构。
hashMap达到最大数量会扩容，扩容table长度变为2倍，每个元素（table中）但重新计算index放到新的table中。
- HashMap在高并发下扩容时使用头插法导致无限循环。
- 比如线程一当前有个链表是1->2->3 扩容时会变为 3->2->1
- 而线程二执行到1, 此时头插法变为先插入2再插入1，这时候由于线程一的影响此时2的下一个元素也是1。就无限循环了。
- 区别：
数组可以包含基本数据类型和引用类型，ArrayList只能包含引用类型。
ArrayList是基于数组实现的，数组大小不可以调整大小，但ArrayList可以通过内部方法自动调整容量。
ArrayList是List接口的实现类，相比数组支持更多的方法和特性。
- 场景：
当集合长度固定时，使用数组；当集合的长度不固定时，使用ArrayList。但如果长度增长频繁，
应考虑预设ArrayList的长度或者使用链表LinkedList代替，ArrayList每次扩容都要进行数组的拷贝。
由于ArrayList不支持基本数据类型，所以保存基本数据类型时需要装箱处理，对比数组性能会下降。这种情况尽量使用数组。
数组支持的操作方法很少，但内存占用少，如果只需对集合进行随机读写，选数组；如果需要进行插入和数组，
使用数组的话，需要手动编写移动元素的代码，ArrayList中内置了这些操作，开发更方便。
ArrayList的底层实现是数组，在数组容量不够的时候新建一个1.5倍大的一个数组（不同JDK可能不一样），
并将原数组中的值复制到新的数组中。（所以当添加元素需要扩容的时候会比较耗时）。
ArrayList在迭代的过程中，如果发生增加，删除等导致modCount发生变化的操作时会抛出异常。
CopyOnWriteArrayList,内部持有一个ReentrantLock lock = new ReentrantLock()。底层是用volatile
transient声明的数组array。
在多线程环境中读多写少场景是比较有效的，它使用写时变更到新数组，然后修改引用指向，
读还是在旧数组上读，实现读写分离，写和读有所延迟，数据不保证实时一致性，只能保证最终一致性，另外需要注意
这种拷贝对象会耗费不少的内存。
LinkList底层的实现是Node节点类，该类包含前一个元素的引用，当前Node的值，下个元素的引用，
而LinkedList持有头节点和尾节点，所以LinkedList是双向链表，但是定位某个元素的话需要遍历链表，
所以查找性能较慢。好处是插入数组和删除数组时间复杂度为O（1），不需要扩容。
大O符号表示一个程序运行时所需要的渐进时间复杂度上界。 当数据结构中的元素增加时，算法的规模和性能在最坏情景下有多好。 大O还可以描述其它行为，比如内存消耗。因为集合类实际上是数据结构，因此我们一般使用大O符号基于时间，内存， 性能选择最好的实现。 大O符号可以对大量数据性能给予一个很好的说明。
- HashMap可以存null键和null值。ConcurrentHashMap不支持null键null值。
- HashMap不是线程安全的，ConcurrentHashMap是线程安全的。采用锁分段的机制来实现， 采用的是CAS的机制来更新map，因为其实map发生冲突的几率比较小，采用锁分段成本与收益比不高。
hashmap是数组+链表实现，数组是主体部分，而数组中的每一个元素可以就是一个链表的头节点。链表主要是为了用来解决hash冲突。
在1.8版本中，当链表长度超过8的时候，查找效率会退化成O(n)的复杂度，这时候会进化成红黑树。
hashMap内部类Entry，这个Entry存储了key和value。
hashMap的key和value都可以为null，如果key为null的话，会去找数组第一个元素，也就是下标为0的位置。
不是线程安全的，hashTable才是线程安全的，但是hashtable采用的同步是用synchronize修饰方法，效率不高。
推荐使用并发包中 concurrentHashMap，这个map采用的同步机制是锁分段的机制。
在1.8之后取消了锁分段的机制。 采用的是CAS的机制来更新map，因为其实map发生冲突的几率比较小，采用锁分段成本与收益比不高。
当元素超过阈值，并且新增的元素发生了哈希冲突的话，此时会进行扩容。负载因子默认为0.75.
如果key是自定义类的话，要重写equals和hashCode方法。
ArrayList是线性数组，LinkedList是双向链表。添加元素的话，性能应该差不多。但是ArrayList涉及到扩容的话，性能会较差。
最主要的原因是因为它的hash算法是 n & (length - 1)
在当length是2^n的时候，length - 1的二进制表现为全是1的二进制数，例如8-1的话就是111
这时候再将这个二进制数与n进行与操作的话，就会将n的二进制数字都不丢失的情况下获取到。
稍微举例一下 比如 110 和 100 分别与 101 进行与操作的话 得到的都是100 即产生哈希冲突
而 110 和 100 分别与 111 进行与操作的话 得到还是 110 和 100 就不会造成哈希冲突
这个效果相当于n % length 取模运算，但使用的是位运算性能更好。
这个问题在JDK7和JDK8的实现上不一样。
-
在JDK7当中： ConcurrentHashMap将数据分段，分为一个一个的segment, 在写的时候针对所在区间的segment进行加锁，
而对其他segment的写操作就可以并发操作了。 -
在JDK8当中： ConcurrentHashMap抛弃了数据分段segment的做法。通过CAS的做法与Node节点中volatile修饰变量进行并发访问。
class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; volatile V val; volatile Node<K,V> next; //... 省略部分代码 }
TreeMap是一个有序的key-value集合，基于红黑树(Red-Black tree)实现。该映射根据其键的自然顺序进行排序，
或者根据创建时提供的Comparator进行排序
- 在并发add的情况下，会发生数组越界
- 这是因为在Add方法中有两步操作，一个是ensureCapacityInternal(size + 1)确保数组容量的操作如果不够 位置添加元素的话则进行扩容，一个是elementData[size++] = e，将size值自增并将值e填入到数组当中
- 当数组中的位置仅剩一个的时候，线程1和线程2同时进入add方法中并都执行到了第一步ensureCapacityInternal操作，
- 这时候两个线程都认为数组中有位置可以填入，此时线程1填入后，size加1。然后线程2填入元素的时候就会数组越界。
- 因为之前当数组中的元素仅剩1个的时候，并没有进行扩容操作。
- 集合类当中分为Collection和Map
- Collection大概分为List(ArrayList、LinkedList、Vector)，Set(HashSet、TreeSet、LinkedHashSet),Queue(priorityQueue)
- Map大概分为HashMap,TreeMap,LinkedHashMap,HashTable
接口中没有实现，但在具体类当中是有实现的。
克隆(cloning)或者是序列化(serialization)的语义和含义是跟具体的实现相关的。
因此，应该由集合类的具体实现来决定如何被克隆或者是序列化。
迭代器是一种设计模式，提供一种方法顺序访问一个聚合对象中的各种元素，而又不暴露该对象的内部表示。
Java中的Iterator提供了统一遍历操作集合元素的统一接口, Collection接口实现Iterable接口,
每个集合都通过实现Iterable接口中iterator()方法返回Iterator接口的实例, 然后对集合的元素进行迭代操作.
有一点需要注意的是：在迭代元素的时候不能通过集合的方法删除元素, 否则会抛出ConcurrentModificationException
异常. 但是可以通过Iterator接口中的remove()方法进行删除.
Iterator可用来遍历Set和List集合，但是ListIterator只能用来遍历List。
Iterator对集合只能是前向遍历，ListIterator既可以前向也可以后向。
ListIterator实现了Iterator接口，并包含其他的功能，比如：增加元素，替换元素，获取前一个和后一个元素的索引，等等。
首先这两种机制都是对于迭代器而言的。
一：快速失败（fail—fast）
在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），
则会抛出Concurrent Modification Exception。
原理：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果
内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount
变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。
注意：这里异常的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果集合发生变化时修改modCount值
刚好又设置为了expectedmodCount值，则异常不会抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个
异常只建议用于检测并发修改的bug。
场景：java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改）。
二：安全失败（fail—safe）
采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。
原理：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发
Concurrent Modification Exception。
缺点：基于拷贝内容的优点是避免了Concurrent Modification Exception，但同样地，迭代器并不能访问到修改后的内容，
即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。
场景：java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改。
ArrayList和Vector底层都是利用数组。但是Vector有synchronized修饰，性能较差。这两个类往数组中间插入元素较慢，
查询元素的话较快。LinkendList的实现是双向链表，查找元素较慢，添加元素，插入元素的会较快。
Collection是java.util下的接口，它是各种集合结构的父接口，继承于它的接口的主要有set和List，
提供关于集合的一些操作，比如插入、删除、判断一个元素是否是其成员，遍历等。
Collections是java.utis下的类，是针对集合类的一个工具类，提供一系列静态方法，
实现对集合的查找、排序、替换、线程安全(将非同步的集合转换成同步的)等操作。
散列表是无序的，TreeSet才是有序的。
拉链法，开放定址法（线性探测，二次探测，伪随机数），再哈希法，建立公共溢出区。
- 直接定址法：去关键字的某个线性函数作为散列地址
- 除留余数法：取关键字除散列表长度取余数
- 数字分析法：分析关键字中分布较为平均的数字作为散列地址
- 平方取中法：将关键字进行平方然后再取中间部分
其实底层存储的是一个HashMap。通过类组合的方式复用hashMap来实现hashset。
TreeSet和TreeMap排序时比较元素要求元素对象必须实现Comparable接口
Collections的sort方法比较元素有两种方法：
- 元素对象实现Comparable接口
- 传入自定义比较器Collections.sort(List list，Comparator compare)
Java中的队列都有哪些，有什么区别。 队列分为Queue和Deque，Deque是双端队列 非阻塞队列有：LinkedList，PriorityQueue，ConcurrentLinkedQueue 阻塞队列有：ArrayBlockingQueue，LinkedBlockingQueue，PriorityBlockingQueue，SynchronousQueue
LinkedHashMap是HashMap的一个子类，它保留插入的顺序，如果需要输出的顺序和输入时的相同，那么就选用LinkedHashMap。
底层是采用哈希表存储加链表维持顺序。
LinkedHashMap也可以用于扩展成LRU缓存，通过设置access-order为true，使得元素按访问顺序排序，并且重写removeEldestEntry方法即可。
当频繁的出现哈希冲突时开始变慢。
在JDK8之前会出现死循环，原因在于扩容的时候位于同一哈希位置的链表重新挪到新的数组当中时。假设原本哈希位置上的元素是1、2、3。
线程一完成了迁移，采用了头插法变成了3、2、1。此时线程二刚好执行到e = 1 next=2 的中间状态与3、2、1是不一致的。
此时再进行头插法倒插的时候，1指向null，2指向1，next依然是还是1，于是1又指向2。最终导致2指向1，1又指向2.
- 加入多个分段锁浪费内存空间。
- 生产环境中， map 在放入时竞争同一个锁的概率非常小，分段锁反而会造成更新等操作的长时间等待。
- 为了提高 GC 的效率
JDK8新的做法：
源码保留了segment代码，但并没有使用）put首先通过 hash 找到对应链表过后， 查看是否是第一个object，如果是，
直接用cas原则插入，无需加锁。然后，如果不是链表第一个object，则直接用链表第一个object加锁，这里加的锁是synchronized，
虽然效率不如 ReentrantLock，但节约了空间，这里会一直用第一个object为锁， 直到重新计算map大小，比如扩容或者操作了第一个object为止。
- 减少内存开销
假设使用可重入锁来获得同步支持，那么每个节点都需要通过继承AQS来获得同步支持。但并不是每个节点都需要获得同步支持的，
只有链表的头节点（红黑树的根节点）需要同步，这无疑带来了巨大内存浪费。 - 获得JVM的支持
可重入锁毕竟是API这个级别的，后续的性能优化空间很小。synchronized则是JVM直接支持的，JVM能够在运行时作出相应的优化措施：
锁粗化、锁消除、锁自旋等等。这就使得synchronized能够随着JDK版本的升级而不改动代码的前提下获得性能上的提升。
LinkedList : 实现了Deque接口，受限的队列
PriorityQueue ： 优先队列，本质维护一个有序列表。可自然排序亦可传递 comparator构造函数实现自定义排序。
ConcurrentLinkedQueue：基于链表 线程安全的队列。增加删除O(1) 查找O(n)
实现blockqueue接口的五个阻塞队列，其特点：线程阻塞时，不是直接添加或者删除元素，而是等到有空间或者元素时，才进行操作。
ArrayBlockingQueue： 基于数组的有界队列
LinkedBlockingQueue： 基于链表的无界队列
ProiporityBlockingQueue： 基于优先次序的无界队列
DelayQueue： 基于时间优先级的队列
SynchronousQueue： 内部没有容器的队列 较特别 –其独有的线程一一配对通信机制
| 方法 | 用途 | 状况 |
|---|---|---|
| add | 增加一个元索 | 如果队列已满，则抛出一个IIIegaISlabEepeplian异常 |
| remove | 移除并返回队列头部的元素 | 如果队列为空，则抛出一个NoSuchElementException异常 |
| element | 返回队列头部的元素 | 如果队列为空，则抛出一个NoSuchElementException异常 |
| offer | 添加一个元素并返回true | 如果队列已满，则返回false |
| poll | 移除并返问队列头部的元素 | 如果队列为空，则返回null |
| peek | 返回队列头部的元素 | 如果队列为空，则返回null |
| put | 添加一个元素 | 如果队列满，则阻塞 |
| take | 移除并返回队列头部的元素 | 如果队列为空，则阻塞 |