В VS 2008 без SP1 (но с пакетом возможностей, который предоставляет библиотеку TR1) хеш-функция по умолчанию для tr1::unordered_map<> учитывает только младшие 32 бита значения ключа.По крайней мере, это из-за того, что я прочитал реализацию template<class _Kty> class hash::operator() в заголовке <functional>.
Переменная footstep, являющаяся ключом, использует все, что рассчитано для y как его младшие 32 бита - достаточно ли этого?вариация в y, что он будет делать хорошее хеш-значение само по себе (я не могу сказать, что делает код, вычисляющий y)?Если нет, то вы можете поместить в конкретное хеш-хранилище гораздо больше элементов, чем вам хотелось бы, и создать слишком много коллизий.
В этом случае вы можете рассмотреть возможность предоставления собственной хеш-функции.
Кстати, похоже, что VS 2010 имеет специализации для hash::operator() при использовании с 64-разрядными целыми числами, поэтому он будет хешировать все 64-разрядные - если вы используете VS 2010, предположение в моем ответе должноне применимо.
Обновление:
После некоторого тестирования я убежден, что это проблема (проблема также существует в VS 2008 SP1).Вы можете исправить это, обновив компилятор до VS 2010, который имеет лучшие хэш-функции для 64-битных типов, или используйте свою собственную хеш-функцию, чтобы справиться с этим самостоятельно.Ниже приведен пример, который я быстро протестировал в VS2008, и, похоже, он работает:
class hash_int64
: public unary_function<__int64, size_t>
{
public:
typedef __int64 key_t;
typedef unsigned int half_t;
size_t operator()(const key_t& key) const
{
// split the 64-bit key into 32-bit halfs, hash each
// then combine them
half_t x = (half_t) (key & 0xffffffffUL);
half_t y = (half_t) (((unsigned __int64) key) >> 32);
return (hash<half_t>()(x) ^ hash<half_t>()(y));
}
};
Затем измените typedef на:
typedef std::tr1::unordered_map <__int64, int, hash_int64> umap_id;