What data structure can give O(1) for looking up decimal keys?

Question

I have an array of random data containing pairs of numbers.

[{width: 123.89000000, length: 4.50},{width: 23.45360, length: 7.20}, ...]

I want to look up the width to get the length in O(1) time and I want the array to be sorted by width.

What is the best way data structure to store this in Javascript / NodeJS? I tested

var hashtable = {};
hashtable[17400.23400000] = { width: 17400.23400000, length: 4.5 };
console.log(hashtable[17400.234]); // check that the key is treated like a real number

It seems to work, but does it?

EDIT:

To clarify the requirement, let me explain the situation:

I am getting the width and length data from a websocket in real-time. The width is discrete up to 4 decimal places, and I need to update the corresponding length as the data streams in, sometimes adding a new width, and sometimes removing an existing width. So for this I need a fast solution for lookup.

Then on every indeterminate x number of milliseconds, I need to return a snapshot of this array of width and length as a sorted array. The number of pairs in this array is maybe around 260,000. Ideally, x should be as small as possible.

Currently I am using a hashtable and using lodash to sort upon request, but I am wondering if there is a faster data structure that is suitable.

You didn't specify the complexity you expect from the insertion. Also, if your array is sorted you can achieve better performance than O(n) when searching. Finally, if your only requirement is for the lookup to be O(n), an array is just fine. — Federico klez Culloca, Dec 14 '17 at 09:15
The complexity of `hashtable[17400.234]` is `O(1)`. The complexity of adding each element using a for loop is `O(n)` (where `n` is the length of your array ). This doesn't sort though implementing an [efficient sort](https://stackoverflow.com/a/40727307/542251) is going to be in the realm of `O(n^2)`. There is no way to sort and iterate an array in `O(n)` complexity. — Liam, Dec 14 '17 at 09:35
Your added code, neither sorts nor iterates your array so I don't really see how it solves your problem at all, let alone do it efficiently. — Liam, Dec 14 '17 at 09:38
Do you have the possibility to use the [Map](https://stackoverflow.com/questions/33611509/es6-map-and-set-complexity-v8-implementation) structure? — L. Meyer, Dec 20 '17 at 10:08

Kresimir Pendic · Answer 1 · 2017-12-14T09:36:09.597

0

Don't know if this helps you, but I'd do something like this.. although sorting does seams unneeded here..

// example array;
var a = [{
  width: 123.89000000,
  length: 4.50
}, {
  width: 23.45360,
  length: 7.20
}, {
  width: 56.35360,
  length: 2.20
}, {
  width: 254.1260,
  length: 1.20
}];

// sort the array
a.sort(function(a, b) {
  return a.width < b.width
});

// lookup fn
a.O = function(lookup) {
  var flag = 0;
  for (var i = 0; i < a.length; i++) {
    if (lookup == a[i].width) return a[i].length;
  }
  return false;
};

// exec lookup
console.log(a.O(123.59), a.O(123.89));

edited Dec 14 '17 at 09:36

answered Dec 14 '17 at 09:19

Kresimir Pendic

3,597
1
21
28

FYI It's not that clear what the [complexity of .sort is](https://stackoverflow.com/questions/234683/javascript-array-sort-implementation), presuming a best case of `O(log n)` and given that `a.O` complexity is `O(n)` (worst case) that gives a complexity of the line `console.log(a.O(123.59), a.O(123.89));` of `O(log n * n * n)` (Pessimistic) or `O(log n)` (very optimistic) – Liam Dec 14 '17 at 09:59
@liam thx, I don't understand 1/2 of the stuff that goes on in SO answer that you linked,, does seams like hardcore stuff :) .. Jake, hail me if this answer is not what you need, I can remove it! – Kresimir Pendic Dec 14 '17 at 10:10
I don't think there is anyway to get what the OP wants, this is as good a solution as any. Just added some context as the OP was asking about Big O. Big O is just a way of describing complexity, so iterating an array `n` in size if `O(n)`, a binary tree of `n` size if `O(log n)`, etc. the lower the result of O the less complex the algorithm (therefore quicker). `log n` < `n` so a binary tree is quicker. – Liam Dec 14 '17 at 10:14

What data structure can give O(1) for looking up decimal keys?

1 Answers1