Java集合面试题

常见的java集合？

主要分为三类，List  Map Set       列表 映射 集

集合相关的接口都在 java.util中

java集合的主要关系

List 特性： 存储的元素有序，可重复

Set 特性：存储的元素无序，不可重复

Map 特性：键值对映射结构的集合

List 

ArrayList和LinkedList的区别？  

ArrayyList基于数组实现  数组更便于查找。根据下标查找，支持随机访问。需要连续的内存空间，申请数组需要先定义要大小，存在一定的内存空间浪费。

LinkedList基于双向链表实现， 链表更利于增加删除。没法根据序号直接获取元素，不支持随机访问，需要存储前驱和后继。每个节点占用更多的内存。

Map

说一下HashMap的数据结构？

Jdk1.7数据结构是 数组+链表

Jdk1.8 数据结构 数组+链表+红黑树

数组用来存储数据元素，链表用来解决冲突，红黑树为了提高查询效率

数据元素通过散列函数，映射到桶数组对应索引的位置

如果发生冲突，从冲突位置拉一个链表，插入冲突的元素

如果链表长度 > 8 & 数组大小>=64 链表转为红黑树

如果红黑树节点个数< 6  转为链表

哈希函数

Set

什么集合有序且去重？

LinkedHashSet是基于linkedHashMap实现的，有序去重的集合

LinkedHashSet可以存储null值，是线程不安全的

底层有序实现机制：底层是LinkedHashMap 底层维护了一个数据+双向链表，根据元素的hashcode值来决定存储位置，同时使用链表来元素的插入顺序。

适用的场景：先进先出FIFO的场景