Википедија

Асоцијативни низ — разлика између измена

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
м додана категорија Асоцијативни низови помоћу геџета HotCat
Autobot (разговор | доприноси)
1.572.075 измена
м Бот: исправљена преусмерења; козметичке измене
Ред 2:
У [[Информатика|информатици]], '''асоцијативни низ''', '''мапа''' или '''речник''', представља [[апстрактни тип података]] скуп парова кључ:вредност, тако да је кључ јединствен, односно појављује се само једном у скупу.
Операције везане за овај тип података:<ref name="gt">{{citation|contribution=9.1 The Map Abstract Data Type|title=Data Structures & Algorithms in Java|last1=Goodrich|first1=Michael T.|author1-link=Michael T. Goodrich|last2=Tamassia|first2=Roberto|author2-link=Roberto Tamassia|publisher=Wiley|edition=4th|year=2006|pages=368–371}}.</ref><ref name="ms">{{citation|contribution=4 Hash Tables and Associative Arrays|title=Algorithms and Data Structures: The Basic Toolbox|first1=Kurt|last1=Mehlhorn|author1-link=Kurt Mehlhorn|first2=Peter|last2=Sanders|publisher=Springer|year=2008|pages=81–98}}.</ref>
* додавање парова скупу
* уклањање парова из скупа
* измена вредности постојећих парова
* проналажење вредности везане за одређен кључ
'''Проблем речника''' представља задатак дизајнирања [[Структура_податакаСтруктура података|структуре података]], која имплементира асоцијативни низ. Уобичајено решење проблема речника су [[Хеш_табелаХеш табела|хеш табеле]], док је у неким случајевима проблем могуће решити коришћењем коришћењем дирекотно повезаних [[Низ_Низ (структура_податакаструктура података)|низова]], [[Бинарно_стаблоБинарно стабло|бинарних стабала претраге]] или других специјализованих структура.<ref name="gt"/><ref name="ms"/><ref name="clrs">{{citation | last1 = Cormen | first1 = Thomas H. | author1-link=Thomas H. Cormen | coauthors = [[Charles E. Leiserson|Leiserson, Charles E.]]; [[Ron Rivest|Rivest, Ronald L.]]; [[Clifford Stein|Stein, Clifford]] | title = [[Introduction to Algorithms]] | edition = 2nd | year = 2001 | publisher = [[MIT Press]] and [[McGraw-Hill]] | isbn=0-262-03293-7 | chapter = 11 Hash Tables | pages = 221–252}}.</ref>
Многи програмски језици укључују асоцијативне низове у [[основне типове података]], док су за многе друге доступни у [[библиотекама]]. [[Асоцијативна меморија]] је директна хардверска подршка асоцијативним низовима.
Асоцијативни низови имају широку примену укључујући и основне шаблоне попут [[мемоизације]] и [[декораторa шаблона]].<ref name="decorator">{{harvtxt|Goodrich|Tamassia|2006}}, pp. 597–599.</ref>
 
== Операције ==
У асоцијативном низу, веза између кључа и вредности је позната као везивање, а исти термин се може односити и на процес креирања нове везе.
Операције које су обично дефинисане су:<ref name="gt"/><ref name="ms"/>
* '''Додавање''' или '''уметање''': додаје нови кључ:вредност пар у колекцију, везујући нови кључ и додељену вредност. Аргументи ове операције су кључ и вредност.
* '''Замена''': мења вредност једног кључ:вредност пара који се већ налази у колекцији, везујући стари кључ и нову вредност. Као и код уметања, аргументи ове операције су кључ и вредност.
* '''Уклањање''' или '''брисање''': уклања кључ:вредност пар из колекције, бришући везу између датог кључа и његове вредности. Аргумент ове операције је кључ.
* '''Претрага''': проналази вредност (уколико постоји) која је везана за дати кључ. Аргумент ове операције је кључ, а враћа се вредност. Уколико вредност није пронађена, неке имплементације асоцијативних низова креирају [[Изузетак_Изузетак (програмирање)|изузетак]].
Додатно, асоцијативни низови могу укључити друге операције попут одређивање броја везивања или конструисање [[итератора]] којим би се, кроз петљу, прошло кроз сва везивања. Обично се за такву операцију ред у коме се враћају везивања бира случајно.
[[Мултимапе|Мултимапа]] генерализује асоцијативни низ омогућујући да више вредности буду везане за један кључ.<ref>{{harvtxt|Goodrich|Tamassia|2006}}, pp. 389–397.</ref> [[Двосмерна мапа]] је повезани апстрактни тип података, у којој везивања раде у оба смера: свака вредност мора бити везана јединственим кључем, а друга операција претраге узима вредност као аргумент и проналази кључ везан за ту вредност.
== Примери ==
Претпоставимо да је скуп изнајмљивања књига у библиотеци представљен у облику структуре података. Свака књига у библиотеци, у одређеном тренутку, може бити изнајмљена од стране само једног члана. Такође, један члан може изнајмити више књига. Стога, информације о томе која књига је издата ком члану, може бити представљена асоцијативним низом, где су књиге кључеви, а чланови су вредности. На пример (користећи [[Пајтон_Пајтон (програмски_језикпрограмски језик)|Пајтон]] нотацију, где су везе представљене постављањем колоне између кључа и вредности), текућа изнајмљивања могу бити приказана асоцијативним низом.
<pre>{
"Great Expectations": "John",
Ред 33:
}</pre>
У новом стању, иста претрага са кључем "Great Expectations" би створила изузетак, пошто овај кључ више не постоји у низу.
== Имплементација ==
За речнике са малим бројем везивања, има смисла имплементирати речник користећи [[асоцијативну листу]], [[повезану листу]] везивања. У овој имплементацији, временска сложеност је линеарна и зависи од укупног броја везивања.Међутим, лака је за имплементацију и фактори временске сложености су мали.<ref name="gt"/><ref>{{cite web |url=http://www.faqs.org/faqs/lisp-faq/part2/section-2.html
|title=When should I use a hash table instead of an association list?
|publisher=lisp-faq/part2
|date=1996-02-20}}</ref> Још једна једноставна имплементациона техника, употребљива када је кључ ограничен на узак скуп целих бројева, је директно адресирање у низу: вредност датог кључа к се чува у ћелији низа А[к], или укуолико нема везивања за к, онда ћелија чува [[променљиве чуваре]] које дају назнаку непостојања везе. Поред тога што је једноставна, ова техника је и брза: свака операција над речником има константно трајање. Mеђутим, просторна сложеност је велика, што ову технику чини непрактичном. <ref name="clrs"/>
Најчешће коришћена универзална имплементација асоцијативног низа је [[Хеш_табела|хеш табела]]: [[Низ_Низ (структура_податакаструктура података)|Низ]] везивања са [[хеш функцијом]] која мапира сваки могући кључ у индекс низа. Основна идеја хеш табела је да је везивање за сваки дати кључ, сачувано на позицији добијеној применом хеш функције на дати кључ, а операције претраге се врше посматрањем те ћелије низа и употребом везе у њој. Међутим, речници засновани на хеш таблицама, морају бити у могућности да рукују [[колизијама]], које настају када су два кључа мапирана на исти индекс од стране хеш функције. Многе различите стратегије за избегавање колизије су развијене, а често су базиране на [[затвореном хеширању]] или [[хеш везивању]].<ref name="gt"/><ref name="ms"/><ref name="clrs"/>
Речници такође могу бити складиштени у облику [[Бинарно_стаблоБинарно стабло|бинарних стабала претраге]] или у структурама података специјализованим за посебне врсте кључева као што су [[радикс стабла]], [[Џуди низови]] или [[фон Емде Боа стабла]], али су те имплементације мање ефикасне од хеш табела, а такође су рестриктивније према типовима података којим могу да рукују. Њихова предност је у томе што могу да рукују већим бројем операција од основних асоцијативних низова, као што су проналажење везивања чији је кључ најближи датом кључу, а дати кључ се не налази у скупу везивања.
== Језичка подршка ==
Асоцијативни низови могу бити имплементирани у било ком језику у облику пакета, док су код неких присутни у стандардним библиотекама. У неким језицима, не само да су имплементирани у стандардним библиотекма, већ имају и посебну синтаксу.
Уграђена подршка за асоцијативне низове је уведена у [[SNOBOL]]4, под називом "табела". [[SETL]] их је подржавао као једна од могућих имплементација сетова и мапа. Многи модерни скрипт језици, почевши од [[AWK]] и укључујући [[Перл (програмски језик)|Perl]], [[Tcl]], [[Јаваскрипт|JavaScript]], [[Пајтон_Пајтон (програмски_језикпрограмски језик)|Пајтон]],[[Ruby (programming language)|Ruby]] и [[Lua (programming language)|Lua]] подржавају асоцијативне низове као примарне контејнерске типове. У многим другим језицима доступни су као функције библиотеке без специјалне синтаксе.
== Референце ==
{{Reflist|2}}
Преузето из „https://sr.wikipedia.org/wiki/Асоцијативни_низ”