Понимание алгоритма расчета мощности в HashMap - PullRequest
Новая
       41

Понимание алгоритма расчета мощности в HashMap

0 голосов
/ 19 октября 2018

Мне интересно знать, как работает алгоритм расчета емкости в HashMap.

, где, если мы создадим объектную HashMap с некоторой требуемой емкостью 20, тогда алгоритм всегда вычислит следующую наибольшую емкость, т. Е. (2 ^x> 20)

Ниже приведена реализация jdk ..... 

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;
}

Может кто-нибудь объяснить мне, как работает вышеупомянутый алгоритм, что происходит на каждом шаге.

Я понял, что на каждом шаге они делят число 2 и делают побитовое ИЛИ к более старому значению.и это они делают, потому что им нужно распределить следующее (2 ^ x) значение больше n,

Но кто-то может помочь объяснить мне на каждом шаге, что происходит с некоторыми числами, я пытался отладить, ноощущение сложности.

Я имею в виду некоторую реализацию, подобную приведенной ниже. 

private static int calculateCapacity(int cap){

    int max_capcity = 256;
    if(cap<16){
        return 16;
    }else if(cap <32){
        return 32;
    }else if(cap <64){
        return 64;
    }else if(cap < 128){
        return 128;
    }
    return max_capcity;
}

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

1 Ответ

0 голосов
/ 19 октября 2018

Этот алгоритм является быстрым способом определения наименьшей мощности 2, которая больше или равна заданной cap.

Способ, которым это работает, заключается в том, что он вычисляет число, для которого установлен только один бит, и этот бит находится в позиции выше, чем все остальные биты в вашем исходном номере (или в старшем бите исходного числа, еслион имеет только один установленный бит).Для этого он устанавливает все биты, меньшие, чем начальный бит, в 1, а затем добавляет 1.

. Вот как это работает для положительного числа, записанного 001XXXXXXXXX (биты послестарший бит не имеет значения): 

int n = cap - 1;    // will not change anything to the leading bit except
                    // if cap is already a power of 2. In that case,  
                    // we had cap = 001000000000 and now n = 000111111111 and
                    // the other lines won't change anything, we just have to
                    // do +1 in the end and we're done, n = cap;
                    // otherwise, let's assume that not every 'X' is a '0'

n |= n >>> 1;       // n >>> 1 = 0001XXXXXXX
                    // so    n = 0011XXXXXXX

n |= n >>> 2;       // n >>> 2 = 000011XXXXX
                    // so    n = 001111XXXXX

n |= n >>> 4;       //       n = 0011111111X

n |= n >>> 8;       //       n = 00111111111

n |= n >>> 16;      //       n = 00111111111

return n + 1;       //  result = 01000000000

Для отрицательных чисел n отрицателен в каждой строке, поскольку знаковый бит всегда равен 1, поэтому результат будет 1.

...