- 正确答案：HashMap 是一种基于哈希表实现的键值对存储结构，在 Java 中底层采用数组 + 链表（或红黑树）的数据结构。具体来说，它使用一个 Node 数组（也称为桶数组 bucket array），每个桶中存放链表或红黑树节点，用于解决哈希冲突。 - 解答思路：首先明确 HashMap 的核心功能是通过 key 快速查找 value，这依赖于哈希函数将 key 映射到数组索引。当多个 key 被映射到同一个位置时（即哈希冲突），需要通过额外结构存储这些键值对。Java 8 引入了优化机制：当链表长度超过一定阈值（默认 8）且数组长度大于等于 64 时，链表会转换为红黑树以提升查找性能。因此，HashMap 的数据结构可总结为“数组 + 链表 + 红黑树”。 - 深度知识讲解： 1. 底层结构组成： - Entry 数组（在 Java 中是 Node[] table）：初始容量为 16，负载因子默认 0.75。 - 每个数组元素称为“桶”（bucket），是一个链表头节点或红黑树根节点。 - 当发生哈希冲突时，新元素被添加到链表尾部（Java 8 后改为尾插法，避免环形链表问题）。 - 当链表长度 ≥ 8 且数组长度 ≥ 64 时，链表转为红黑树；若删除节点导致树太小（< 6），则转回链表。 2. 哈希计算过程： - 并非直接使用 key.hashCode() 作为索引，而是进行扰动处理防止高位未参与运算导致的碰撞过多。 - 计算方式：(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16) - 最终索引：index = hash & (n - 1)，其中 n 是数组长度，必须是 2 的幂，这样可以用位运算替代取模提高效率。 3. 扩容机制（resize）： - 当元素数量超过 threshold（capacity * load factor）时触发扩容。 - 扩容后容量变为原来的两倍。 - 所有元素需要重新计算位置，但 Java 8 利用扩容是 2 倍的特点，通过高位 bit 判断是否迁移：只看新增的一位是否为 1，决定留在原位置还是移动到原索引 + oldCap 位置。 4. 数据节点类型： - static class Node implements Map.Entry { final int hash; final K key; V value; Node next; // 下一个节点，构成链表 } - 当升级为红黑树时，节点类型变为 TreeNode，继承自 LinkedHashMap.Entry，并额外包含父、左、右指针以及颜色标记。 5. 关键参数： - initialCapacity: 初始容量，默认 16 - loadFactor: 负载因子，默认 0.75，控制空间使用与查询效率的平衡 - threshold: 扩容阈值，等于 capacity * loadFactor - TREEIFY_THRESHOLD: 链表转树阈值，8 - UNTREEIFY_THRESHOLD: 树转链表阈值，6 - MIN_TREEIFY_CAPACITY: 最小树化容量，64 - 代码示例（简化版结构定义）： ``` public class HashMap { static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16 static final float DEFAULT_LOAD_FACTOR = 0.75f; static final int TREEIFY_THRESHOLD = 8; static final int UNTREEIFY_THRESHOLD = 6; static final int MIN_TREEIFY_CAPACITY = 64; transient Node[] table; static class Node implements Map.Entry { final int hash; final K key; V value; Node next; Node(int hash, K key, V value, Node next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } } // 红黑树节点（部分） static final class TreeNode extends LinkedHashMap.Entry { TreeNode parent; TreeNode left; TreeNode right; TreeNode prev; boolean red; TreeNode(int hash, K key, V val, Node next) { super(hash, key, val, next); } } // hash 计算方法 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } // 获取索引位置 final int indexFor(int h, int length) { return h & (length - 1); // 因为 length 是 2^n } } ``` - 扩展知识点： - 为什么容量总是 2 的幂？为了用位运算代替取模（%），提升性能。因为 a % (2^n) == a & (2^n - 1)，前提是 2^n 是整数。 - 为什么负载因子是 0.75？这是时间和空间成本之间的折中。太小浪费空间，太大增加冲突概率。 - null 键的处理：HashMap 允许一个 null 键，put 时特殊判断，get 时优先检查第一个节点。 - 并发问题：HashMap 不是线程安全的，多线程环境下可能导致死循环（旧版本链表反转）、数据丢失等。应使用 ConcurrentHashMap。 - JDK 1.7 与 1.8 差异：1.7 使用头插法，扩容时可能形成环；1.8 改为尾插法并引入红黑树，解决了该问题。综上所述，HashMap 的数据结构设计兼顾了高效存取和冲突处理，其核心在于哈希函数设计、冲突解决策略（拉链法+树化）、动态扩容机制三者的结合。理解其底层原理对于应对面试中的高频问题至关重要。

悦点科技

全站热榜

创作者周榜