Array, Hash, and Set

Array is Ruby's variable-length sequential container; Hash is its keyed associative container; Set is a Ruby-level wrapper backed by a Hash.

Files

File	Purpose
array.c	Array implementation. ~255 KB.
array.rb	Array methods written in Ruby.
hash.c	Hash implementation. ~217 KB.
hash.rb	A few Hash methods in Ruby.
set.c	The C-level Set primitive. ~59 KB.
lib/set.rb	Public Set class on top of the C primitive.
st.c	The general-purpose hash table used by Hash and other code. ~96 KB.
st.h	Public st_table API.
concurrent_set.c	Concurrent set used internally by the VM.
darray.h	A typed dynamic array macro library.

Array internals

struct RArray {
    struct RBasic basic;
    union {
        struct {
            long len;
            VALUE *ptr;
            union {
                long capa;
                VALUE shared_root;
            } aux;
        } heap;
        const VALUE ary[RARRAY_EMBED_LEN_MAX];   /* embedded small arrays */
    } as;
};

Like String, Array has three flavors:

1. Embedded: arrays of up to ~3 elements live inline in the RArray.
2. Heap-allocated: longer arrays have a separate ptr/capa allocation.
3. Shared: the result of Array#slice or similar may share storage with the parent.

Mutations on shared arrays may trigger a copy-on-write before modifying.

Capacity and growth

array.c::ary_double_capa doubles capacity when full, with a minimum size class. The growth pattern matches what's typical in dynamic-array implementations. Array#new(n) and Array.new(n, default) pre-allocate.

Selected methods

Method	Where
Array#push / <<	array.c::rb_ary_push
Array#each	array.c::rb_ary_each
Array#map	array.c::rb_ary_collect
Array#select, #reject	array.c
Array#sort / #sort_by	array.c::rb_ary_sort_bang (uses ruby_qsort)
Array#flatten	array.c (recursive)
Array#concat, +	array.c::rb_ary_concat, rb_ary_plus
Array#join	array.c::rb_ary_join
Array#pack	pack.c (described in pack.rb shim)
Array#hash	array.c::rb_ary_hash (combines element hashes)

Array specialisations in the VM

The compiler emits specialized opcodes for hot Array operations: opt_aref, opt_aset, opt_length, opt_empty_p. These check the receiver class and inline the operation if it's a built-in Array.

Hash internals

Hash is a hash table of (key, value) pairs with insertion-order iteration. CRuby has gone through several internal layouts; the current one (Ruby 3.x onward) uses an open-addressing array for small hashes and an st_table for larger ones.

Two layouts

struct RHash {
    struct RBasic basic;
    /* small hashes use an inline array; large hashes use ar_table or st_table */
    union {
        struct st_table *st;       /* general-purpose hash table */
        struct ar_table_struct *ar;/* small open-addressing table */
    } as;
    const VALUE ifnone;            /* default value or block */
};

• ar_table: a flat array of (hash, key, value) triples for hashes with up to 8 entries. Linear scan for lookup. No collision handling needed.
• st_table: a full hash table for larger hashes. Open-addressing with double hashing and a separate "bin" array for fast lookups.

The transition from ar_table to st_table happens when the hash exceeds the small-hash threshold (SMALL_HASH_LIMIT, currently 8). The Hash's flags record which layout is in use.

Iteration order

Both layouts preserve insertion order. For ar_table, iteration walks the array in insertion order. For st_table, the table records insertion order separately and iteration walks that sequence.

Hashing

Keys are hashed via rb_hash_proc (hash.c), which calls the key's hash method. The result is a st_index_t (a 64-bit integer). For String keys, string.c::rb_str_hash is used directly.

hash.c::any_hash_general / any_hash is the central hashing function. It uses SipHash for strings, and a custom mixing function for non-string keys.

The hash seed is randomised per process to mitigate hash-flooding attacks (hash.c::ruby_hash_seed).

Selected methods

Method	Where
Hash#[] (read)	hash.c::rb_hash_aref
Hash#[]= (write)	hash.c::rb_hash_aset
Hash#each	hash.c::rb_hash_each_pair
Hash#merge	hash.c::rb_hash_merge_bang and friends
Hash#select / #reject	hash.c
Hash#delete	hash.c::rb_hash_delete
Hash#to_a	hash.c::rb_hash_to_a
Hash#invert	hash.c::rb_hash_invert

st.c — the general-purpose hash table

st.c (~96 KB) is a portable hash table library used both by Hash and by other parts of CRuby (the symbol table, method tables, constant tables, etc.). It predates the modern Hash and is largely unchanged for ~20 years.

Key features:

• Open addressing with separate "bin" arrays for fast probe sequences.
• Pluggable hash and equality functions per st_table.
• Iteration safe under insertion (with caveats).
• Several specialised variants (st_numhash, st_strhash).

Set

The Set class is implemented in two layers:

1. set.c provides a low-level Set primitive that's basically a Hash with true values.
2. lib/set.rb defines the public Set API on top.

A pre-Ruby-3.2 Set used a Hash with sentinel values from Ruby. The C version is faster and the default since 3.2.

Sample API:

s = Set.new([1, 2, 3])
s.add(4)
s.member?(2)    # true
s & other_set
s | other_set

ConcurrentSet

concurrent_set.c implements a lock-free hash set used internally by the VM (e.g., for the constant cache cross-Ractor synchronisation). It's not exposed to Ruby code; it's an implementation detail of how Ractors share state.

DArray macros

darray.h provides a typed dynamic-array macro library used heavily in CRuby internals (e.g., the iseq instruction array, callinfo lists):

typedef rb_darray(int) int_darray_t;
int_darray_t arr = NULL;
rb_darray_append(&arr, 42);
rb_darray_for(arr, i) {
    int x = rb_darray_get(arr, i);
    /* ... */
}
rb_darray_free(arr);

A darray is a length-prefixed pointer (void *) with a typed accessor. It's a building block — many internal data structures use it directly rather than maintaining their own length fields.

Shape interaction

When an Array or Hash is treated as a generic object (instance variables added to it), the shape system kicks in. But the per-element storage (the array buffer or the hash table) is independent of shape.

Common pitfalls

• Mutating during iteration: Hash and Array do not raise during in-place mutation under each, but the result is undefined. Use Hash#dup.each or Array#dup.each if you need a stable snapshot.
• Hash ordering: insertion order is preserved, but only insertion order. Re-inserting a key keeps the original position. Use dup if you want the new order.
• Hash#hash: depends on key/value identities, so two hashes with the same content may hash differently if their keys are distinct objects.
• Equal-by-eql? requirement: hash keys must implement eql? and hash consistently.

Entry points for modification

• New Array method: add to array.c and register in Init_Array. Mirror in array.rb if it can be Ruby.
• New Hash optimisation: hash.c::ar_* for the small-hash variant, or st.c for the general path.
• Set behaviour: set.c for the C primitive, lib/set.rb for the user-facing class.

See reference/data-models.md for memory layouts and systems/vm.md for opcode-level Array specialisations.