java：数据结构面试题

亦凉 2024-04-17 20:18 61阅读 0赞

数据结构是面试一定会问的问题。  
1.常用的数据结构有哪些？  
set,list,map,Quene.二叉树  
set子类：  
HashSet:HashSet不能保证元素的排列顺序；使用Hash算法来存储集合中的元素，有良好的存取和查找性能；通过equal()判断两个元素是否相等，并两个元素的hashCode()返回值也相等。  
TreeSet是SortedSet接口的实现类，根据元素实际值的大小进行排序；采用红黑树的数据结构来存储集合元素；支持两种排序方法：自然排序（默认情况）和定制排序。前者通过实现Comparable接口中的compareTo()比较两个元素之间大小关系，然后按升序排列；后者通过实现Comparator接口中的compare()比较两个元素之间大小关系，实现定制排列。

list子类：  
ArrayList:  
底层数据结构是数组，查询快，增删慢。 线程不安全，效率高。 空间不足时，增加原来空间的50%。  
Vector:  
底层数据结构是数组，查询快，增删慢。 线程安全，效率低。 空间不足时，增加原来空间的一倍。 Vector相对ArrayList查询慢(线程安全的) ，Vector相对LinkedList增删慢(数组结构)  
LinkedList: 底层数据结构是链表，查询慢，增删快。 线程不安全，效率高。

Map子类：HashMap、Hashtable、 ConcurrentHashMap，LinkedHashMap、TreeMap  
HashMap基于AbstractMap类，实现了Map、Cloneable（能被克隆）、Serializable（支持序列化）接口； 非线程安全；允许存在一个为null的key和任意个为null的value；采用链表散列的数据结构，即数组和链表的结合；初始容量为16，填充因子默认为0.75，扩容时是当前容量翻倍，即2capacity，hashmap采用拉链法解决冲突。

何保证HashMap线程安全？  
ConcurrentHashMap是线程安全的HashMap，它采取锁分段技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。在JDK1.8中对ConcurrentHashmap做了两个改进：  
取消segments字段，直接采用transient volatile HashEntry<K,V>\[\] table保存数据，将数组元素作为锁，对每一行数据进行加锁，可减少并发冲突的概率  
数据结构由“数组＋单向链表”变为“数组＋单向链表＋红黑树”，使得查询的时间复杂度可以降低到O(logN)，改进一定的性能。

HashMap实现有序？  
HashMap是无序的，而LinkedHashMap是有序的HashMap，默认为插入顺序，还可以是访问顺序，基本原理是其内部通过Entry维护了一个双向链表，负责维护Map的迭代顺序。

HashMap在put、get元素的过程？体现了什么数据结构？  
向Hashmap中put元素时，首先判断key是否为空，为空则直接调用putForNullKey()，不为空则计算key的hash值得到该元素在数组中的下标值；如果数组在该位置处没有元素，就直接保存；如果有，还要比较是否存在相同的key，存在的话就覆盖原来key的value，否则将该元素保存在链头，先保存的在链尾。  
从Hashmap中get元素时，计算key的hash值找到在数组中的对应的下标值，返回该key对应的value即可，如果有冲突就遍历该位置链表寻找key相同的元素并返回对应的value  
由此可看出HashMap采用链表散列的数据结构，即数组和链表的结合，在Java8后又结合了红黑树，当链表元素超过8个将链表转换为红黑树。

二叉树：  
B+树：  
平衡二叉树（AVL树）：各个结点左右子树深度差的绝对值不超过1。  
哈夫曼树：带权路径长度最小的二叉树称为最优二叉树。哈夫曼树构造不唯一，但所有叶子结点的带权路径长度之和都是最小的。  
红黑树：一种自平衡二叉查找树，它的性质有：  
节点是红色或黑色。  
根节点是黑色。  
每个叶子节点都是黑色的空节点（NIL节点）。  
每个红色节点的两个子节点都是黑色。  
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

2.各个数据结构的底层实现原理？  
二叉树遍历等？  
插入，删除，查找效率的比较？  
线程安全？  
你用过哪些？

3.手写代码  
链表排序，反转？  
map排序？