Устройство java.util.HashMap. Часть 4.

Рассмотрим, как объекты кладутся в хеш-таблицу и получаются из нее. Для начала рассмотрим функцию хеширования:

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.