集合（ArrayList,HashMap,HashSet）扩容，hashmaphashset

CVTE一面

• 集合扩容问题
• hasMap \ hasTable
• 数据库引擎InnoDB MyASM
• MongoDB 和 MySql 的区别 为什么选用MongoDB
• 两个有序链表合并成一个有序列表
• 根据项目提问

感受：面试官很耐心，一直在引导我回答问题，无奈之前学过的东西实在是忘记的太多了。从现在开始要崛起了。加油！！

---

集合扩容：

ArrayList :

• 线性表存储
• 默认开辟大小为10的空间
• 当默认开辟空间不够的时候（比如此时需要add第11个元素），则以原数组的长度长度的1.5倍+1 ： (原长度*3)/2+1
• 重新确定数组容量，然后将第11个元素添加进去，申请空间并赋值
• 线程不同步（非线程安全）：如果多个线程同时访问一个ArrayList实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步，所以为了保证同步，最好的办法是在创建的时候完成加锁，保证线程同步。
  

List list = Collections.synchronizedList(new ArrayList(…));

HashMap:

• 存储结构hash表类似于桶：线性表+链表+红黑树
• 默认初始化容量16,装载因子默认为0.75
  

衡量hashMap主要性能的两个指标 :初始化容量,装载因子

初始化容量：是创建hash表的容量；
装载因子：是hash表在其容量自动增长之前，所能到达的多满的一种尺度，衡量的是hash表的空间使用程度。
    衡量描述：装载因子越大，散列表装填程度越高；反之越小
    实际情况：对于链表法的散列表来说
装载因子越大，则空间利用率越高，但是查找效率减少，原因是在桶内链表中进行查找需要便利整个链表。
装载因子越小，则散列程度越高，空间利用率越低，对空间造成严重浪费。

• 极限容量计算（桶存储数据达到该容量的时候进行扩容）

初始容量最小的2的n次方的值 * 装载因子  
eg: 默认初始容量16(桶的个数)，装载因子0.75，则极限容量计算：
            2^4 = 16 
            16 * 0.75 = 12 (极限容量)
eg:默认初始容量为20，装载因子不变0.75 ，极限容量计算：
            2^5 = 32 < 32 --->32
            32 * 0.75 = 24 (极限容量)

• 扩容:http://blog.csdn.net/gaopu12345/article/details/50831631

为什么扩容？
答 ： 保证hashMap的效率。
原因：随着hashMap中存储的元素越来越多，则发生碰撞的概率就会越来越大，链表的长度也会越来越长，那么就会hashMap的效率就会减低，为了保证hashMap的效率，则，就需要在存储容量达到一定值的时候进行扩容处理。

什么时候扩容？
答 ： 当达到临界值的时候进行扩容处理。
      临界值：容量*装载因子   
      eg :　容量：16  装载因子：0.75  ===>  临界值为：16 * 0.75 = 12
            即：当初始容量为16，装载因子为0.75的hashMap                                      存储容量到达12的时候进行扩容.
优化点：
原因：由于扩容是非常耗时的操作，为它需要重新计算元数据在新数组中的存储位置，并复制；
因此：如果我们预知hashMap中元素的个数，预设元素个数可以有效的提高hashMap的效率。

怎样扩容？
答：首先计算扩容大小：存储容量*2 ===>  16 * 2 = 32;
    申请线性表表空间，长度为 32;
    重新计算原来的数据在新数组中的位置，并进行复制；


扩多少？
答：桶和极限值都扩大为原来的2倍 16 * 2 = 32   |  12 * 2 = 24 

• 存储细节：首先判断key是否为null，若为null，则直接调用putForNullKey方法；如果不为空则，获取key的hash值，然后根据hash值搜索在table数组中的索引位置（使用indexFor），如果table中在该位置没有元素，则直接存储在该位置；如果table在该位置有元素，则比较是否存在相同的key(hash值和key都相同)则更新value，如果hash值相同，key值不同，则将节点插入链表头部。

保证数据存储分布均匀，减少碰撞次数

static int indexFor(int h, int length) {
        return h & (length-1);
    }

• 为什么要保证hashMap底层数组是2^n？

 原因：减少碰撞次数
 eg：假设底层数据长度为15，hashcode 有0,1,2,3,4,5
     则对应i计算为 ： h & (length-1)   ===> h & 14
         length-1      hashcode         index
     即：1110      &    0000     ===>   0000
         1110      &    0001     ===>   0000  (碰撞 1 次)
         1110      &    0010     ===>   0010  
         1110      &    0011     ===>   0010  (碰撞 2 次)
         ...           ....              ....
    由上述例子，可以发现，不管怎样 对应hashcode 最后一位都为0的都都访问不到 也就是说0001,0011,0101,0111,1001,1101,1111,1011 => 1,3,5,7,9,11,13,15为下标的元素都访问不到，浪费存储空间。

    而如果底层数据长度为2^n (eg :16)那么与之对应的index求取公式为 ：
            h & (16-1) = index 即  ： h & 1111 = index
    则对应的数据都能访问得到，减少了不同hash值的碰撞概率，并且能够使数据均匀分布，提高查询效率。

• 非线程安全的：https://m.aliyun.com/yunqi/articles/25347

表现：多线程访问 出死循环 =>  cpu利用率100%
原因：多线程访问，多个线程同时扩容的时候有可能造成链表闭环，出现死循环。
解决：加锁。使用Collections.synchronizedMap(map);
总结：在并发情况下选择非线程安全的容器是没有保障的。

• jdk 1.8优化：
  

jdk 1.7 时对于扩容时计算下标值的过程：
1.得到hashCode值 ： hash(key);
2.高位相与: h & (h >> 16)
3.取模: h & (legth-1)



jdk 1.8与1.7类似，但是在扩展的时候采用的2次幂扩展，
所以，元素的移动要么在原位置，要么在移动原位置的2次幂的位置。
不需要重新计算hash值，也可以直接定位原来的数据在新的数组中的位置，且分布均匀。


eg:1.7 计算hash值的过程：n = 16

h = hashCode()     : 1111 1111 1111 1111 1111 0000 1110 1010  得到hashCode

       h           : 1111 1111 1111 1111 1111 0000 1110 1010  计算hash值
    h >>> 16       : 0000 0000 0000 0000 1111 1111 1111 1111

hash = h^(h>>>16)  : 1111 1111 1111 1111 0000 1111 0001 0101  
      n - 1        : 0000 0000 0000 0000 0000 0000 0000 1111  取模求下标

   (n-1) & hash    : 0000 0000 0000 0000 0000 0000 0000 0101  

      index        ：  0101 = 5


eg：1.7余1.8扩容对比

n = 16
hash(key1) = 1111 1111 1111 1111 0000 1111 0000 0101
hash(key2) = 1111 1111 1111 1111 0000 1111 0000 0101

 1. jdk 1.7 中：

扩容前  n = 16                                               index_bin   index
      n - 1       ：0000 0000 0000 0000 0000 0000 0000 1111     
     hash(key1)   : 1111 1111 1111 1111 0000 1111 0000 0101   (0) 0101 => 5
     hash(key2)   : 1111 1111 1111 1111 0000 1111 0001 0101   (0) 0101 => 5
扩容后 n = 32
      n - 1       ：0000 0000 0000 0000 0000 0000 0001 1111     
     hash(key1)   : 1111 1111 1111 1111 0000 1111 0000 0101  (0)0 0101 => 5
     hash(key2)   : 1111 1111 1111 1111 0000 1111 0001 0101  (0)1 0101 => 5+16=21     


可发现：

0101 = 5  -->  resize() : 16 * 2 = 32  -->  0 0101 = 5          原位置
                                       --> 1 0101 = 21 = 5+16 原位置+oldCap

因此，当扩容的时候，jdk1.8不用像1.7一样重新计算hash值,
只需要看新增的是bit位是1还是0,
若为0则在新数组中与原来位置一样，
若为1则在新 原位置+oldCap 即可。

1.为什么要做这样的优化？（连地址法）

答：增加效率：
高效率的关键点有两个：减少冲突，合适的空间占用数量。

空间越多，即使差的hash算法，也会比较分散；
空间越小，即使好的hash算法，也会出现较多的碰撞；

因此提高其效率的关键点就是：在实际情况中确定桶的个数，并在此基础上设计好的hash算法减少碰撞，提高效率。


2.怎样优化？通过什么方式来控制map使得Hash碰撞的概率又小，哈希桶数组占用空间又少呢？

答案就是好的Hash算法和扩容机制。

jdk1.7 与1.8性能对比：
如果hash表的桶数合适，并且key经过hash算法得到的index全不相同，那么此时hash表的查找效率就为O(1);然而如果hash算法非常差，那么所有key计算出的结果就有可能全部集中在一个链表/一个红黑树中，那么此时的效率就为O(1)/O(lgn);

在hash表分布均匀的情况下jdk1.8 效率不是特别明显高于jdk1.7，红黑树的优势没有体现出来；

在hash表分布及其不均的情况下，
1.7 数据全都集中在某一个链表中，查找效率为O(n),且查询花费时间呈增长趋势
1.8 优化后，红黑树查询效率降低为O(lgn)，查询时间呈递减趋势

小结

HashSet

• HashSet底层实现是hashMap
• key 值比较 需要重写equals方法，重写hashcode方法
• value static final PRESENT
• 扩容机制和hashMap一样 16,0.75
• add的时候调用的是hashMap的put(key,PRESENT)；方法。