HashTable in PHP7

PHP's array type is built on top of HashTable—a data structure that powers not only user-space arrays but also internal mechanisms like function tables, class registries, constants, and the global symbol table.

HashTable provides O(1) average lookup time by computing a direct mapping from keys to memory locations through a hash function. Unlike search trees that rely on key comparisons, HashTable uses direct addressing to achieve fast access.

Core Data Structures

The PHP HashTable implementation consists of two primary structures:

// Individual storage unit for key-value pairs
typedef struct _Bucket {
    zval              value;            // Actual stored value
    zend_ulong        hash;             // Precomputed hash or numeric index
    zend_string      *key;              // String key identifier
} Bucket;

// Main hash table container
typedef struct _zend_array HashTable;
struct _zend_array {
    zend_refcounted_h gc;
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                    zend_uchar    flags,
                    zend_uchar    apply_count,
                    zend_uchar    iterators_count,
                    zend_uchar    reserve)
        } v;
        uint32_t flags;
    } u;
    uint32_t          table_mask;       // Negative of table size
    Bucket           *data;             // Points to bucket array start
    uint32_t          used_slots;       // Total allocated slots (used + deleted)
    uint32_t          element_count;    // Active elements only
    uint32_t          table_size;       // Power of 2 bucket capacity
    uint32_t          internal_pos;     // Current iterator position
    zend_long         next_free_index;  // Auto-increment for [] syntax
    dtor_func_t       destructor;
};

Understanding nNumUsed vs nNumOfElements

These two counters serve distinct purposes. When an element is deleted, PHP doesn't remove the bucket—instead, it marks the zval as IS_UNDEF. The bucket remains in the array to avoid expensive reindexing.

Periodic cleanup occurs when the ratio of deleted-to-active elements exceeds a threshold. The condition triggers compaction when:

used_slots - element_count > (element_count >> 5)

This design keeps deletions cheap while maintaining insertion order.

Maintaining Insertion Order

Unlike traditional hash tables that scatter elements based on hash values, PHP preserves insertion order through a separate bucket array. Elements are stored sequentially in arData[0], arData[1], and so on. The hash table itself lives in memory before the bucket array, acccessible via negative offsets from arData.

Memory Layout:
[uint32_t][uint32_t][uint32_t]... | [Bucket][Bucket][Bucket]...
       ↑ Hash array                    ↑ arData points here

The hash array stores indices pointing into the bucket array, enabling both fast lookups and order preservation.

Hash Function Implementation

PHP computes bucket positions using bitwice operations instead of modulo:

index = key->hash | table_mask;

Since table_mask equals -table_size and table_size is always 2^n, the mask has all bits set except the lower n bits. This guarantees the computed index stays within bounds:

table_mask values (negative):
-8  = 0xFFFFFFF8
-16 = 0xFFFFFFF0
-32 = 0xFFFFFFE0
-64 = 0xFFFFFFC0

Bitwise OR with the hash value naturally constrains the result to |index| <= table_size.

Collision Resolution

When multiple keys hash to the same position, PHP uses a collision chain. Rather than storing pointers in buckets, collision links live within the zval structure's auxiliary feild:

struct _zval_struct {
    zend_value        value;
    union {
        uint32_t     var_flags;
        uint32_t     next;              // Collision chain link
        uint32_t     cache_slot;
        uint32_t     lineno;
        uint32_t     arg_count;
        uint32_t     foreach_pos;
        uint32_t     foreach_idx;
    } u2;
};

On collision, the new element's zval stores the old position in u2.next, and the hash table entry updates to point to the new element. This creates a last-in-first-out chain.

Lookup traverses this chain until a matching key is found:

zend_ulong hash = zend_string_hash_val(search_key);
uint32_t slot = ht->data + (hash & ht->table_mask);

while (slot != INVALID_IDX) {
    Bucket *bucket = ht->data + slot;
    if (bucket->hash == hash && zend_string_equals(bucket->key, search_key)) {
        return bucket;
    }
    slot = Z_NEXT(bucket->value);
}
return NULL;

Insertion, Lookup, and Deletion

After locating the target bucket position, these operations resemble standard linked-list manipulations. The hash table provides O(1) access to the initial bucket, with collision chains handling edge cases.

Dynamic Resizing

Hash table capacity doubles when insertions exceed available space. Before growing, PHP checks whether enough deleted slots exist to reclaim:

static void zend_hash_do_resize(HashTable *ht)
{
    if (ht->used_slots > ht->element_count + (ht->element_count >> 5)) {
        zend_hash_rehash(ht);  // Compact instead of grow
    } else if (ht->table_size < HT_MAX_SIZE) {
        uint32_t new_cap = ht->table_size << 1;  // Double capacity
        void *new_region = pemalloc(HT_SIZE_EX(new_cap, -new_cap), ...);
        
        Bucket *old_buckets = ht->data;
        ht->table_size = new_cap;
        ht->table_mask = -new_cap;
        HT_SET_DATA_ADDR(ht, new_region);
        
        memcpy(ht->data, old_buckets, sizeof(Bucket) * ht->used_slots);
        pefree(old_region, ht->u.flags & HASH_FLAG_PERSISTENT);
        
        zend_hash_rehash(ht);
    }
}

Hash Table Reconstruction

Rehashing becomes necessary after deletions compact the array or after capacity expansion changes the mask value. The process iterates through all buckets, recalculates hash positions, and updates the index table:

ZEND_API int zend_hash_rehash(HashTable *ht)
{
    Bucket *current;
    uint32_t hash_index, position;
    
    position = 0;
    current = ht->data;
    
    if (ht->used_slots == ht->element_count) {
        // No deleted elements - straightforward reindexing
        do {
            hash_index = current->hash | ht->table_mask;
            Z_NEXT(current->value) = HT_HASH(ht, hash_index);
            HT_HASH(ht, hash_index) = HT_IDX_TO_HASH(position);
            current++;
        } while (++position < ht->used_slots);
    } else {
        // Compact while rehashing - remove IS_UNDEF placeholders
        Bucket *write_ptr = ht->data;
        uint32_t write_pos = 0;
        
        do {
            if (Z_TYPE_INFO(current->value) == IS_UNDEF) {
                // Skip deleted slots, shift remaining elements forward
                while (++position < ht->used_slots) {
                    current++;
                    if (Z_TYPE_INFO(current->value) != IS_UNDEF) {
                        ZVAL_COPY_VALUE(&write_ptr->value, &current->value);
                        write_ptr->hash = current->hash;
                        write_ptr->key = current->key;
                        
                        hash_index = write_ptr->hash | ht->table_mask;
                        Z_NEXT(write_ptr->value) = HT_HASH(ht, hash_index);
                        HT_HASH(ht, hash_index) = HT_IDX_TO_HASH(write_pos);
                        
                        if (ht->internal_pos == position) {
                            ht->internal_pos = write_pos;
                        }
                        write_ptr++;
                        write_pos++;
                    }
                }
                ht->used_slots = write_pos;
                break;
            }
            
            hash_index = current->hash | ht->table_mask;
            Z_NEXT(current->value) = HT_HASH(ht, hash_index);
            HT_HASH(ht, hash_index) = HT_IDX_TO_HASH(position);
            current++;
        } while (++position < ht->used_slots);
    }
}

This compaction phase slides active elements together, reclaiming space occupied by deleted entries and updating the internal iterator position accordingly.