VPF::Как вычисляется индекс в HashMap'е?

Royan

Дата 19.3.2009, 01:46 (ссылка)

(нет голосов)

Загрузка ...

Dreamer

Профиль
Группа: Участник Клуба
Сообщений: 1708
Регистрация: 14.9.2002
Где: Лондон

Репутация: 3
Всего: 15

Чего-то решил убедиться в том, что я понимаю как работает HashMap и убедился, что я не понимаю. Кто может ответить, почему с точки зрения математики следующий код (внутри метода indexFor) всегда выдает правильный индекс контейнера внутри мапы для конкретного объекта:

Код


/* Этот фрагмент привожу в справочных целях */
int hash = hash(key.hashCode()); // тут хэш перехешируется в целях избавления от коллизий 
int i = indexFor(hash, table.length);
// ...
addEntry(hash, key, value, i);
// ...

/* Соль вопроса, почему вот это всегда правильно? */
static int indexFor(int h, int length) {
    return h & (length-1);
}

--------------------

Открыта вакансия Junior Java Developer'а в нашем лондонском офисе, подробнее можно узнать здесь

ivg

Дата 19.3.2009, 04:35 (ссылка)

(голосов:1)

Загрузка ...

Autonomous R&D

Профиль
Группа: Участник
Сообщений: 686
Регистрация: 8.2.2006
Где: Екатеринбург

Репутация: 33
Всего: 81

Потому что length - в HashMap всегда равно степени двойки. Ну и дальше с двоичной арифметикой тогда сразу становится всё понятно.

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Java: Общие вопросы \| Следующая тема »