Definition
An associative array is a collection that maps keys to values, where keys are arbitrary strings or other comparable values rather than consecutive integers. Different languages call the same structure by different names — Python calls it a dict, Ruby and Perl call it a hash, Java calls it a Map, JavaScript calls it an Object or a Map. The underlying idea is the same: given a key, look up its associated value in near-constant time.
Bash gained associative arrays in version 4. They must be declared explicitly with declare -A name before use, and elements are assigned with name[key]=value and read with ${name[key]}. The declaration matters: without it, bash treats name[key] as an indexed array and silently coerces the key to zero.
Why it matters
How it works
The dominant implementation is a hash table. The key is passed through a hash function that produces an integer; the integer is mapped (via modulo) to a slot in an internal array; the value is stored at that slot, along with the original key for collision handling. Lookup follows the same path: hash the key, jump to the slot, compare keys, return the value. Collisions — different keys hashing to the same slot — are resolved either by chaining (a linked list at each slot) or by open addressing (probing for the next free slot). Either way, with a reasonable load factor, the average operation cost is constant.
The limits are real but manageable. Hash tables have no inherent ordering, so iterating over an associative array does not guarantee any particular sequence — bash, Python, and most others now insert-order or hash-order by version, but relying on the order is fragile. Memory overhead is higher than a packed indexed array because every slot stores both key and value plus collision metadata. And keys must be hashable: in stricter languages this rules out using mutable objects as keys without care.