- **正确答案**：实现一个简单的 HashMap 需要理解哈希函数、冲突解决机制（如链地址法或开放寻址法）、数组与链表的结合使用。基本结构是一个数组，数组中的每个元素是一个链表头节点，用于存储键值对。 - **解答思路**： 1. 确定数据结构：使用数组 + 链表（或红黑树）的方式实现。 2. 定义哈希函数：将 key 映射到数组索引上。 3. 处理哈希冲突：当不同 key 映射到同一索引时，使用链表或红黑树进行存储。 4. 实现 put 和 get 方法： - put(key, value)：计算哈希值，找到数组位置，插入键值对；如果存在相同 key，则更新 value。 - get(key)：查找对应 key 的 value。 5. 考虑扩容机制：当负载因子超过阈值时，重新分配更大的数组并重新哈希（rehashing）。 - **深度知识讲解**： ### 1. 哈希函数哈希函数的目标是将任意对象映射为整数，并尽量减少冲突。Java 中 HashMap 使用的是 `key.hashCode() ^ (key.hashCode() >>> 16)` 再与数组长度取模。 ### 2. 哈希冲突解决方式 - **链地址法**（Separate Chaining）：每个数组元素指向一个链表，发生冲突时在链表中添加新节点。 - **开放寻址法**（Open Addressing）：线性探测、二次探测等方法寻找下一个空位。 Java HashMap 在 JDK 8 中引入了红黑树优化：当链表长度超过阈值（默认是 8），链表转为红黑树以提高查找效率。 ### 3. 扩容机制当 HashMap 中的元素数量超过容量 × 负载因子（load factor，默认是 0.75）时，会触发扩容操作。扩容后数组大小变为原来的两倍，并对所有元素重新计算哈希值并插入。 ### 4. 数据结构设计 - 数组：用于快速定位桶（bucket） - 链表/红黑树：处理哈希冲突 - **伪代码示例**： ```java class Entry { K key; V value; Entry next; Entry(K key, V value, Entry next) { this.key = key; this.value = value; this.next = next; } } class MyHashMap { private static final int INITIAL_CAPACITY = 16; private static final float LOAD_FACTOR = 0.75f; private Entry[] table; private int size; public MyHashMap() { table = new Entry[INITIAL_CAPACITY]; size = 0; } private int hash(K key) { return key.hashCode() ^ (key.hashCode() >>> 16); } private int indexFor(int hash, int length) { return hash & (length - 1); // 等价于 hash % length } public void put(K key, V value) { if (size >= table.length * LOAD_FACTOR) { resize(); } int hash = hash(key); int i = indexFor(hash, table.length); Entry e = table[i]; while (e != null) { if (e.key.equals(key)) { e.value = value; // 更新已存在的 key return; } e = e.next; } Entry newEntry = new Entry<>(key, value, table[i]); table[i] = newEntry; size++; } public V get(K key) { int hash = hash(key); int i = indexFor(hash, table.length); Entry e = table[i]; while (e != null) { if (e.key.equals(key)) { return e.value; } e = e.next; } return null; } private void resize() { int newCapacity = table.length * 2; Entry[] newTable = new Entry[newCapacity]; for (int j = 0; j < table.length; j++) { Entry e = table[j]; if (e != null) { do { Entry next = e.next; int i = indexFor(e.key.hashCode(), newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } table = newTable; } } ``` - **扩展知识点**： ### 1. 红黑树优化（JDK 8+）当链表长度达到 8 且当前桶数量大于等于 64 时，链表转换为红黑树，提升查找效率从 O(n) 到 O(log n)。 ### 2. 并发安全问题 HashMap 是非线程安全的，多线程环境下可能引发死循环或数据不一致问题。可以使用 ConcurrentHashMap 或 Collections.synchronizedMap() 来实现线程安全。 ### 3. 哈希扰动（扰动函数） Java HashMap 中使用的 `(h = key.hashCode()) ^ (h >>> 16)` 是为了增加低位随机性，避免高位变化小导致的哈希冲突。 ### 4. 负载因子的作用负载因子控制 HashMap 的填充程度。太大会增加冲突概率，影响性能；太小则浪费空间。0.75 是时间和空间的一个折中选择。 ### 5. 应用场景 - 缓存系统 - 查找表（如数据库索引） - 统计频率（如单词出现次数） - 去重（如找出重复数字）通过掌握这些底层原理和实现细节，面试者不仅能回答 HashMap 相关问题，还能举一反三地理解和实现其他哈希结构的应用。

小厂面经

全站热榜

创作者周榜