Flash AS3，如何用整数键索引哈希映射

Question

交易如下。

现在我有一本游戏状态字典

history = new Dictionary();

每个状态的key是一个时间戳（int）

history[100] = currentState;
history[500] = currentState;
history[699] = currentState;

我的问题是，我如何才能找到最近的游戏状态。假设我想知道670的状态，我想要不大于670的最新历史（我不想展示未来）。这将是history[500]。

现在我循环浏览每一个键，找到最近的一个。有没有什么方法可以索引这些时间戳，这样我可以比线性时间搜索得更快？（我会有很多钥匙！）也许我不想要字典？

Answer 1

您可以使用二进制搜索（分治）方法，将状态保存在排序数组中，然后递归：

1. 把数组分成两半
2. 如果数组包含一个项，则返回该项
3. 确定哪一半包含正确的结果
4. 转到步骤1

这应该可以在对数时间中找到结果。（请注意，log₂（1000）~10和log₂（10000）~13）

---

以下是一个草案（未经测试）实现：

class HistoryEntry
{
    public var timestamp:int;
    public var state:GameState;
    public function HistoryEntry(timestamp:int, state:GameState)
    {
        this.timestamp = timestamp;
        this.state = state;
    }
}
class History
{
    private var states:Array;
    public function History()
    {
        super();
        states = [];
    }
    public function addState(state:State):void
    {
        var timestamp:int = getTimer();
        var entry:HistoryEntry = new HistoryEntry(timestamp, state);
        states.push(entry);
    }
    public function getStateBefore(timestamp:int):State
    {
        return doGetStateBefore(timestamp, 0, states.length - 1);
    }
    // Recursive function
    private function doGetStateBefore(timestamp:int, beginIndex:int, endIndex:int):State
    {
        if (beginIndex == endIndex) {
            return states[beginIndex];
        }
        var beginEntry:HistoryEntry = states[beginIndex];
        var endEntry:HistoryEntry = states[endIndex];
        if (beginEntry.timestamp == timestamp) {
            return beginEntry.state;
        }
        if (endEntry.timestamp == timestamp) {
            return endEntry.state;
        }
        var middleIndex:int = (beginIndex + endIndex) / 2;
        var middleEntry:HistoryEntry = states[middleIndex];
        if (midleEntry.timestamp >= timestamp) {
            return doGetStateBefore(timestamp, beginIndex, middleIndex);
        } else {
            return doGetStateBefore(timestamp, middleIndex + 1, endIndex);
        }
    }
}

我引入了类HistoryEntry，以便从数组中获得类型化对象，因为使用动态对象会对性能产生负面影响。