正式01-集合_牛客博客

ArrayList：底层实现数组、线程不同步、可通过数组下标查询，常用在查询较多的情况下。

LinkedList：底层实现链表、线程不同步，插入删除性能要优于ArrayList。

Vector：Vector和ArrayList和linkedlist一样也是实现了java.util.list接口，线程同步

ArrayList初始化大小为10.

 int newCapacity = (oldCapacity * 3)/2 + 1;

ArrayList扩容：扩容后的大小=（原始大小*3）/2+1

jdk1.7扩容规则进行了修改扩容后的大小=（原始大小*3）/2+

LinkedList： LinkedList的底层实现是双向链表，没有初始化大小，也没有扩容的机制。

--------------------------------------------------------------------------------------------------------------------------

（参考链接：https://baijiahao.baidu.com/s?id=1618550070727689060&wfr=spider&for=pc）

HashMap底层原理：

HashMap的数据结构：数组+链表

HashMap是一个散列桶（数组和链表），

HashMap是线程不同步的，HashMap可以接受null键和值，

而hashtable则不能，

使用put方法传递键和值的时候，我们先对键调用hashcode方法，

计算并返回hashcode是用于找到Map数组的bucket位置来存储Node对象。

以下是具体的put过程（JDK1.8版）

1、对Key求Hash值，然后再计算下标

2、如果没有碰撞，直接放入桶中（碰撞的意思是计算得到的Hash值相同，需要放到同一个bucket中）

3、如果碰撞了，以链表的方式链接到后面

4、如果链表长度超过阀值( TREEIFY THRESHOLD==8)，就把链表转成红黑树，链表长度低于6，就把红黑树转回链表

5、如果节点已经存在就替换旧值

6、如果桶满了(容量16*加载因子0.75)，就需要 resize（扩容2倍后重排）

当我们调用get()方法，HashMap会使用键对象的hashcode找到bucket位置，

找到bucket位置之后，会调用keys.equals()方法去找到链表中正确的节点，

最终找到要找的值对象。

1、通过hashcode找到散列桶的具***置

2、通过key的equals方法在链表中找到key对应的value

减少碰撞：

扰动函数可以减少碰撞，让不同的对象生成不同的hashcode那么碰撞的概率就会减小，

这就意味着链表的长度减小，这样取值的话就不会频繁调用equal方法，这样就能提高HashMap的性能。

（扰动即Hash方法内部的算法实现，目的是让不同对象返回不同hashcode。）

拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？

之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。

说说你对红黑树的理解？

红黑树是一种平衡的二叉查找树

1、每个节点非红即黑

2、根节点总是黑色的

3、如果节点是红色的，则它的子节点必须是黑色的（反过来则不一定）

4、每个叶子节点都是黑色的空节点（NIL节点）

5、任意一节点到每个叶子节点的路径都包含数量相同的黑色节点

解决hash碰撞还有哪些方法？

开放地址法：

当冲突发生时，使用某种探查技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定的地址。

8、如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？

默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，

和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，

来重新调整map的大小，并将原来的对象放入新的bucket数组中。

--------------------------------------------------------------------------------------------------------------------------

HashMap详细介绍一下，怎么计算下标值的，时间复杂度是多少，最坏的时间复杂度是多少，

在扩容的时候时间复杂度是O(n)的，你有什么方式去优化这个时间复杂度吗；

数组查找时间复杂度O(1)

如果桶里的元素有元素，并且个数小于6，则调用equals方法，比较是否存在相同名字的key，

时间复杂度O（n）

如果桶里有元素，并且元素个数大于6，则调用equals方法，比较是否存在相同名字的key，

时间复杂度O(1)+O(logn)=O(logn)。红黑树查询的时间复杂度是logn。

通过上面的分析，我们可以得出结论，HashMap新增元素的时间复杂度是不固定的，可能的值有O(1)、O(logn)、O(n)。

hashmap解决hash冲突的方法是链地址法，就是把冲突的key连接起来，放到桶里。

当桶中的元素个数不超过6个时，以单链表的形式串起来，当桶中的元素个数超过6个时，以红黑树的形式串起来。

--------------------------------------------------------------------------------------------------------------------------

ConcurrentHashMap的底层实现原理，怎么查找的的，如何保证查找时的线程安全性；

ConcurrentHashMap是线程安全且高效的HashMap。

在并发编程中使用HashMap可能导致程序死循环，而使用线程安全的HashTable效率又非常低下，基于以上两个原因，

并有了ConcurrentHashMap登场的机会。

HashMap在并发执行put操作时会引起死循环，是因为多线程会导致HashMap的Entry链表形成环形数据结构。

ConcurrentHashMap的锁分段技术可有效提升并发访问率。首先将数据分成一段一段地存储，

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

ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。

Segment是一种可重入锁(ReentrantLock)，在ConcurrentHashMap里扮演锁的角色；

HashEntry则用于存储键值对数据。

一个ConcurrentHashMap包含一个Segment数组。Segment的结构和HashMap类似，

是一种数组和链表结构。一个Segment里包含一个HashEntry数组，每个HashEntry是一个

链表结构的元素，当对HashEntry数组的数据进行修改时，必须首先获得与它对应的Segment锁。

--------------------------------------------------------------------------------------------------------------------------

题目来自（https://www.nowcoder.com/discuss/222265）

多线程介绍一下，如果一个方法被synchronized修饰了，你有什么方法可以去掉这个关键字，保证线程安全并且可以提升效率吗；

--------------------------------------------------------------------------------------------------------------------------

线程池介绍一下，常用的拒绝策略有哪些；

线程池的概念：

线程池就是首先创建一些线程，它们的集合称为线程池。

使用线程池可以很好地提高性能，线程池在系统启动时即创建大量空闲的线程，程序将一个任务传给线程池，

线程池就会启动一条线程来执行这个任务，执行结束以后，该线程并不会死亡，

而是再次返回线程池中成为空闲状态，等待执行下一个任务。

2. 线程池的工作机制

2.1 在线程池的编程模式下，任务是提交给整个线程池，而不是直接提交给某个线程，线程池在拿到任务后，就在内部寻找是否有空闲的线程，如果有，则将任务交给某个空闲的线程。

2.1 一个线程同时只能执行一个任务，但可以同时向一个线程池提交多个任务。

3. 使用线程池的原因：

多线程运行时间，系统不断的启动和关闭新线程，成本非常高，会过渡消耗系统资源，以及过渡切换线程的危险，从而可能导致系统资源的崩溃。这时，线程池就是最好的选择了。
四种常见的线程池：

线程池的返回值ExecutorService简介：

ExecutorService是Java提供的用于管理线程池的类。该类的两个作用：控制线程数量和重用线程

具体的4种常用的线程池实现如下：（返回值都是ExecutorService）

2.1 Executors.newCacheThreadPool()：可缓存线程池，先查看池中有没有以前建立的线程，如果有，就直接使用。如果没有，就建一个新的线程加入池中，缓存型池子通常用于执行一些生存期很短的异步型任务

2.2 Executors.newFixedThreadPool(int n)：创建一个可重用固定个数的线程池，以共享的无界队列方式来运行这些线程。

2.3 Executors.newScheduledThreadPool(int n)：创建一个定长线程池，支持定时及周期性任务执行

2.4 Executors.newSingleThreadExecutor()：创建一个单线程化的线程池，它只会用唯一的工作线程来执行任务，保证所有任务按照指定顺序(FIFO, LIFO, 优先级)执行。

缓冲队列BlockingQueue简介：

BlockingQueue是双缓冲队列。BlockingQueue内部使用两条队列，允许两个线程同时向队列一个存储，一个取出操作。在保证并发安全的同时，提高了队列的存取效率。

2. 常用的几种BlockingQueue：

ArrayBlockingQueue（int i）:规定大小的BlockingQueue，其构造必须指定大小。其所含的对象是FIFO顺序排序的。

LinkedBlockingQueue（）或者（int i）:大小不固定的BlockingQueue，若其构造时指定大小，生成的BlockingQueue有大小限制，不指定大小，其大小有Integer.MAX_VALUE来决定。其所含的对象是FIFO顺序排序的。

PriorityBlockingQueue（）或者（int i）:类似于LinkedBlockingQueue，但是其所含对象的排序不是FIFO，而是依据对象的自然顺序或者构造函数的Comparator决定。

SynchronizedQueue（）:特殊的BlockingQueue，对其的操作必须是放和取交替完成。

3. 自定义线程池（ThreadPoolExecutor和BlockingQueue连用）：

自定义线程池，可以用ThreadPoolExecutor类创建，它有多个构造方法来创建线程池。

常见的构造函数：ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, long keepAliveTime, TimeUnit unit, BlockingQueue<Runnable> workQueue)

ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, long keepAliveTime, TimeUnit unit, BlockingQueue<Runnable> workQueue，ThreadFactory threadFactory,RejectedExecutionHandler handler)

线程池的拒绝策略，是指当任务添加到线程池中被拒绝，而采取的处理措施。
当任务添加到线程池中之所以被拒绝，可能是由于：第一，线程池异常关闭。第二，任务数量超过线程池的最大限制。

（详解见博客：https://www.cnblogs.com/duanxz/p/3458352.html）

--------------------------------------------------------------------------------------------------------------------------

线程池中一般设置多少线程，你是怎么设定的，为什么；

线程池究竟设成多大是要看你给线程池处理什么样的任务，任务类型不同，线程池大小的设置方式也是不同的。

任务一般可分为：CPU密集型、IO密集型、混合型，对于不同类型的任务需要分配不同大小的线程池。

CPU密集型任务尽量使用较小的线程池，一般为CPU核心数+1。因为CPU密集型任务使得CPU使用率很高，若开过多的线程数，只能增加上下文切换的次数，因此会带来额外的开销。

IO密集型任务可以使用稍大的线程池，一般为2*CPU核心数。 IO密集型任务CPU使用率并不高，因此可以让CPU在等待IO的时候去处理别的任务，充分利用CPU时间。

混合型任务可以将任务分成IO密集型和CPU密集型任务，然后分别用不同的线程池去处理。只要分完之后两个任务的执行时间相差不大，那么就会比串行执行来的高效。因为如果划分之后两个任务执行时间相差甚远，那么先执行完的任务就要等后执行完的任务，最终的时间仍然取决于后执行完的任务，而且还要加上任务拆分与合并的开销，得不偿失。

--------------------------------------------------------------------------------------------------------------------------

线程中中常用阻塞队列有哪些，你一般用哪个，LinkedBlockingQueue与ArrayBlockingQueue的优缺点对比；

什么是阻塞队列？阻塞队列（BlockingQueue）是一个支持两个附加操作的队列，这两个附加的操作支持阻塞的插入和移除方法。

JDK7提供了7个阻塞队列：

ArrayBlockingQueue

LinkedBlockingQueue

PriorityBlockingQueue

DelayQueue

。。。

见并发书籍

LinkedBlockingQueue与ArrayBlockingQueue：

（博客：https://blog.csdn.net/chang_ge/article/details/79974121）

相同：

1、LinkedBlockingQueue和ArrayBlockingQueue都实现了BlockingQueue接口；

2、LinkedBlockingQueue和ArrayBlockingQueue都是可阻塞的队列

内部都是使用ReentrantLock和Condition来保证生产和消费的同步；

当队列为空，消费者线程被阻塞；当队列装满，生产者线程被阻塞；

使用Condition的方法来同步和通信：await()和signal()

不同：

1、由上图可以看出，他们的锁机制不同

LinkedBlockingQueue中的锁是分离的，生产者的锁PutLock，消费者的锁takeLock

而ArrayBlockingQueue生产者和消费者使用的是同一把锁；

2、他们的底层实现机制也不同

LinkedBlockingQueue内部维护的是一个链表结构

在生产和消费的时候，需要创建Node对象进行插入或移除，大批量数据的系统中，其对于GC的压力会比较大

而ArrayBlockingQueue内部维护了一个数组

在生产和消费的时候，是直接将枚举对象插入或移除的，不会产生或销毁任何额外的对象实例

3、构造时候的区别

LinkedBlockingQueue有默认的容量大小为：Integer.MAX_VALUE，当然也可以传入指定的容量大小

ArrayBlockingQueue在初始化的时候，必须传入一个容量大小的值

--------------------------------------------------------------------------------------------------------------------------

JVM的CMS介绍一下，CMS重新标记时标记什么，为什么这么标记，标记待回收垃圾和标记保留对象的区别是什么，哪个更好一些；

--------------------------------------------------------------------------------------------------------------------------

Java开发中遇到问题了（比如报了异常），你一般怎么去处理；

消息队列

（博客：https://www.cnblogs.com/doit8791/p/7759806.html）

--------------------------------------------------------------------------------------------------------------------------

MySQL的索引，怎么建立索引，建立索引时有哪些好的习惯；

（博客：https://www.cnblogs.com/lfs2640666960/p/9147768.html）

MySQL在300万条记录左右性能开始下降，所有大数据量建立索引是非常有必要的。MySQL提供了Explain，

用于显示SQL执行的详细信息，可以进行索引的优化。

什么是索引？

MySQL官方对索引的定义为：索引(Index)是帮助MySQL高效获取数据的数据结构。我们可以简单理解为：快速查找排好序的一种数据结构。Mysql索引主要有两种结构：B+Tree索引和Hash索引。我们平常所说的索引，如果没有特别指明，一般都是指B树结构组织的索引(B+Tree索引)。

--------------------------------------------------------------------------------------------------------------------------

Java中的Map接口及其实现进行一些介绍；

java集合框架用于存储数据，也被称为集合类

位于java.util包下

java.util包下常用接口和类

Collection和Map是Java集合框架的根接口

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

Set集合是无序集合，集合中的元素不可以重复，访问集合中的元素只能根据元素本身来访问（也是不能集合里元素不允许重复的原因）。

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

Map接口

Map接口不是Collection接口的继承。Map接口用于维护键/值对(key/value pairs)。该接口描述了从不重复的键到值的映射。

HashMap 是一个最常用的Map,它根据键的HashCode 值存储数据,根据键可以直接获取它的值，具有很快的访问速度。

HashMap最多只允许一条记录的键为Null;允许多条记录的值为Null;HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap;

可能会导致数据的不一致。如果需要同步，可以用Collections的synchronizedMap方法使HashMap具有同步的能力。

TreeMap 不仅可以保持顺序，而且可以用于排序

Map与Collection：
   Map与Collection在集合框架中属并列存在
   Map存储的是键值对
   Map存储元素使用put方法，Collection使用add方法
   Map集合没有直接取出元素的方法，而是先转成Set集合，在通过迭代获取元素

Map集合中键要保证唯一性

--------------------------------------------------------------------------------------------------------------------------

LinkedHashMap与TreeMap中的有序是同样的概念吗？LinkedHashMap的顺序调整是怎么完成的；

（博客：https://www.cnblogs.com/benwu/articles/7751640.html）

HashMap大家都很了解，是一中比较常用的，也比较好用的集合，但是HashMap有一个顺序的问题，

就是在对HashMap进行迭代访问时，添加的顺序和访问的顺序可能就不一样的，这个时候我们可以选择LinkedHashMap，