关于容器的一些基础知识点

1.hashmap与hashtable区别，hashmap的key可以是任何对象或数据类型吗，hashtable线程安全吗

hashtable是线程安全的，hashmap不是
hashtable不允许null（key，value都不行），hashmap都可
hashtable遍历使用Enumeration，hashmap使用Iterator
hashtable直接使用hashcode作为hash值，hashmap有自己的hash算法进行二次hash
hashtable的hash数组默认为11，扩容方式为old2+1,hashmap的数组大小默认为16，扩容*2

key必须是不可变对象，如果非要用可变对象做key的话，需要同时重写该类的hashCode()方法和它的equals()方法。

· 从源码可以得知，在插入元素的时候是先算出该对象的hashCode。如果hashcode相等话的。那么表明该对象是存储在同一个位置上的。

· 如果调用equals()方法，两个key相同，则替换元素

· 如果调用equals()方法，两个key不相同，则说明该hashCode仅仅是碰巧相同，此时是散列冲突，将新增的元素放在桶子上

一般来说，我们会认为：只要两个对象的成员变量的值是相等的，那么我们就认为这两个对象是相等的！因为，Object底层比较的是两个对象的地址，而对我们开发来说这样的意义并不大~这也就为什么我们要重写equals()方法

重写了equals()方法，就要重写hashCode()的方法。因为equals()认定了这两个对象相同，而同一个对象调用hashCode()方法时，是应该返回相同的值的！

hashtable是线程安全的，它的线程安全是在对应方法上添加synchronized关键字进行修饰。

2.hashmap多线程下的安全问题

put的时候导致的多线程数据不一致

比如有两个线程A和B，首先A希望插入一个key-value对到HashMap中，首先计算记录所要落到的 hash桶的索引坐标，

然后获取到该桶里面的链表头结点，此时线程A的时间片用完了，而此时线程B被调度得以执行，和线程A一样执行，

只不过线程B成功将记录插到了桶里面，假设线程A插入的记录计算出来的 hash桶索引和线程B要插入的记录计算出来的hash桶索引是一样的，那么当线程B成功插入之后，线程A再次被调度运行时，它依然持有过期的链表头但是它对此一无所知，

以至于它认为它应该这样做，如此一来就覆盖了线程B插入的记录，这样线程B插入的记录就凭空消失了，造成了数据不一致的行为。

resize而引起死循环（JDK1.8已经不会出现该问题）

这种情况发生在JDK1.7 中HashMap自动扩容时，当2个线程同时检测到元素个数超过数组大小 × 负载因子。

此时2个线程会在put()方法中调用了resize()，两个线程同时修改一个链表结构会产生一个循环链表（JDK1.7中，会出现resize前后元素顺序倒置的情况）。

接下来再想通过get()获取某一个元素，就会出现死循环。

1.7中的transfer方法会取出一个数组中的链表头将它插入到数组另一个位置的链表头上，所以会倒序

JDK8中HashMap的实现为数组+链表/红黑树；默认当链表的长度大于8之后，数据结构就变成红黑树

3.concurrenthashmap1.8

1.8中放弃了Segment臃肿的设计，取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现

4.hashmap与concurrenthashmap区别

hashmap非线程安全，concurrenthashmap线程安全

5.为什么hashmap数组大小要是2的n次方

hashMap的数组大小总是2的N次方，当length为2的n次方时，h&(length - 1)就相当于h对length取模，而且速度比直接取模快得多。

当length = 2^n时，length-1每一位都是1，不同的hash值发生碰撞的概率比较小，

这样就会使得数据在table数组中分布较均匀，查询速度也较快。

6.说出ArrayList,LinkedList的存储性能和特性

ArrayList底层实现是数组，查询操作复杂度O（1），插入复杂度O（n）；LinkedList底层实现是链表，查询你O（n），插入O（1）。

7.CopyOnWriteArrayList

它是线程安全的，采用的是写时复制的概念，也就是当执行add操作时，不在原数组上操作，而是new出一个原数组的副本，对副本进行修改操作后再将原数组指针指向修改后的数组。也就是说在修改时其他线程看到的是老的版本，保证的是弱一致性。为了保证add操作的线程安全，需要进行加锁（该类中采用的是Lock接口）。

8.ArrayList集合加入1万条数据，应该怎么提高效率

在newArrayList时提前指定容量为10000，这样可以避免添加元素过程中的扩容操作。