Объясните наиболее доступно, как работает ассоциативный массив?

Во многих языках программирования ассоциативный массив является хеш-таблицей. Попробую объяснить именно на этом примере с парой упрощений.

Что мы умеем: создать массив и обращаться к его элементам по индексу за константное, очень маленькое время.

Что мы хотим уметь: обращаться к элементам так, чтобы вместо индексов мог быть любой тип данных и это было так же быстро.

Что мы делаем:

1. Разработаем хеш-функцию f(x), значение которой определено для любой строки (или других типов данных). Ее значением является некоторое число в диапазоне от 0 до N. Причем сделаем так, что распределение результирующих значений будет довольно равномерным.
Пример очень глупой хеш-функции: для строки s f(s) = (s[0] * 25 + s[1] * 47 + s[2] * 13) % N

2. Создадим массив длиной N + 1, пусть будет A. Пусть элементами массива будут векторы (для простоты).

3. При добавлении пары (ключ, значение) посчитаем хеш ключа, получим число от 0 до N, скажем, k. Добавим в k-тый элемент массива A нашу пару.

4. Если хотим достать элемент по какому-то ключу, посчитаем его хеш той же функцией. Посмотрим по адресу A[k], потому что умеем - просто обращаемся к элементу массива по индексу. И ищем нужную пару (ключ, значение) в этой ячейке. Если хеш-функция хорошая, то немного ключей будут иметь одинаковый хеш, поэтому поиск будет очень-очень быстрый. (кстати, если все-таки имеют, то это называется коллизией)

5. В итоге получаем структуру данных, которая позволяет вставлять и удалять элементы почти за константное время (в худшем случае за линейное, конечно, но это почти невозможно в нормальных условиях).

В качестве индексов ассоциативного массива используются не подряд идущие целые числа, а произвольные строки (а в некоторых языках индексом может быть не только строка, а значение практически любого типа).

И если обычный массив имеет фиксированный в момент создания размер, то в ассоциированном массиве можно добавлять и удалять элементы.

А вот внутреннее устройство в разных языках разное: для их реализации могут использоваться и деревья, и хеш-таблицы...

По адресу находится дом
Адрес - ключ, дом - значение