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

У [[Информатика|информатици]], '''асоцијативни низ''', '''мапа''' или '''речник''', представља [[апстрактни тип података]] скуп парова кључ:вредност, тако да је кључ јединствен, односно појављује се само једном у скупу.

 

Најчешће коришћена универзална имплементација асоцијативног низа је [[хеш табела]]: [[Низ (структура података)|Низ]] везивања са [[хеш функцијом]] која мапира сваки могући кључ у индекс низа. Основна идеја хеш табела је да је везивање за сваки дати кључ, сачувано на позицији добијеној применом хеш функције на дати кључ, а операције претраге се врше посматрањем те ћелије низа и употребом везе у њој. Међутим, речници засновани на хеш таблицама, морају бити у могућности да рукују [[колизијама]], које настају када су два кључа мапирана на исти индекс од стране хеш функције. Многе различите стратегије за избегавање колизије су развијене, а често су базиране на [[затвореном хеширању]] или [[хеш везивању]].<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}}

 

 

[[Категорија:Типови података]]