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

Здесь мы рассмотрим варианты создания хеш-таблицы: ее конструкторы, включая и неявные конструкторы (т.е. clone).

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
 
    // Find a power of 2 >= initialCapacity
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;
 
    this.loadFactor = loadFactor;
    threshold = (int)(capacity * loadFactor);
    table = new Entry[capacity];
    init();
}

Здесь все довольно просто. Сначала мы проверяем аргументы на валидность в этом блоке кода:

if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal initial capacity: " +
                                       initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
    initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
    throw new IllegalArgumentException("Illegal load factor: " +
                                       loadFactor);

Затем находим ближайшую ступень двойки и записываем ее в capacity. Устанавливаем loadFactor и threshold = (int)(capacity * loadFactor), а также массив бакетов:
table = new Entry[capacity];
Затем вызываем метод init(), который является хуком для классов, наследующих от HashMap. В данной реализации это просто пустой метод.

Теперь рассмотрим конструктор без аргументов:

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
    table = new Entry[DEFAULT_INITIAL_CAPACITY];
    init();
}

Здесь все то же самое, за исключением проверки аргументов. Это и логично, т.к. аргументов в конструкторе нет. Они могли бы вызвать конструктор с аргументами вот так:

public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

но не стали этого делать, т.к. это бы повлекло за собой проверку аргументов, которая в данном случае является лишней. Поэтому они скопипастили инициализирующий код сюда, сэкономив на проверке аргументов. Такая небольшая, но все-таки оптимизация.

Теперь рассмотрим конструктор, который создает хеш-таюлицу по другой хеш-таблице:

public HashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    putAllForCreate(m);
}

Здесь также все просто - выбираются значения initialCapacity и loadFactor, после этого все элементы копируются из одной таблицы в другую, используя метод putAllForCreate. Этот же метод используется в методе clone.

А вот и метод clone:

public Object clone() {
    HashMap<K,V> result = null;
    try {
        result = (HashMap<K,V>)super.clone();
    } catch (CloneNotSupportedException e) {
        // assert false;
    }
    result.table = new Entry[table.length];
    result.entrySet = null;
    result.modCount = 0;
    result.size = 0;
    result.init();
    result.putAllForCreate(this);
 
    return result;
}

В следующем посте мы рассмотрим как объекты получаются из и кладутся в таблицу, а также хеширование, изменение емкости и т.п.

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