如何做网站反链老师直播课
39. 说一下 HashMap 的实现原理？
HashMap 是 Java 中使用非常普遍的一种基于散列的映射数据结构，主要用于存储键值对。它允许使用任何非空对象作为键和值，主要实现原理如下：
- 数组 + 链表 + 红黑树：HashMap 内部主要由一个数组构成，每个数组元素是一个链表或红黑树，链表或红黑树用于存储具有相同散列码的键值对。
- 散列函数：当向 HashMap 中插入一个键值对时，首先会使用散列函数计算键的散列码，散列码决定了键值对在数组中的位置。
- 索引计算：通过散列码与数组长度的模运算（散列码 % 数组长度）得到该键值对应在数组中的索引位置。
- 链表和红黑树：如果两个不同的键具有相同的散列码，它们会被存储在同一个数组索引位置对应的链表中。如果链表长度过长（默认超过8），则会转换为红黑树，以减少搜索时间。
- 键的唯一性：HashMap 中键的唯一性是通过 equals() 方法和 hashCode() 方法来保证的。如果两个键的 hashCode() 返回相同的值，并且 equals() 也返回 true，则认为这两个键是相同的。
- 扩容机制：当 HashMap 中的元素数量达到一定的阈值（容量*加载因子，默认加载因子是 0.75），HashMap 会进行扩容，即创建一个新的更大的数组，并将旧数组的内容重新计算索引并复制到新数组中，这个过程称为“rehash”。
以下是一个简化的 HashMap 插入操作代码示例：
public V put(K key, V value) {if (key == null)return putForNullKey(value); // 键为null时特殊处理int hash = hash(key.hashCode()); // 计算散列码int i = indexFor(hash, table.length); // 计算索引位置for (Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;return oldValue;}}addEntry(hash, key, value, i); // 添加新条目return null;
}
上述代码简化了实际的实现，但基本展示了 HashMap 的插入过程，包括散列计算、查找链表、替换旧值或添加新节点等步骤。
40. 说一下 HashSet 的实现原理？
HashSet 是 Java 中集合框架的一部分，实现了 Set 接口。它基于 HashMap 实现，用于存储无序且不重复的元素集合。以下是 HashSet 的实现原理：
- 存储结构：
HashSet内部使用HashMap来存储元素。在HashMap中，元素以键值对（Entry）的形式存储，其中键就是我们要存储的元素本身，而值则是一个固定的常量。 - 哈希函数：当向
HashSet添加一个元素时，会使用这个元素自身的hashCode()方法来计算它的哈希值，并通过这个哈希值来确定在哈希表中的存储位置。 - 碰撞处理：如果两个不同的元素具有相同的哈希值（即发生了哈希碰撞），
HashSet会利用链表（在 JDK8 中，当链表长度超过一定阈值时，会转换为红黑树）来处理这种情况。在链表或红黑树中，元素按照插入顺序进行存储。 - 唯一性保证：对于每个要添加的元素，
HashSet不仅仅检查其哈希值，还会调用元素的equals()方法来确保没有重复元素被添加。如果元素的equals()方法返回true，HashSet将不会添加这个元素。- 如果在对应位置上没有元素，直接添加。
- 如果有元素，但
equals()方法返回false，则会添加到链表或红黑树中。 - 如果有元素且
equals()方法返回true，则忽略添加操作。
以下是 HashSet 添加元素流程的简化版：
public boolean add(E e) {return map.put(e, PRESENT) == null;
}
这里的 map 是 HashSet 内部维护的 HashMap 实例，而 PRESENT 是一个静态的常量对象，作为所有键对应的值。
总结：
HashSet基于哈希表实现，提供快速的查找、添加和删除操作。- 元素的唯一性由其
hashCode()和equals()方法共同决定。 HashSet不保证元素的顺序，且迭代顺序可能会随着元素数量的变化而变化。
领【150 道精选 Java 高频面试题】请go公众号：码路向前 。