如何将域名和网站绑定,做网站找投资人,西安有什么好玩的地方适合年轻人,平面设计接单攻略电子书39. 说一下 HashMap 的实现原理#xff1f;
HashMap 是 Java 中使用非常普遍的一种基于散列的映射数据结构#xff0c;主要用于存储键值对。它允许使用任何非空对象作为键和值#xff0c;主要实现原理如下#xff1a;
数组 链表 红黑树#xff1a;HashMap 内部主要由一…39. 说一下 HashMap 的实现原理
HashMap 是 Java 中使用非常普遍的一种基于散列的映射数据结构主要用于存储键值对。它允许使用任何非空对象作为键和值主要实现原理如下
数组 链表 红黑树HashMap 内部主要由一个数组构成每个数组元素是一个链表或红黑树链表或红黑树用于存储具有相同散列码的键值对。散列函数当向 HashMap 中插入一个键值对时首先会使用散列函数计算键的散列码散列码决定了键值对在数组中的位置。索引计算通过散列码与数组长度的模运算散列码 % 数组长度得到该键值对应在数组中的索引位置。链表和红黑树如果两个不同的键具有相同的散列码它们会被存储在同一个数组索引位置对应的链表中。如果链表长度过长默认超过8则会转换为红黑树以减少搜索时间。键的唯一性HashMap 中键的唯一性是通过 equals() 方法和 hashCode() 方法来保证的。如果两个键的 hashCode() 返回相同的值并且 equals() 也返回 true则认为这两个键是相同的。扩容机制当 HashMap 中的元素数量达到一定的阈值容量*加载因子默认加载因子是 0.75HashMap 会进行扩容即创建一个新的更大的数组并将旧数组的内容重新计算索引并复制到新数组中这个过程称为“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 (EntryK,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() 方法返回 trueHashSet 将不会添加这个元素。 如果在对应位置上没有元素直接添加。如果有元素但 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公众号码路向前 。
