当前位置： 首页 > article >正文

java基础面试题七数据结构与集合源码

article 2024/11/27 1:43:04

目录

1. 链表和数组有什么区别？

2. 栈是如何运行的？

3. ArrayList的默认大小是多少，以及扩容机制

4. ArrayList的底层是怎么实现的?

5. 数组和 ArrayList 的区别

6. 什么是线程安全的List？

7. 说说HahMap底层实现

8. HashMap初始值16，临界值12是怎么算的

9.HashMap长度为什么是2的幂次方

10. HashMap怎么计算哈希值和索引？扩容机制？怎么解决hash冲突？

11. HashMap底层是数组+链表，有数组很快了，为什么加链表？

12. HashMap为什么长度达到一定的长度要转化为红黑树

13. HashMap什么时候扩充为红黑树，什么时候又返回到链表？

14. 在 JDK1.8中，HashMap的数据结构与1.7相比有什么变化，这些变化的好处在哪里？

15. HashMap的get()方法的原理?

16. hashcode和equals区别？

17. hashCode() 与 equals() 生成算法、方法怎么重写？

18. 说一下equals和==的区别，然后问equals相等hash值一定相等吗？hash值相等equals一定相等吗？

19. HashSet存放数据的方式？

20. Set是如何实现元素的唯一性？

21. 用哪两种方式来实现集合的排序

1. 链表和数组有什么区别？

  • 选择数组：当数据量固定且需要高效的随机访问时。
  • 选择链表：当数据量动态变化且需要频繁插入或删除操作时。

2. 栈是如何运行的？

先进后出。属于ADT(abstract data type)，可以使用数组、链表实现栈结构

3. ArrayList的默认大小是多少，以及扩容机制

ArrayList的扩容机制

ArrayList 的扩容机制是通过增加底层数组的大小来实现的。当元素数量超过当前容量时，ArrayList 会自动扩容。扩容的过程如下：

  1. 触发扩容：当向 ArrayList 中添加元素时，如果当前容量不足以容纳新元素，就会触发扩容操作。
  2. 新容量计算：
    • 扩容后的新容量为 原容量的1.5倍（即：newCapacity = oldCapacity + (oldCapacity >> 1)）。
    • 例如：
      • 如果当前容量为10，扩容后容量将变为15。
      • 如果当前容量为15，扩容后容量将变为22。
  3. 数组复制：
    • 扩容后，会创建一个新的数组，并将旧数组中的元素复制到新数组中。

4. ArrayList的底层是怎么实现的?

ArrayList 是 Java 中的一个动态数组实现，属于 java.util 包。其底层依赖于一个可变大小的数组来存储元素。以下是 ArrayList 的核心实现原理：

1. 底层数据结构

  • 数组：ArrayList 内部使用一个 Object[] 数组 来存储元素。它的声明如下：

transient Object[] elementData; // 用于存储元素的数组

transient 关键字：表示该字段不会被序列化，这是一种优化手段。

2. 添加元素（add 操作）

当调用 add(E e) 方法时：

  1. 检查容量：
    • 确保底层数组有足够的空间容纳新元素。如果当前容量不足，会调用 ensureCapacityInternal 方法进行扩容。
  2. 存储元素：
    • 将元素添加到数组的下一个空位。
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 确保有足够的容量
    elementData[size++] = e;           // 将元素存入数组并增加size
    return true;
}

3. 扩容机制

  • 如果当前数组满了，会触发扩容。扩容的步骤包括：

    1. 计算新容量：通常是原容量的 1.5 倍。
    2. 创建新数组：分配一个新的、更大的数组。
    3. 复制元素：将旧数组中的元素复制到新数组中。

4. 删除元素（remove 操作）

  • 删除元素时，ArrayList 会将所有后续元素向前移动一位，以填补被删除元素的位置，并将最后一个元素置空。

5. 数组和 ArrayList 的区别

  ArrayList看做是对数组的常见操作的封装。

总结

特性数组ArrayList
大小固定动态调整
存储类型基本类型和对象仅存储对象（使用包装类）
访问速度O(1)O(1)
插入/删除效率低，需要手动移动元素高，内置方法处理
内存使用高效，无额外开销可能有预留空间，开销较大
功能支持无内置方法提供丰富的方法
多维支持直接支持通过嵌套实现
适用场景固定大小、性能优先大小变化、不确定元素数量

6. 什么是线程安全的List？

线程安全的 List 是指在多线程环境中，多个线程可以安全地访问和修改同一个 List 实例，而不会导致数据不一致或抛出异常。线程安全的 List 提供了同步机制，确保每个线程在操作 List 时，不会与其他线程发生冲突。

Vector：线程安全的。

ArrayList：线程不安全。----> 使用同步机制处理。

7. 说说HahMap底层实现

1. HashMap 的基本结构

  • 数组 + 链表 + 红黑树：
    • HashMap 由一个 Node 数组 组成，每个元素（桶）都是一个 链表 或 红黑树。
    • 在 Java 8 之前，HashMap 只使用 数组 + 链表。Java 8 引入了 红黑树，解决链表过长导致的性能问题。

2. 核心数据结构

  • Node 类（存储键值对）：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;   // 键的哈希值
    final K key;      // 键
    V value;          // 值
    Node<K,V> next;   // 下一个节点引用（用于链表）
}

重要字段：

  • hash：通过键计算出的哈希值。
  • key 和 value：键值对数据。
  • next：指向下一个节点（用于解决哈希冲突）。

总结

  • 核心结构：HashMap 由 数组 + 链表 + 红黑树 组成。
  • 存储逻辑：根据键的哈希值计算索引，并存储在对应的桶中。
  • 哈希冲突解决：使用链表解决冲突，链表过长时转换为红黑树。
  • 性能：平均时间复杂度为 O(1)；在最坏情况下（大量冲突时），链表查找是 O(n)，而红黑树是 O(log n)。

通过引入红黑树，Java 8 优化了 HashMap 在高冲突场景下的性能，确保了更高的查询效率。

8. HashMap初始值16，临界值12是怎么算的

HashMap 的初始容量（默认值）是 16，默认负载因子是 0.75。临界值（threshold）是指触发 扩容 的元素数量阈值。临界值的计算公式如下：

临界值=初始容量×负载因子

9.HashMap长度为什么是2的幂次方

1. 高效的哈希计算

在 HashMap 中，确定元素存储位置（索引）是通过以下公式计算的：索引=(hash&(length−1))

其中：

  • hash：键的哈希值。
  • length：数组长度（必须是 2 的幂次方）。

为什么用 2 的幂次方能简化计算？

  1. 位运算的优势：

    • 位运算（&）比取模运算（%）更快。
    • 当 length 是 2 的幂次方时，hash & (length - 1) 等价于 hash % length，但效率更高。

  2. 避免负数问题：

    • 位运算直接操作二进制位，避免了负数取模的复杂处理。

  3. 均匀分布：

    • length - 1 的二进制形式是全 1（如 16 - 1 = 15 的二进制为 1111）。
    • hash & (length - 1) 操作能确保索引均匀分布在 [0, length - 1] 之间，减少哈希冲突。

2. 减少哈希冲突

  • 哈希冲突：当不同键的哈希值计算出相同的数组索引时，就会发生哈希冲突。

  • 2 的幂次方长度的作用：

    • 确保在计算索引时，只取哈希值的低位参与计算，而低位的变化更容易分散。
    • 如果长度是 2 的幂次方，哈希值中的所有位都能有效参与索引计算，从而提高分散性，减少冲突。

3. 负载因子与扩容效率

  • 扩容机制：
    当 HashMap 扩容时，容量会变为原来的 2 倍。这样扩容后，原索引的元素要么保持不变，要么移动到新数组中的新索引（原索引 + 原容量）。

    • 例如，当前容量为 16，扩容到 32：
      • 原索引 index = hash & 15
      • 新索引有两种情况：
        • index（保留原位置）
        • index + 16（原位置 + 旧容量）

    这种扩展方式避免了重新计算所有哈希值，提升了扩容效率。

10. HashMap怎么计算哈希值和索引？扩容机制？怎么解决hash冲突？

  • 哈希值计算：

    1. 获取键的 hashCode()。
    2. 通过扰动函数混合高低位：(h = key.hashCode()) ^ (h >>> 16)。

  • 索引计算：

    索引=(hash&(length−1))

  • 扩容机制：

    • 触发条件：元素数量达到 容量 × 负载因子。
    • 扩容后，容量翻倍，并重新分配元素。

  • 哈希冲突解决：

    • 使用 链表 存储冲突元素。
    • 链表长度超过阈值时，转换为 红黑树，提高性能。

通过这些设计，HashMap 实现了高效的存储、查找和扩容，保证了在多种场景下的性能表现。

11. HashMap底层是数组+链表，有数组很快了，为什么加链表？

 总结：为什么数组需要链表？

  1. 解决哈希冲突：数组只能存储一个元素，链表使得同一个桶可以存储多个元素。
  2. 数据完整性：确保即使哈希冲突发生，也不会覆盖已有数据。
  3. 平衡时间与空间复杂度：
    • 正常情况：数组提供快速访问。
    • 冲突情况：链表保证数据存储，红黑树提升性能。
  4. 扩展性：链表结构灵活，支持动态增加元素；结合红黑树后，可以应对大规模数据和严重冲突。

12. HashMap为什么长度达到一定的长度要转化为红黑树

  • 链表转换为红黑树的原因：为了优化哈希冲突严重时的查找性能。
  • 触发条件：
    • 链表长度 ≥ 8 且数组长度 ≥ 64。
    • 删除元素后，链表长度 ≤ 6 时转换回链表。
  • 红黑树的优势：查找、插入、删除操作的时间复杂度为 O(log n)，远优于链表的 O(n)。

通过这种设计，HashMap 在处理大量数据或严重哈希冲突时依然能保持高效的性能。

13. HashMap什么时候扩充为红黑树，什么时候又返回到链表？

转换方向触发条件原因
链表 → 红黑树链表长度 ≥ 8 且数组长度 ≥ 64提高查找性能，避免线性时间复杂度。
红黑树 → 链表链表长度 ≤ 6节省内存开销，链表在小规模冲突下高效。

14. 在 JDK1.8中，HashMap的数据结构与1.7相比有什么变化，这些变化的好处在哪里？

① 在jdk8中，当我们创建了HashMap实例以后，底层并没有初始化table数组。当首次添加(key,value)时，进行判断，
如果发现table尚未初始化，则对数组进行初始化。
② 在jdk8中，HashMap底层定义了Node内部类，替换jdk7中的Entry内部类。意味着，我们创建的数组是Node[]
③ 在jdk8中，如果当前的(key,value)经过一系列判断之后，可以添加到当前的数组角标i中。如果此时角标i位置上有
   元素。在jdk7中是将新的(key,value)指向已有的旧的元素（头插法），而在jdk8中是旧的元素指向新的
   (key,value)元素（尾插法）。 "七上八下"
④ jdk7:数组+单向链表
   jk8:数组+单向链表 + 红黑树
   什么时候会使用单向链表变为红黑树：如果数组索引i位置上的元素的个数达到8，并且数组的长度达到64时，我们就将此索引i位置上
                               的多个元素改为使用红黑树的结构进行存储。（为什么修改呢？红黑树进行put()/get()/remove()
                               操作的时间复杂度为O(logn)，比单向链表的时间复杂度O(n)的好。性能更高。
   什么时候会使用红黑树变为单向链表：当使用红黑树的索引i位置上的元素的个数低于6的时候，就会将红黑树结构退化为单向链表。

15. HashMap的get()方法的原理?

  • 时间复杂度：

    • 最佳情况：O(1)（键分布均匀，无冲突）。
    • 最坏情况：O(n)（大量冲突，链表较长）。
    • 红黑树优化：在冲突严重时，复杂度降低为 O(log n)。

  • 关键点：

    • 通过哈希值和数组索引定位桶。
    • 使用 hashCode() 和 equals() 保证键的准确匹配。
    • 通过链表或红黑树解决哈希冲突，提高查找效率。

16. hashcode和equals区别？

属性hashCode()equals()
返回值返回一个整数（哈希值）返回一个布尔值（true 或 false）
作用用于确定对象在哈希集合中的存储位置用于判断两个对象的内容是否相等
比较逻辑计算哈希码（可能不同对象有相同哈希值）比较对象的实际内容
默认实现基于对象内存地址生成哈希值基于对象引用比较（==）
重写要求如果重写了 equals()，通常也要重写 hashCode()可以根据需要自定义比较逻辑

17. hashCode() 与 equals() 生成算法、方法怎么重写？

1. 重写 equals() 方法

基本原则：

  1. 自反性：x.equals(x) 必须返回 true。
  2. 对称性：x.equals(y) 为 true 时，y.equals(x) 也必须为 true。
  3. 传递性：x.equals(y) 和 y.equals(z) 都为 true 时，x.equals(z) 必须为 true。
  4. 一致性：在对象状态未改变的情况下，多次调用 equals() 应返回相同的结果。
  5. 与 null 比较：任何对象与 null 比较都应返回 false。

2. 重写 hashCode() 方法

基本原则：

  1. 如果两个对象通过 equals() 方法比较返回 true，那么它们的 hashCode() 值必须相等。
  2. 如果两个对象 equals() 返回 false，它们的 hashCode() 值不必不同，但不同的哈希值有助于提高哈希集合的性能。
  3. hashCode() 生成的哈希值应尽量分布均匀，以减少哈希冲突。

18. 说一下equals和==的区别，然后问equals相等hash值一定相等吗？hash值相等equals一定相等吗？

问题 1：equals() 相等，hashCode() 一定相等吗？

答案：是的。
根据 Java 规范：

  • 如果两个对象通过 equals() 比较返回 true，那么它们的 hashCode() 必须相等。
  • 这是为了确保在哈希集合（如 HashMap、HashSet）中能正确地存储和检索对象。

问题 2：hashCode() 相等，equals() 一定相等吗？

答案：不一定。

  • 不同对象可能具有相同的哈希值（这种情况称为 哈希冲突）。
  • 因此，hashCode() 相等并不意味着 equals() 也一定返回 true。

19. HashSet存放数据的方式？

  • 底层数据结构：HashSet 基于 HashMap。
  • 存储元素：将元素作为 HashMap 的键，固定常量 PRESENT 作为值。
  • 元素唯一性：依赖于 HashMap 的 hashCode() 和 equals() 方法来判断重复。

20. Set是如何实现元素的唯一性？

实现唯一性的原理

不同类型的 Set 实现唯一性的方式略有不同，但核心依赖于元素的 hashCode() 和 equals() 方法：

  1. hashCode() 方法：用于计算对象的哈希值。
  2. equals() 方法：用于比较对象的内容是否相等。

1. HashSet 的唯一性实现

  • 底层结构：HashSet 使用 HashMap 存储元素。
  • 存储逻辑：
    • 当向 HashSet 添加元素时，实际上是将元素作为 HashMap 的键（key）。
    • HashMap 的键不能重复，因此 HashSet 也不会存储重复元素。
  • 流程：
    1. 调用元素的 hashCode() 计算哈希值，定位到哈希桶。
    2. 如果哈希桶中已有元素，使用 equals() 比较新旧元素。
    3. 若 equals() 返回 true，认为元素重复，不插入。
    4. 若返回 false，插入元素。

2. LinkedHashSet 的唯一性实现

  • 底层结构：基于 LinkedHashMap。
  • 与 HashSet 的区别：
    • 同样使用 HashMap 存储元素，但维护一个双向链表来记录元素的插入顺序。
  • 唯一性判断逻辑：
    • 与 HashSet 相同，依赖于 hashCode() 和 equals()。

3. TreeSet 的唯一性实现

  • 底层结构：基于 红黑树。
  • 存储逻辑：
    • 使用自然顺序或自定义比较器（Comparator）对元素进行排序。
    • 在插入新元素时，会根据比较器判断新元素与已有元素是否相等：
      • 如果比较结果为 0，表示元素重复，不插入。
  • 依赖方法：
    • 自然排序：对象必须实现 Comparable 接口，重写 compareTo() 方法。
    • 自定义排序：使用 Comparator 对象比较。

21. 用哪两种方式来实现集合的排序

1. 使用 Comparable 接口

  • 定义：Comparable 是一个用于定义对象自然排序顺序的接口。
  • 实现方式：类实现 Comparable 接口，并重写 compareTo() 方法。
  • 适用场景：当对象具有自然顺序（例如，按数字大小、字母顺序）时使用。

2. 使用 Comparator 接口

  • 定义：Comparator 是一个函数式接口，可以用来定义自定义排序规则。
  • 实现方式：
    • 创建 Comparator 实例，通常使用匿名类或 Lambda 表达式。
    • 适用于无法修改类本身，或需要多个排序规则的情况。
  • 适用场景：当需要对对象进行多种不同的排序或不方便修改对象类时使用。

http://www.kler.cn/a/410729.html

相关文章：

  • Apache Maven 标准文件目录布局
  • React表单联动
  • 数学建模_基于对数和傅里叶变换的多通道图像增强模型(处理模糊)Matlab代码包教会使用,直接替换数据即可
  • ORB-SLAM2源码学习：Initializer.cc:Initializer::ComputeF21地图初始化——计算基础矩阵
  • 记录一些PostgreSQL操作
  • Python 网络爬虫操作指南
  • go语言闭包捕获的是变量的引用而不是变量的值
  • 【GoF23种设计模式】01_建造者模式
  • 40_U²-Net网络详解
  • 【shodan】（五）网段利用
  • 跨标签通信的几种方式
  • Sickos1.1 详细靶机思路 实操笔记
  • 【人工智能】Python与Scikit-learn的模型选择与调参：用GridSearchCV和RandomizedSearchCV提升模型性能
  • 音视频处理PCM相关概念：帧（Frame）、周期（Period Size）、量化、 声道数（Channels）、采样位数（Sample Bits）、采样频率
  • 鸿蒙操作系统（HarmonyOS）开发的初学者了解和入门
  • goframe开发一个企业网站 在vue-next-admin 显示验证码 19
  • Android 底部导航栏未选中菜单项显示文本title
  • 移动端，树形数据的一种展示形式
  • 嵌入式硬件设计：从概念到实现的全流程
  • python中的把列表组合成字典
  • 【MySQL实战45讲笔记】基础篇—— 全局锁和表锁
  • linux mount nfs开机自动挂载远程目录
  • C++ Qt QTextBrowser使用方法总结
  • FPGA实现PCIE3.0视频采集转10G万兆UDP网络输出，基于XDMA+GTH架构，提供工程源码和技术支持
  • 亚太杯数学建模A题——复杂场景下水下图像增强技术的研究 思路（更新部分）
  • docker创建vue镜像