一、数组的索引为什么从0开始？

寻址公式： 数组的首地址+索引乘以存储数据的类型大小
在根据数组索引获取元素的时候，会用索引和寻址公式来计算内存所对应的元素数据。如果数组的索引从1开始，寻址公式中，就需要增加一次减法操作（数组的首地址-1），对于CPU来说就多了一次指令，性能会降低。

二、数组进行查找操作的时间复杂度

• 如果是通过下标，查询的时间复杂度是O(1)
• 如果不通过下标，和使用的查找方式有关
  – 从头往后顺序查找是O(n)
  – 排序后，使用二分查找发是O(log)

三、数组进行修改操作的时间复杂度

进行插入或者修改操作是，为了保证数组的连续性，需要挪动元素，平均复杂度是O（n）

四、ArrayList的底层实现原理

• ArrayList底层是用动态的数组实现的
• ArrayList初始容量为0，当第一次添加数据的时候才会初始化容量为10
• ArrayList在进行扩容的时候是原来容量的1.5倍，每次扩容都需要拷贝数组
• ArrayList在添加数据的时候
  1. 确保数组已使用长度（size）加1之后足够存下下一个数据
  2. 计算数组的容量，如果当前数组已使用长度+1后的大于当前的数组长度，则调用grow方法扩容，扩容为原来的1.5倍
  3. 确保新增的数据有地方存储之后，则将新元素添加到位于size的位置上。
  4. 返回添加成功布尔值。

五、List list = new ArrayList(10)中list扩容了几次

未进行扩容，该语句只是声明了一个长度为10的ArrayList。

六、数组和List之间如何转换

• 数组转List
  – 调用Arrays.asList()方法

// 转换完成后，进行的修改会影响生成的List,因为只进行了地址的引用
String[] strArr = {"1","2"};
List<String> stringList = Arrays.asList(strArr);

• List转数组
  – 调用list的toArray方法（）

// 转换完成后，进行的修改不会影响生成的Array数组，因为底层进行了数据的拷贝
List<String> list = new ArrayList(n);
String[] toArray = list.toArray(new String[list.size()]);

七、单向链表和双向链表的区别是什么

• 单向链表只有一个方向，结点只有一个后继指针next。
• 双向链表它支持两个方向，每个结点不止有一个后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点
• 单项链表的增删查操作时间复杂度在头结点是O(1)，其他是O(n)。
• 双向链表的增删查操作时间复杂度在头尾结点是O(1)，其他是O(n)，如果给定节点，则增删是O(1)

八、ArrayList好LinkedList区别是什么

• ArrayList是动态数组的数据结构实现； LinkedList是双向链表的数据结构实现
• ArrayList按照下标查询的时间复杂度O(1）；LinkedList按照下标查询的时间复杂度O(n)
• ArrayList插入或者删除元素的速度是O(n)；LinkedList插入或者删除元素的速度是O(1)
• ArrayList底层是连续的数组，占用内存更小；LinkedList是双向链表需要存储数据，和两个指针，更占用内存

线程方面
ArrayList和LinkedList都不是线程安全的，想要保证安全有两个方法

1. 在方法内使用，局部变量大多数情况下是线程安全的（在内部开多线程或者引用了共享的变量就不安全了）
2. 使用线程安全的ArrayList和LinkedList（用Collections.synchronizedList方法包一下）

// 性能会下降
List<Object> syncArrayList = Collections.synchronizedList(new ArrayList<>());
List<Object> syncLinkedList = Collections.synchronizedList(new LinkedList<>());

九、说一说二叉树和二叉搜索树

二叉树

1. 每个节点最多有两个“叉”，分别是左子节点和右子节点。
2. 不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。
3. 二叉树每个节点的左子树和右子树也分别满足二叉树的定义

二叉搜索树

1. 二叉搜索树(Binary Search Tree,BST)又名二叉查找树，有序二叉树
2. 在树中的任意一食节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值
3. 没有键值相等的节点
4. 通常情况下二叉树搜索的时间复杂度为O(logn)

十、说一说红黑树

1. 红黑树也是一种自平衡二叉树
2. 红黑树的增删查时间复杂度都是O(logn)
3. 红黑树节点要么是红色要么是黑色
4. 红黑树节点根节点都是黑色，叶子结点也是黑色且为空值
5. 红黑树红色节点的子节点都是黑色
6. 从任意节点到叶子节点的所有路径都包含相同数目的黑色节点
7. 红黑树所有规则都是为了保证平衡

十一、说一说散链表

1. 散列表(Hash Table)又名哈希表/Hash表，是根据键(Key)直接访问在内存存储位置值(Value)的数据结构。是由数组演化而来的，利用了数组支持按照下标进行随机访问数据
2. 散列表的key是根据hash计算得来的，相同和key算出来的hash值一定相同。当不同的key计算出相同的hash值时，就会发生散列冲突，又名哈希碰撞
3. 解决散列表冲突方方法是链表法，又名拉链。存储hashkey数组的每个下标位置称之为桶(bucket)或者槽(slot)，每个桶会对应一条链表。hash冲突后的元素都放到相同的桶对应的链表中或红黑树中。

十二、说一说HashMap的实现原理

1. HashMap的底层的数据结构是hash表，即数组加链表或数组加红黑树
2. 当我们往HashMap中put元素时，利用寻址算法算出当前对象的元素在数组中的下标。此时如果出现hash值相同的key会再次对key进行比较：如果key相同，则覆盖原始值；如果key不同，则将当前的key-value放入链表或红黑树中
3. 获取时，寻址算法得到对应的桶索引位置，在进一步判断key是否相同，从而找到对应值。
4. jdk1.8之后当链表的长度大于8且数组长度大于64时，会转换为红黑树；扩容resize()时，红黑树拆分成的树的结点数小于等于临界值6个，则退化成链表

十三、说一说HashMapput方法的具体流程

1. 判断键值对数组table是否为空或为null,否则执行resize()进行扩容(初始化)
2. 根据寻址算法得到对应的桶索引位置table[i]
3. 判断table[i]==null,条件成立，直接新建节点添加
4. 如果table[i]==null,不成立
   4.1 判断table[i的首个元素是否和key一样，如果相同直接覆盖value
   4.2 判断table[i]是否为treeNode,即table[i]是否是红黑树，如果是红黑树，则直接在树中插入键值对
   4.3 否则遍历table[i]，链表的尾部插入数据，然后判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，若遍历过程中若发现key已经存在则直接覆盖value
5. 插入成功后，判断实际存在的键值对数量size是否超过了最大容量threshold(数组长度*0.75)，如果超过，进行扩容。

十四、说一说HashMap的扩容机制

1. 在添加元素或初始化的时候需要调用resize方法进行扩容，第一次添加数据初始化数组长度为16，以后每次扩容都是达到了扩容阈值（数组长度*0.75）
2. 每次扩容的时候，都是扩容之前容量的2倍；
3. 扩容之后，会新创建一个数组，需要把老数组中的数据挪动到新的数组中
   – 没有hash冲突的节点，则直接使用e.hash&(newCap-1)计算新数组的索引位置（newCap是新数组长度）
   – 如果是红黑树，走红黑树的添加
   – 如果是链表，则需要遍历链表，可能需要拆分链表，判断(e.hash&oldCap)是否为0，为0该元素的位置停留在原始位置，否则移动到原始位置+增加的数组大小这个位置上（oldCap是老数组长度）

十五、说一说HashMap的寻址算法

1. 计算对象的hashCode()
2. 再进行调用hash()方法进行二次哈希，hashcode值右移16位再异或运算，让哈希分布更为均匀
3. 最后(capacity-1)&hash得到索引。这个运算相当于hash%capacity且更快，但是这个只对2的幂数生效

十六、为何HashMap的数组长度一定是2的次幂？

1. 计算索引时效率更高：如果是2的n次幂可以使用位与运算代替取模
2. 扩容时重新计算索引效率更高：hash&oldCap==0的元素留在原来
   位置，否则新位置=旧位置+oldCap

十七、说一说hashmap在jdk1.7情况下的多线程死循环问题

在jdk1.7的hashmap中在数组进行扩容的时候，因为链表是头插法，在进行数据迁移的过程中，有可能导致死循环

比如说，现在有两个线程
线程一：读取到当前的hashmap数据，数据中一个链表，在准备扩容时，线程二介入
线程二：也读取hashmap，直接进行扩容。因为是头插法，链表的顺序会进行颠倒过来。比如原来的顺序是AB，扩容后的顺序是BA，线程二执行结束。
线程一：继续执行的时候就会出现死循环的问题。
线程一先将A移入新的链表，再将B插入到链头，由于另外一个线程的原因，B的next指向了A，所以B->A->B,形成循环。
当然，JDK8将扩容算法做了调整，不再将元素加入链表头（而是保持与扩容前一样的顺序），尾插法，就避免了jdk7中死循环的问题。