- 正确答案：Java中常用的数据结构主要包括数组（Array）、链表（LinkedList）、栈（Stack）、队列（Queue）、双端队列（Deque）、集合（Set）、映射（Map）、堆（Heap）以及树（Tree）等。这些数据结构在Java集合框架（Java Collections Framework, JCF）中有对应的实现类。 - 解答思路：要回答这个问题，首先需要明确“数据结构”是指组织和存储数据的方式，而Java通过其标准库提供了丰富的数据结构实现。我们可以从线性结构、非线性结构和接口与实现的角度进行分类说明，并结合常见使用场景和底层实现机制来展开。 - 深度知识讲解： 1. 数组（Array） - 底层原理：数组是连续内存空间，用于存储相同类型的数据，支持随机访问。 - 特点：长度固定，访问时间复杂度为O(1)，插入删除效率低（O(n)）。 - 示例： int[] arr = new int[10]; 2. ArrayList - 实现类：java.util.ArrayList - 底层结构：基于动态数组，内部使用Object[] elementData存储元素。 - 扩容机制：当容量不足时，默认扩容为原来的1.5倍（oldCapacity + (oldCapacity >> 1)）。 - 时间复杂度：随机访问O(1)，尾部插入O(1)均摊，中间插入删除O(n)。 - 线程不安全。 3. LinkedList - 实现类：java.util.LinkedList - 底层结构：双向链表（每个节点包含prev、next指针），实现了List和Deque接口。 - 节点结构（简化）： class Node { E item; Node next; Node prev; } - 优势：任意位置插入删除O(1)，前提是已定位到节点；但查找需遍历O(n)。 - 适用场景：频繁在中间增删元素。 4. Stack（栈） - 后进先出（LIFO） - Java中可通过继承Vector实现的Stack类，但推荐使用Deque替代： Deque stack = new ArrayDeque<>(); stack.push(1); stack.pop(); - 常用于递归模拟、表达式求值、括号匹配等。 5. Queue 和 Deque（队列与双端队列） - Queue：先进先出（FIFO），常用实现：LinkedList、ArrayDeque - Deque：两端均可进出，ArrayDeque是高效实现（基于循环数组） - 方法对比： add()/offer() 入队 remove()/poll() 出队 element()/peek() 查看队首 6. PriorityQueue（优先队列） - 底层实现：基于二叉堆（Binary Heap），通常是小顶堆或大顶堆 - 插入和删除时间复杂度：O(log n) - 构造时可传入Comparator自定义排序 - 注意：不能存储null，且元素必须可比较 - 内部使用Object[] queue数组表示完全二叉树 - 父节点i，左孩子=2*i+1，右孩子=2*i+2 - 插入后上浮（sift-up），删除根后下沉（sift-down） 7. HashSet - 实现类：java.util.HashSet - 底层结构：基于HashMap实现（value统一为一个静态对象PRESENT） - 添加元素调用map.put(e, PRESENT) != null 判断是否重复 - 允许null元素，无序，非同步 - 时间复杂度：平均O(1)，最坏O(n)（哈希冲突严重） 8. LinkedHashSet - 继承HashSet，维护插入顺序 - 底层：HashMap + 双向链表（记录插入顺序） - 适用于需要去重且保持插入顺序的场景 9. TreeSet - 基于红黑树（Red-Black Tree）实现的NavigableSet - 元素自动排序（自然顺序或Comparator） - 时间复杂度：插入、删除、查找均为O(log n) - 不允许null（否则抛NullPointerException） 10. HashMap - 最常用的映射结构 - 底层：数组 + 链表 + 红黑树（JDK 8+） - 初始容量16，负载因子0.75 - 当链表长度超过8且数组长度>=64时，转为红黑树 - 树节点数量少于6时退化为链表 - 哈希函数：key.hashCode() 经过高位运算扰动（h ^ (h >>> 16)） - 存储位置计算：(n - 1) & hash （n为数组长度，保证索引合法） - 扩容：达到阈值（capacity * loadFactor）时扩容两倍，并重新哈希 - 线程不安全，多线程下建议使用ConcurrentHashMap 11. LinkedHashMap - 继承HashMap，维护插入顺序或访问顺序（accessOrder参数） - 底层：哈希表 + 双向链表 - 可用于实现LRU缓存（配合removeEldestEntry方法） 12. TreeMap - 基于红黑树的SortedMap实现 - 支持有序遍历（升序/降序）、范围查询（subMap、headMap、tailMap） - 所有操作O(log n) 13. ConcurrentHashMap - 线程安全的HashMap - JDK 8之前：分段锁Segment - JDK 8之后：CAS + synchronized 锁单个桶 - 支持高并发读写扩展知识点： - 红黑树性质（用于TreeMap、TreeSet）： 1. 节点是红色或黑色 2. 根节点是黑色 3. 所有叶子（NIL）是黑色 4. 红色节点的子节点必须是黑色（不能有两个连续红节点） 5. 从任一节点到其每个叶子的所有路径包含相同数目的黑节点 - 哈希冲突解决方法： - 开放定址法（如线性探测、平方探测） - 链地址法（Java HashMap采用） - 再哈希法 - 建立公共溢出区 - 负载因子（load factor）： - 默认0.75，平衡空间利用率和冲突概率 - 太小导致频繁扩容，太大导致链表过长代码示例：手动实现简单HashMap（简化版） ``` class SimpleHashMap { private static class Node { final int hash; final K key; V value; Node next; Node(int h, K k, V v, Node n) { hash = h; value = v; key = k; next = n; } } private Node[] table; private int size; private static final float LOAD_FACTOR = 0.75f; private int threshold; @SuppressWarnings("unchecked") public SimpleHashMap() { table = new Node[16]; threshold = (int)(16 * LOAD_FACTOR); } private int hash(Object key) { if (key == null) return 0; int h = key.hashCode(); return h ^ (h >>> 16); } private int indexFor(int h, int length) { return h & (length - 1); } public V put(K key, V value) { int hash = hash(key); int i = indexFor(hash, table.length); for (Node e = table[i]; e != null; e = e.next) { if (e.hash == hash && (e.key == key || (key != null && key.equals(e.key)))) { V oldValue = e.value; e.value = value; return oldValue; } } // 新增节点 table[i] = new Node<>(hash, key, value, table[i]); size++; if (size > threshold) resize(); return null; } @SuppressWarnings("unchecked") private void resize() { Node[] oldTab = table; int oldCap = oldTab.length; int newCap = oldCap << 1; Node[] newTab = new Node[newCap]; threshold = (int)(newCap * LOAD_FACTOR); // 重新哈希 for (int j = 0; j < oldCap; j++) { Node e = oldTab[j]; if (e != null) { oldTab[j] = null; if (e.next == null) { int i = indexFor(e.hash, newCap); newTab[i] = e; } else { // 处理链表迁移（简化处理） Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node next; for (Node p = e; p != null; p = next) { next = p.next; if ((p.hash & oldCap) == 0) { if (loTail == null) loHead = p; else loTail.next = p; loTail = p; } else { if (hiTail == null) hiHead = p; else hiTail.next = p; hiTail = p; } } if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } table = newTab; } public V get(Object key) { int hash = hash(key); int i = indexFor(hash, table.length); for (Node e = table[i]; e != null; e = e.next) { if (e.hash == hash && (e.key == key || (key != null && key.equals(e.key)))) return e.value; } return null; } } ``` 总结： Java常用数据结构覆盖了几乎所有经典的数据组织方式，理解它们的底层实现对于写出高性能代码至关重要。面试中常考察： - ArrayList vs LinkedList 区别 - HashMap工作原理（哈希、冲突、扩容、红黑树转换） - ConcurrentHashMap如何保证线程安全 - TreeMap与HashMap的选择依据 - 如何设计一个LRU Cache（通常用LinkedHashMap或手写双向链表+HashMap）掌握这些内容不仅有助于通过技术面试，也能提升实际开发中的系统设计能力。

10/30英威腾开发工程师

全站热榜

创作者周榜