如何避免在低延迟环境中重新分配？

Question

在交易平台（低延迟环境）的订单中，您需要存储每个订单ID，至少要验证每个订单是唯一的。您在交易日可以获得的订单ID数量是无限的。除了使用历史数据分析之外，没有数字可以适当地“猜测”来预先分配数据结构。有什么方案可以避免日间订单ID容器重新分配？

Answer 1

在交易平台（低延迟环境）的订单中，您需要存储每个订单ID，至少要验证每个订单的唯一性。您在交易日可以获得的订单ID数量是无限的。除了使用历史数据分析之外，没有数字可以适当地“猜测”来预先分配数据结构。有什么方案可以避免日间订单ID容器重新分配？

好问题。一种解决方案是使用树形数据结构，其中每个分支是独立的堆分配。这就是大多数纯功能数据结构（例如OCaml和F＃中的Set和Map）如何工作的原因，它使它们增量，因此插入和删除总是O（最坏情况是O（日志n））。