performance - 在非连续内存中进行O(1)查找？

是否有任何已知的数据结构可提供O(1)随机访问，而无需使用大小为O(N)或更大的连续内存块？这是受this answer启发的，出于好奇心的缘故而不是任何特定的实际用例被要求，尽管据推测，这可能在堆严重碎片化的情况下很有用。

最佳答案

是的，这是C++中的示例:

template<class T>
struct Deque {
  struct Block {
    enum {
      B = 4*1024 / sizeof(T), // use any strategy you want
                              // this gives you ~4KiB blocks
      length = B
    };
    T data[length];
  };
  std::vector<Block*> blocks;

  T& operator[](int n) {
    return blocks[n / Block::length]->data[n % Block::length]; // O(1)
  }

  // many things left out for clarity and brevity
};

与std::deque的主要区别在于，它具有O(n)push_front而不是O(1)，实际上，实现std::deque具有以下所有功能存在一些问题:

O(1)push_front

O(1)push_back

O(1)op []

也许我误解了“不使用大小为O(N)或更大的连续内存块”，这似乎很尴尬。您能说清楚您想要什么吗？我将其解释为“没有单个分配包含所代表序列中每个项目的一个项目”，这将有助于避免大量分配。 (即使我确实为向量分配了大小为N/B的单个分配。)

如果我的答案不符合您的定义，那么什么都不会，除非您人为地限制了容器的最大大小。 (例如，我可以将您限制为LONG_MAX个项目，将上述块存储在树中，然后调用该O(1)查找。)

关于performance - 在非连续内存中进行O(1)查找？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2098475/