数据结构面试专题1、常用数据结构简介数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素间的关系组成。常用的数据有：数组、栈、队列、链表、树、图、堆、散列表。1）数组：在内存中连续存储多个元素的结构。数组元素通过下标访问，下标从0开始。优点：访问速度快；缺点：数组大小固定后无法扩容，只能存储一种类型的数据，添加删除操作慢。适用场景：适用于需频繁查找，对存储空间要求不高，很少添加删除。2）栈：一种特殊的线性表，只可以在栈顶操作，先进后出，从栈顶放入元素叫入栈，从栈顶取出元素叫出栈。应用场景：用于实现递归功能，如斐波那契数列。3）队列：一种线性表，在列表一端添加元素，另一端取出，先进先出。使用场景：多线程阻塞队列管理中。4）链表：物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域，一个是指向下一个结点地址的指针域。有单链表、双向链表、循环链表。优点：可以任意加减元素，不需要初始化容量，添加删除元素只需改变前后两个元素结点的指针域即可。缺点：因为含有大量指针域，固占用空间大，查找耗时。适用场景：数据量小，需频繁增加删除操作。5）树：由n个有限节点组成一种具有层次关系的集合。二叉树（每个结点最多有两个子树，结点的度最大为2，左子树和右子树有顺序）、红黑树（HashMap底层源码）、B+树（mysql的数据库索引结构）6）散列表（哈希表）：根据键值对来存储访问。7）堆：堆中某个节点的值总是不大于或不小于其父节点的值，堆总是一棵完全二叉树。8）图：由结点的有穷集合V和边的集合E组成。2、并发集合了解哪些？1）并发List，包括Vector和CopyOnWriteArrayList是两个线程安全的List，Vector读写操作都用了同步，CopyOnWriteArrayList在写的时候会复制一个副本，对副本写，写完用副本替换原值，读时不需要同步。2）并发Set，CopyOnWriteArraySet基于CopyOnWriteArrayList来实现的，不允许存在重复的对象。3）并发Map，ConcurrentHashMap，内部实现了锁分离，get操作是无锁的。4）并发Queue，ConcurrentLinkedQueue适用于高并发场景下的队列，通过无锁方式实现。BlockingQueue阻塞队列，应用场景，生产者-消费者模式，若生产快于消费，生产队列装满时会阻塞，等待消费。5）并发Deque,LinkedBlockingDueue没有进行读写锁分离，同一时间只能有一个线程对其操作。6）并发锁重入锁ReentrantLock，互斥锁，一次最多只能一个线程拿到锁。7）读写锁ReadWriteLock，有读取和写入锁两种，读取允许多个读取线程同时持有，而写入只能有一个线程持有。3、列举java的集合以及集合之间的继承关系5、容器类介绍以及之间的区别1）Collection接口：集合框架的根接口，它是集合类框架中最具一般性的顶层接口。2）Map接口：提供了键值对的映射关系的集合，关键字不能有重复值，每个关键字至多可映射一个值。HashMap(通过散列机制，用于快速访问)，TreeMap（保持key处于排序状态，访问速度不如hashmap）,LinkedHashMap(保持元素的插入顺序)3）Set接口：可包含重复的元素，LinkedHashSetTreeSet(用红黑树来存储元素)HashSet4）List接口:可通过索引对元素进行精准的插入和查找，实现类有ArrayListLinkedList5）Queue接口：继承自Collection接口，LinkedList实现了Queue接口，提供了支持队列的行为。6）Iterator接口：为了迭代集合7）Comparable接口：用于比较6、List,Set,Map的区别Set是一个无序的集合，不能包含重复的元素；list是一个有序的集合可以包含重复的元素，提供了按索引访问的方式；map包含了key-value对，map中key必须唯一，value可以重复。7、HashMap的实现原理1）数据结构jdk1.7及以前，HashMap由数组+链表组成，数组Entry是HashMap的主体，Entry是HashMap中的一个静态内部类，每一个Entry包含一个key-value键值对，链表是为解决哈希冲突而存在。从jdk1.8起，HashMap是由数组+链表/红黑树组成，当某个bucket位置的链表长度达到阀值8时，这个链表就转变成红黑树。2）HashMap是线程不安全的，存储比较快，能接受null...
