Отделить функцию хеширования std::hash от собственно хешируемых данных

Igor Baidiuk
Igor Baidiuk

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

1. Свой функтор.
Достоинства:
+ очевидно и "прямолинейно"
Недостатки:
- надо явно использовать во всех контейнерах
- надо вручную реализовывать "микширование" хешей компонентов в единый хеш
- хешер оказывается "прибит гвоздями" к конкретному алгоритму хеширования
2. Специализация std::hash
Достоинства:
+ Будет использован автоматически
Недостатки:
- "Влазить" в namespace std не поощряется стандартом за исключением оговорённых случаев
- надо вручную реализовывать "микширование" хешей компонентов в единый хеш
- хешер оказывается "прибит гвоздями" к конкретному алгоритму хеширования

Итак, собственно proposal sketch

Типы, желающие быть хешированными, добавляют либо метод

template<typename Hasher>
void hash(Hasher& hasher) const;

либо свободную функцию

template<typename Hasher>
void hash(MyType const& self, Hasher& hasher);

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

struct MyVec {
    double x, y, z;

    template<typename Hasher>
    void hash(Hasher& hasher) const {
        hasher(x);
        hasher(y);
        hasher(z);
    }
};

Вторым компонентом этой системы является непосредственно хешер (ниже пример примитивного хешера)

struct MyHasher {
    void operator()(const void* bytes, size_t nBytes) {
        accumulated = myFancyHashFunc(accumulated, bytes, nBytes);
    }

    template<typename T>
    void operator()(T&& value) {
        hasher_traits<MyHasher>{}(*this, std::forward<T>(value));
    }

    size_t hash() const noexcept { return accumulated; }
private:
    size_t accumulated = StarterHashConstant;
};

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

Преимущества:
+ Каждому конкретному типу не требуется ни знать про хеширование как таковое, ни даже про метод "примешивания" байт к имеющемуся хешу - к примеру, отпадает головная боль как правильно соединить хеши трёх чисел с плавающей точкой
+ Тип может быть хеширован любым подходящим по месту способом, а не так, как решил автор типа
+ В месте использования контейнера можно использовать нестандартный алгоритм хеширования без необходимости переопреелять его для всех типов по месту
+ Наконец, результат хеширования не обязан быть всегда size_t, и конкретному типу совершенно не нужно об этом знать. Любой тип, поддерживающий хеширование, можно при необходимости пропустить через CRC32, MD5, SHA1, SHA512 и т.п. При этом стандартные контейнеры могут всё так же спокойно требовать size_t как тип результата хеширования.

Как всё это встроить в текущую модель.
Стандартом предполагается наличие "включенных" и "выключенных" реализаций std::hash. При этом большинство реализаций выключены по умолчанию с помощью бланкет-реализации для любого типа T. Эту бланкет-реализацию можно расширить поддержкой указанных систем хеширования. Таким образом, std::hash по умолчанию приобретает примерно следующий вид

namespace std {
    template<Hashable T>
    struct hash {
        size_t operator()(T const& value) const {
            std::hasher hasher;
            hasher(value);
            return hasher.hash();
        }
    };
}
3
рейтинг
3 комментария
yndx-antoshkka

Подобные предложения уже рассматриваются комитетом: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0199r0.pdf, http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0814r2.pdf

 

yndx-antoshkka
Igor Baidiuk

yndx-antoshkka, спасибо за ссылки.
Если я правильно понимаю, первый концентрируется на default hash operator, а второй - на hash_combine. Первый ортогонален, а второй - не решает проблему "прибитости гвоздями" хеш-оператора к конкретному алгоритму.
Это же предложение лежит в несколько иной плоскости.

Igor Baidiuk
Igor Baidiuk

Нашёл этот пропозал: p0029r0
Пока что наиболее близко к теме.

Igor Baidiuk
Другие идеи
Группа создана, чтобы собирать предложения к стандарту C++, организовывать их внутренние обсуждения, помогать готовить их для отправки в комитет и защищать на общих собраниях в рабочей группе по С++ Международной организации по стандартизации (ISO).
Все предложения