Я должен генерировать быстрый хэш-код в GetHashCode для BitArray. У меня есть Словарь, где ключами является BitArrays, и все BitArrays имеют ту же длину.
Кто-либо знает о быстром способе генерировать хороший хеш от переменного числа битов, как в этом сценарии?
ОБНОВЛЕНИЕ:
Подход, который я первоначально проявил, должен был получить доступ к внутреннему массиву ints непосредственно посредством отражения (скорость более важна, чем инкапсуляция в этом случае), затем XOR те значения. Подход XOR, кажется, работает хорошо, т.е. мой 'Равняется' методу, не назван чрезмерно при поиске в Словаре:
public int GetHashCode(BitArray array)
{
int hash = 0;
foreach (int value in array.GetInternalValues())
{
hash ^= value;
}
return hash;
}
Однако подход, предложенный Mark Byers и замеченный в другом месте на StackOverflow, был немного лучше (16570, Равняется вызовам по сравнению с 16 608 для XOR для моих данных тестирования). Обратите внимание, что этот подход исправляет ошибку в предыдущей, где биты вне конца битового массива могли влиять на значение хэш-функции. Это могло произойти, если бы битовый массив был уменьшен в длине.
public int GetHashCode(BitArray array)
{
UInt32 hash = 17;
int bitsRemaining = array.Length;
foreach (int value in array.GetInternalValues())
{
UInt32 cleanValue = (UInt32)value;
if (bitsRemaining < 32)
{
//clear any bits that are beyond the end of the array
int bitsToWipe = 32 - bitsRemaining;
cleanValue <<= bitsToWipe;
cleanValue >>= bitsToWipe;
}
hash = hash * 23 + cleanValue;
bitsRemaining -= 32;
}
return (int)hash;
}
Метод расширения GetInternalValues реализован как это:
public static class BitArrayExtensions
{
static FieldInfo _internalArrayGetter = GetInternalArrayGetter();
static FieldInfo GetInternalArrayGetter()
{
return typeof(BitArray).GetField("m_array", BindingFlags.NonPublic | BindingFlags.Instance);
}
static int[] GetInternalArray(BitArray array)
{
return (int[])_internalArrayGetter.GetValue(array);
}
public static IEnumerable<int> GetInternalValues(this BitArray array)
{
return GetInternalArray(array);
}
... more extension methods
}
Любые предложения для улучшения приветствуются!
Если битовые массивы 32-битные или короче, вам просто нужно преобразовать их в 32-битные целые числа (при необходимости заполнить нулевыми битами).
Если они могут быть длиннее, вы можете либо преобразовать их в серию 32-битных целых чисел и выполнить XOR, либо лучше: использовать алгоритм, описанный в Эффективной Java.
public int GetHashCode()
{
int hash = 17;
hash = hash * 23 + field1.GetHashCode();
hash = hash * 23 + field2.GetHashCode();
hash = hash * 23 + field3.GetHashCode();
return hash;
}
Взято из здесь . Поле 1, поле 2 соответствуют первым 32 битам, вторым 32 битам и т. Д.
Это ужасный класс для работы в качестве ключа в словаре. Единственный разумный способ реализовать GetHashCode() - это использовать его метод CopyTo() для копирования битов в байт[]. Это не очень хорошо, это создает тонну мусора.
Убедите, украдите или одолжите, чтобы вместо этого использовать BitVector32. Он имеет хорошую реализацию для GetHashCode(). Если у вас больше 32 бит, подумайте о создании собственного класса, чтобы можно было добраться до основного массива без необходимости копирования.