1、 常用数据结构简介

a、数组：顺序存储，随机访问      链表：链表存储，顺序访问
b、栈，分为栈顶和栈底，遵循先进后出原则
c、队列 ，一个线性表，像排队一样，受约束控制，遵循先进先出原则
d、树：二叉树、平衡二叉树、大顶堆，小顶堆等
e、图：最短路径，关键路径

2、 并发集合了解哪些？

并发List
Vector和CopyOnWriteArrayList是两个线程安全的List，Vector读写操作都用了同步，相对来说更适用于写多读少的场合，CopyOnWriteArrayList在写的时候会复制一个副本，对副本写，写完用副本替换原值，读的时候不需要同步，适用于写少读多的场合。

并发Set
CopyOnWriteArraySet基于CopyOnWriteArrayList来实现的，只是在不允许存在重复的对象这个特性上遍历处理了一下。

并发Map
ConcurrentHashMap是专用于高并发的Map实现，内部实现进行了锁分离，get操作是无锁的。

并发的Queue
在并发队列上JDK提供了两套实现，一个是以ConcurrentLinkedQueue为代表的高性能队列，一个是以BlockingQueue接口为代表的阻塞队列。ConcurrentLinkedQueue适用于高并发场景下的队列，通过无锁的方式实现，通常ConcurrentLinkedQueue的性能要优于BlockingQueue。BlockingQueue的典型应用场景是生产者-消费者模式中，如果生产快于消费，生产队列装满时会阻塞，等待消费。

并发的Dueue
Queue是一种双端队列，它允许在队列的头部和尾部进行出队和入队的操作。Dueue实现类有非线程安全的LinkedList、ArrayDueue和线程安全的LinkedBlockingDueue。LinkedBlockingDueue没有进行读写锁的分离，因此同一时间只能有一个线程对其操作，因此在高并发应用中，它的性能要远远低于LinkedBlockingQueue，更低于ConcurrentLinkedQueue。

并发锁重入锁ReentrantLock
ReentrantLock是一种互斥锁的实现，就是一次最多只能一个线程拿到锁；

读写锁ReadWriteLock
读写锁有读取和写入两种锁，读取锁允许多个读取的线程同时持有，而写入锁只能有一个线程持有。

条件Condition
调用Condition对象的相关方法，可以方便的挂起和唤醒线程。

3、 列举java的集合以及集合之间的继承关系

java 集合框架由两个根接口Collection 和map构成：

QQ截图20180629100805.png

QQ截图20180629100920.png

4、 集合类以及集合框架

如上图，基本已经涵盖相应的集合类和框架内容，在工作中用得比较多得是ArrayList, LinkList,HashSet和HashMap .由于我们可能需要在多线程环境中对我们定义的数据进行并发访问，所以我们必须确保我们当前得数据是同步的或者我们在需要调用的地方进行加锁，但synchronized关键字和Lock类等都增加了代码复杂度而且容易出错，还有一种更为便捷的办法就是我们直接使用线程安全的数据结构或者用系统的Collections对其进行包装让不安全的成为安全的，所以这里我们需要去了解上图中的一些类
    在List链表中，ArrayList 和LinkList 都是线程不安全的；Vector是线程安全的，ArrayList和Vector类的底层都是基于数组来储存集合元素，封装了一个动态的Object[]数组，是一种顺序存储的线性表；LinkedList是一个链式存储的线性表，本质上是一个双向链表，它不仅实现了List接口还实现了Dueue接口(双端队列，既具有队列的特征，也具有栈的特征)
    set集合代表不重复的集合；而queue是一种队列

5、 容器类介绍以及之间的区别（容器类估计很多人没听这个词，Java容器主要可以划分为4个部分：List列表、Set集合、Map映射、工具类（Iterator迭代器、Enumeration枚举类、Arrays和Collections），具体的可以看看这篇博文 Java容器类）

ArrayList

ArrayList定义如下：

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList是一个动态数组，也是我们最常用的集合。它允许任何符合规则的元素插入甚至包括null。每一个ArrayList都有一个初始容量：

private static final int DEFAULT_CAPACITY = 10;

随着容器中的元素不断增加，容器的大小也会随着增加。在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作。所以如果我们明确所插入元素的多少，最好指定一个初始容量值，避免过多的进行扩容操作而浪费时间、效率。
size、isEmpty、get、set、iterator 和 listIterator 操作都以固定时间运行。add 操作以分摊的固定时间运行，也就是说，添加 n 个元素需要 O(n) 时间（由于要考虑到扩容，所以这不只是添加元素会带来分摊固定时间开销那样简单）。
ArrayList擅长于随机访问。同时ArrayList是非同步的。

LinkedList

LinkedList定义如下：

public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable

同样实现List接口的LinkedList与ArrayList不同，ArrayList是一个动态数组，而LinkedList是一个双向链表。所以它除了有ArrayList的基本操作方法外还额外提供了get，remove，insert方法在LinkedList的首部或尾部。
由于实现的方式不同，LinkedList不能随机访问，它所有的操作都是要按照双重链表的需要执行。在列表中索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端，节约一半时间）。这样做的好处就是可以通过较低的代价在List中进行插入和删除操作。
与ArrayList一样，LinkedList也是非同步的。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：

List list = Collections.synchronizedList(new LinkedList(…));

Vector

Vector定义如下：

public class Vector<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable

与ArrayList相似，但是Vector是同步的。所以说Vector是线程安全的动态数组。它的操作与ArrayList几乎一样。

Stack

Stack定义如下：

public class Stack<E> extends Vector<E> {}

Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

HashSet

HashSet定义如下：

public class HashSet<E> extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable

HashSet堪称查询速度最快的集合，因为其内部是以HashCode来实现的。集合元素可以是null,但只能放入一个null。它内部元素的顺序是由哈希码来决定的，所以它不保证set的迭代顺序；特别是它不保证该顺序恒久不变。

TreeSet

TreeSet定义如下：

public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable

TreeSet是二叉树实现的，基于TreeMap，生成一个总是处于排序状态的set，内部以TreeMap来实现，不允许放入null值。它是使用元素的自然顺序对元素进行排序，或者根据创建Set时提供的 Comparator 进行排序，具体取决于使用的构造方法。

LinkedHashSet

LinkedHashSet定义如下：

public abstract class EnumSet<E extends Enum<E>> extends AbstractSet<E>
implements Cloneable, java.io.Serializable

LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起 来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素。LinkedHashSet在迭代访问Set中的全部元素时，性能比HashSet好，但是插入时性能稍微逊色于HashSet。

EnumSet

EnumSet定义如下：

public abstract class EnumSet<E extends Enum<E>> extends AbstractSet<E>
implements Cloneable, java.io.Serializable

EnumSet中所有值都必须是指定枚举类型的值，它的元素也是有序的，以枚举值在枚举类的定义顺序来决定集合元素的顺序。EnumSet集合不允许加入null元素，否则会抛出NullPointerException异常。EnumSet类没有暴露任何构造器来创建该类的实例，程序应该通过它提供的static方法来创建EnumSet对象

Map接口

Map与List、Set接口不同，它是由一系列键值对组成的集合，提供了key到Value的映射。在Map中它保证了key与value之间的一一对应关系。也就是说一个key对应一个value，所以它不能存在相同的key值，当然value值可以相同。
实现map的集合有：HashMap、HashTable、TreeMap、WeakHashMap。

HashMap

HashMap定义如下：

public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

以哈希表数据结构实现，查找对象时通过哈希函数计算其位置，它是为快速查询而设计的，其内部定义了一个hash表数组（Entry[] table），元素会通过哈希转换函数将元素的哈希地址转换成数组中存放的索引，如果有冲突，则使用散列链表的形式将所有相同哈希地址的元素串起来，可能通过查看HashMap.Entry的源码它是一个单链表结构。

HashTable

HashTable的定义如下：

public class Hashtable<K,V> extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable

也是以哈希表数据结构实现的，解决冲突时与HashMap也一样也是采用了散列链表的形式。HashTable继承Dictionary类，实现Map接口。其中Dictionary类是任何可将键映射到相应值的类（如 Hashtable）的抽象父类。每个键和每个值都是一个对象。在任何一个 Dictionary 对象中，每个键至多与一个值相关联。Map是”key-value键值对”接口。 HashTable采用”拉链法”实现哈希表不过性能比HashMap要低。

TreeMap

TreeMap的定义如下：

public class TreeMap<K,V> extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable

有序散列表，实现SortedMap接口，底层通过红黑树实现。

WeakHashMap

WeakHashMap的定义如下：

public class WeakHashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>

谈WeakHashMap前先看一下Java中的引用（强度依次递减）
强引用：普遍对象声明的引用，存在便不会GC
软引用：有用但并非必须，发生内存溢出前，二次回收
弱引用：只能生存到下次GC之前，无论是否内存足够
虚引用：唯一目的是在这个对象被GC时能收到一个系统通知
以弱键实现的基于哈希表的Map。在 WeakHashMap 中，当某个键不再正常使用时，将自动移除其条目。更精确地说，对于一个给定的键，其映射的存在并不阻止垃圾回收器对该键的丢弃，这就使该键成为可终止的，被终止，然后被回收。丢弃某个键时，其条目从映射中有效地移除，因此，该类的行为与其他的 Map 实现有所不同。null值和null键都被支持。该类具有与HashMap类相似的性能特征,并具有相同的效能参数初始容量和加载因子。像大多数集合类一样，该类是不同步的。

Iterator

Iterator定义如下：

public interface Iterator<E> {}

Iterator是一个接口，它是集合的迭代器。集合可以通过Iterator去遍历集合中的元素。Iterator提供的API接口，包括：是否存在下一个元素、获取下一个元素、删除当前元素。
注意：Iterator遍历Collection时，是fail-fast机制的。即，当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。

6、 List,Set,Map的区别

1、List,Set都是继承自Collection接口，Map则不是

2、List特点：元素有放入顺序，元素可重复 ，Set特点：元素无放入顺序，元素不可重复，重复元素会覆盖掉，（注意：元素虽然无放入顺序，但是元素在set中的位置是有该元素的HashCode决定的，其位置其实是固定的，加入Set 的Object必须定义equals()方法 ，另外list支持for循环，也就是通过下标来遍历，也可以用迭代器，但是set只能用迭代，因为他无序，无法用下标来取得想要的值。）

3.Set和List对比：
Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。
List：和数组类似，List可以动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变。

4.Map适合储存键值对的数据

5.线程安全集合类与非线程安全集合类
LinkedList、ArrayList、HashSet是非线程安全的，Vector是线程安全的;
HashMap是非线程安全的，HashTable是线程安全的;
StringBuilder是非线程安全的，StringBuffer是线程安全的。

7、 List和Map的实现方式以及存储方式

list:是一个有序的集合可以包含重复的元素，提供了按索引访问的方式，采用数组或者链表的方式进行储存
map:包含了key-value对，map中key必须唯一，value可以重复。

8、 HashMap的实现原理

hashmap原理涉及地址bucket、hashing、hashcode和equal、不可变键、hash碰撞、线程安全、数组和链表共同储存等内容
https://www.jianshu.com/p/8b372f3a195d/

9、 HashMap数据结构？

https://www.jianshu.com/p/8b372f3a195d/

10、 HashMap源码理解

https://www.jianshu.com/p/8b372f3a195d/

11、 HashMap如何put数据（从HashMap源码角度讲解）？

1、对key的hashCode()做hash，然后再计算index;
2、如果没碰撞直接放到bucket里；
3、如果碰撞了，以链表的形式储存在buckets后；
4、如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树；
5、如果节点已经存在就替换old value(保证key的唯一性)
6、如果bucket满了(超过load factor*current capacity)，就要resize。

12、 HashMap怎么手写实现？

要手写hashMap，必须先理解其数据结构：hashMap的数据是通过hash散列后存放到数组+单链表中的，其内部读取采用的位运算，考虑到速度的原因。具体实现参考博客：
对HashMap的思考及手写实现

13、 ConcurrentHashMap的实现原理

jdk1.7版本原理：
ConcurrentHashMap采用 分段锁的机制，实现并发的更新操作，底层采用数组+链表的存储结构。
其包含两个核心静态内部类 Segment和HashEntry。
1、Segment继承ReentrantLock用来充当锁的角色，每个 Segment 对象守护每个散列映射表的若干个桶。
2、HashEntry 用来封装映射表的键 / 值对；
3、每个桶是由若干个 HashEntry 对象链接起来的链表。

分段锁图解.png

jdk1.8版本原理：
利用CAS+Synchronized来保证并发更新的安全，底层采用数组+链表+红黑树的存储结构。

jdk1.8版本结构.png

14、 ArrayMap、SparseArray和HashMap的对比

ArrayMap及SparseArray是android的系统API，是专门为移动设备而定制的。用于在一定情况下取代HashMap而达到节省内存的目的。
hashMap 采用数组加单链表结构前面说过，采用hash进行散列速度还是很快的;
ArrayMap 采用两个数组进行储存，采用二分查找进行数据操作；
SparseArray 采用固定key类型方式进行储存，即key只能为int类型，直接进行对比int数值，所以没有拆箱和装箱的操作，效率上会有一定的提升，查找算法也是采用的二分查找；
1.在数据量小的时候一般认为1000以下，当你的key为int的时候，使用SparseArray确实是一个很不错的选择，内存大概能节省30%，相比用HashMap，因为它key值不需要装箱，所以时间性能平均来看也优于HashMap,建议使用！
2.ArrayMap相对于SparseArray，特点就是key值类型不受限，任何情况下都可以取代HashMap,但是通过研究和测试发现，ArrayMap的内存节省并不明显，也就在10%左右，但是时间性能确是最差的，当然了，1000以内的数据量也无所谓了，加上它只有在API>=19才可以使用
详情参考HashMap，ArrayMap，SparseArray源码分析及性能对比

15、 HashTable实现原理

16、 TreeMap具体实现

17、 HashMap和HashTable的区别

18、 HashMap与HashSet的区别

19、 HashSet与HashMap怎么判断集合元素重复？

20、 集合Set实现Hash怎么防止碰撞

21、 ArrayList和LinkedList的区别，以及应用场景

22、 数组和链表的区别

23、 二叉树的深度优先遍历和广度优先遍历的具体实现

24、 堆的结构

25、 堆和树的区别

26、 堆和栈在内存中的区别是什么(解答提示：可以从数据结构方面以及实际实现方面两个方面去回答)？

27、 什么是深拷贝和浅拷贝

28、 手写链表逆序代码

29、 讲一下对树，B+树的理解

30、 讲一下对图的理解

31、 判断单链表成环与否？

32、 链表翻转（即：翻转一个单项链表）

33、 合并多个单有序链表（假设都是递增的）