客户主题列表的数据结构
我需要一个对客户端列表订阅的主题具有 O(1) 添加、查找和删除操作的数据结构。
它需要支持的一些函数包括：isTopicExists、isClientExists、getClientsForTopic、addClientForTopic、removeClientForTopic 和 getTopicsForClient。
给定一个主题名称、一个我们可以假设是唯一的客户端 ID 和客户端指针，最好使用什么数据结构？有哪些可用的实现？
I need a data structure with O(1) add, find, and delete operations for a topic subscribed by a list of clients.
Some of the functions it needs to support are: isTopicExists, isClientExists, getClientsForTopic, addClientForTopic, removeClientForTopic, and getTopicsForClient.
Given a topic name, a client id that we can assume to be unique, and client pointer, what is the best data structure to use? What implementations are available?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
哈希映射似乎不是一个坏主意。它的预期复杂度是 O(1)，但在有许多冲突的悲观场景中，复杂度可能会达到 O(n)，具体取决于链接的实现方式。对数搜索在这里很难被击败，所以我会选择自平衡二叉搜索树，甚至 std::map （大多数 STL 实现中的红黑树）。提高效率的唯一方法是使用向量（数组），但前提是您的 ID 很小或有偏移但彼此接近。在这里你无法击败数学。
A hash map may seem not a bad idea. Its expected complexity is O(1) but a pessimistic scenario with many collisions can get you to O(n) depending on how chaining is implemented. A logarithmic search will be hard to beat here, so I would go for a self-balancing binary search tree, even std::map (red-black tree in most STL implementations). The only way of making it more efficient is using a vector (an array), but only as long as your IDs are small or offseted but close to each other. You can't beat maths here.