Java集合面试-1
目录
Java集合框架
- 主要分为Collection和Map两类
- Collection分为List、Set、Queue。List包含ArrayList、LinkedList、Vector、Stack。Set包含HashSet、TreeSet、LinkedHashSet。Queue包含PriorityQueue、Deque。
- Map包含HashMap、TreeMap、LunkedHashMap、HashTable、ConcurrentHashMap
说说几个集合之间的区别
- List是有序的，元素可重复的。
- Set是无序的，元素不可重复，但是TreeSet是有序的。
- Map是键值对的集合，键不可重复，值可以重复。
- Queue是一个先进先出的队列，元素有序且可以重复。
如何选用集合
- 需要根据键获取值就选择Map，需要排序就选择TreeMap，不需要排序就选择HashMap，需要确保线程安全就选择ConcurrentHashMap。需要存储列表就选用List，需要去重就选择Set。
ArrayList和Array的区别
- ArrayList是动态扩容的，创建时不需要指定大小，会自动扩容。Array是静态的，创建的时候就需要指定大小，且大小不可变。
- ArrayList可以使用泛型来进行约束。
- ArrayList可以使用插入、删除、排序等集合方法，Array不能使用，只能通过下标的方式访问元素。
- ArrayList存储的只能是对象，对于基本类型的数据需要存储其包装类。Array可以存基本类型也可以存对象。
ArrayList的操作复杂度
- 头插O(n)，因为需要将所有元素向后移动一位
- 尾插入，当数据空间足够时，直接在尾部添加即可，时间复杂度为O(1)，当数据空间不足时，需要扩容，时间复杂度为O(n)
- 中间插入，因为平均移动的元素为n/2，所以时间复杂度为O(n)
- 头部删除操作，时间复杂度为O(n)
- 尾部删除操作，时间复杂度为O(1)
- 中间删除操作，时间复杂度为O(n)
- 查找操作，通过下标查找，时间复杂度为O(1)
LinkedList的操作复杂度
- 头插/删都是O(1)
- 尾插/删都是O(1)
- 中间插/删都是O(n)，因为需要将指针移动到对应的位置再进行操作。
- 查找操作，通过遍历查找，时间复杂度为O(n)
ArrayList和LinkedList的区别
- 二者都是线程不安全的
- ArrayList使用的是Object数组，LinkedList使用的是双向链表
- ArrayList支持随机访问，可以直接通过下标进行访问，但是LinkedList不支持随机访问，需要遍历到对应的位置才能访问。
- ArrayList采用数组存储，所以插入删除都是受元素位置影响的，而LinkedList采用链表存储，在头部和尾部进行插入删除操作是不受元素位置影响的，但是中间操作会受元素位置影响。
ArrayList的动态扩容机制
- 首先使用无参的构造函数创建一个ArrayList时实际上创建的是一个空的数组，没有任何元素，也就是length为0。
- 每次执行add操作时会先计算出容纳所有元素所需要的最小容量，如果是空数组第一次添加元素，最小容量就是默认的容量10。
- 接着会判断最小容量是否可以容量当前所有的元素，也就是目前实际分配的长度，如果最小容量减去实际分配的长度大于0就会触发扩容。
- 在扩容逻辑中会先记录当前的数组长度作为旧长度，接着将旧长度增加1.5倍左右作为新的长度（使用旧的长度+旧长度向右移1位计算的）。
- 如果新的长度依然小于最小容量就直接使用最小容量作为扩容后的长度。
- 如果新的长度大于MAX_ARRAY_SIZE，会再判断一次最小容量是否也大于MAX_ARRAY_SIZE，如果也大于则返回Integer.MAX_VALUE，否则返回MAX_ARRAY_SIZE。
- 扩容结束后会创建一个新的数组将原来的元素按顺序拷贝到新的数组并将elementData的引用指向新的数组，最后回到add方法将新元素添加即可。