Ассоциативный массив - История изменений

Patarakin в 06:33, 28 ноября 2022

2022-11-28T06:33:15Z

← Предыдущая версия		Версия от 09:33, 28 ноября 2022
Строка 11:		Строка 11:
	Ассоциативный массив с точки зрения интерфейса удобно рассматривать как обычный [[массив (программирование)\|массив]], в котором в качестве индексов можно использовать не только целые числа, но и значения других типов — например, строки.		Ассоциативный массив с точки зрения интерфейса удобно рассматривать как обычный [[массив (программирование)\|массив]], в котором в качестве индексов можно использовать не только целые числа, но и значения других типов — например, строки.

	Поддержка ассоциативных массивов есть во многих [[Интерпретируемый язык программирования\|интерпретируемых]] [[Высокоуровневый язык программирования\|языках программирования высокого уровня]], таких, как [[Perl]], [[PHP]], [[Python]], [[Ruby]], [[Tcl]], [[JavaScript]]~~<ref>~~В [[JavaScript]] объекты поддерживают создание свойств с произвольным (строковым) ключом, таким образом, они реализуют также базовые свойства ассоциативного массива.		Поддержка ассоциативных массивов есть во многих [[Интерпретируемый язык программирования\|интерпретируемых]] [[Высокоуровневый язык программирования\|языках программирования высокого уровня]], таких, как [[Perl]], [[PHP]], [[Python]], [[Ruby]], [[Tcl]], [[JavaScript]]

			В [[JavaScript]] объекты поддерживают создание свойств с произвольным (строковым) ключом, таким образом, они реализуют также базовые свойства ассоциативного массива.

	Примером ассоциативного массива является телефонный справочник: значением в данном случае является совокупность ФИО адрес», а ключом — номер телефона, один номер телефона имеет одного владельца, но один человек может иметь несколько номеров.		Примером ассоциативного массива является телефонный справочник: значением в данном случае является совокупность ФИО адрес», а ключом — номер телефона, один номер телефона имеет одного владельца, но один человек может иметь несколько номеров.
Строка 29:		Строка 31:

	Наиболее популярны реализации, основанные на различных [[Двоичное дерево (структура данных)\|деревьях поиска]]. Так, например, в стандартной библиотеке [[Стандартная библиотека шаблонов\|STL]] языка [[C++]] контейнер <tt>map</tt> реализован на основе [[Красно-чёрное дерево\|красно-чёрного дерева]].		Наиболее популярны реализации, основанные на различных [[Двоичное дерево (структура данных)\|деревьях поиска]]. Так, например, в стандартной библиотеке [[Стандартная библиотека шаблонов\|STL]] языка [[C++]] контейнер <tt>map</tt> реализован на основе [[Красно-чёрное дерево\|красно-чёрного дерева]].
	В языках ~~[[D (язык программирования)\|D]],~~ [[Java]], [[Ruby]], [[Tcl]], [[Python]] используется один из вариантов [[Хеш-таблица\|хеш-таблицы]].		В языках [[Java]], [[Ruby]], [[Tcl]], [[Python]] используется один из вариантов [[Хеш-таблица\|хеш-таблицы]].
	Есть и другие реализации.		Есть и другие реализации.

Patarakin в 09:40, 19 октября 2022

2022-10-19T09:40:54Z

← Предыдущая версия		Версия от 12:40, 19 октября 2022
Строка 39:		Строка 39:


	~~{{Структуры данных}}~~		----


	[[Категория:Структуры данных]]		[[Категория:Структуры данных]]

Patarakin в 09:32, 19 октября 2022

2022-10-19T09:32:45Z

← Предыдущая версия		Версия от 12:32, 19 октября 2022
Строка 11:		Строка 11:
	Ассоциативный массив с точки зрения интерфейса удобно рассматривать как обычный [[массив (программирование)\|массив]], в котором в качестве индексов можно использовать не только целые числа, но и значения других типов — например, строки.		Ассоциативный массив с точки зрения интерфейса удобно рассматривать как обычный [[массив (программирование)\|массив]], в котором в качестве индексов можно использовать не только целые числа, но и значения других типов — например, строки.

	Поддержка ассоциативных массивов есть во многих [[Интерпретируемый язык программирования\|интерпретируемых]] [[Высокоуровневый язык программирования\|языках программирования высокого уровня]], таких, как [[Perl]], [[PHP]], [[Python]], [[Ruby]], [[Tcl]], [[JavaScript]]<ref>В [[JavaScript]] объекты поддерживают создание свойств с произвольным (строковым) ключом, таким образом, они реализуют также базовые свойства ассоциативного массива. См.: {{cite web\|url=http://learn.javascript.ru/object\|title=Объекты как ассоциативные массивы\|work=Учебник JavaScript\|accessdate=2012-12-20\|archiveurl=https://www.webcitation.org/6D72tLIa1?url=http://learn.javascript.ru/object\|archivedate=2012-12-23}}</ref> и других. Для языков, которые не имеют встроенных средств работы с ассоциативными массивами, существует множество реализаций в виде [[Библиотека (программирование)\|библиотек]].		Поддержка ассоциативных массивов есть во многих [[Интерпретируемый язык программирования\|интерпретируемых]] [[Высокоуровневый язык программирования\|языках программирования высокого уровня]], таких, как [[Perl]], [[PHP]], [[Python]], [[Ruby]], [[Tcl]], [[JavaScript]]<ref>В [[JavaScript]] объекты поддерживают создание свойств с произвольным (строковым) ключом, таким образом, они реализуют также базовые свойства ассоциативного массива.

	Примером ассоциативного массива является телефонный справочник: значением в данном случае является совокупность ~~«{{nobr\|Ф. И. О. +}}~~ адрес», а ключом — номер телефона, один номер телефона имеет одного владельца, но один человек может иметь несколько номеров.		Примером ассоциативного массива является телефонный справочник: значением в данном случае является совокупность ФИО адрес», а ключом — номер телефона, один номер телефона имеет одного владельца, но один человек может иметь несколько номеров.

	Три основных операции часто дополняются другими, наиболее популярные расширения:		Три основных операции часто дополняются другими, наиболее популярные расширения:
Строка 32:		Строка 32:
	Есть и другие реализации.		Есть и другие реализации.

	У каждой реализации есть свои достоинства и недостатки. Важно, чтобы все три операции выполнялись как в среднем, так и в худшем случае за время <math>O(\log n)</math>, где <math>n</math> — текущее количество хранимых пар. Для сбалансированных деревьев поиска (в том числе для красно-чёрных деревьев) это условие выполнено.

	В реализациях, основанных на хеш-таблицах, среднее время оценивается как <math>O(1)</math>, что лучше, чем в реализациях, основанных на деревьях поиска. Но при этом не гарантируется высокая скорость выполнения отдельной операции: время операции <tt>INSERT</tt> в худшем случае оценивается как <math>O(n)</math>. Операция <tt>INSERT</tt> выполняется долго, когда коэффициент заполнения становится высоким и необходимо перестроить индекс хеш-таблицы.		В реализациях, основанных на хеш-таблицах, среднее время оценивается как <math>O(1)</math>, что лучше, чем в реализациях, основанных на деревьях поиска. Но при этом не гарантируется высокая скорость выполнения отдельной операции: время операции <tt>INSERT</tt> в худшем случае оценивается как <math>O(n)</math>. Операция <tt>INSERT</tt> выполняется долго, когда коэффициент заполнения становится высоким и необходимо перестроить индекс хеш-таблицы.
Строка 38:		Строка 38:
	Хеш-таблицы плохи также тем, что на их основе нельзя реализовать быстро работающие дополнительные операции MIN, MAX и алгоритм обхода всех хранимых пар в порядке возрастания или убывания ключей.		Хеш-таблицы плохи также тем, что на их основе нельзя реализовать быстро работающие дополнительные операции MIN, MAX и алгоритм обхода всех хранимых пар в порядке возрастания или убывания ключей.

	~~== Примечания ==~~
	~~{{примечания}}~~

	~~== Ссылки ==~~		{{Структуры данных}}
	* [http://www.nist.gov/dads/HTML/assocarray.html NIST’s Dictionary of Algorithms and Data Structures: Associative Array]
	* [http://www.nist.gov/dads/HTML/dictionary.html NIST’s Dictionary of Algorithms and Data Structures: Association List]

	~~{{rq\|sources\|style}}~~
	~~{{Структуры данных}}~~
	~~{{Типы данных}}~~

	[[Категория:Структуры данных]]		[[Категория:Структуры данных]]
	~~[[Категория:Составные типы данных]]~~

Patarakin: 1 версия импортирована

2022-10-19T07:30:41Z

1 версия импортирована

← Предыдущая версия		Версия от 10:30, 19 октября 2022
(нет различий)

109.248.170.183: /* Реализации ассоциативного массива */

2022-09-30T14:27:40Z

Реализации ассоциативного массива

Новая страница

'''Ассоциативный массив''' — [[абстрактный тип данных]] ([[Программный интерфейс|интерфейс]] к хранилищу данных), позволяющий хранить пары вида «(ключ, значение)» и поддерживающий операции добавления пары, а также поиска и удаления пары по ключу:
* <tt>INSERT(ключ, значение)</tt>
* <tt>FIND(ключ)</tt>
* <tt>REMOVE(ключ)</tt>
Предполагается, что ассоциативный массив не может хранить две пары с одинаковыми ключами.

В паре <math>(k, v)</math> значение <math>v</math> называется значением, ассоциированным с ключом <math>k</math>. Где <math>k</math> — это ''key'', a <math>v</math> — ''value''. Семантика и названия вышеупомянутых операций в разных реализациях ассоциативного массива могут отличаться.

Операция <tt>FIND(ключ)</tt> возвращает значение, ассоциированное с заданным ключом, или некоторый специальный объект UNDEF, означающий, что значения, ассоциированного с заданным ключом, нет. Две другие операции ничего не возвращают (за исключением, возможно, информации о том, успешно ли была выполнена данная операция).

Ассоциативный массив с точки зрения интерфейса удобно рассматривать как обычный [[массив (программирование)|массив]], в котором в качестве индексов можно использовать не только целые числа, но и значения других типов — например, строки.

Поддержка ассоциативных массивов есть во многих [[Интерпретируемый язык программирования|интерпретируемых]] [[Высокоуровневый язык программирования|языках программирования высокого уровня]], таких, как [[Perl]], [[PHP]], [[Python]], [[Ruby]], [[Tcl]], [[JavaScript]]<ref>В [[JavaScript]] объекты поддерживают создание свойств с произвольным (строковым) ключом, таким образом, они реализуют также базовые свойства ассоциативного массива. См.: {{cite web|url=http://learn.javascript.ru/object|title=Объекты как ассоциативные массивы|work=Учебник JavaScript|accessdate=2012-12-20|archiveurl=https://www.webcitation.org/6D72tLIa1?url=http://learn.javascript.ru/object|archivedate=2012-12-23}}</ref> и других. Для языков, которые не имеют встроенных средств работы с ассоциативными массивами, существует множество реализаций в виде [[Библиотека (программирование)|библиотек]].

Примером ассоциативного массива является телефонный справочник: значением в данном случае является совокупность «{{nobr|Ф. И. О. +}} адрес», а ключом — номер телефона, один номер телефона имеет одного владельца, но один человек может иметь несколько номеров.

Три основных операции часто дополняются другими, наиболее популярные расширения:
* <tt>CLEAR</tt> — удалить все записи,
* <tt>EACH</tt> — «пробежаться» по всем хранимым парам,
* <tt>MIN</tt> — найти пару с минимальным значением ключа,
* <tt>MAX</tt> — найти пару с максимальным значением ключа.

В последних двух случаях необходимо, чтобы на ключах была определена операция сравнения.

== Реализации ассоциативного массива ==
Существует множество различных реализаций ассоциативного массива.

Самая простая реализация может быть основана на обычном массиве, элементами которого являются пары (ключ, значение). Для ускорения операции поиска можно упорядочить элементы этого массива по ключу и осуществлять нахождение методом [[Двоичный поиск|бинарного поиска]]. Но это увеличит время выполнения операции добавления новой пары, так как необходимо будет «раздвигать» элементы массива, чтобы в образовавшуюся пустую ячейку поместить новую запись.

Наиболее популярны реализации, основанные на различных [[Двоичное дерево (структура данных)|деревьях поиска]]. Так, например, в стандартной библиотеке [[Стандартная библиотека шаблонов|STL]] языка [[C++]] контейнер <tt>map</tt> реализован на основе [[Красно-чёрное дерево|красно-чёрного дерева]].
В языках [[D (язык программирования)|D]], [[Java]], [[Ruby]], [[Tcl]], [[Python]] используется один из вариантов [[Хеш-таблица|хеш-таблицы]].
Есть и другие реализации.

У каждой реализации есть свои достоинства и недостатки. Важно, чтобы все три операции выполнялись как в среднем, так и в худшем случае за время <math>O(\log n)</math>, где <math>n</math> — текущее количество хранимых пар. Для сбалансированных деревьев поиска (в том числе для красно-чёрных деревьев) это условие выполнено.

В реализациях, основанных на хеш-таблицах, среднее время оценивается как <math>O(1)</math>, что лучше, чем в реализациях, основанных на деревьях поиска. Но при этом не гарантируется высокая скорость выполнения отдельной операции: время операции <tt>INSERT</tt> в худшем случае оценивается как <math>O(n)</math>. Операция <tt>INSERT</tt> выполняется долго, когда коэффициент заполнения становится высоким и необходимо перестроить индекс хеш-таблицы.

Хеш-таблицы плохи также тем, что на их основе нельзя реализовать быстро работающие дополнительные операции MIN, MAX и алгоритм обхода всех хранимых пар в порядке возрастания или убывания ключей.

== Примечания ==
{{примечания}}

== Ссылки ==
* [http://www.nist.gov/dads/HTML/assocarray.html NIST’s Dictionary of Algorithms and Data Structures: Associative Array]
* [http://www.nist.gov/dads/HTML/dictionary.html NIST’s Dictionary of Algorithms and Data Structures: Association List]

{{rq|sources|style}}
{{Структуры данных}}
{{Типы данных}}

[[Категория:Структуры данных]]
[[Категория:Составные типы данных]]