JavaScript 设置具有对数搜索时间的数据结构

JavaScript set data structure with logarithmic search time

本文关键字：搜索 时间 数据结构 设置 JavaScript      更新时间：2023-09-26

可能的重复项：
Javascript中是否有Set数据类型的库？

有没有办法创建一个模仿 c++ 集的 JavaScript 数据结构？我需要在log（n）时间内执行搜索，但找不到任何语言中服务良好的内容。我看到过几个问题，说我应该将集合表示为一个对象。这样行得通吗？数组的键和有效负载是数字。

对于无序集合，使用哈希表实现可能会更好。 它们执行 O（1） 查找，只要哈希表不被重载。

对于有序的内存集合，标准答案似乎是 treaps（良好的平均时间、高标准差）和红黑树（较差的平均时间、低标准差）。 这些都是 O（logn） 查找。

它必须，在javascript中一切都是一个对象。

如果你需要有序集（它允许你按照你定义的顺序从最小的元素循环到最大的元素），你可以在JS中实现你自己的数据结构。我不能提供更多信息，因为我没有做过第一手资料。

如果你对无序集感到满意，可以按如下方式实现它：

  1. 定义要存储在集中的对象的规范化字符串表示形式。如果您需要一个带数字的集合，只需使用数字的字符串表示形式。如果需要一组用户定义的对象，则可以选取定义对象标识的属性，并在规范化的 String 表示形式中使用它们。
  2. 通过将规范化的字符串表示形式映射到实际对象来创建要使用的 JS 对象。
  3. 可以通过使用 String 表示形式检查属性名称来完成搜索。
  4. 可以通过以下方式插入到集合中：首先通过搜索检查 String 表示形式是否已存在，如果对象尚未在集合中，则将 String 表示映射到实际对象。
  5. 删除可以通过使用 delete 来完成，属性名称是要删除的对象的字符串表示形式。
相关文章：