Mapy - implementace a složitosti
Mapy mají podobné implementace jako množiny, tj.:
- hašovací tabulky
HashMap
- potenciálně rychlejší, ale neuspořádané klíče
- černobílé stromy
TreeMap
- uspořádané klíče, s garantovanou logaritmickou složitostí
Složitost základních operací (put,
remove, containsKey):
Mapy implementované jako stromy mají nejvýš logaritmickou
složitost základních operací.
U map implementovaných hašovací tabulkou složitost v praxi
závisí na kvalitě hašovací funkce (metody hashCode) na ukládáných
objektech, teoreticky se blíží složitosti konstantní.
