Java-s, alates versioonist 8, kui HashMap-i ämbrisse on liiga palju kokkupõrkeid (üle 8 elemendi), muudetakse ämbris olev nimekiri punase-musta puu jaoks parema jõudluse saavutamiseks.

Selle juhul muutub HashMap-ist elemendi saamise ajakompleksus amortiseerunud O(1)-st (kasutades seotud nimekirja) O(log n)-ks, kus n on konkreetse ämbrisse kuuluvate elementide arv (st puu sügavus).

Seega, kasutades ämbris punase-musta puu, toimub elemendi otsing O(log n) ajal.

Eelmine Edasi