Подтвердить что ты не робот

Почему метод Stream <T> collect возвращает другой порядок ключей?

У меня есть этот код:

public enum Continent {ASIA, EUROPE}

public class Country {      
   private String name;
   private Continent region;

    public Country (String na, Continent reg) { 
        this.name = na;
        this.region = reg;
    }
    public String getName () {return name;} 
    public Continent getRegion () {return region;}
    @Override
    public String toString() {
        return "Country [name=" + name + ", region=" + region + "]";
    }
}

и в основном классе:

public static void main(String[] args) throws IOException {
        List<Country> couList = Arrays.asList(
            new Country ("Japan", Continent.ASIA), 
            new Country ("Sweden", Continent.EUROPE), 
            new Country ("Norway", Continent.EUROPE));
        Map<Continent, List<String>> regionNames = couList
                .stream()
                //.peek(System.out::println)
                .collect(Collectors.groupingBy(Country::getRegion, Collectors.mapping(Country::getName, Collectors.toList())));
        System.out.println(regionNames);
}

Если я запустил этот код, я получаю этот вывод:

{EUROPE=[Sweden, Norway], ASIA=[Japan]}

но если я раскомментирую функцию peek, я получаю этот вывод:

Country [name=Japan, region=ASIA]
Country [name=Sweden, region=EUROPE]
Country [name=Norway, region=EUROPE]
{ASIA=[Japan], EUROPE=[Sweden, Norway]}

Мой вопрос: может ли кто-нибудь сказать мне, почему порядок клавиш отличается на карте regionNames, когда функция peek находится на месте?

4b9b3361

Ответ 1

Реализация enum hashCode использует значение по умолчанию, указанное Object. В документации этого метода упоминается:

Всякий раз, когда он вызывается одним и тем же объектом более одного раза во время выполнения приложения Java, метод hashCode должен последовательно возвращать одно и то же целое число, если информация, используемая при равных сравнениях с объектом, не изменяется. Это целое число не должно оставаться согласованным с одним исполнением приложения на другое выполнение того же приложения.

Так как хэш-код определяет порядок ведер внутри HashMap (что используется groupingBy), порядок изменяется при изменении хеш-кода. Как генерируется этот хеш-код, это деталь реализации виртуальной машины (как отметил Юджин). Комментируя и не комментируя строку с помощью peek, вы просто нашли способ повлиять (надежно или нет) на эту реализацию.


Поскольку этот вопрос получил щедрость, кажется, что люди не удовлетворены моим ответом. Пойду немного глубже и посмотрю на реализацию open-jdk8 (потому что он с открытым исходным кодом) hashCode. ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Я еще раз заявлю, что реализация алгоритма хеш-кода идентификатора не задана и может быть совершенно различной для другой виртуальной машины или между разными версиями одной и той же виртуальной машины. Поскольку OP наблюдает это поведение, Я буду считать, что используемая им виртуальная машина - это Hotspot (Oracle one, который afaik использует ту же реализацию hashcode, что и opendjk). Но главное в этом состоит в том, чтобы показать, что комментарий или отказ от комментариев, казалось бы, несвязанной строки кода может изменить порядок ведер в HashMap.. Это также одна из причин, почему вы должен никогда полагаться на порядок итерации коллекции, которая не указывает ее (например, HashMap).

Теперь, фактический алгоритм хэширования для openjdk8 определен в synchronizer.cpp:

 // Marsaglia xor-shift scheme with thread-specific state
 // This is probably the best overall implementation -- we'll
 // likely make this the default in future releases.
 unsigned t = Self->_hashStateX ;
 t ^= (t << 11) ;
 Self->_hashStateX = Self->_hashStateY ;
 Self->_hashStateY = Self->_hashStateZ ;
 Self->_hashStateZ = Self->_hashStateW ;
 unsigned v = Self->_hashStateW ;
 v = (v ^ (v >> 19)) ^ (t ^ (t >> 8)) ;
 Self->_hashStateW = v ;
 value = v ;

Как вы можете видеть, хеш-код основан на этих _hashState полях объекта Thread, и выход изменяется от одного вызова к другому, так как значения переменных "перетасовываются".

Эти переменные инициализируются в конструкторе Thread следующим образом:

_hashStateX = os::random() ;
_hashStateY = 842502087 ;
_hashStateZ = 0x8767 ;    // (int)(3579807591LL & 0xffff) ;
_hashStateW = 273326509 ;

Единственная движущаяся часть здесь os::random, которая определена в os.cpp, которая имеет комментарий, описывающий алгоритм как:

next_rand = (16807*seed) mod (2**31-1)

Этот seed является единственной движущейся частью и определяется _rand_seed и инициализируется через функцию, называемую init_random, а в конце функции возвращаемое значение используется как семя для следующий звонок. A grep через репо показывает следующее:

PS $> grep -r init_random
os/bsd/vm/os_bsd.cpp:  init_random(1234567);
os/linux/vm/os_linux.cpp:  init_random(1234567);
os/solaris/vm/os_solaris.cpp:  init_random(1234567);
os/windows/vm/os_windows.cpp:  init_random(1234567);
... test methods

Похоже, что начальное семя является константой на тестируемой платформе (windows).


Из этого я пришел к выводу, что сгенерированный хэш-код идентичности (в openjdk-8), изменения, основанные на том, сколько хэш-кодов идентификаторов было создано в одном и том же потоке до него и сколько раз os::random было вызываемый до создания потока, генерирующего хэш-код, который остается неизменным для примера программы. Мы уже можем видеть это, потому что порядок ключей не изменяется от запуска до запуска программы, если программа остается прежней. Но еще один способ увидеть это - положить System.out.println(new Object().hashCode()); в начале метода main и увидеть, что вывод всегда один и тот же, если вы запускаете программу несколько раз.

Вы также заметите, что генерация идентификационных кодов хеша до вызовов потоков также изменит хэш-коды констант перечисления и, следовательно, может изменить порядок ковшей на карте.

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

Map<Continent, List<String>> regionNames = couList
        .stream()
        //.peek(System.out::println) // Does this call Object.hashCode?
        .collect(Collectors.groupingBy(Country::getRegion,
            Collectors.mapping(Country::getName, Collectors.toList()))); // hash code for constant generated here

Вы можете увидеть это с помощью обычного отладчика Java. Я поместил точку останова на Object#hashCode и стал ждать, если это вызовет строка с peek. (Если вы попробуете это самостоятельно, я бы заметил, что VM использует HashMap сам и будет вызывать hashCode несколько раз перед методом main. Поэтому имейте это в виду)

Et voila:

Object.hashCode() line: not available [native method]   
HashMap<K,V>.hash(Object) line: 338 
HashMap<K,V>.put(K, V) line: 611    
HashSet<E>.add(E) line: 219 
Collections$SynchronizedSet<E>(Collections$SynchronizedCollection<E>).add(E) line: 2035 
Launcher$AppClassLoader(ClassLoader).checkPackageAccess(Class<?>, ProtectionDomain) line: 508   
Main.main(String...) line: 19   

Строка с peek вызывает hashCode на объекте ProtectionDomain, который используется загрузчиком классов, который загружает класс LambdaMetafactory (который является Class<?>, который вы видите, я могу получить значение из моего отладчик). Метод hashCode на самом деле называется кучей раз (может быть, несколько сотен?), Для строки с peek, в рамках платформы MethodHandle.

Итак, поскольку строка с peek вызывает Object#hashCode, до того, как генерируются хэш-коды для констант перечисления (также путем вызова Object#hashCode), хэш-коды констант меняются. Таким образом, добавление или удаление строки с помощью peek изменяет хэш-коды констант, что изменяет порядок ковшей на карте.

Последний способ подтвердить, состоит в том, чтобы генерировать хэш-коды констант перед строкой с помощью peek, добавляя:

Continent.ASIA.hashCode();
Continent.EUROPE.hashCode();

В начало метода main.

Теперь вы увидите, что комментарий или отказ от комментария строки с peek не влияет на порядок ведер.