2

这个问题是我在接受 Adob​​e 采访时提出的。我回答hashmap可以用，但他不满意。

文件 1

< tag1 >  
  < subtag1 >  
    < subsubtag1 >  
    </subsubtag1 >  
  < /subtag1 >  
< /tag1 >  
< tag2 >  
< /tag2 >

n个这样的文件（即 XML 文件）需要存储在内存中。编写用于将这些文件存储在内存中的 java 数据结构的实现，目的是有效地执行以下操作：

  1. 访问特定文件中的特定标签。
  2. 访问该标签所在的所有文件中的特定标签。

笔记：

  1. 有数百万个文件要存储
  2. 每个文件包含数百万个标签，每个标签可能包含数百万个子标签
4

3 回答 3

0

我想TreeSet。

访问和检索时间非常快，这使得 TreeSet 成为存储大量必须快速找到的排序信息时的绝佳选择。

像这样的东西：

public class Storage{

  private String mTagName;
  private String mAttribute;
  private TreeSet<Storage> mTree; 
}

包含TreeSet自身的类。适合递归。

于 2013-09-21T20:06:16.107 回答
0

我不认为使用 HashMap 是问题（在底部解释）。假设您的 XML 不包含任何属性HashMap<String, Element>（TreeMap 也可以使用），其中 String 是 XML 标记，并且

class Element {
    Set<Files /* or something that represents them */> filesContainingTag;
    Map<String, Element> subTags;
}

这样你就知道哪些文件包含给定的“标签路径”并且可以获得单个文件。要访问给定文件中的标签，只需按标签浏览此结构并检查此文件是否在filesContainingTag. 或者，如果您以某种方式（例如通过路径）识别这些文件，则使用 Map 而不是 set。

为什么使用 Hash* 而不是 Tree* 结构？因为如前所述 - 当您需要在迭代中排序时， Tree* 是很好的选择。在大多数其他情况下，Hash* 更快且更易于使用（实现散列函数比比较器更容易）。您不喜欢使用 Hash* 的唯一情况是当您预期恶意输入时 - 当有人知道您正在使用什么散列函数并会提供充满冲突的数据时。

于 2013-09-21T20:17:36.410 回答
0

问题可能出在问题的注释上，它需要访问大型数据集。它肯定不会完全适合内存，但如果您卸载未使用的数据，它可能会部分适合。所以我会选择

  • WeakHashMap当您的应用程序中不再使用某个项目时，它会在 GC 期间卸载
  • 或 Google Guava 的CacheBuilder，它具有良好且可调的驱逐策略
于 2013-09-23T12:06:40.577 回答