Наверное, многим знакома проблема с хеш-таблицами и детерминированностью их сериализации. Если менять что-нибудь в базовых либах, то быстро находятся тесты, которые дифуют из-за изменения порядка обхода элементов в хеш-таблицах. Либо при релизе чего-нибудь такого пробивает кеши, ибо система полагалась на стабильность сериализации (тут стоит вспомнить protobuf-map, где в дефолте есть рандомизация хешей - и кто-то это считает ). И там и там лезут дифы, которые по идее не должны быть значимы с точки зрения логики программы (если она правильно написана), но порядок полей едет и с точки зрения "байтовой эквивалентности" что-то всё таки изменилось.

Совершенно очевидно свойство, верное для любого детерминированного кода: если засунуть (*) объекты в хеш-таблицу в неком порядке, то перебор из begin->end будет иметь некоторый определённый порядок.

У меня возник вопрос - а гарантируется ли ещё что-нибудь? Например, как соотносятся порядок элементов begin->end если во второй раз класть их в том порядке, который образовался после первого раза? Чуть более конкретно: как соотносятся порядки элементов между x на входе функции и res на выходе RefillSimple?

template<class T>
T RefillSimple(const T& x) {
    T res;
    for(auto& p : x) {
        res[p.first] = p.second;
    }
    return res;
}

Все числа далее я буду приводить на основе хеш таблицы, заполненной так:

constexpr size_t ElemsToStore = 100'000;
constexpr size_t Seed = 27;

void InitialFill(auto& x) {
    srandom(Seed);
    for(size_t i = 0; i < ElemsToStore; ++i) {
        x[random()] = i;
    }
}

void ResetByOrders(auto& x) {
    size_t counter = 0;
    for(auto& p : x) {
        p.second = counter++;
    }
}

100к случайных ключей с фиксированным сидом добавляются в хеш-таблицу - вышло 99'996 уникальных значений (кстати говоря, вполне в соответствии с так называемым парадоксом дней рождений). Далее значения назначаются в соответствии со сложившимся порядком.

Измерять будем количество нарушений монотонности (в сравнении с исходным порядком в хеш-таблице после завершения добавлений).

size_t CalcMissOrders(const auto& x) {
    size_t res = 0;
    for(auto it = x.begin(); it != x.end();) {
        auto cur_value = it->second;
        // auto bckNum = x.bucket(it->first);
        ++it;
        if (it == x.end()) {
            break;
        }
        auto next_value = it->second;
        res += (next_value < cur_value);
    }
}

Количество нарушений в самой исходной хеш-таблице (до вызова ResetByOrders) получилось 49'568 - вполне ожидаемо видим, что почти с 1/2 вероятностью следующее число будет больше или меньше предыдущего.

Вспоминая вопрос, который был задан в начале статьи: на выходе RefillSimple вышло 43'887 нарушений. Стат-значимо отличается, но в практическом смысле "очевидная закономерность не особо просматривается".

Время сделать паузу и подумать: откуда вообще взялось предположение, что должна быть какая-то связь и что-то должно сохраняться? А идея то очень простая: у нас ведь у данных не меняется ключ, то есть в бакет (unordered_map это хеш-таблица с косвенной адресацией) данные попадут тот же бакет. Более того - всякие размеры тоже должны получиться одинаковыми (мы просто добавляем элементы, и таблица будет расти в соответствии со своими политиками в те же моменты времени), то есть состав бакетов должен воспроизвестись. Замечу, что число бакетов на входе и выходе у RefillSimple действительно одинаковое (172'933 если быть точным). Ну и, конечно, мы предполагаем что перебор работает как последовательный перебор бакетов, в каждом бакете также случается последовательный перебор.

Продолжим эксперимент и посмотрим что будет с RefillReserved:

template<class T>
T RefillReserved(const T& x) {
    T res;
    res.reserve(x.size()); // Добавилась только эта строка
    for(auto& p : x) {
        res[p.first] = p.second;
    }
    return res;
}

Число нарушений монотонности станет 74'304 - почти 3/4. Сильное отклонение в убывание подозрительно, хотя догадаться что ждать сильных совпадений неоткуда - число бакетов здесь всего 107'897 - конечно много чего будет другим

Замечание: тестирую с std которое автоматом юзается клангом, в этой реализации max_load_factor в дефолте равен 1.

Давайте сделаем что-то более осмысленно: res.reserve(x.bucket_count() * x.max_load_factor) (или в более короткой форме - res.rehash(x.bucket_count())). И тут получается то, что в начале меня очень удивило: 99'995 - ровно на 1 меньше нарушений,чем число элементов. Другими словами, порядок получился строго обратным.

В частности, двойное применение действительно (report.txt ) сохраняет порядок

template<class T>
T RefillRehash(const T& x) {
    T res;
    res.rehash(x.bucket_count());
    for(auto& p : x) {
        res[p.first] = p.second;
    }
    return res;
}

{
   auto double_refill = RefillRehash(RefillRehash(initial_data));
}

Кажется, мы только что эмпирически определили, что

  1. бакеты в данном unordered_map являются односвязным списком, добавление элемента происходит в начало списка (можно сказать что это стэк)

  2. поддерживается список непустых бакетов, добавление бакета в этот список также случается со стороны головы

Суммарно выходит, что добавленные элементы образуют обратный порядок

Тут можно попытаться объяснить почему отклоняются так сильно от случайного первые два варианта: каждый rehash меняет порядок на обратный у уже добавленного префикса (если было a,b,c, rehash-happens , d e то получится c b a d e ) - конкретными моментами rehash должен объясняться первый пример. Также порядок перебора меняется достаточно хаотично если образуется или распадается коллизия (новый элемент добавляется куда-то ранее в точке перебора), вероятно, это объясняет "почти обратный порядок" в случае с reserve - мы его почти получили, но другие коллизии немного подломали (мат ожидание числа коллизий в случае с 107к бакетами - примерно 50к, а в случае с 172к бакетами - всего 29к ~1e5 * 1e5 / 2 / 1.72e5)

Можно сказать пару слов и про другие реализации хеш-мап

Например, в яндексовой аркадии есть THashMap - бакеты провязывает в прямой список и там поведение совсем другое: 746 нарушений в RefillSimple, и RefillReserved, а двойной refill даёт 385 нарушений.

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

(*) - тут следовало бы уточнить что должны совпадать все действия с хеш-таблицей, в том числе всякие reserve