Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
В компьютерном программировании, и особенно в Lisp, ассоциативный список, часто называемый alist, — это связный список, в котором каждый элемент списка (или узел) состоит из ключа и значения. Ассоциативный список связывает значение с ключом. Для поиска значения, соответствующего заданному ключу, используется последовательный поиск: каждый элемент списка просматривается по порядку, начиная с начала, пока ключ не будет найден. Ассоциативные списки предоставляют простой способ реализации ассоциативного массива, но эффективны только при очень небольшом количестве ключей.
In computer programming and particularly in Lisp, an association list, often referred to as an alist, is a linked list in which each list element (or node) comprises a key and a value. The association list is said to associate the value with the key. In order to find the value associated with a given key, a sequential search is used: each element of the list is searched in turn, starting at the head, until the key is found. Associative lists provide a simple way of implementing an associative array, but are efficient only when the number of keys is very small.
Операция
Ассоциативный массив — это абстрактный тип данных, который можно использовать для хранения коллекции пар «ключ-значение» и поиска значения, связанного с заданным ключом. Список ассоциаций предоставляет простой способ реализации этого типа данных. Чтобы проверить, связан ли ключ со значением в данном списке ассоциаций, необходимо выполнить поиск в списке, начиная с первого узла и продолжая до тех пор, пока не будет найден узел, содержащий ключ, или пока поиск не достигнет конца списка (в этом случае ключ отсутствует). Чтобы добавить новую пару «ключ-значение» в список ассоциаций, создайте новый узел для этой пары, установите ссылку узла на предыдущий первый элемент списка ассоциаций и замените первый элемент списка ассоциаций новым узлом. Хотя некоторые реализации списков ассоциаций запрещают наличие нескольких узлов с одинаковыми ключами, такие дубликаты не являются проблемой для данного алгоритма поиска: дублирующиеся ключи, встречающиеся позже в списке, игнорируются. Также можно удалить ключ из списка ассоциаций, просматривая список для поиска каждого вхождения ключа и удаляя узлы, содержащие этот ключ. Для больших списков это может быть значительно медленнее, чем время, необходимое для представления ассоциативного массива в виде двоичного дерева поиска или хеш-таблицы. Кроме того, если список регулярно не очищается от элементов с дублирующимися ключами, множественные значения, связанные с одним и тем же ключом, увеличат размер списка и, следовательно, время поиска, не давая никаких преимуществ взамен. Одним из преимуществ списков ассоциаций является возможность добавления нового элемента за постоянное время. Кроме того, когда количество ключей очень мало, поиск в списке ассоциаций может быть более эффективным, чем поиск в двоичном дереве поиска или хеш-таблице, благодаря большей простоте их реализации.
An associative array is an abstract data type that can be used to maintain a collection of key–value pairs and look up the value associated with a given key. The association list provides a simple way of implementing this data type. To test whether a key is associated with a value in a given association list, search the list starting at its first node and continuing either until a node containing the key has been found or until the search reaches the end of the list (in which case the key is not present). To add a new key–value pair to an association list, create a new node for that key value pair, set the node's link to be the previous first element of the association list, and replace the first element of the association list with the new node. Although some implementations of association lists disallow having multiple nodes with the same keys as each other, such duplications are not problematic for this search algorithm: duplicate keys that appear later in the list are ignored. It is also possible to delete a key from an association list, by scanning the list to find each occurrence of the key and splicing the nodes containing the key out of the list. For large lists, this may be much slower than the times that can be obtained by representing an associative array as a binary search tree or as a hash table. Additionally, unless the list is regularly pruned to remove elements with duplicate keys, multiple values associated with the same key will increase the size of the list, and thus the time to search, without providing any compensatory advantage. One advantage of association lists is that a new element can be added in constant time. Additionally, when the number of keys is very small, searching an association list may be more efficient than searching a binary search tree or hash table, because of the greater simplicity of their implementation.