- **正确答案**：HashMap 是 Java 中常用的数据结构，用于存储键值对（Key-Value Pair）。它基于哈希表实现，提供了高效的插入（put）和查找（get）操作。其基本原理是通过哈希函数将键（Key）映射到数组的某个位置，从而实现快速访问。 - put(K key, V value)：将键值对插入到 HashMap 中。 - get(Object key)：根据键获取对应的值。 - remove(Object key)：移除指定键的映射关系。 - containsKey(Object key)：判断是否包含某个键。 - size()：返回当前 HashMap 中键值对的数量。 - **解答思路**：面试官问这个问题，主要是想考察你对 HashMap 内部实现机制的理解，包括： 1. 哈希冲突如何解决？ 2. 扩容机制是如何工作的？ 3. 如何处理 hash 相同的键？ 4. 线程安全性问题？回答时应从以下几个方面展开： - 数据结构基础：数组 + 链表/红黑树 - 哈希函数计算与索引定位 - 哈希冲突处理（链地址法） - 树化与反树化（Java 8 引入） - 扩容机制（负载因子、阈值） - 线程不安全原因及替代方案（如 ConcurrentHashMap） - **深度知识讲解**： ### 1. 数据结构设计 HashMap 的底层结构是数组 + 链表/红黑树（Java 8+）： - 数组：称为桶（bucket），每个元素是一个 Node 节点。 - 链表：当发生哈希冲突时，多个键值对会以链表形式存储在同一个桶中。 - 红黑树：当链表长度超过阈值（默认为8）时，链表转换为红黑树，提高查找效率。 ### 2. 哈希计算与索引定位 - 键对象的 hashCode() 方法返回一个整数。 - HashMap 对这个整数进行扰动（扰动函数是为了减少哈希碰撞）： ```java static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } ``` - 然后通过 `(n - 1) & hash` 计算出该键应该放在数组中的哪个位置（n 是数组长度，必须是 2 的幂）。 ### 3. put 方法流程 - 计算 key 的 hash 值； - 定位到数组中的 bucket； - 如果没有冲突，直接放入； - 如果有冲突，遍历链表或红黑树，比较 key 是否相同： - 相同则更新 value； - 不同则添加新节点； - 插入后检查是否需要扩容（size >= threshold）； - 检查链表长度是否达到树化阈值（8），如果是则转为红黑树。 ### 4. get 方法流程 - 计算 key 的 hash； - 定位到数组中的 bucket； - 遍历链表或红黑树，使用 equals 比较 key； - 找到则返回 value，否则返回 null。 ### 5. 扩容机制 - 初始容量为16，负载因子默认0.75； - 当元素个数超过 `capacity * loadFactor` 时触发扩容； - 新容量为原来的两倍； - 扩容后所有元素重新计算 hash 并重新分布（rehashing）； ### 6. 树化与反树化 - 当链表长度 ≥ 8 时，链表转为红黑树； - 当红黑树节点数 ≤ 6 时，红黑树转为链表； - 这样可以平衡查找效率和空间开销。 ### 7. 线程安全性 - HashMap 是非线程安全的； - 多线程环境下可能出现死循环（JDK 1.7 及之前头插法导致）； - 推荐使用 ConcurrentHashMap 或 Collections.synchronizedMap()。 - **伪代码示例**（简化版 HashMap 实现）： ```java class MyHashMap { private static class Node { int hash; 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; } } private Node[] table; private int size; private static final float LOAD_FACTOR = 0.75f; public MyHashMap() { table = new Node[16]; } private int hash(K key) { int h = key == null ? 0 : key.hashCode(); return h ^ (h >>> 16); } private int indexFor(int hash, int length) { return hash & (length - 1); } public void 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.equals(e.key))) { e.value = value; return; } } table[i] = new Node<>(hash, key, value, table[i]); if (++size > table.length * LOAD_FACTOR) { resize(); } } public V get(K 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.equals(e.key))) { return e.value; } } return null; } private void resize() { Node[] oldTable = table; table = new Node[oldTable.length * 2]; for (Node e : oldTable) { while (e != null) { Node next = e.next; int i = indexFor(e.hash, table.length); e.next = table[i]; table[i] = e; e = next; } } } } ``` - **扩展知识点**： 1. **ConcurrentHashMap**：线程安全版本的 HashMap，采用分段锁（JDK 1.7）或 CAS + synchronized（JDK 1.8）实现高效并发控制。 2. **LinkedHashMap**：继承自 HashMap，支持按插入顺序或访问顺序排序。 3. **TreeMap**：基于红黑树实现，键有序。 4. **WeakHashMap**：键是弱引用，适用于缓存场景。 5. **HashCode 与 Equals 合约**：如果两个对象相等（equals 返回 true），它们的 hashCode 必须相同；反之不一定成立。 6. **哈希碰撞攻击（HashDoS）**：恶意构造大量 hash 相同的 key，使性能退化为 O(n)，可通过随机盐值缓解。总之，HashMap 是面试高频考点，掌握其底层实现原理、扩容机制、线程安全问题是关键。

快手 大数据引擎(凉经)

全站热榜

创作者周榜

快手大数据引擎(凉经)