集合面试题

List

特点：

有序(存储和取出的顺序)

可重复

可通过索引值操作元素

ArrayList底层是数组，查询快，增删慢

线程不安全，效率高，初始化容量0，在第一次执行add方法之后，将容量设为10，

当长度超过容量的0.75时，扩容为15。底层数据结构elementData

Vector:线程安全，效率低，底层数据结构elementData，不适合高并发，初始化容量为10，当长度超过容量的0.75时，扩容到20

扩容，通过grow方法进行扩容，创建新的数据赋予新的长度，转移数据

LinkedList:底层是链表，查询慢，增删快、线程不安全，效率高，双向链表，初始化容量为0

Set

特点：无序（存储和取出的顺序），元素唯一、底层是哈希表

Hashset-保证元素的唯一性，hashcode(),equals()

初始化容量为0，第一次put的时候将容量设为16，当长度超过容量的0.75时，扩容为32

Hashset初始化是创建一个HashMap对象，然后将key通过hashcode方法获取哈希值，然后通过位运算获取到在数组中的存储位置，添加key的值，value值是默认present常量值，如果当前位置有元素，则进行equals对比，如果返回true则替换，如果返回false则添加新的key-value

Treeset:保证元素排序，允许插入Null，底层是二叉树

自然排序，让对象所属的类去实现comparable接口，无参构造函数，内部比较器

如果引用comparable接口，必须重写equals和hashcode方法

比较器接口，comparator，带参构造，外部比较器，优先级高

Map：映射关系，默认16，复合结构

K-v结构

Key是set结构，value时候collection结构

Hashmap,允许插入null的key和null的值

1.6版本：数组+链表,延迟创建

1.8版本：数组+链表+红黑树

put方法的逻辑：

如果HashMap未被初始化，则初始化；对key进行hash求值，然后通过位运算计算下标；如果没有碰撞，则直接放入桶中，如果发生碰撞，则进行equal比较，如果返回为true，则替换，如果返回为false，则以链表的方式链接到后面，并且位于链表的头部；如果链表长度超过阈值，就把链表转换为红黑树，调用红黑树的添加节点方法将数据添加到树中；如果链表的长度低于6，则将红黑树转化为链表；如果节点已经存在就替换；如果桶满了，就需要进行扩容,执行resize方法