1

有没有更好的方法在 Java 中执行以下操作，而不使用外部库。

我需要对 int（原始）的组/子（树状）结构进行建模。在 Json 中

[{1,1}, {1,2}, {2,1},{3,1}]

我需要支持添加/删除元素（元素是一对 {group, child} ）而不重复。

我在想，保持一个数据结构。

ArrayList<HashMap<Integer,Integer>>

加上。

遍历 ArrayList，对照要插入的值检查 HashMap 键和值，如果不存在则插入。

删除：

遍历 ArrayList，对照要删除的值检查 HashMap 键和值，如果存在则删除。

标准库是否有更好的数据结构/方法。

根据以下答案之一，我开设了这样的课程。请让我知道有什么要注意的。我期待（并将尝试）arraylist 将通过使用 KeyValue 类中的 equal 方法正确处理添加/删除。谢谢。

 static class KeyValue {
        int groupPos;
        int childPos;

        KeyValue(int groupPos, int childPos) {
            this.groupPos = groupPos;
            this.childPos = childPos;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            KeyValue keyValue = (KeyValue) o;

            if (childPos != keyValue.childPos) return false;
            if (groupPos != keyValue.groupPos) return false;

            return true;
        }

        @Override
        public int hashCode() {
            int result = groupPos;
            result = 31 * result + childPos;
            return result;
        }
    }
4

5 回答 5

2

如果我了解您要做什么，这可能会更简单：

TreeMap<Integer,TreeSet<Integer>>
  or
HashMap<Integer,HashSet<Integer>>

所以，而不是

[{1,1}, {1,2}, {2,1}, {3,1}]

你会有

[{1, {1, 2}},
 {2, {1}},
 {3, {1}}]

请注意，上述所有 4 个类都会自动处理消除重复项。

加上：

TreeMap<Integer, TreeSet<Integer>> map;
TreeSet<Integer> set = map.get(group);
if (set == null) // create it if it doesn't exist
{
  set = new TreeSet<Integer>();
  map.put(group, set);
}
set.add(child);

去除：

TreeMap<Integer, TreeSet<Integer>> map;
TreeSet<Integer> set = map.get(group);
set.remove(child);
if (set.isEmpty()) // remove it if it is now empty
  map.remove(group);
于 2013-02-07T17:12:21.990 回答
1

您可以编写一个具有名称的类，该类具有KeyValue两个属性来保存组和子项。将KeyValue对象添加到ArrayList. 对于 CRUD 操作，您可以在 KeyValue 对类中实现equals和。compare

于 2013-02-07T17:15:36.933 回答
0

取而代之的是HashMap，使用一个带有两个将实现接口Pair的字段调用的类。然后实现/覆盖它的,和方法。然后使用 a或根据您的需要来持有它们。实施后，您也可以灵活地轻松排序。{group,child}Comparableequals()hashCode()compareTo()List<Pair>Set<Pair>compareTo()Pairs

于 2013-02-07T17:20:49.077 回答
0

我是数据结构世界的新手，但我认为我们可以基于没有两个 Set 对象相似的假设来使用它

设置validSet=new HashSet(); // 这里使用泛型

HashSet 将为添加/删除/包含提供恒定的时间

SomeObject{
     Integer parent ;
     Integer child;
     //define equals method based on your requirement
}
于 2013-02-07T17:42:15.263 回答
0

按照你的问题，我认为你想展示这条线

[{1,1}, {1,2}, {2,1},{3,1}]

作为

Group 1-> 1 , 2 (来自前两对)
Group 2-> 1(来自第三对)
Group 3-> 1 (来自第四对)

最适合存储此层次结构的数据结构是：

Map<Integer,Set<Integer>> map = new HashMap<Integer,Set<Integer>>();

地图key部分存储组号的位置。地图的value一部分是存储TreeSet该组的孩子。
作为代码示例：

import java.util.HashMap;
import java.util.ListIterator;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
class  TreeLike
{
    public static void main(String[] args) 
    {
        Map<Integer,Set<Integer>> map = new HashMap<Integer,Set<Integer>>();
        int groups[] = {1,2,3,4,5,6,7};
        //To add new group in map
        for (int i = 0 ; i < groups.length; i++)
        {
            Set<Integer> child = new TreeSet<Integer>();
            child.add(1);child.add(2);child.add(3);child.add(4);child.add(5);
            map.put(groups[i],child);
        }
        //To add new child(8) to a group (say group 1)
        Set<Integer> child = map.get(1);
        if (child != null)
        {
            child.add(8);
            map.put(1,child);
        }

        //To remove a child (say child 4) from group 3
        child = map.get(3);
        if (child != null)
        {
            child.remove(4);
            map.put(1,child);
        }
        //To Iterate through all trees
        Set<Map.Entry<Integer,Set<Integer>>> entrySet = map.entrySet();
        Iterator<Map.Entry<Integer,Set<Integer>>> iterator = entrySet.iterator();
        while (iterator.hasNext())
        {
            Map.Entry<Integer,Set<Integer>> entry = iterator.next();
            int group = entry.getKey();
            Set<Integer> children = entry.getValue();
            System.out.println("Group "+group+" children-->"+children);
        }
    }
}
于 2013-02-07T17:56:26.383 回答