HashMap'tе ачкыч боюнча элементти издөө канчалык татаал?

Ортача татаалдык — O(1), эң жаман учур — O(n).

• Орто учур (O(1)): Жакшы хэш-функция жана элементтердин бирдей бөлүштүрүшү менен издөө хэштин эсептелиши жана тиешелүү кутучага түз жетүү менен чектелет. Кутучада, эгер коллизиялар болбосо, элемент убакыттын константында табылат.
• Эң жаман учур (O(n)): Бардык элементтер бир эле кутучага хештелгенде болот. Бул учурда издөө байланышкан тизмеде сызыктуу издөө болуп калат (же Java 8+ үчүн көп элементтүү кутучаларда балансталган даракка, бирок даракты өтүү дагы O(log n) убакыт алат, жана көп коллизиялар болсо, жалпы O(n) жакындап калат).

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