将数据存储为 HashMap 和记录实例之间的时间复杂度差异

Question

对于我的一项学校作业，我必须使用 Java 解析 GenBank files。我必须存储和检索文件的内容以及提取的信息，以尽可能保持最小的时间复杂度。使用 HashMap 或将数据存储为记录有区别吗？我知道使用 HashMap 的时间复杂度为 O(1)，但使用记录的可读性和不变性让我更喜欢使用它们。这些对象将存储在一个数组中。

这是我现在的方法

public static GenBankRecord parseGenBankFile(File gbFile) throws IOException {
    try (var fileReader = new FileReader(gbFile); var reader = new BufferedReader(fileReader)) {
        String organism = null;
        List<String> contentList = new ArrayList<>();

        while (true) {
            String line = reader.readLine();
            if (line == null) break; //Breaking out if file end has been reached

            contentList.add(line);
            
            if (line.startsWith("  ORGANISM  ")) {
                // Organism type found
                organism = line.substring(12);  // Selecting the correct part of the line
            }
        }
        // Loop ended
        var content = String.join("\n", contentList);
        return new GenBankRecord(gbFile.getName(),organism, content);
    }
}

GenBankRecord 如下：

record GenBankRecord(String fileName,String organism, String content) {
    @Override
    public String toString(){
        return organism;
    }
}

假设键值对与记录的字段相同，使用记录和 HashMap 有区别吗？

String current_organism = gbRecordInstance.organism();

和

String current_organism = gbHashMap.get("organism");

Answer 1

I have to store and retrieve the content of the files together with the extracted information maintaining the smallest time complexity possible.

首先，我有点怀疑你们的老师是否真的提出了这样的要求。仅仅针对时间 复杂性 .

进行优化没有多大意义

复杂性不是效率。

大 O 复杂性与度量值（例如所用时间）本身无关。它实际上是关于度量（例如所用时间）如何随着某些变量变得非常大而变化。

例如，HashMap.get(nameStr)和someRecord.name都是O(1)复杂度。

但它们在效率上并不等同。使用带有命名字段的 Java 17 record 类型或常规 Java class 类型将比使用 [=] 快 个数量级 14=]。（而且它将使用更少数量级的内存。）

假设您的对象具有固定数量的命名字段，复杂性（即性能如何随着字段数量的不断增加而变化）甚至都不相关。

性能不是一切。

HashMap 和 record class 之间的最大区别实际上在于它们提供的功能：

A Map<String, SomeType> 提供一组名称/值对，其中：
- 集合中的对数不固定
- 名称不固定
- 值的类型都是 SomeType 或子类型的实例。
A record（或classic class）可以被视为一组字段名/值对，其中：
- 编译时固定对数
- 字段名称在编译时固定
- 字段类型不必是任何给定类型的子类型。

正如@Louis Wasserman 评论的那样：

Records and HashMap are apples and oranges -- it doesn't really make sense to compare them.

所以，实际上，您应该通过比较它们提供的功能/约束与您的应用程序实际需要的功能/约束来在记录和哈希图之间进行选择。

（您问题中的问题描述不够明确，我们无法做出判断。）

效率问题可能是相关的，但它是次要问题。（如果代码不满足功能需求，效率就没意义了。）

复杂性与您的作业相关吗？

嗯...也许是的。但不在您正在查看的区域。

我对这些要求的理解是，其中之一是您能够有效地从 in-memory 数据结构中检索信息。

但到目前为止，您一直在考虑存储个人记录。检索意味着您有一组记录并且您必须（有效地）检索特定记录，或者可能是一组符合某些条件的记录。所以这意味着你需要考虑数据结构来表示 collection.

假设您有一组 N 记录（或其他）代表（比如说）N 生物体：

如果集合是 List<SomeRecord>，您需要迭代列表以找到（比如）"cat" 的记录。即O(N).
如果集合是以有机体名称为关键字的 HashMap<String, SomeRecord>，您可以在 O(1).
中找到 "cat" 记录

将数据存储为 HashMap 和记录实例之间的时间复杂度差异

Difference in time complexity between storing data as a HashMap and record instance

java

record

hashmap

time-complexity

复杂性不是效率。

性能不是一切。

复杂性与您的作业相关吗？