Адрес памяти для хэш-кода без объединения
При изучении структур данных, в частности хеш-таблиц, нам сказали, что изобрести эффективную хеш-функцию для типа данных — очень сложная задача, но было высказано предположение, что существует быстрый ярлык. А именно, если мы можем предположить, что объекты не перемещаются в памяти, и мы можем определить равенство объектов как имеющих один и тот же адрес памяти (использовать равенство ссылок в противоположность равенству значений), то мы можем получить хэш-код объекта, подобный этому:
#include<iostream>
template<typename T>
class hashcoder {
private:
union impl {
T* ptr;
int32_t hashcode; // or int64_t on a 64-bit architecture = architecture with 64-bit pointers
};
public:
static int32_t hash(const T& r) {
impl i;
i.ptr = &r;
return i.hashcode;
}
};
class myclass {
// whatever
};
int main() {
myclass m;
std::cout << hashcoder<myclass>::hash(m) << std::endl;
}
Итак, мой вопрос:
- Есть ли что-то не так с использованием адреса памяти для хэш-кода (опять же, предполагая, что ссылочное равенство — желаемое поведение)?
- Учитывая, что использование союзов для преобразования неопределенное поведение, Как мы можем преобразовать адрес памяти в целое число?
- (Не стесняйтесь указывать на любые другие ошибки, которые я допустил в приведенном выше коде. Указатели C ++ опасно легко ошибиться.)
Решение
- Нет, ничего плохого в этом нет; хеш является целым числом и гарантированно будет уникальным для каждого объекта, что уменьшает вероятность столкновения.
-
Приведите указатель к
uintptr_t, Нет необходимости в союзе. Также,uintptr_tимеет правильный размер для платформы, поэтому вам больше не нужно гадить сint32_tи т.п.uintptr_t hash(const T &r) { return uintptr_t(&r); }
(Если хеш должен быть 32-битным, либо приведите это к uint32_t или на 64-битной платформе объедините две половины, используя соответствующая магия.)
Другие решения
Во-первых, ваш код предполагает, что отдельные экземпляры T всегда разные (для != оператор). Это не всегда так и, конечно, неверно, например, std::string когда вы хотите хешировать строковое значение (то есть содержимое), а не какой-либо адрес …. Аналогично, если вы хотите хешировать (математические) векторы целых чисел, вы должны хешировать их содержимое (математические компоненты вектора) ,
Затем вы должны знать, что простое использование адреса чего-либо в качестве его хеша, вероятно, является неоптимальным, поскольку адреса достаточно больших объектов, как правило, кратны 8 или 16 байтам (точнее, выравниванию этого типа объектов), и часто адреса объектов, размещенных в один и тот же момент, очень похожи. Фактически, некоторые «средние биты» указателя, вероятно, являются более «случайными», чем младшие биты или очень старшие биты.
Немного лучшим подходом может быть выполнение побитовой арифметики с адресом указателя, например,
static inline int32_t ptrhash(const void*p) {
uintptr_t u = (uintptr_t)p;
return u ^ (u >> 10);
}
или же
static inline int32_t ptrhash(const void*p) {
uintptr_t u = (uintptr_t)p;
return (u * 200771) + (u % 300823);
}
И 200771, и 300823 являются простыми числами. Вы могли бы заменить + с побитовым xor ^
или какой-то трюк смешивает соответственно биты адреса.
Конечно, YMMV, и это абсолютно зависит от системы (например, зависит, если ваша система имеет ASLR)
Другой подход, для некоторых class Tможет быть сгенерировать в конструкторе, например, во время построения экземпляров T некоторый случайный хеш (используя быстрый ПСЧ лайк lrand48 …), и поместите этот хеш как личную переменную-член экземпляра. Или просто используйте какой-то статический счетчик для уникальной нумерации каждого экземпляра и используйте этот номер в качестве хэша.
Важно убедиться, что все ваши экземпляры разные! Если вы хотите хэшировать содержимое, это не так (но посмотрите мемоизации, так далее…).
Кроме того, я бы не согласился с вашим учителем: действительно, очень сложно придумать очень хорошую хеш-функцию, но сделать «достаточно хорошую» функцию средней хеш-функции обычно легко (например, использовать линейную комбинацию с простые числа Коэффициенты хеша составных частей см. Теорема Безу). А также обычно, в практика, такие «легкие» хеш-функции работают достаточно хорошо (конечно, есть исключения, и невероятный наихудший случай может быть ужасным).
Читайте также о идеальный хэш, например с помощью GNU Gperf.
Если вы хотите ссылочного равенства, нет ничего плохого в использовании адреса в качестве хеш-кода. Тем не менее, гораздо более разумный способ его реализации, чем объединение, заключается в использовании intptr_t, В случае intptr_t больше чем int32_t, вы можете и с -1, а затем static_cast в uint32_t,
Вам просто нужен шаблон функции.
Вот что вы могли бы сделать (при условии, что ваша хеш-таблица имеет ограниченное количество сегментов):
template <typename T>
uintptr_t hashcode(const T &obj, size_t size) {
return reinterpret_cast<uintptr_t>(&obj) % size;
}