面试流水（二）

arraylist和hashmap容易混淆的点

初始化

arraylist初始化默认容量是10，扩容条件是放不下才扩容，也就是扩容因子是1（或者没有扩容因子这个说法），扩容大小1.7之前是1.5N+1，之后是1.5N(N是原先大小)

hashmap初始化16，扩容因子是0.75，扩容大小是翻倍，16-32-64.。。。（数组大小为2的幂，减少hash冲突）

Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1

arraylist是线程不安全的，vector是安全的，它在arraylist的增删改方法上加了synchronied，但要明确vetor是先出来的，与hashtable一样，先有vector、hashtable这种线程安全的老一辈才有的arraylist和hashmap(为了增加性能实现了线程不安全的类)

arraylist与vector对比，

相同点：

1、都是数组实现的list，方法差不多，扩容都是 创建新数组，然后拷贝数组，丢弃原数组（交给垃圾回收）

2、初始化容量都是10

不同点：

1、线程安全方面

2、arraylist初始化是懒加载的（hashmap也是懒加载的），第一个add才分配空间，vector在new的时候就分配好了

3、arraylist扩容基本是1.5倍方式 10-15-，vector翻倍 10-20-30

hashmap扩容

元素在扩容后的数组中要么是留在原来的下标处，要么是在原位置基础上再移动2的N次幂

========================

个人思考

1、hashmap最好用string充当key，原因是string重写了hashcode方法。

如果用对象（hashcode是地址），可能值相等但hashcode肯定不同，浪费空间，多存了几份。

2、string为什么没有用md5和sha1常用的散列hash算法，原因是节省计算时间，因为无需加密。使用质数31来生成hashcode h = 31 * h + val[i]; // val[0]*31^(n-1) + val[1]*31^(n-2) + ... + val[n-1]

3、哈希值是32位的（一个int 4个字节[一个字节8位]），

hashmap找桶  获得key的hash=》高16位要和底16位做与=》16位在和数组长度的2进制区与（其实就是模运算），数组长度最大不适合超过2的16次【65536】（一般也超不过，没那么大）

4、扩容的过程是数组拷贝，但为了少影响原来的hash（有的不变，有的变成2^n+源地址），容量应该增加到右边，左边是原先的数组不变，桶中的部分节点可能被挪到新的桶（新桶的索引=2^n+旧桶的索引）

2^n=增加的容量，如从16到32，那么n=4;又如原先某个节点挂在2桶后，现在可能挂着18桶下，没准还是老大（第一个）。

我们使用2的N次幂的扩容机制，所以元素在扩容后的数组中要么是留在原来的下标处，要么是在原位置基础上再移动2的N次幂

这有点费解，我们看一下下面的寻址过程：

上图的（a）(b)分别对应扩容前和扩容后的hash&(n-1)也就是寻找元素存放位置的过程，可以看到扩容后的n-1相比扩容前的n-1多了一高位1，则再进行&运算时，key1和key2也多了一高位参与运算：

所以，原hash值新增参与运算的的那一bit如果是0，则在新数组中的下标不变，如果原hash值新增参与运算的那一bit是1，则在新数组中的下标为：原索引+原数组容量。

因此现在JDK只需要判断每个元素的hash值新增参与运算的那一bit是1还是0就可以给每个元素确定新数组中的位置，这样做可以巧妙的把原来处于同一个下标索引处的多个元素在新的数组中分散开来，如上面的（a）(b)过程，（a）过程中key1和key2虽然hash值不同，但是运算出了同一个索引值，所以存在同一个位置，但是在（b）过程中由于扩容的影响多了1bit参与运算，所以key1和key2就被分配到了不同的索引处