0

Допустим, у меня есть коллекция из 5 объектов. Мне необходимо эту коллекцию объединить с другими данными по принципу Ключ-значение. Для этих целей я использую интерфейс Map. Поскольку мне заранее известно макс. кол-во объектов, я хочу максимально оптимально инициализировать данную мапу.

Для этого я пишу Map<K,V> someMap = new HashMap(5,1);, где 5-initialCapacity, а 1-loadFactor. Однако мне кажется, что данный способ не является правильным, т.к. взглянув "под капот" мапы можно увидеть метод, который судя по описанию возвращает степень двойки от заданной мной initialCapacity для размера таблицы:

/**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

Каким образом в данном случае наиболее оптимально инициализировать мапу (для точного макс. кол-ва ключей)?

1
  • Не совсем понятен вопрос, потому что если выбор ближайшей степени двойки в качестве объёма УЖЕ зашит в структуру данных, то как ни крутись, ничего вас от этого не спасёт. По-видимому, алгоритм работы данного хэша таков, что степень двойки очень выгодна для внутренних расчётов (таких как расчёт позиции, вместо остатка от деления берём просто побитовое И).
    – Zealint
    9 дек 2016 в 8:53

1 ответ 1

1

К сожалению, судя по реализации этой структуры данных невозможно сделать то, что вы хотите. Дело в том, что степень двойки - это очень удобное число для вычисления позиции. То есть вместо остатка от деления x % m вы считаете побитовое И x & (m-1) в каждый момент, когда обращаетесь к таблице (ищите, добавляете или удаляете что-то). Это может выглядеть так (взял здесь):

static int indexFor(int h, int length) {
    return h & (length-1);
}

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

Так же и вы, хотите оптимизировать по объёму, не зная, что проиграете в скорости, причём, возможно, очень существенно.

Если для вас всё же ситуация критична, напишите свой хэшмап, это не так трудно, как кажется.

1
  • Благодарю. В целом для небольших размерностей разница получается вполне адекватной. Так что в любом случае имеет смысл явно указывать параметры инициализации для известных заранее размерностей
    – I. Perevoz
    9 дек 2016 в 9:24

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.