Коллекции middle
HashMap: расчёт бакета на примере?
Ответ
Формула: (n-1) & hash(key). Если capacity=16 (n=16): 15 & hash. 15 в бинарном = 1111. hash = 2_000_000_000: 2000000000 & 15 = 0 (последние 4 бита = 0000). Результат: bucket 0. Поэтому capacity — степень двойки: побитовое И эквивалентно взятию модуля.
Разбор: Индекс бакета считается как (n-1) & hash, что эквивалентно hash % n только потому, что n — степень двойки. При n=16 маска (n-1)=15 в двоичном виде 1111, и 2_000_000_000 & 15 = 0 (младшие 4 бита нулевые), значит bucket 0. Дистракторы берут модуль по (n-1) вместо побитового И по n-1, используют неверную маску 10000 или подставляют n вместо n-1, ломая маску.
Хочешь так же по своей компании — с вопросами по грейдам и задачами? Закажи гайд или забери свежее в Telegram.