LANGUAGES Signal 409
Ruby's small Hash lookup uses linear O(n) search over an array of up to 8 pairs
↗
Illustration only Photo by Bruno Martins on Unsplash
An analysis of Ruby's internal ar_table implementation reveals that Hashes with 8 or fewer entries are stored as flat arrays of key-value pairs with single-byte hash hints, and lookups perform a linear scan rather than a true hash-table probe.
Most Ruby Hashes in real applications are small, so the performance characteristics of this linear search path directly affect everyday code. Understanding the ar_table structure and its O(n) lookup behavior helps engineers reason about when Hash access is cheap and when growing past 8 entries triggers a transition to the st_table implementation.
Written by elseif from the cluster below · every claim links back to a sourceThe three things worth knowing
Ruby Hashes with up to 8 entries use an ar_table, a flat array of pairs, rather than a true hash table.
Lookups in ar_table perform a linear scan comparing single-byte hash hints, then fall back to Object#eql? on hint matches to handle collisions.
The author identifies this O(n) search as a candidate for optimization after studying the ar_find_entry_hint routine in detail.
THE CLUSTER