Day08

1. 请你说说HashMap底层原理

1. 在1.8之前，HashMap的底层是数组加链表，在1.8之后是数组+链表+红黑树；
2. 它的put流程是：基于哈希算法来确定元素位置，当我们向集合存入数据时，他会计算传入的key的哈希值，并利用哈希值绝对值再根据集合长度取余来确定元素位置，如果这个位置已经存在其他元素了，就会发生哈希碰撞，则hashmap就会通过链表将这些元素组织起来，如果链表的长度达到8并且数组长度大于64，就会转化为红黑树，从而提高查询速度。
3. 扩容机制：HashMap中的数组的默认初始容量为16，当达到默认的负载因子0.75时，会以2的指数倍进行扩容。
4. HashMap是非线程安全的，在多线程环境下建议使用ConcurrentHashMap

2. 请你说说HashMap和Hashtable的区别

1. HashTable在实现Map接口时保证了线程安全性，而HashMap是非线程安全的。所以，HashTable的性能不如HashMap，因为为了保证线程安全性它牺牲了一些性能。
2. HashTable不允许存入null，无论是以null作为key或value，都会引发异常。而HashMap是允许存入null的，无论是以null作为key或value，都是可以的。
3. 虽然HashTable是线程安全的，但仍然不建议在多线程环境下使用HashTable。因为它是一个古老的API，从Java1.0开始就出现了，它的同步方案还不成熟，性能不好。如果要在多线程环境下使用HashMap，建议使用ConcurrentHashMap。它不但保证了线程安全，也通过降低了锁粒度提高了并发访问的性能。

3. HashMap是线程安全的吗？如果不是该如何解决？

1. HashMap不是线程安全的，在添加数据时，会根据key和value计算出底层数组中的位置，然后封装成entry对象插入，但由于HashMap并没有做对应的线程安全处理，所以如果恰好两个线程同时操作的话，就有可能将其中一个数据覆盖掉。
2. 解决方法是可以在操作这个HashMap时手动上锁，也可以通过Lock和Synchronized关键字。当然更推荐直接使用java提供的ConcurrentHashMap，其内部采用了Lock来解决线程安全问题，并且底层结构也进行了一些变动，上锁的时候只会锁对应下标的元素，不会对其他位置造成影响，既保证了线程安全，有保证了性能

4. 请你说说ConcurrentHashMap

1. ConcurrentHashMap的底层数据结构与HashMap一样，也是采用“数组+链表+红黑树”
2. 采用锁定头结点的方式降低了锁粒度，以较低的性能代价保证了线程安全
3. 实现机制：1.初始化数组或头结点时，ConcurrentHashMap并没有加锁，而是CAS的方式进行原子替换；2.插入数据时会进行加锁处理，但锁定的不是整个数组，而是槽中的头结点。所以ConcurrentHashMap中锁的粒度是槽，而不是整个数组，并发的性能很好
4. 扩容时会进行加锁处理，锁定的仍是头结点。并且支持多个线程同时对数组扩容，提高并发性能
5. 在扩容过程中依然支持查找操作

5. 说说你对ArrayList的理解

1. ArrayList是基于数组实现的，它的内部封装了一个Object[]数组。通过默认构造器创建容器时，该数组先被初始化为空数组，之后在首次添加数据时再将其初始化为长度为10的数组。
2. 我们也可以使用有参构造器来创建容器，并通过参数来显式指定数组的容量，届时该数组被初始化为指定容量的数组。
3. 如果向ArrayList中添加数据造成了超出数组长度限制，则会触发自动扩容，新数组的长度是原数组的1.5倍
4. List提供了listIterator()方法，增强了迭代能力。iterator()方法返回Iterator迭代器，listIterator()方法返回ListIterator迭代器，并且ListIterator是Iterator的子接口。ListIterator在Iterator的基础上，增加了向前遍历的支持，增加了在迭代过程中修改数据的支持