Java基础：集合类之ArrayList、HashMap简介

１、ArrayList

1.1 ArrayList的底层数据结构是什么？初始容量是多少？

ArrayList的底层数据结构是一个object类型的数组。

如果不指定初始容量的话，默认为长度为10的空数组。

1.2 ArrayList添加元素的过程是什么？会用到哪些方法？

答：
１、确保arraylist容量满足大小：ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
　　1.1 计算所需最小容量minCapacity：当到达最大容量后，更新为最新最小所需容量
　　1.2 确保容量满足所需大小：如果当前所需最小容量比当前元素总数多，那么需要扩容
　　　　1.2.1 新容量为原容量的1.5倍：newCapacity = oldCapacity + (oldCapacity >> 1);
　　　　1.2.2 通过Arrays.copyOf复制原数组：
　　　　　　　elementData = Arrays.copyOf(elementData, newCapacity);
２、数组添加新元素：elementData[size++] = e;

1.3 ArrayList是线程安全的么？保证list线程安全的方法有哪些？

arraylist不是线程安全的。
１）使用Vector替代
２）使用Collections包装：Collections.synchronizedList(new ArrayList<>())
３）使用CopyOnWriteArrayList替代

1.4 什么情况下会使用ArrayList，什么情况下会使用LinkedList?

由于ArrayList使用add方法时，会频繁调用System的arraycopy方法进行扩容，因此如果该list是以查询为主的话，使用ArrayList；

如果增删多的话，就不适合使用arrayList了，此时就可以使用LinkedList了，因为它的增删操作的时间复杂度为O(1)，而ArrayList的时间复杂度为O(n)，n为ArrayList的长度。

2、HashMap

2.1 HashMap的底层数据结构是什么？初始容量是多少？

jdk1.8之后，HashMap采用：数组 + 链表/红黑树 的方式来存储数据。

HashMap的底层数据结构是node类型的数组：transient Node[] table。默认初始容量大小为16，默认扩容因子是0.75。

2.2 HashMap添加元素的过程是什么？会用到哪些方法？

2.2.1 如何计算该key在数组中的位置？

计算该key所在数组的位置主要有３个步骤：

1. 通过key.hashCode()获取key的hashcode；
2. 通过(h = key.hashCode()) ^ (h >>> 16)进行高16位的位运算；
3. 通过(n - 1) & hash对计算的hash值取模运算，得到节点插入的数组所在位置。

说明：
１）为什么要将hashcode右移16位再进行异或运算？
这样做的好处是，可以将hashcode高位和低位的值进行混合做异或运算。这样，低位的信息中加入了高位的信息，等于说计算下标时把hash的高16位也参与进来了，掺杂的元素多了，那么生成的hash值的随机性会增大，减少了hash碰撞。
２）为什么HashMap的长度一般是2^n？
当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。

2.2.2 HashMap添加元素的过程？

HashMap的添加元素的过程：

1. 判断键值对数组table[i]是否为空/null，是则执行resize()扩容
2. 根据键key计算hash值得到插入数组的索引i，如果tab[i]== null则直接插入，执行第6步；如果tab[i] != null，执行第3步
3. 判断tab[i]的第一个元素与插入元素key的hashcode&equals是否相等，相等则覆盖，否则执行第4步
4. 判断tab[i]是否是红黑树节点TreeNode，是则在红黑树中插入节点，否则执行第5步
5. 遍历tab[i]判断链表是否大于8，大于8则可能转成红黑树（要求数组同时需要大于64），满足则在红黑树中插入节点；否则在链表中插入；在遍历链表的过程中如果存在key的hashcode&equals相等则替换即可
6. 插入成功，判断hashmap的size是否超过threshold的值，超过则扩容

2.3 HashMap是线程安全的么？保证map线程安全的方法有哪些？

１）使用HashTable替代
２）使用Collections包装：Collections.synchronizedMap(new HashMap());
３）使用ConcurrentHashMap替代