Java面试中的数据结构核心知识点

数组与链表的特点与区别

数组在内存中是连续存储的，支持随机访问，时间复杂度为O(1)，但插入和删除操作需要移动元素，时间复杂度为O(n)。链表通过指针连接节点，内存不连续，插入和删除操作时间复杂度为O(1)，但随机访问需要遍历，时间复杂度为O(n)。

ArrayList基于动态数组实现，适合频繁查询场景；LinkedList基于双向链表实现，适合频繁增删场景。在Java集合框架中，Vector是线程安全的ArrayList，但性能较差。

哈希表的实现原理与冲突解决

HashMap通过数组+链表+红黑树实现，默认负载因子0.75。当链表长度超过8且数组长度大于64时，链表会转为红黑树。哈希冲突解决方法包括开放定址法和链地址法。Java 8的HashMap使用高低位异或优化哈希计算：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

ConcurrentHashMap采用分段锁（Java 7）或CAS+synchronized（Java 8）实现线程安全。HashTable使用全表锁，性能较差。

树结构的应用与遍历

二叉搜索树的中序遍历可以得到有序序列，平衡二叉树（AVL）通过旋转保持平衡。红黑树通过颜色标记和旋转规则保证近似平衡，插入删除查找的时间复杂度都是O(logn)。

堆是完全二叉树，常用于实现优先队列。PriorityQueue默认是小顶堆，可通过Comparator修改为大顶堆。树的遍历包括前序、中序、后序和层次遍历，递归和非递归实现都需要掌握。

图算法与常见问题

图的表示方法有邻接矩阵和邻接表。Dijkstra算法用于单源最短路径，Floyd用于多源最短路径。拓扑排序检测有向无环图，常用DFS或Kahn算法实现。

并查集用于处理不相交集合的合并与查询问题，路径压缩和按秩合并可优化性能。最小生成树算法包括Prim和Kruskal，前者适合稠密图，后者适合稀疏图。

字符串匹配与高级数据结构

KMP算法通过部分匹配表避免回溯，时间复杂度O(n+m)。Trie树用于高效存储和查询字符串集合，AC自动机是多模式串匹配算法。后缀数组和后缀树可用于解决复杂字符串问题。

跳表通过多层索引提升有序链表的查询效率，Redis的有序集合采用跳表实现。布隆过滤器通过多个哈希函数和位数组判断元素可能存在或一定不存在，适合海量数据去重场景。