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

'''Проблем речника''' представља задатак дизајнирања [[Структура података|структуре података]], која имплементира асоцијативни низ. Уобичајено решење проблема речника су [[Хеш табела|хеш табеле]], док је у неким случајевима проблем могуће решити коришћењем коришћењем дирекотно повезаних [[Низ (структура података)|низова]], [[Бинарно стабло|бинарних стабала претраге]] или других специјализованих структура.<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>

Многи програмски језици укључују асоцијативне низове у [[основне типове података]], док су за многе друге доступни у [[библиотекама]]. [[Асоцијативна меморија]] је директна хардверска подршка асоцијативним низовима.

 

== Операције ==

У новом стању, иста претрага са кључем "Great Expectations" би створила изузетак, пошто овај кључ више не постоји у низу.

== Имплементација ==

|title=When should I use a hash table instead of an association list?

|publisher=lisp-faq/part2

Најчешће коришћена универзална имплементација асоцијативног низа је [[хеш табела]]: [[Низ (структура података)|Низ]] везивања са [[хеш функцијом]] која мапира сваки могући кључ у индекс низа. Основна идеја хеш табела је да је везивање за сваки дати кључ, сачувано на позицији добијеној применом хеш функције на дати кључ, а операције претраге се врше посматрањем те ћелије низа и употребом везе у њој. Међутим, речници засновани на хеш таблицама, морају бити у могућности да рукују [[колизијама]], које настају када су два кључа мапирана на исти индекс од стране хеш функције. Многе различите стратегије за избегавање колизије су развијене, а често су базиране на [[затвореном хеширању]] или [[хеш везивању]].<ref name="gt"/><ref name="ms"/><ref name="clrs"/>

Речници такође могу бити складиштени у облику [[Бинарно стабло|бинарних стабала претраге]] или у структурама података специјализованим за посебне врсте кључева као што су [[радикс стабла]], [[Џуди низови]] или [[фон Емде Боа стабла]], али су те имплементације мање ефикасне од хеш табела, а такође су рестриктивније према типовима података којим могу да рукују. Њихова предност је у томе што могу да рукују већим бројем операција од основних асоцијативних низова, као што су проналажење везивања чији је кључ најближи датом кључу, а дати кључ се не налази у скупу везивања.

== Језичка подршка ==

Асоцијативни низови могу бити имплементирани у било ком језику у облику пакета, док су код неких присутни у стандардним библиотекама. У неким језицима, не само да су имплементирани у стандардним библиотекма, већ имају и посебну синтаксу.

== Референце ==

{{Reflist|2}}