Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Компьютерлік бағдарламалауда және әсіресе Lisp тілінде, қауымдастыру тізімі, көбінесе "алiст" деп аталады, бұл әрбір тізім элементінен (немесе түйінден) кілт пен мән тұратын байланысты тізім. Қауымдастыру тізімі мәнді кілтпен байланыстырады дейді. Белгілі бір кілтқа байланысты мәнді табу үшін тізбекті іздеу қолданылады: кілт табылғанға дейін тізімнің әрбір элементі басынан бастап ретімен тексеріледі. Қауымдастыру тізімдері ассоциативтік массивті іске асырудың оңай жолын ұсынады, бірақ кілттер саны өте аз болғанда ғана тиімді болады.
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.