Java面试系列

Java面试题系列

前言

记录常见的面试题目，针对不同面试题给出解答方法。

一、JDK1.8之前（数组+链表）

1)new HashMap

• 创建一个空对象，如不指定数组长度，默认数组长度16；如果指定了数组长度，会找一个和该数组临近的2的n次方数据做为长度。
• 数组中存入的是Entry<k,v>的entry对象。
• 创建的时候还加入了0.75的负载因子，这个负载因子和扩容的rehash()方法有关。

2）map.put(k,v)方法

• 首先，先判断key存放的位置，判断出位置了，然后将entry对象放到数组对应位置中。
• key通过hashcode方法（hashmap内部的hashcode扰动函数）算出hash值，然后通过**(数组长度-1)&hash值，得到一个位于0-15区间的数字**，这就是对应数组的下标了。
• 如果equals()方法为true，则说明就是同一个key，value值就会覆盖。
• 如果equals()方法为false，则不是同一个key，就在数组对应索引位置变为链表存储心的Entry<key,value>.
• 上一步说到的链表是拉链法：将链表和数组相结合，也就是说创建一个链表数组，数组中每一格就是一个链表，若遇到哈希冲突，则将冲突的值加到链表中即可。
• 插入链表的时候是首插法，也就是链表中的新元素在旧元素前面，因为都会认为新存入的数据是被应用最多的，所以新数据排在旧数据前面。

3）map.get(k)实现原理

• 先调用k的hashCode()方法得出hash值，并通过hash值&(数组长度-1)运算转转换成数组的下标。
• 在通过数组下标快速定位到某个位置上，这个位置上什么都没有，则返回null。
• 如果这个位置上有单向链表，那么它就会拿着参数K和单向链表上的每一个节点的K进行equals，如果所有equals方法都返回false，则get方法返回null。如果其中一个节点的K和参数K进行equals返回true，那么此时该节点的value就是我们要找的value，get方法最终返回这个要找的的value。

二、JDK1.8之后（数组+链表+红黑树）

1）new HashMap

• JDK1.8以后只有在put数据的时候才会创建对象，而且每个数组中存的是node对象。
• 如果不指定数组长度，默认数组长度16，如果指定了数组长度，会找一个和该数组临近的2的n次方数据做为长度。
• 数组中存入的是Node<k,v>的node对象。
• 创建的时候还加入了0.75的负载因子，这个负载因子和扩容rehash()方法有关。

2）map.put(k,v)方法

• 和JDK1.8之前不同的是，但是这里的链表当打到一定程度后会转为红黑树。
• 如果链表的长度超过8则转为红黑树，也就是该位置存储的是数组+红黑树结构。
• 当链表长度小于等于6时又变为链表，也就是该位置存储的是数组+链表结构。
• 链表法采用的是尾插法，也就是新的元素排在当前元素的后面。
• JDK1.8的时候，数组中存在的是ndoe对象，而不是entry对象，node对象包括三部分（这里博主没找到这幅图，有知道的小伙伴评论留言告知一下）。

3）map.get(k)原理

• 和JDK1.8之前一样：
• 先调用k的hashCode()方法得出hash值，并通过hash值&(数组长度-1)运算转转换成数组的下标。
• 在通过数组下标快速定位到某个位置上，这个位置上什么都没有，则返回null。
• 如果这个位置上有单向链表，那么它就会拿着参数K和单向链表上的每一个节点的K进行equals，如果所有equals方法都返回false，则get方法返回null。如果其中一个节点的K和参数K进行equals返回true，那么此时该节点的value就是我们要找的value，get方法最终返回这个要找的的value。

2.JDK1.8之后（数组+链表+红黑树）

1）new HashMap

• JDK1.8以后只有在put数据的时候才会创建对象，而且每个数组中存的是node对象。
• 如果不指定数组长度，默认数组长度16，如果指定了数组长度，会找一个和该数组临近的2的n次方数据做为长度。
• 数组中存入的是Node<k,v>的node对象。
• 创建的时候还加入了0.75的负载因子，这个负载因子和扩容rehash()方法有关。

2）map.put(k,v)方法

• 和JDK1.8之前不同的是，但是这里的链表当打到一定程度后会转为红黑树。
• 如果链表的长度超过8则转为红黑树，也就是该位置存储的是数组+红黑树结构。
• 当链表长度小于等于6时又变为链表，也就是该位置存储的是数组+链表结构。
• 链表法采用的是尾插法，也就是新的元素排在当前元素的后面。
• JDK1.8的时候，数组中存在的是ndoe对象，而不是entry对象，node对象包括三部分。

3）map.get(k)原理

• 和JDK1.8之前一样：
• 先调用k的hashCode()方法得出hash值，并通过hash值&(数组长度-1)运算转转换成数组的下标。
• 在通过数组下标快速定位到某个位置上，这个位置上什么都没有，则返回null。
• 如果这个位置上有单向链表，那么它就会拿着参数K和单向链表上的每一个节点的K进行equals，如果所有equals方法都返回false，则get方法返回null。如果其中一个节点的K和参数K进行equals返回true，那么此时该节点的value就是我们要找的value，get方法最终返回这个要找的的value。