1、HashMap的底层数据结构是什么？

哈希表底层数据结构实际上就是数组。它利用数组支持按照下标随机访问的时候，时间复杂度是o(1)的特性。我们通过哈希函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，我们使用相同的哈希函数，将键值转化为数组下标，从对应的数组下标的位置取出数据。

2、JDK1.8中对hash算法和寻址算法是如何优化的？

//JDK1.8以后的HashMap部分源码
static final int hash(Object key){
	int h;
	return (key == null)?0(h=key.hashCode())^(h>>>16);
	}

hash算法的优化：
对每个hash值，将他的高低十六位进行异或操作，让低十六位同时保持了高低十六位的特征。同时也可以避免一些hash值后续出现冲突。

寻址算法的优化：
寻址算法就是对长度为n的数组取模，得到在数组中的位置。根据数学规律，对n取模，就是和n-1进行与运算。与运算的效率远远高于求模运算，所以采用与运算。而数组的长度通常没有很大，所以高位与出来都是0，如果不进行hash算法优化，那么高位的信息就会丢失。
综上就是JDK8的hash算法的优化。

3、HashMap是如何解决hash碰撞问题的？

hash冲突问题， 链表 + 红黑树 ，o(n)和o(logn)
当发生hash冲突时，会在数组中重复的位置放置一个链表，然后将value的值加入链表中。但是由于链表的查询时间复杂度是o(n)，所以当链表的变的很长的时候，我们获取值会变的很慢。为了提升性能，当链表的长度到达一定值时，我们将链表转换成红黑树，红黑树的查询时间复杂度是o(logn),提升性能。

4、说说HashMap是如何进行扩容的？

hashMap底层默认是一个数组，当这个数组满了以后，就会自动扩容，变成一个更大的数组，可以在里面放更多的元素。
hashMap的默认大小是16位的，当16存满以后就会进行2倍扩容，变成长度为32的数组。这个时候就要对原先数组中存储的元素进行rehash，即将他们的哈希值和（32-1）进行与运算，原本在长度为16的处于相同位置的几个元素，可能就要变换位置，不在同样的位置了。
为什么进行两倍扩容？
两倍扩容就是二进制位的上一位变成1，比如
0000 0000 0000 1111
变成
0000 0000 0001 1111
在进行rehash操作时，判断二进制结果是否多了一个bit的1，如果没多，那么就是原来的index,如果多了，那么就是index + oldcap，通过这个方式，避免rehash的时候，进行取模运算，位运算的性能更高。
注意，我们最好在使用hashMap的时候能够指定合适的hashMap的大小，来避免扩容，这样就能避免rehash操作，影响性能。

5、ArrayList,LinkedList,TreeMap,LinkedHashMap,HashSet等底层的数据结构和各自的优势和劣势？

List: List是用来存储数据的集合，也就是容器。它的特点是支持存储重复的元素，是有序的。（这里的有序指的是取出的顺序和存储的顺序是相同的。）

• ArrayList：底层数据结构是数组。特点是增删慢，但是查询很快。因为每次增删的时候都会创建一个新的符合大小的数组，然后将原来的数据拷贝到新数组中，然后删除原来的数组。
• LinkedList: 底层数据结构是链表。（java中创建队列和双端队列可以使用它）特点是增删很快，但是查询相对ArrayList来说比较慢。其实就是链表和数组的结构造成的不同。
  Set:set也是用来存储数据的集合，也是一种容器。它的特点是不支持重复元素，实际上java中的set在底层都是通过map来实现的，就是取map中key的那一列，所以只需要理解下面的map就能理解set。

Map

• HashMap:这个容器要非常熟悉，上面有详细的讲述，这里就不赘述了
• LinkedHashMap: 用链表实现的HashMap,是有序的（存入和取出的顺序是一样的），它的底层是哈希表和链表的结合，首先使用散列函数找到要存储的位置，然后用链表将他们连接起来。简单理解就是定义了一个双向链表，将entry按照顺序连接起来，这样就保证了有序性。
• TreeMap:底层是红黑树。通过一个比较器，可以自己定义，然后结果按照红黑树的原则找到合适的位置，具体关于红黑树的理解参见另一篇博客：平衡二叉搜索树、二三树与红黑树

6、equals和hashcode之间的关系？

• equals 相同hashcode一定要相同
• hashcode相同 equals不一定相同