用于以下场景的最佳数据结构（如哈希映射/列表等）是什么

Question

我有一个要求，比如有一个项目 A，它有几个子项目，如 a1,b1,c1...，每个子项目又有几个子项目，如 {a11,a12,a13...} 对应于a1 和 {b11,b12,b13..} 对应于 b1。所以，它基本上就像一个以项目 A 为根的树结构。现在，每个项目及其子项目都有一些关联的时间戳。所有这些项目和子项目的时间戳都不同。我需要找到具有最新时间戳的项目/子项目。如何在java中继续解决这个问题。我对使用数据结构有点陌生。

Answer 1

使用 TreeMap

它会满足您的需要。这是来自 java.samples.com 的示例程序

// Create a tree map 
TreeMap tm = new TreeMap(); 
// Put elements to the map 
tm.put("John Doe", new Double(3434.34)); 
tm.put("Tom Smith", new Double(123.22)); 
tm.put("Jane Baker", new Double(1378.00)); 
tm.put("Todd Hall", new Double(99.22)); 
tm.put("Ralph Smith", new Double(-19.08)); 
// Get a set of the entries 
Set set = tm.entrySet(); 
// Get an iterator 
Iterator i = set.iterator(); 
// Display elements 
while(i.hasNext()) { 
Map.Entry me = (Map.Entry)i.next(); 
System.out.print(me.getKey() + ": "); 
System.out.println(me.getValue()); 
} 
System.out.println(); 
// Deposit 1000 into John Doe's account 
double balance = ((Double)tm.get("John Doe")).doubleValue(); 
tm.put("John Doe", new Double(balance + 1000)); 
System.out.println("John Doe's new balance: " + 
tm.get("John Doe"));

Answer 2

对于数据结构，请查看 java.util.TreeMap 以了解树支持的 Map 实现，并查看 java.util.TreeSet 以了解树支持的 Set 实现。这些是 Java Collections API 中的标准实现。

package com.mindprod.example;

import java.util.Collection;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

import static java.lang.System.out;

/**
 * Example use of java.util.TreeMap.
 *
 * @author Roedy Green, Canadian Mind Products
 * @version 1.0 2010-02-25 initial version
 * @see TestHashMap
 * @since 2010-02-25
 */
public final class TestTreeMap
{
// --------------------------- main() method ---------------------------

/**
 * Sample code to TEST TreeMap.
 *
 * @param args not used
 */
public static void main( String[] args )
    {
    // create a new HashMap
    TreeMap<String, String> t = new TreeMap<String, String>( /* no size estimates needed */ );
    // add some key/value pairs to the TreeMap
    t.put( "WA", "Washington" );
    t.put( "NY", "New York" );
    t.put( "RI", "Rhode Island" );
    t.put( "BC", "British Columbia" );
    t.put( "NC", "North Carolina" );
    t.put( "NE", "Nebraska" );
    // look up a key in the TreeMap
    String stateName = t.get( "NY" );
    // prints "New York"
    out.println( stateName );
    out.println( "enumerate all the keys in the TreeMap, by key" );
    // keySet gives you a Set, which is not a List.
    // If you need something you can sort, use toArray.
    // If you need a List, then use Arrays.asList.
    for ( String key : t.keySet() )
        {
        String value = t.get( key );
        // prints lines of the form NY New York
        // in key order, unlike a HashMap
        out.println( key + " " + value );
        }
    out.println( "enumerate all the values in the TreeMap, by key, note values out of order" );
    // values gives you a Collection which is not a List.
    // If you need something you can sort, use to Array.
    // If you need a List, then use Arrays.asList.
    for ( String value : t.values() )
        {
        // prints lines of the form New York
        // in key order, unlike a HashMap
        out.println( value );
        }
    out.println( "enumerate all the key/value Entries in the TreeMap, by key" );
    // This gives you a Map of Entry items. This is not suitable for sorting.
    for ( Map.Entry<String, String> entry : t.entrySet() )
        {
        // prints lines of the form NY=New York
        // in key order, unlike a HashMap
        out.println( "as Entry: " + entry );
        // this does not require an expensive get lookup to find the value.
        String key = entry.getKey();
        String value = entry.getValue();
        out.println( "separately: " + key + " " + value );
        }
    out.println( "extract the keys into an array" );
    // actual type is a private nested static class TreeMap.KeySet
    // This Set is not Serializable.
    Set<String> justKeys = t.keySet();
    // Use toArray that takes an skeleton String[] array,
    // otherwise we end up with a useless Object[] instead of a String[].
    final String[] keys = justKeys.toArray( new String[ justKeys.size() ] );
    out.println( "extract values into an array, may contain duplicates unlike a Set." );
    // the actual type is a private nested static class TreeMap.Values
    // This Collection is not Serializable.
    final Collection<String> justValues = t.values();
    final String[] values = justValues.toArray( new String[ justValues.size() ] );
    out.println( "extract key/value pair entries into an array." );
    final Set<Map.Entry<String, String>> justEntries = t.entrySet();
    @SuppressWarnings( "unchecked" ) final Map.Entry<String, String>[] keyValuePairs =
            justEntries.toArray( new Map.Entry[ justEntries.size() ] );
    // Infuriatingly, this generates an unchecked conversion warning message.
    // Type erasure won't let us say:
    // Map.Entry<String, String>[] keyValuePairs =
    // justEntries.toArray ( new Map.Entry<String,String>[justEntries.size()] );
    // There might be some clever way of using Class.asSubclass to mollify the compiler.
    // There so many times when generics create more problems than they solve.
    }
}

您可能也对此链接感兴趣

Answer 3

JDK 中实现了一个不错的树结构。

查看 TreeModel 和 TreeNode，它们设计为与 JTreePanel 一起使用，但没有什么可以阻止您在 Swing 之外使用它。

Answer 4

我建议您为 Item 创建一个类，然后您可以单独设计该类。

对于子项取决于数据类型，选择不同的数据结构。
首先，如果您知道项目具有相同的类型，例如 a1、b1、c1 都是字符串，那么您可以使用 ArrayList 来保存它们，或者如果总数有界，则可以使用数组。如果类型不同，就考虑hashmap。

Answer 5

您可以简单地使用数组

ArrayList list=new ArrayList();
ArrayList sublist=new ArrayList();
ArrayList subsublist=new ArrayList();
subsublist.add("cat");
sublist.add(subsublist);
list.add(sublist);

Answer 6

假设不存在B项：

1. 将A项、B项、C项……存储在一个链表中。 （每个节点成为根）
2. 项目 A 将在链表中具有以下子节点：a1、b1、c1 ...。 （每个节点成为根）
3. a11、a12、a13可以存储为a1的子节点。
4. b11、b12、b13 类似...

现在，您在哪里面临问题？

Answer 7

将每个项目视为一个节点。所以创建一个Node类。这个班级将有以下成员 -
节点名称、父节点、子节点。

public class Node
  {
    private String name;
    private Node parentNode;
    private Node childNode;
  }

根据您的用途添加附加属性。

编写构造函数来创建 Node 对象，如下所示 -

public Node(String name)
  {
    this.name = name;
    this.parentNode = null;
    this.childNode = null;
  }

您将需要为它们生成 getter 和 setter，以获取关联的父节点和子节点。

我没有测试过代码。请根据要求重新格式化它，并让我知道它是否解决了您的问题。

Answer 8

建议实现您自己的树结构，因为看起来您的要求是自己维护一个显式的树模型。例如，

public class Item implements Comparable<Item>{

    private String name;
    private long timestamp;
    private List<Item> subItems = new ArrayList<Item>();

    public Item(String name, long timestamp){
        this.name = name;
        this.timestamp = timestamp;
    }

    public void addItem(Item subItem){
        this.subItems.add(subItem);
    }

    @Override
    public int compareTo(Item o) {
        return Long.signum(this.timestamp - o.timestamp);
    }

}

如果您想获取时间戳最大或最小的项目或对它们进行排序，您可以将所有项目放入一个 List 中并使用 Collections.sort() 进行排序，因为您已经实现了 Comparable 接口。