Не является ли "int GetHashCode" немного близоруким?

Учитывая, что .Net обладает способностью обнаруживать битту через IntPtr (просмотр рефлектора в хорошем количестве помечается небезопасным, хотя - позор). Я думал, что GetHashCode, возвращающий int, потенциально близорук.

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

В равной степени - я единственный, кто считает это забавным:

struct Int64{
  public override int GetHashCode()
  {
    return (((int) this) ^ ((int) (this >> 0x20)));
  }
}

Пока Int32 просто возвращает this.

Если IntPtr не может быть оспорено из-за проблем с производительностью, лучше ли IHashCode, который реализует IEquatable и т.д.?

Как наши платформы становятся все больше и больше с точки зрения объема памяти, размера диска и т.д., наверняка, дни с 32-битными хэшами достаточно потенциально пронумерованы?

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

Ответы

Ответ 1

Хеш-функция Int64 позволяет убедиться, что все биты рассмотрены - так что в основном это XORing верхних 32 бит с нижними 32 битами. Я не могу представить себе лучшего общего назначения. (Усечение до Int32 не было бы хорошо - как вы могли бы правильно хэш-64-битные значения, которые имели все нули в младших 32 битах?)

Если IntPtr использовался как возвращаемое значение хеша, тогда код должен иметь условные ветки (это 32-разрядный? это 64-бит? и т.д.), что замедлит хеш-функции, победив всю точку.

Я бы сказал, что если у вас есть хеш-таблица, у которой на самом деле есть 2 миллиарда ведер, вы, вероятно, на стадии написания всей настраиваемой системы. (Возможно, лучше было бы использовать базу данных?) При таком размере уверенность в том, что ведра будут заполнены равномерно, будет более актуальной. (Другими словами, лучшая хеш-функция, вероятно, выплатит больше дивидендов, чем большее количество ковшей).

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

Ответ 2

Вы понимаете, что хеш-код, возвращаемый GetHashCode, используется для адресации в хэш-таблице? Использование большего типа данных было бы бесполезным упражнением, поскольку все хеш-таблицы в любом случае меньше. Дополнительная информация будет просто потрачена впустую, потому что ее нельзя использовать адекватно.

Общие хеш-таблицы имеют от нескольких тысяч до нескольких миллионов записей. 32-битное целое число более чем достаточно для покрытия этого диапазона индексов.