81、ArrayList在增删的时候是怎么做的？（为什么慢）
ArrayList有指定index（索引下标）新增，也有尾部新增，但是都有校验长度的判断ensureCapacityInternal，就是说如果⻓度不够，是需要扩容的。
在扩容的时候，1.7是取余，1.8是位运算，右移⼀位，其实就是除以2这个操作。
//尾插add方法 public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } //index(索引)插入，指定位置新增的时候，在校验之后的操作很简单，就是数组的copy public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } //真正扩容 private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } //删除 public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue; }
总结：总的来说，不论是删除还是新增，其实本质上都是移动位置，当指定位置新增的时候，新增的索空出，后面向后移一位，然后赋值，当删除时，也是一样，将要删除的索引下标的值置为null。
82、ArrayList是线程安全的么？
不是，可以用Vector,Collections.synchronizedList(),原理都是給方法套个synchronized，
CopyOnWriteArrayList
83、ArrayList⽤来做队列合适么？
队列⼀般是FIFO（先⼊先出）的，如果⽤ArrayList做队列，就需要在数组尾部追加数据，数组头部删除数组，反过来也可以。但是⽆论如何总会有⼀个操作会涉及到数组的数据搬迁，这个是⽐较耗费性能的。
结论：ArrayList不适合做队列。
84、那数组适合⽤来做队列么？
数组是⾮常合适的。 ⽐如ArrayBlockingQueue内部实现就是⼀个环形队列，它是⼀个定⻓队列，内部是⽤⼀个定⻓数组来实现的。
另外著名的Disruptor开源Library也是⽤环形数组来实现的超⾼性能队列，具体原理不做解释，⽐较复杂。
简单点说就是使⽤两个偏移量来标记数组的读位置和写位置，如果超过⻓度就折回到数组开头，前提是它们是定⻓数组。
85、ArrayList的遍历和LinkedList遍历性能⽐较如何？
ArrayList要比LinkedList快得多，ArrayList遍历最大的优势在于内存的连续性，CPU的内部缓存结构会缓存连续的内存片段，可以大幅降低读取内存的性能开销。
86、再理解ArrayList数组扩容
//详细扩容 private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }
87、为什么需要散列表
HashMap中的数据结构为散列表，又名哈希表。在这里我会对散列表进行一个简单的介绍，在此之前我们需要先回顾一下 数组、链表 的优缺点。
数组：数组删除、插入性能不佳，寻址性能极优
链表：链表查询性能不佳，删除、插入性能极优
数组的优缺点取决于他们在内存中存储的模式，也就是直接使用顺序存储或链式存储导致的。无论是数组还是链表，都有明显的缺点。而在实际业务中，我们想要的往往是寻址、删除、插入性能都很好的数据结构，散列表就是这样一种结构，它巧妙的结合了数组与链表的优点，并将其缺点弱化（并不是完全消除）
88、能说一下HashMap的数据结构吗？
JDK1.7的数据结构是数组+链表
JDK1.8的数据结构是数组+链表+红黑树。
数据结构示意图如下：
其中，桶数组是用来存储数据元素，链表是用来解决冲突，红黑树是为了提高查询的效率。
数据元素通过映射关系，也就是散列函数，映射到桶数组对应索引的位置
如果发生冲突，从冲突的位置拉一个链表，插入冲突的元素
如果链表长度>8&数组大小>=64，链表转为红黑树
如果红黑树节点个数<6 ，转为链表
89、你对红黑树了解多少？为什么不用二叉树/平衡树呢？
红黑树本质上是一种二叉查找树，为了保持平衡，它又在二叉查找树的基础上增加了一些规则：
每个节点要么是红色，要么是黑色；
根节点永远是黑色的；
所有的叶子节点都是是黑色的（注意这里说叶子节点其实是图中的 NULL 节点）；
每个红色节点的两个子节点一定都是黑色；
从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；
之所以不用二叉树：
红黑树是一种平衡的二叉树，插入、删除、查找的最坏时间复杂度都为 O(logn)，避免了二叉树最坏情况下的O(n)时间复杂度。
之所以不用平衡二叉树：
平衡二叉树是比红黑树更严格的平衡树，为了保持保持平衡，需要旋转的次数更多，也就是说平衡二叉树保持平衡的效率更低，所以平衡二叉树插入和删除的效率比红黑树要低。
90、红黑树怎么保持平衡的知道吗？
红黑树有两种方式保持平衡：旋转和染色。
- 旋转：旋转分为两种，左旋和右旋
- 染⾊
91、HashMap的put流程知道吗？
首先进行哈希值的扰动，获取一个新的哈希值。(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
判断tab是否位空或者长度为0，如果是则进行扩容操作。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
1
2
根据哈希值计算下标，如果对应小标正好没有存放数据，则直接插入即可否则需要覆盖。tab[i = (n - 1) & hash])
判断tab[i]是否为树节点，否则向链表中插入数据，是则向树中插入节点。
如果链表中插入节点的时候，链表长度大于等于8，则需要把链表转换为红黑树。treeifyBin(tab, hash);
最后所有元素处理完成后，判断是否超过阈值；threshold，超过则扩容。
92、HashMap怎么查找元素的呢？
HashMap的查找就简单很多：
- 使用扰动函数，获取新的哈希值
- 计算数组下标，获取节点
- 当前节点和key匹配，直接返回
- 否则，当前节点是否为树节点，查找红黑树
- 否则，遍历链表查找
93、HashMap的哈希/扰动函数是怎么设计的?
HashMap的哈希函数是先拿到 key 的hashcode，是一个32位的int类型的数值，然后让hashcode的高16位和低16位进行异或操作。
static final int hash(Object key) { int h; // key的hashCode和key的hashCode右移16位做异或运算 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
这么设计是为了降低哈希碰撞的概率。
94、为什么哈希/扰动函数能降hash碰撞？
因为 key.hashCode() 函数调用的是 key 键值类型自带的哈希函数，返回 int 型散列值。int 值范围为 -2147483648~2147483647，加起来大概 40 亿的映射空间。
只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。
假如 HashMap 数组的初始大小才 16，就需要用之前需要对数组的长度取模运算，得到的余数才能用来访问数组下标。
源码中模运算就是把散列值和数组长度 - 1 做一个 “与&” 操作，位运算比取余 % 运算要快。
bucketIndex = indexFor(hash, table.length);
static int indexFor(int h, int length) {
return h & (length-1);
顺便说一下，这也正好解释了为什么 HashMap 的数组长度要取 2 的整数幂。因为这样（数组长度 - 1）正好相当于一个 “低位掩码”。与 操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度 16 为例，16-1=15。2 进制表示是 0000 0000 0000 0000 0000 0000 0000 1111。和某个散列值做 与 操作如下，结果就是截取了最低的四位值。
右移 16 位，正好是 32bit 的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。
95、为什么HashMap的容量是2的倍数呢？
第一个原因是为了方便哈希取余：
将元素放在table数组上面，是用hash值%数组大小定位位置，而HashMap是用hash值&(数组大小-1)，却能和前面达到一样的效果，这就得益于HashMap的大小是2的倍数，2的倍数意味着该数的二进制位只有一位为1，而该数-1就可以得到二进制位上1变成0，后面的0变成1，再通过&运算，就可以得到和%一样的效果，并且位运算比%的效率高得多
HashMap的容量是2的n次幂时，(n-1)的2进制也就是1111111***111这样形式的，这样与添加元素的hash值进行位运算时，能够充分的散列，使得添加的元素均匀分布在HashMap的每个位置上，减少hash碰撞。
第二个方面是在扩容时，利用扩容后的大小也是2的倍数，将已经产生hash碰撞的元素完美的转移到新的table中去.
96、如果初始化HashMap，传一个17的值new HashMap<>，它会怎么处理？
简单来说，就是初始化时，传的不是2的倍数时，HashMap会向上寻找离得最近的2的倍数，所以传入17，但HashMap的实际容量是32。
我们来看看详情，在HashMap的初始化中，有这样⼀段⽅法；
public HashMap(int initialCapacity, float loadFactor) { ... this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }
- 阀值 threshold ，通过⽅法 tableSizeFor 进⾏计算，是根据初始化传的参数来计算的。
- 同时，这个⽅法也要要寻找⽐初始值⼤的，最⼩的那个2进制数值。⽐如传了17，我应该找到的是32。
static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }
- MAXIMUM_CAPACITY = 1 << 30，这个是临界范围，也就是最⼤的Map集合。
- 计算过程是向右移位1、2、4、8、16，和原来的数做|运算，这主要是为了把⼆进制的各个位置都填上1，当⼆进制的各个位置都是1以后，就是⼀个标准的2的倍数减1了，最后把结果加1再返回即可。
97、你还知道哪些哈希函数的构造方法呢？
HashMap里哈希构造函数的方法叫：
除留取余法：H（key)=key%p（p<=N）,关键字除以一个不大于哈希表长度的正整数p，所得余数为地址，当然HashMap里进行了优化改造，效率更高，散列也更均衡。
除此之外，还有这几种常见的哈希函数构造方法：
直接定址法
直接根据key来映射到对应的数组位置，例如1232放到下标1232的位置。
数字分析法
取key的某些数字（例如十位和百位）作为映射的位置
平方取中法
取key平方的中间几位作为映射的位置
折叠法
将key分割成位数相同的几段，然后把它们的叠加和作为映射的位置
98、解决哈希冲突有哪些方法呢？
HashMap使用链表的原因为了处理哈希冲突，这种方法就是所谓的：
链地址法：在冲突的位置拉一个链表，把冲突的元素放进去。
开放定址法：开放定址法就是从冲突的位置再接着往下找，给冲突元素找个空位。
找到空闲位置的方法也有很多种：
线行探查法: 从冲突的位置开始，依次判断下一个位置是否空闲，直至找到空闲位置
平方探查法: 从冲突的位置x开始，第一次增加12个位置，第二次增加22…，直至找到空闲的位置 ……
再哈希法：换种哈希函数，重新计算冲突元素的地址。
建立公共溢出区：再建一个数组，把冲突的元素放进去。
99、为什么HashMap链表转红黑树的阈值为8呢？
树化发生在table数组的长度大于64，且链表的长度大于8的时候。
为什么是8呢？源码的注释也给出了答案。
红黑树节点的大小大概是普通节点大小的两倍，所以转红黑树，牺牲了空间换时间，更多的是一种兜底的策略，保证极端情况下的查找效率。
阈值为什么要选8呢？和统计学有关。理想情况下，使用随机哈希码，链表里的节点符合泊松分布，出现节点个数的概率是递减的，节点个数为8的情况，发生概率仅为0.00000006。
至于红黑树转回链表的阈值为什么是6，而不是8？是因为如果这个阈值也设置成8，假如发生碰撞，节点增减刚好在8附近，会发生链表和红黑树的不断转换，导致资源浪费。
100、扩容在什么时候呢？为什么扩容因子是0.75？
为了减少哈希冲突发生的概率，当前HashMap的元素个数达到一个临界值的时候，就会触发扩容，把所有元素rehash之后再放在扩容后的容器中，这是一个相当耗时的操作。
而这个临界值threshold就是由加载因子和当前容器的容量大小来确定的，假如采用默认的构造方法：threshold = （DEFAULT_INITIAL_CAPACITY） *（DEFAULT_LOAD_FACTOR）
那就是大于16x0.75=12时，就会触发扩容操作。
那么为什么选择了0.75作为HashMap的默认加载因子呢？
简单来说，这是对空间成本和时间成本平衡的考虑。
我们都知道，HashMap的散列构造方式是Hash取余，负载因子决定元素个数达到多少时候扩容。
假如我们设的比较大，元素比较多，空位比较少的时候才扩容，那么发生哈希冲突的概率就增加了，查找的时间成本就增加了。
我们设的比较小的话，元素比较少，空位比较多的时候就扩容了，发生哈希碰撞的概率就降低了，查找时间成本降低，但是就需要更多的空间去存储元素，空间成本就增加了。
101、扩容机制了解吗？
HashMap是基于数组+链表和红黑树实现的，但用于存放key值的桶数组的长度是固定的，由初始化参数确定。
那么，随着数据的插入数量增加以及负载因子的作用下，就需要扩容来存放更多的数据。而扩容中有一个非常重要的点，就是jdk1.8中的优化操作，可以不需要再重新计算每一个元素的哈希值。
因为HashMap的初始容量是2的次幂，扩容之后的长度是原来的二倍，新的容量也是2的次幂，所以，元素，要么在原位置，要么在原位置再移动2的次幂。
看下这张图，n为table的长度，图a表示扩容前的key1和key2两种key确定索引的位置，图b表示扩容后key1和key2两种key确定索引位置。
102、jdk1.8对HashMap主要做了哪些优化呢？为什么？
jdk1.8 的HashMap主要有五点优化：
数据结构：数组 + 链表改成了数组 + 链表或红黑树
原因：发生 hash 冲突，元素会存入链表，链表过长转为红黑树，将时间复杂度由O(n)降为O(logn)
链表插入方式：链表的插入方式从头插法改成了尾插法
简单说就是插入时，如果数组位置上已经有元素，1.7 将新元素放到数组中，原始节点作为新节点的后继节点，1.8
遍历链表，将元素放置到链表的最后。
原因：因为 1.7 头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环。
扩容rehash：扩容的时候 1.7 需要对原数组中的元素进行重新 hash 定位在新数组的位置，1.8
采用更简单的判断逻辑，不需要重新通过哈希函数计算位置，新的位置不变或索引 + 新增容量大小。
原因：提高扩容的效率，更快地扩容。
扩容时机：在插入时，1.7 先判断是否需要扩容，再插入，1.8 先进行插入，插入完成再判断是否需要扩容；
散列函数：1.7 做了四次移位和四次异或，jdk1.8只做一次。
原因：做 4 次的话，边际效用也不大，改为一次，提升效率。
103、HashMap 是线程安全的吗？多线程下会有什么问题？
HashMap不是线程安全的，可能会发生这些问题：
多线程下扩容死循环。JDK1.7 中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8 使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。
多线程的 put 可能导致元素的丢失。多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在 JDK 1.7 和 JDK 1.8 中都存在。
put 和 get 并发时，可能导致 get 为 null。线程 1 执行 put 时，因为元素个数超出 threshold 而导致 rehash，线程 2 此时执行 get，有可能导致这个问题。这个问题在 JDK 1.7 和 JDK 1.8 中都存在。
104、有什么办法能解决HashMap线程不安全的问题呢？
Java 中有 HashTable、Collections.synchronizedMap、以及 ConcurrentHashMap 可以实现线程安全的 Map。
HashTable 是直接在操作方法上加 synchronized 关键字，锁住整个table数组，粒度比较大；
Collections.synchronizedMap 是使用 Collections 集合工具的内部类，通过传入 Map 封装出一个 SynchronizedMap 对象，内部定义了一个对象锁，方法内通过对象锁实现；
ConcurrentHashMap 在jdk1.7中使用分段锁，在jdk1.8中使用CAS+synchronized。
105、能具体说一下ConcurrentHashmap的实现吗？
ConcurrentHashmap线程安全在jdk1.7版本是基于分段锁实现，在jdk1.8是基于CAS+synchronized实现。
106、HashMap 内部节点是有序的吗？
HashMap是无序的，根据 hash 值随机插入。如果想使用有序的Map，可以使用LinkedHashMap 或者 TreeMap。
107、说一说SecurityException
根据异常信息，定位到java.lang.ClassLoader.preDefineClass进行排查，发现以下代码片断：
/* Determine protection domain, and check that: - not define java.* class, - signer of this class matches signers for the rest of the classes in package. */ private ProtectionDomain preDefineClass(String name, ProtectionDomain protectionDomain) { if (!checkName(name)) throw new NoClassDefFoundError("IllegalName: " + name); if ((name != null) && [color=red]name.startsWith("java.")[/color]) { throw new SecurityException("Prohibited package name: " + name.substring(0, name.lastIndexOf('.'))); } if (protectionDomain == null) { protectionDomain = getDefaultDomain(); } if (name != null) checkCerts(name, protectionDomain.getCodeSource()); return protectionDomain; } ...... // true if the name is null or has the potential to be a valid binary name private boolean checkName(String name) { if ((name == null) || (name.length() == 0)) return true; if ((name.indexOf('/') != -1) || (!VM.allowArraySyntax() && (name.charAt(0) == '['))) return false; return true; }
可以看出preDefineClass方法首先对类名进行了检查，发现以java作为一级包名，则抛出安全异常：禁止使用的包名！
这条安全异常是由Java类加载的“双亲委派模型”（详见这里）所导致的。在双亲委派模型中，由父加载类加载的类，下层加载器是不能加载的。本例中最高层加载器BootstrapClassLoader加载了classpath路径下所定义的java.*包内的类，而java.research包就不能由BootstrapClassLoader的下层加载器AppClassLoader加载了。这也是java安全机制中对于恶意代码所采取的防护措施。
