1

I'm looking for a concise way to build a hash table from an array (of numbers) in JavaScript.

(This comes up a lot, at least on a lot of those O(n^2)-type problems that could be optimized to run in one-pass, like those Leetcode-type 'algorithm' problems.)

It seems like it could be a concise one-liner... But here's a two-liner of what I have:

const freq = {}; // An Object is often used to implement a Hash Table in JavaScript
nums.forEach(num => freq[num] = freq[num] === undefined ? 1 : freq[num] + 1);

... Assuming nums is an Array<number> and freq represents a conceptual hash table data structure, like so:

const nums = [2, 0, 2, 0, 0, 3, 0, 2, 0, 1];
// freq == { '0': 5, '1': 1, '2': 3, '3': 1 }

Does anybody know of a more syntactically concise way to achieve this?

user3773048
  • 5,839
  • 4
  • 18
  • 22
  • 3
    Why is it important to make it more syntactically concise? The goal is readability, not brevity. Leave minifying to minifiers. – T.J. Crowder Mar 02 '20 at 18:09
  • 2
    The example you give is not what I would imagine a hash table of values would look like. However in general you can come up with a hash function that returns a string, then use that string as a key into a list of values that hash to that same key. – Pointy Mar 02 '20 at 18:09
  • I was looking for syntactically concise, not at the cost of performance, ideally. I also would like some level of readability (but I guess readability is acquired depending on paradigm..?). I admit that I basically want to be able to solve Leetcode/whiteboarding interview problems faster, especially when it comes to very common things where the solution to the simple sub-problem should be easily understood, or at least the purpose should be. – user3773048 Mar 02 '20 at 19:00

1 Answers1

2

You can do it with reduce and some comma operator (ab)use, but I frankly can't think of a good reason to. :-) It looks like this:

const freq = nums.reduce((acc, num) => (acc[num] = (acc[num] || 0) + 1, acc), {});

Live Example:

const nums = [2, 0, 2, 0, 0, 3, 0, 2, 0, 1];
const freq = nums.reduce((acc, num) => (acc[num] = (acc[num] || 0) + 1, acc), {});
console.log(freq);
T.J. Crowder
  • 1,031,962
  • 187
  • 1,923
  • 1,875
  • 1
    You can also do it without the comma abuse, at the cost of some potential [performance problems](https://www.richsnapp.com/blog/2019/06-09-reduce-spread-anti-pattern) like this: `nums.reduce((acc, num) => ({... acc, [num]: (acc [num] || 0) + 1}), {})` – Scott Sauyet Mar 02 '20 at 18:21
  • Interesting – I didn't know of the `comma operator` – thanks for that knowledge! However, I initially thought of doing a similar reduce – but using the `spread syntax` (even ignoring readability for a second), but wouldn't this end up taking quadratic time to build (I'm assuming the comma operator iterates through each of the properties in the `Object` in linear time on the number of 'keys' + 'values' in the object... or is it doing some kind of O(1)-time reference..?). – user3773048 Mar 02 '20 at 18:21
  • (I'm curious about concise syntax but not at the cost of big-O running-time performance.) – user3773048 Mar 02 '20 at 18:24
  • 1
    @user3773048: that comma operator is not being used to iterate anything; it's just a way of combining two expressions, returning the value of the second. Usually, as here, it combines some side-effect in the first expression with the actual value here. That could also be rewritten as `nums.reduce((acc, num) => {acc[num] = (acc[num] || 0) + 1; return acc}, {})` But a strong convention would separate out those two `;`-separated statements, and this would no longer be a one-liner. – Scott Sauyet Mar 02 '20 at 18:25
  • Ahh, yes, ok. I guess that concern was irrelevant anyways, since `reduce` is a bigger problem, speaking of big-O run-time (if it matters in say Leetcode). Thanks for that clarification – sorry for the brief stupidity on my end. – user3773048 Mar 02 '20 at 18:27
  • First line from the link that T.J. referenced: `The comma operator evaluates each of its operands (from left to right) and returns the value of the last operand.` – user3773048 Mar 02 '20 at 18:28
  • @user3773048 - Why is `reduce` a bigger problem in big-O terms? It makes exactly one pass through the array. – T.J. Crowder Mar 02 '20 at 18:31
  • 1
    @ScottSauyet - Good point about spread! Perhaps problematic if the OP is worried about time complexity, but a very good point regardless... – T.J. Crowder Mar 02 '20 at 18:31
  • 1
    `reduce` will not change your Big-O run-time. It is slower than a for-loop mostly because of additional function calls per iteration, but it is not algorithmically slower. I would choose it for the more explicit code unless an actual performance test demonstrates that it's a bottleneck in my codebase. My alternative in the first comment is different as it does theoretically increase algorithmic times. But if you're using this as you seem to suggest, as some sort of helper data structure, the time to hash your list is probably irrelevant. – Scott Sauyet Mar 02 '20 at 18:31
  • 1
    @T.J.Crowder: that's my current style unless I find that the code is an actual performance problem in my codebase. I wouldn't use in public library code for the performance reasons discussed, but I find it much cleaner in most application code. – Scott Sauyet Mar 02 '20 at 18:33
  • The big reason to use a `reduce`-based solution is that it has some inherent semantics that should make your code more expressive. It's less clear than, say, `map` or `filter`, but it's not bad. However `for`-loops, including `forEach` have *no* inherent semantics. – Scott Sauyet Mar 02 '20 at 18:37
  • @T.J.Crowder: You're correct in your question – thank you for that. I had naiively assumed that the accumulator in `reduce` is copied each time that `reduce` calls the provided callback. That isn't the case, it's simply reassigned, as described in the spec at step 9.c.ii: https://tc39.es/ecma262/#sec-array.prototype.reduce . In this case, (ab)using the comma operator is much more efficient than using the `spread syntax`. Using `spread syntax` would result in quadratic run-time. Your provided solution is arguably more concise... I mean, it fits on one line. Do you consider it as readable? – user3773048 Mar 02 '20 at 18:55
  • 1
    lol I just tried checking on what `spread syntax` actually does and saw an answer T.J. gave in 2015: https://stackoverflow.com/questions/31048953/what-do-these-three-dots-in-react-do#answer-31049016 – user3773048 Mar 02 '20 at 18:56
  • I think that there is a general community feeling that the comma operator is less readable than other techniques. But it doesn't stop people (including me!) from using it occasionally to create one-liners. – Scott Sauyet Mar 02 '20 at 19:41