是否可以在不使用数组的情况下实现 O(1) 搜索的数据结构？
我目前正在学习数据结构的大学课程，这个话题已经困扰我一段时间了（这不是作业，只是一个纯粹的理论问题）。
假设您想要实现一本字典。当然，字典应该有一个搜索功能，接受一个键并返回一个值。
现在，我只能想象两种非常通用的方法来实现这样的事情：
- 使用某种搜索树，这将（总是？）给出 O(log n) 最坏情况下的运行时间来查找通过键计算值，或者对
- 键进行哈希处理，它本质上返回一个与值数组中的索引相对应的自然数，从而给出最坏情况下的运行时间O(1)。
在不使用数组的情况下，搜索函数是否可以实现 O(1) 最坏情况 运行时间？
随机访问只能通过使用数组来实现吗？
是否可以通过使用基于指针的数据结构（例如链表、搜索树等）来实现？
做出一些特定的假设（例如密钥按某种顺序排列）是否可能？
换句话说，您能否想到搜索函数和字典的实现（如果可能的话），它将接收字典中的任何键并在 O(1) 中返回其值时间，不使用数组进行随机访问？
I am currently taking a university course in data structures, and this topic has been bothering me for a while now (this is not a homework assignment, just a purely theoretical question).
Let's assume you want to implement a dictionary. The dictionary should, of course, have a search function, accepting a key and returning a value.
Right now, I can only imagine 2 very general methods of implementing such a thing:
- Using some kind of search tree, which would (always?) give an O(log n) worst case running time for finding the value by the key, or,
- Hashing the key, which essentially returns a natural number which corresponds to an index in an array of values, giving an O(1) worst case running time.
Is O(1) worst case running time possible for a search function, without the use of arrays?
Is random access available only through the use of arrays?
Is it possible through the use of a pointer-based data structure (such as linked lists, search trees, etc.)?
Is it possible when making some specific assumptions, for example, the keys being in some order?
In other words, can you think of an implementation (if one is possible) for the search function and the dictionary that will receive any key in the dictionary and return its value in O(1) time, without using arrays for random access?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这是我就该一般主题所做的另一个回答。
本质上，算法通过处理一定数量的信息来达到其结果。他们花费的时间长短取决于他们能多快做到这一点。
仅具有 2 个分支的决策点无法处理超过 1 位的信息。然而，具有 n 个分支的决策点最多可以处理 log(n) 位（基数为 2）。
我知道，在计算机中，可以在单个操作中处理超过 1 位信息的唯一机制是索引，无论是索引数组还是执行跳转表（即索引数组）。
Here's another answer I made on that general subject.
Essentially, algorithms reach their results by processing a certain number of bits of information. The length of time they take depends on how quickly they can do that.
A decision point having only 2 branches cannot process more than 1 bit of information. However, a decision point having n branches can process up to log(n) bits (base 2).
The only mechanism I'm aware of, in computers, that can process more than 1 bit of information, in a single operation, is indexing, whether it is indexing an array or executing a jump table (which is indexing an array).
并不是使用数组使查找时间复杂度为 O(1)，而是查找时间不依赖于数据存储的大小。因此，任何直接访问数据而不进行与数据存储大小成比例的搜索的方法都将是 O(1)。
It is not the use of an array that makes the lookup O(1), it's the fact that the lookup time is not dependent upon the size of the data storage. Hence any method that accesses data directly, without a search proportional in some way to the data sotrage size, would be O(1).
您可以使用 trie 树实现哈希。复杂度为 O(max(length(string)))，如果字符串的大小有限，那么您可以说它在 O(1) 中运行，它不依赖于结构中字符串的数量。 http://en.wikipedia.org/wiki/Trie
you could have a hash implemented with a trie tree. The complexity is O(max(length(string))), if you have strings of limited size, then you could say it runs in O(1), it doesn't depend on the number of strings you have in the structure. http://en.wikipedia.org/wiki/Trie