HashMapте кілт боюнча элементти издөө натыйжалуулугун кантип баалоо кылуу керек?

HashMap ичинде, элементти ачкыч боюнча издөө орто эсеп менен убакыт O(1) болот, бирок кагылышуулар болсо, алардын иштетүү ыкмасы натыйжалуулукка таасир этет.

Эртеби, кагылышуулар чынжырлар (байланышкан тизмектер) аркылуу чечилчү, жана эң начар учурларда (бардык ачкычтар бир себетке түшсө) издөө O(n) болмок.

Java 8ден бери, эгер бир себеттеги элементтердин саны белгиленген чекеден ашса, байланышкан тизмек тепкичтүү даракка (мисалы, кызыл-кара дарак) айлантылат. Бул ошол себет үчүн эң начар учурдагы издөө убактысын O(log n)га жакындатып турат.

Ошондуктан:

• Аз кагылышуулар менен издөө O(1) жакын калат.
• Көп кагылышуулар болсо, издөө O(log n) болот.

Бул өркүндөтүү HashMapдин иштөө ылдамдыгын кыйынчылык сценарийлерде кыйла жогорулатат.