3 ms·
Hashing is indexing and there is no faster and memory efficient index than an array (not vector) of sorted items. Iteration is the best if you can organize your
by glibgil 9y ago
Hashing is indexing and there is no faster and memory efficient index than an array (not vector) of sorted items. Iteration is the best if you can organize your data for it
- deleted 9y ago[deleted]
- jdmichal 9y agoNot sure what you're trying to get at. Indexing by surrogate index, yes. Indexing by value? That doesn't help. The best you can do is binary search -- O(log n). Hash-based structures are average amortized constant time -- O(1). This works because the key is a function of the value, rather than a surrogate key which is unrelated to the value. Straight from Wikipedia: "In many situations, hash tables turn out to be more efficient than search trees or any other table lookup structure. For this reason, they are widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches, and sets." https://en.wikipedia.org/wiki/Hash_table https://en.wikipedia.org/wiki/Hash_table
- deleted 9y ago[deleted]