集合面试题

集合

Collection

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:保证元素排序，底层是二叉树

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

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

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

Queue

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方法

为什么HashMap是线程不安全的？

同时put发生碰撞时，造成数据丢失

同时put扩容导致数据丢失

死循环造成CPU100%【扩容时产生；仅在JDK7中存在；原因：造成链表的死循环】

如何有效的减少碰撞？

扰动函数：促使元素位置分布均匀，减少碰撞的机率

使用final对象，并采用合适的equals和hashcode方法

扩容问题：

多线程环境下，调整大小会存在竞争关系，容易造