我需要为以下情况找到合适的数据结构。我已经编写了一个带有事件和监听器的简单事件分发系统。该系统是完全顺序的，因此没有任何并发​​和同步问题。

需求与思考

• 每个监听器都注册到预定义(编译时)的 1 种或多种类型的事件。
• 监听器可以在运行时注册和注销。
• 必须保持监听器注册的顺序，因为这是他们接收事件的顺序(监听器总是在最后添加，但可以从任何地方删除)。
• 一个事件类型可以有 0 个或多个注册的监听器随时接收它。

这种关系的可视化可以用表格来解释:

       | Listener1 | Listener2 | Listener3 | Listner5
-----------------------------------------------------
Event1 |     X     |           |     X     |    X
-----------------------------------------------------
Event2 |           |     X     |     X     |    X
-----------------------------------------------------
Event3 |           |           |           |
-----------------------------------------------------
Event4 |           |           |           |    X
-----------------------------------------------------

• 行的顺序无关紧要。
• 必须保持列的顺序。
• 可以添加和删除列。
• 行数在运行期间是恒定的。

我的想法是:

• 调度事件时，我需要知道注册了哪些监听器来接收事件类型。我在考虑 Event -> Collection<Listener>键无序的映射。监听器集合需要维护插入顺序(或者不需要，如果可以使用以下几点代替)。
• 我需要保留一组保持插入顺序的监听器，无论它们注册到什么事件(此需求来自监听器所附加的对象)。因为即使 Collection<Listener>上面是插入顺序的，它是每个事件类型而不是全局的。我在考虑 OrderedCollection<Listener> .
• 取消注册时，我需要找到监听器已注册的所有事件类型，以便将其删除。我在考虑 Listener -> Collection<Event> , 除非第一点中的映射可以做 removeAll(Listener)对值位置的列表进行操作，但这可能会留下空列表，而不是完全删除键。

在我看来，双向多图适合这种情况。后备多图是一个 UnorderedMap<Event, OrderedCollection<Listener>>和一个 OrderedMap<Listener, UnorderedCollection<Event>> . OrderedCollection<Listener>如果从 OrderedMap 订购，则可能不需要订购可以使用。显然，任何无序的数据结构都可以进行排序，但这是不必要的。

或者，我看到过带有 reverse 的单一多重 map 的想法。/invert操作得到相反的映射。我的担忧是双重的:

1. 我不知道一方是否可以订购其 key 而另一方不能。
2. 这似乎是一项昂贵的操作，如果我需要一直反转映射，效率可能会很低。

伪代码用法

注册监听器:

// somewhere
Listener1 listener = new Listener1();
listener.register(); 

// class definition
class Listener1 extends AbstractListener {

    void register() {

        DataStructure.put(Event1.class, this);
        DataStructure.put(Event2.class, this);

        // or
                                 // some collection
        DataStructure.put(this, [Event1.class, Event2.class])
    }
}

调度一个事件:

// somewhere
EventManager.dispatch(new Event2());

// class definition
class EventManager {

    static void dispatch(Event event) {

        OrderedCollection<Listener> listeners = DataStructure.get(event);
        listeners.forEach(l -> l.processEvent(event)); // forEach maintains the order
    }
}

注销监听器:

Listener2 listener = ...;        // got it from somewhere
DataStructure.remove(listener);  // remove from everywhere and if a key is left with an empty list remove that key

最终细节和问题

如果重要的话，大约有 30 种事件类型，并发注册监听器的数量是 O(10)，尽管在程序的整个生命周期中可能有 O(100) 个监听器 - 其中大部分注销并被 GC .

关于订购的注释。由于监听器具有增量唯一 int id字段，我也许能够确保按 ID 号排序等同于按注册(插入)顺序排序。目前的差异是 id 是在监听器初始化时设置的，而注册是在之后完成的(并且可以在该间隙创建和注册另一个监听器)。如果在这种情况下使用排序集合比使用有序集合有优势，我可以做一些工作来保证按 id 排序等同于插入顺序。

什么数据结构适合我的需要？我是否需要自己编写(我不想重新发明轮子)或者是否已经实现了一个( Guava ，我正在看着你)？

最佳答案

如果我很好地理解您的问题，最好的结构似乎是 AbstractListener 列表的数组。

List<AbstractListener>[]

这里按要求描述要求:

要求:监听器可以在运行时注册和注销。

一个List可以处理add和 remove没有问题

要求:必须保持监听器注册的顺序，因为这是他们接收事件的顺序(监听器总是在最后添加，但可以从任何地方删除)。

列表维护顺序。来自 javadoc

An ordered collection (also known as a sequence)

要求:一个事件类型可以有 0 个或多个注册的监听器随时接收它。

一个列表可以包含 0 个或多个元素。

要求:必须保持列的顺序。

列表维护元素的顺序。

要求:可以添加和删除列。

List可以添加或删除元素(列)

要求:行的顺序无关紧要。

任何数据结构都没有问题

要求:行数在运行期间是恒定的。

数组大小不变

从您的评论到答案似乎另一种可能的解决方案是定义一个包含所有事件的类:

public interface Listener {
    public void handleEvent(Event event);
}

public class EventGenerator {
    private List<Listener> listeners;

    public void addListener(Listener listener) {
        listeners.add(listener);
    }

    public void removeListener(Listener listener) {
        listeners.remove(listener);
    }

    public void doSomething(Event event) {
        for (Listener listener : listeners) {
            listener.handleEvent(event);
        }
    }
}

对于每种事件，您都可以这样做:

// Create an event generator for each kind of event
EventGenerator eventGenerator1 = new EventGenerator();

EventGenerator eventGenerator2 = new EventGenerator();

// Register listeners to eventGenerators
eventGenerator1.addListener(listener1);
eventGenerator1.addListener(listener2);
eventGenerator1.addListener(listener3);

eventGenerator2.addListener(listener1);
eventGenerator2.addListener(listener2);
eventGenerator2.addListener(listener3);

...

// Eventually remove a listener
eventGenerator2.removeListener(listener2);

...

// When doSomething is invoked all listeners on that eventGenerator are invoked
eventGenerator1.doSomething(event1);  // Dispatched to listener 1, 2 and 3
eventGenerator1.doSomething(event2);  // Dispatched to listener 1, 2 and 3
eventGenerator1.doSomething(event3);  // Dispatched to listener 1, 2 and 3
eventGenerator1.doSomething(event4);  // Dispatched to listener 1, 2 and 3

eventGenerator1.removeListener(listener3);

eventGenerator1.doSomething(event5);  // Dispatched to listener 1, 2

eventGenerator1.removeListener(listener1);

eventGenerator1.doSomething(event6);  // Dispatched to listener 2

关于java - 什么数据结构适合事件和监听器的顺序事件分发系统？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38224772/