Which is more efficient in Ruby, Hash vs Array

Question

I am learning Ruby through the canonical pickaxe book. In Section 2.3 of that book, I came across a sentence saying that,

It’s more efficient to access array elements, but hashes provide more flexibility

As I understand, accessing array elements and looking up hash values by key both take O(1) time.

What does the author mean, when he says that arrays are more efficient for access? Does it simply mean that array is more efficient, because the internal representation of an array is simpler than a hash?

In essence, yes. Although the time complexity is the same, for an array it's really just an index in bounds check and then a multiplication. Hash tables have to do a lot more in that individual step. — Linuxios
– Linuxios, Commented Jul 24, 2015 at 13:53
In addition to the answers you'll get below, make sure to consider your use cases. If you're not dealing with many multiple iterations over large data sets, then it's likely that you won't notice a performance difference. In that case, let the model suggest the correct structure. Are you storing discrete, sequential items? Use an Array. Are you storing items by arbitrary key values? Use a Hash. Are you storing unique items where you don't care about the order? Use a Set. And so on. — Palpatim
– Palpatim, Commented Jul 24, 2015 at 13:57

davmac · Accepted Answer · 2015-07-24 13:50:11Z

3

Does it simply mean that array is more efficient, because the internal representation of an array is simpler than a hash?

Yes. The algorithmic complexity may be the same, but an array is going to be faster generally, because the lookup procedure is much simpler. On the other hand when using an array the "keys" (indices) can only be integers, and an array is not sparse - if you store to a[100], there will be at least 101 elements in the array afterwards.

(For extremely sparse arrays, a hash map should actually perform better).

answered Jul 24, 2015 at 13:50

davmac

20.8k1 gold badge45 silver badges72 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Which is more efficient in Ruby, Hash vs Array

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related