Материал array что это
Полезные методы массивов и объектов в JavaScript
Автор статьи, перевод которой мы сегодня публикуем, говорит, что её идею подсказал ему один из выпусков подкаста Syntax FM, в котором давался обзор полезных методов объектов и массивов в JavaScript. Эти методы помогают разработчикам писать чистый и читабельный код. Их применение снижает потребность в сторонних библиотеках наподобие Lodash.
Array.prototype.filter()
Метод Array.prototype.filter() создаёт новый массив, в который попадают только те элементы исходного массива, которые соответствуют заданному условию.
▍Пример
Создадим на основе массива, содержащего сведения о студентах, новый массив, в который попадут записи только о тех студентах, возраст которых позволяет им покупать спиртные напитки.
Array.prototype.map()
Метод Array.prototype.map() позволяет создать новый массив, основанный на каким-то образом обработанных значениях другого массива. Этот метод отлично подходит для модификации данных, он, благодаря тому, что не вносит изменений в исходный массив, часто используется в React.
▍Пример
Array.prototype.reduce()
Метод Array.prototype.reduce() нередко незаслуженно обходят вниманием. Он позволяет свести массив к единственному значению, накапливаемому в элементе-приёмнике. Значение, возвращаемое этим методом, может быть любого типа. Например, это может быть объект, массив, строка или число.
▍Пример
На самом деле, этот метод можно использовать множеством интереснейших способов. Соответствующие примеры можно найти в документации MDN. В частности, речь идёт о разворачивании массивов, состоящих из массивов, о группировке объектов по свойствам, и об удалении из массивов повторяющихся элементов.
Array.prototype.forEach()
Метод Array.prototype.forEach() применяет переданную ему функцию к каждому элементу массива.
▍Пример
Array.prototype.some()
▍Пример
Array.prototype.every()
▍Пример
Проверим, все ли оценки, хранящиеся в массиве, равны или больше чем 3.
Array.prototype.includes()
▍Пример
Проверим, имеется ли в массиве строковой элемент waldo :
Array.from()
▍Пример
Создадим массив на основе строки.
Создадим массив, содержащий удвоенные значения элементов исходного числового массива.
Object.values()
Метод Object.values() возвращает массив значений свойств переданного ему объекта.
▍Пример
Сформируем массив из значений свойств объекта.
Object.keys()
Метод Object.keys() возвращает массив, состоящий из имён свойств объекта (ключей).
▍Пример
Сформируем массив из имён свойств объекта.
Object.entries()
▍Пример
Сформируем массив, содержащий, для интересующего нас объекта, данные об именах свойств и их значениях.
Оператор расширения и массивы
▍Пример
Объединим два массива.
Сформируем новый массив, представляющий собой исходный массив, из которого удалён элемент. При этом исходный массив меняться не должен.
Оператор расширения и объекты
Применение оператора расширения к объектам позволяет добавлять к ним новые свойства и значения без изменения исходных объектов (то есть, в результате подобных операций создаются новые объекты). Кроме того, этот оператор можно использовать для объединения объектов. Тут стоит отметить, что оператор расширения, применённый к объекту, не воздействует на объекты, вложенные в него.
▍Пример
Создадим новый объект, добавив к исходному объекту новое свойство, не меняя при этом исходный объект.
Синтаксис оставшихся параметров функции
При работе с функциями можно использовать синтаксис оставшихся параметров для того, чтобы организовать приём любого количества аргументов в виде массива.
▍Пример
Выведем массив, содержащий аргументы, переданные функции.
Object.freeze()
▍Пример
«Заморозим» объект, после чего попытаемся изменить его свойство и убедимся в том, что сделать этого нельзя.
Object.seal()
Метод Object.seal() позволяет «запечатать» объект, предотвратив добавление новых свойств. При этом существующие свойства можно менять.
▍Пример
«Запечатаем» объект, что не позволит добавить в него новое свойство, но оставит возможность менять существующие свойства.
Object.assign()
Метод Object.assign() позволяет объединять объекты, копируя свойства из одного объекта в другой. На самом деле, того же эффекта можно достичь с помощью вышеописанного оператора расширения, поэтому без этого метода вполне можно обойтись. Надо отметить, что этот метод, как и оператор расширения, не выполняет глубокого клонирования объектов. Если вам нужно готовое средство для глубокого клонирования объектов — взгляните на инструменты библиотеки Lodash.
▍Пример
Создадим из двух объектов один.
Итоги
Уважаемые читатели! Какими методами массивов и объектов в JavaScript вы пользуетесь чаще всего?
Вы правда знаете о том, что такое массивы?
Там, где я тружусь, от веб-разработчиков ожидают знания PHP и JavaScript. Я, проводя собеседования, обнаружил, что достаточно задать всего один простой вопрос для того чтобы узнать о том, насколько глубоко разработчик понимает инструменты, которыми пользуется каждый день. Вот этот вопрос:
Каковы сходства и различия массивов в JavaScript и в PHP?
Одно дело — умение писать код. И совершенно другое — понимание внутренних механизмов используемых языков.
Ответ на этот единственный вопрос даёт мне целое море сведений о собеседуемом. Ведь почти в каждом распространённом языке есть массивы. Легко выдвинуть предположение, в соответствии с которым массивы в разных языках — это, более или менее, одно и то же. Многие программисты так и делают.
Это — некорректное предположение, ведущее к множеству мелких ошибок, к написанию нерационально устроенного кода, к невозможности эффективно пользоваться сильными сторонами языка.
Массивы и их родной язык — C
Язык C — это не первый в истории язык программирования, но это — язык, который сильнее других повлиял на IT-индустрию. Многие разработчики учили в институтах C в качестве первого языка. И PHP, и JavaScript что-то взяли от C. В результате можно наблюдать некоторое сходство между этими языками и C, и именно анализ массивов в C позволит показать то, как далеко эти структуры данных продвинулись с 1972 года.
В C массивы строго типизированы и имеют фиксированную длину.
Выше показана пара объявлений массивов. Они могут хранить только целые числа, количество которых не превышает 10.
Подобная конструкция не выглядит дикой ни в JavaScript, ни в PHP. Но именно здесь и кроется опасность.
Массивы в JavaScript
Можно представить себе, что массивы в JavaScript очень похожи на массивы в C. И правда — в JS совершенно нормально смотрятся следующие конструкции:
Однако массивы в JavaScript и в C — это разные вещи. Например, следующее, совершенно очевидно, в C невозможно:
В JavaScript массивы имеют переменную длину. Тип их содержимого не контролируется — точно так же, как и тип обычных переменных. Язык берёт на себя управление памятью, в результате длина массива способна увеличиваться или уменьшаться, а разработчик может об этом не задумываться. JavaScript-массивы, на самом деле, очень похожи на списки.
Перебор массива можно организовать, пользуясь неудачным способом, позаимствованным из C:
Но в JavaScript имеются гораздо более совершенные механизмы для работы с массивами. Массивы в JS — это не просто некие простейшие структуры данных. Они, как и функции, являются объектами первого класса. У них есть методы, позволяющие адекватно решать различные задачи:
Некоторые методы массивов
Массивы в PHP
Массивы в PHP почти похожи на JavaScript-массивы.
Они, как и JS-массивы, отличаются переменной длиной и слабой типизацией. Поэтому может возникнуть соблазн решить, что массивы в PHP и в JS — это одно и то же.
Лямбда-функции в PHP не так красивы, как похожие функции в JS (в ES6), но этот пример, написанный на PHP, функционально эквивалентен ранее рассмотренному JS-примеру.
Но на JavaScript (как и на C) нельзя написать нечто подобное следующему (написать похожий код на JavaScript, конечно, можно, но работать это будет не так, как в PHP):
Это означает, что PHP-массивы могут с успехом выполнять роль простых поисковых таблиц:
Конечно, что-то подобное доступно и в JavaScript, хотя тут уже надо будет прибегнуть к возможностям объектов. Но из-за этого придётся пойти на некоторые компромиссы. А именно, при работе с объектами в распоряжении разработчика не будет методов массивов вроде тех, о которых мы говорили выше.
В цикле даётся доступ и к ключам, и к значениям, что позволяет программисту работать и с тем, и с другим.
Стоит отметить, что PHP-массивы отличаются от JS-массивов тем, что в PHP для выполнения некоторых операций с массивами приходится пользоваться внешними по отношению к ним функциями:
Это — функционально, но не так красиво, как в JavaScript. Если вы хотите писать код для работы с PHP-массивами, который напоминает код, используемый в JavaScript (существуют сильные аргументы в пользу такого подхода), то вам, возможно, стоит взглянуть на специализированное решение. Скажем — на класс Collection из фреймворка Laravel. Однако PHP позволяет создавать объекты, возможности которых напоминают возможности массивов (их, например, можно обрабатывать в циклах foreach ).
Если PHP — это ваш основной язык программирования — вы, привыкнув к нему, вполне можете забыть о той мощи, которая таится в его фундаментальных механизмах.
PHP-массивы — это, в двух словах, самая недооценённая и самая незаметная возможность языка, которая, если ей правильно пользоваться, способна принести огромную пользу.
Итоги: вопрос и ответ
Вопрос: Каковы сходства и различия массивов в JavaScript и в PHP?
Ответ: в PHP и JavaScript массивы — это, по сути, слабо типизированные списки переменной длины. В JavaScript ключами элементов массивов являются упорядоченные целые числа. В PHP массивы можно сравнить и со списками, которые поддерживают сортировку, и со словарями, в которых удобно осуществлять поиск элементов по ключу. Ключи PHP-массивов могут быть любыми значениями примитивных типов, а сортировать такие массивы можно по ключам или по значениям.
Уважаемые читатели! Как вы думаете, каких стандартных возможностей больше всего не хватает JavaScript-массивам?
Что нужно знать о массивах JavaScript
Представляем вам перевод статьи автора Thomas Lombart, которая была опубликована на сайте medium.freecodecamp.org. Перевод публикуется с разрешения автора.
Пример использования метода reduce для сокращения массива
Позвольте мне сделать смелое заявление: циклы часто бывают бесполезными и затрудняют чтение кода. Для итераций в массивах, поиска, сортировки элементов и других подобных действий вы можете использовать один из методов, приведенных ниже.
Несмотря на эффективность, большинство этих методов все еще малоизвестны и не очень популярны. Я проделаю для вас трудную работу и расскажу о самых полезных. Считайте эту статью своим путеводителем по методам массивов JavaScript.
Примечание: Прежде чем мы начнем, вам нужно узнать одну вещь: я с предубеждением отношусь к функциональному программированию. Чтобы избежать побочных эффектов, я стремлюсь применять методы, не изменяющие исходный массив напрямую. Я не говорю вам отказаться от изменения массива вообще, но стоит учитывать, что некоторые методы к этому приводят. В результате появляются побочные эффекты, нежелательные изменения и, как следствие, баги.
Изначально эта статья была опубликована на сайте thomlom.dev — там вы можете найти больше материалов по веб-разработке.
Основы
Он принимает один параметр — функцию, которая вызывается на каждом элементе массива, а затем возвращает новый массив так, что никаких побочных эффектов быть не может.
Также вы можете создать новый массив, который хранит только одно определенное свойство объекта.
Итак, запомните: когда вам нужно изменить массив, подумайте об использовании map.
filter
Название этого метода говорит само за себя: применяйте его, когда хотите отфильтровать массив.
Например, в массиве можно сохранить только нечетные цифры.
Также можно использовать filter, чтобы убрать определенный элемент в массиве.
reduce
На мой взгляд, этот метод — самый сложный для понимания. Но как только вы его освоите, у вас появится куча возможностей.
Обычно метод reduce берет массив значений и соединяет их в одно значение. Он принимает два параметра, функцию callback (которая является редуктором) и опциональное начальное значение (которое является первым элементом массива по умолчанию). Сам редуктор принимает четыре параметра:
В первой итерации аккумулятор, являющийся суммой, принимает начальное значение 37. Возвращенное значение — 37 + n, где n = 12. Получаем 49.
Во время второй итерации аккумулятор равен 49, возвращенное значение — 49 + 28 = 77. И так далее.
Как правило, мы присваиваем методу reduce начальное значение [] — аккумулятор. Для map мы запускаем функцию, результат которой добавляется в конец аккумулятора при помощи оператора spread (мы поговорим о нем ниже, не волнуйтесь). Для filter проделываем практически то же самое, только функцию filter запускаем на элементе. Если она принимает значение true, мы возвращаем предыдущий массив. В противном случае добавляем элемент в конец массива.
Оператор spread (ES2015)
Я согласен, это не метод. Однако оператор spread помогает достигать разных целей при работе с массивами. Вы можете применить его, чтобы расширить значения одного массива в другом, а затем сделать копию или связать несколько массивов вместе.
Внимание: оператор spread делает поверхностную копию оригинального массива. Но что значит «поверхностную»?
Такая копия будет дублировать оригинальные элементы как можно меньше. Если у вас есть массив с цифрами, строками или булевыми значениями (примитивные типы), проблем не возникает и значения действительно дублируются. Однако с объектами и массивами дело обстоит по-другому: копируется только ссылка на оригинальное значение. Поэтому если вы сделаете поверхностную копию массива, включающего объект, и измените объект в скопированном массиве, в оригинальном он тоже будет изменен, потому что у них одинаковая ссылка.
Итак, если вы хотите создать реальную копию массива, который содержит объект или массивы, можете воспользоваться функцией lodash вроде cloneDeep. Но не нужно считать себя обязанным это сделать. Ваша цель — узнать, как все устроено под капотом.
Полезные методы
Ниже вы найдете другие методы, о которых тоже полезно знать и которые могут пригодиться для решения таких проблем, как поиск элемента в массиве, изъятие части массива и многое другое.
К счастью, метод includes делает проверку за нас. Задайте параметр для includes, и он проведет поиск элемента по массиву.
concat
Метод concat можно применять для слияния двух или более массивов.
indexOf
Этот метод используют, чтобы вернуть первый индекс, при котором элемент можно найти в массиве. Также с помощью indexOf часто проверяют наличие элемента в массиве. Честно говоря, сейчас я применяю его нечасто.
Вам может показаться, что findIndex и indexOf — это одно и тоже. Не совсем. Первым параметром indexOf является примитивное значение (булево значение, номер, строка, неопределенное значение или символ), тогда как первый параметр findIndex — функция обратного вызова.
В начале статьи я упомянул, что циклы часто бывают бесполезными. Давайте я покажу, как от них можно избавиться.
Также some подходит для работы с разрешениями.
flat (ES2019)
Это совершенно новые методы в мире JavaScript. Обычно flat создает новый массив, соединяя все элементы вложенного массива. Он принимает один параметр — число, которое указывает, насколько сильно вы хотите уменьшить размерность массива.
flatMap (ES2019)
Угадаете, что делает этот метод? Могу поспорить, вы поймете по одному его названию.
Сначала он запускает функцию mapping для каждого элемента, а затем сокращает массив за один раз. Проще простого!
Метод flatMap также часто используется в реактивном программировании. Пример вы можете посмотреть здесь.
join
Если вам нужно создать строку, основанную на элементах массива, метод join — то, что вам нужно. Он позволяет создавать новую строку, соединяя все элементы массива, разделенные предоставленным разделителем.
Например, с помощью join можно визуально отобразить всех участников деятельности.
А это более реальный пример, где вы можете сначала отфильтровать участников и получить их имена.
from
Это статический метод, который создает новый массив из массивоподобного или итерируемого объекта, например строки. Он может пригодиться, когда вы работаете с объектной моделью документа.
Вы увидели, что мы использовали тип массива вместо экземпляра массива? Вот почему этот метод называется статическим.
Методы, изменяющие массив, о которых стоит знать
Ниже приведены другие стандартные методы. Их отличие в том, что они изменяют оригинальный массив. В изменении нет ничего плохого, но стоит учитывать это при работе.
Если вы не хотите изменять оригинальный массив, работая с этими методами, сделайте его поверхностную или полную копию заранее.
sort
Да, sort изменяет оригинальный массив. Фактически он сортирует элементы массива на месте. Метод сортировки по умолчанию трансформирует все элементы в строки и сортирует их в алфавитном порядке.
Будьте внимательны: если вы, например, перешли с языка Python, то метод sort при работе с массивом цифр не даст вам желаемого результата.
Как же тогда отсортировать массив? Метод sort принимает одну функцию — функцию сравнения. Она принимает два параметра: первый элемент ( а ) и второй элемент для сравнения ( b ). Сравнение между этими двумя элементами требует возврата цифры:
Или можно отсортировать даты от наиболее поздней.
fill
Метод fill изменяет или заполняет все элементы массива от начального индекса до конечного заданным значением. Пример отличного использования fill — заполнение нового массива начальными данными.
reverse
Мне кажется, название метода полностью объясняет его суть.
pop
Этот метод убирает последний элемент из массива и возвращает его.
Методы, которые можно заменить
В последнем разделе вы найдете методы, которые изменяют оригинальный массив и которым легко найти альтернативу. Я не утверждаю, что их нужно сбрасывать со счетов, просто хочу донести до вас, что у некоторых методов есть побочные эффекты и их можно заменить.
push
Этот метод используется часто. Он позволяет добавлять один или более элементов в массив, а также строить новый массив, основанный на предыдущем.
shift
Метод shift убирает первый элемент массива и возвращает его. Чтобы сделать это в стиле функционального программирования, можно использовать оператор spread или rest.
array
array name — имя массива
data array — массив данных
array list — список массивов
binary array — двоичный массив
array element — элемент массива
Смотреть что такое «array» в других словарях:
array — ar·ray 1 /ə rā/ vt: to set (a jury) for trial; specif: to set (a jury) by calling out the names of the jurors one at a time compare impanel array 2 n: the group of people summoned to serve as jurors from which the jury will be chosen; also: a… … Law dictionary
array — ar‧ray [əˈreɪ] noun [countable] 1. a range of many different things: • a vast array of electronic and consumer products 2. COMPUTING a set of computer memory units arranged in rows across or down: • a device that stores massive amounts of… … Financial and business terms
array — [n1] collection, considerable group arrangement, batch, body, bunch, bundle, clump, cluster, design, display, disposition, exhibition, formation, host, lineup, lot, multitude, order, parade, pattern, set, show, supply, throng; concepts… … New thesaurus
array — vb 1 *line, line up, range, align Analogous words: marshal, arrange, *order Antonyms: disarray 2 *clothe, apparel, attire, robe, dress array n *display, parade, pomp Analogous words: showing … New Dictionary of Synonyms
array — ► NOUN 1) an impressive display or range of a particular thing. 2) an ordered arrangement of troops. 3) literary elaborate or beautiful clothing. ► VERB 1) display or arrange in a neat or impressive way. 2) (be arrayed in) be elaborately clothed… … English terms dictionary
Array — Datenfeld; Feld * * * Ar|ray 〈[ərɛı] m. 6 oder n. 15〉 1. Anordnung, Anreihung gleichartiger Dinge 2. 〈EDV〉 Liste von Datenwerten gleichen Typs 3. 〈El.〉 reihenartige Anordnung gleichartiger elektronischer Bauelemente [engl., „Aufstellung,… … Universal-Lexikon
array — noun ADJECTIVE ▪ broad, endless, extensive, full, huge, large, vast, wide ▪ a seemingly endless array of options … Collocations dictionary
Свой инструмент нужно знать в лицо: обзор наиболее часто используемых структур данных
Некоторое время назад я сходил на собеседование в одну довольно большую и уважаемую компанию. Собеседование прошло хорошо и понравилось как мне, так и, надеюсь, людям его проводившим. Но на следующий день, в процессе разбора полетов, я обнаружил, что в ходе собеседования ответ на как минимум один вопрос был неверен.
Вопрос: Почему поиск в python dict на больших объемах данных быстрее чем итерация по индексированному массиву?
Ответ: В dict хранятся хэши от ключей. Каждый раз, когда мы ищем в dict значение по ключу, мы сначала вычисляем его хэш, а потом (внезапно), выполняем бинарный поиск. Таким образом, сложность составляет O(lg(N))!
На самом деле никакого бинарного поиска тут нет. И сложность алгоритма не O(lg(N)), а Amort. O(1) — так как в основе dict питона лежит структура под названием Hash Table.
Причиной неверного ответа было то, что я не удосужился досконально изучить те структуры, которые лежат в основе работы с коллекциями моего любимого языка. Правда, по результатам опроса нескольких знакомых разработчиков, оказалось что это не только моя проблема, очень многие вообще не задумываются, как работают коллекции в их любимых ЯП. А ведь используем мы их каждый день и не по разу. Так родилась идея этой статьи.
1. Array — он же индексированный массив.
Array — это коллекция фиксированного размера, состоящая из элементов одинакового типа.
Почему время доступа к элементу по индексу постоянно? Массив состоит из элементов одного типа, имеет фиксированный размер и располагается в непрерывной области памяти => чтобы получить j-й элемент массива, нам достаточно взять указатель на начало массива и прибавить к нему размер элемента умноженный на его индекс. Результат этого несложного вычисления будет указывать как раз на искомый элемент массива.
*aj = beginPointer + elementSize*j-1
Примеры:
с/с++: int i_array[10];
java/C#: int[10] i_array;
Python: array.array
php: SplFixedArray
2. List (список).
List — это список элементов произвольного типа переменной длины (то есть мы можем в любой момент добавить элемент в список или удалить его). Список позволяет перебирать элементы, получать элементы по индексу, а так же добавлять и удалять элементы. Реализации у List возможны разные, основные — это (Single/Bidirectional) Linked List и Vector. Классический List предоставляет возможность работы с ним напрямую и через итератор, интерфейсы обоих классов рассмотрим ниже.
Перейдем к реализациям списка.
2.1 Single Linked List
Однонаправленный связный список (односвязный список) представляет из себя цепочку контейнеров. Каждый контейнер содержит внутри себя ссылку на элемент и ссылку на следующий контейнер, таким образом, мы всегда можем переместиться по односвязному списку вперед и всегда можем получить значение текущего элемента. Контейнеры могут располагаться в памяти как им угодно => добавление в односвязный список нового элемента тривиально.
Bidirectional Linked List мы подробно рассматривать не будем, вся разница между ним и Single Linked List заключается в том, что в контейнерах есть ссылка не только на следующий, но и на предыдущий контейнер, что позволяет перемещаться по списку не только вперед, но и назад.
2.2 Vector
Vector — это реализация List через расширение индексированного массива.
Очевидно, что главное преимущество Vector’а — быстрый доступ к элементам по индексу, унаследовано им от обычного индексированного массива. Итерировать Vector так же достаточно просто, достаточно увеличивать некий счетчик на единицу и осуществлять доступ по индексу. Но за скорость доступа к элементам приходиться платить временем их добавления. Для того чтобы вставить элемент в середину Vector’a (insert-after) необходимо скопировать все элементы между текущим положением итератора и концом массива, как следствие время доступа в среднем O(N). То же и с удалением элемента в середине массива, и с добавлением элемента в начало массива. Добавление элемента в конец массива при этом может быть выполнено за O(1), но может и не быть — если опять таки потребуется копирование массива в новый, потому говорится, что добавление элемента в конец Vector’а происходит за Amort. O(1).
Примеры:
с/с++: std::vector
Java: java.util.ArrayList
C#: System.Collections.ArrayList, System.Collections.List
Python: list
3. Ассоциативный массив(Словарь/Map)
Коллекция пар ключ=>значение. Элементы (значения) могут быть любого типа, ключи обычно только строки/целые числа, но в некоторых реализация диапазон объектов, которые могут быть использованы в качестве ключа, может быть шире. Размер ассоциативного массива можно изменять путем добавления/удаления элементов.
3.1 Hash Table
Как можно догадаться из названия, тут используются хэши. Механика работы Hash Table следующая: в основе лежит все тот же индексированный массив, в котором индексом работает значение хэша от ключа, а значением — ссылка на объект, содержащий ключ и хранимый элемент (bucket). При добавлении элемента — хэш функция вычисляет хэш от ключа и сохраняет ссылку на добавляемый элемент в ячейку массива с соответствующим индексом. Для получения доступа к элементу мы опять таки берем хэш от ключа и, работая так же как с обычным массивом получаем ссылку на элемент.
То есть, кроме значения ключа, она так же получает текущий размер массива, это необходимо для определения длины хэша: если мы храним всего 3 элемента — нет смысла делать хэш длиной в 32 разряда. Обратная сторона такого поведения хэш функции — возможность коллизий. Коллизии на самом деле характерны для Hash Table, и существует два метода их разрешения:
Chaining:
Каждая ячейка массива H является указателем на связный список (цепочку) пар ключ-значение, соответствующих одному и тому же хеш-значению ключа. Коллизии просто приводят к тому, что появляются цепочки длиной более одного элемента.
В массиве H хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива H в некотором порядке до тех пор, пока не будет найдена первая свободная ячейка, в которую и будет записан новый элемент. Этот порядок вычисляется на лету, что позволяет сэкономить на памяти для указателей, требующихся в хеш-таблицах с цепочками.
Примеры:
c++: за исключением QHash автору не известныboost::unordered_map/boost::unordered_set (by NickLion)
java: java.util.HashMap
c#: System.Collections.Hashtable, System.Collections.Dictionary
python: dict
php: array()
3.2 Binary Tree
На самом деле не просто Binary Tree, а Self-balancing Binary Tree. Причем следует отметить, что существует несколько различных деревьев, которые могут быть использованы для реализации Ассоциативного массива: red-black tree, AVL-tree и т.д. Мы не будем рассматривать каждое из этих деревьев в деталях, так как это возможно тема еще одной, отдельной статьи, а может и нескольких (если изучать деревья особо тщательно). Опишем только общие принципы.
Определение: двоичное дерево — древовидная структура данных в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. В случае, если у узла нет наследников — он называется листовым узлом.
4. Множество (Set).
Immutable набор элементов. Множество определяется один раз — при создании, и в дальнейшем предоставляет доступ к элементам только на чтение. Множество нельзя расширить, равно как нельзя и удалить из него элементы или изменить элемент множества. В качестве базы для реализации данной коллекции обычно используется Hash Table — описание которого см. Выше.
Множество — это просто реализация абстракции математического множества, т.е. набора уникальных различимых элементов. (спс. danilI)
Примеры:
c++: std::set
java: java.util.Set
C#: System.Collections.HashSet
python: set/frozenset
Сравнительные характеристики структур данных: 
Структуры данных в различных языках программирования: 
Ссылки:
Так же автор заглянул в исходники PHP и почитал доку по STL.
Upd. Да, в питоне есть обычный индексированный массив (array.array). Спасибо enchantner. С поправкой, тип не обязательно числовой, тип можно указывать.
Upd.
Из комментариев zibada:
Да, вот как раз из-за отсутствия описания итерации по Map из статьи вообще непонятно, зачем, казалось бы, нужны деревья, когда есть хэши. (O(logN) против O(1)).
Нужны они затем, что перечислять элементы Map (или Set) можно хотеть:
— в любом, негарантированном порядке (HashMap, встроенные хэши в некоторых скриптовых языках);
— в порядке добавления (LinkedHashMap, встроенные хэши в некоторых других скриптовых языках);
— в порядке возрастания ключей + возможность перебрать только ключи в заданном диапазоне.
А вот для последнего случая альтернатива деревьям — только полная сортировка всей коллекции после каждого изменения или перед запросом.
Что долго и печально для больших коллекций, но вполне работает для небольших — поэтому в скриптовые языки деревья особо и не встраивают.