数据结构面试题（三）
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
对于高并发场景下，还有一些特殊的数据结构：
1、并发List ：Vector、CopyOnWriteArrayList
2、并发Set：CopyOnWriteArraySet
3、并发Map:ConcurrentHashMap、Collections.synchronizedMap(map)
4、并发Queue:ConcurrentLinkedQueue-高性能队列、BlockingQueue-阻塞队列
参考：并发数据结构
由浅入深理解java集合(一)
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。
