Рассмотрим, как объекты кладутся в хеш-таблицу и получаются из нее. Для начала рассмотрим функцию хеширования:
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}Эта функция применяется к хеш-кодам ключей - она защищает от плохого хеширования.
Теперь рассмотрим функцию, которая получает индекс в массиве бакетов:
static int indexFor(int h, int length) {
return h & (length-1);
}Т.к. длина массива бакетов - это степень двойки, то побитовое умножение позволяет нам отсечь старшие биты - таким образом мы избегаем операции получения остатка от деления.
Теперь рассмотрим функцию получения объекта по ключу:
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}Здесь все просто: для получения значения по null-ключу мы используем специальный метод:
getForNullKey. Затем получаем индекс в массиве бакетов и проходимся по списку
Entry в данной ячейке списка.
Рассмотрим метод
getForNullKey:
private V getForNullKey() {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) return e.value;
}
return null;
}Как видно из кода, мы просто проходимся по списку
Entry в первой ячейке массива бакетов, до тех пор, пока не встретили
Entry с нулевым ключом.
Теперь рассмотрим метод для записи объекта в хеш-таблицу:
public V put(K key, V value) {
if (key == null) return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}Здесь для добавления объекта в null-ключом вызывается специальный метод -
putForNullKey. Далее, просматривается список в массиве бакетов по данному хешу. Если в этом списке нет такого ключа, то для добавления объекта в этот список вызывается метод
addEntry, заодно увеличивается счетчик modCount - который подсчитывает количество структурных модификаций.
Рассмотрим метод
addEntry:
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}Этот метод добавляет новый объект в начало списка, и также увеличивает размер массива бакетов, если достигнуто пороговое значение.
Мы рассмотрели основные аспекты
java.util.HashMap - все остальное можно легко посмотреть по исходникам.
Устройство java.util.HashMap. Часть 1.
Устройство java.util.HashMap. Часть 2.
Устройство java.util.HashMap. Часть 4.
