Генерация хорошего хэш-кода (GetHashCode) для BitArray

Я должен генерировать быстрый хэш-код в 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
}

Любые предложения для улучшения приветствуются!

5
задан bart 29 June 2010 в 10:41
поделиться

2 ответа

Если битовые массивы 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 битам и т. Д.

1
ответ дан 15 December 2019 в 00:50
поделиться

Это ужасный класс для работы в качестве ключа в словаре. Единственный разумный способ реализовать GetHashCode() - это использовать его метод CopyTo() для копирования битов в байт[]. Это не очень хорошо, это создает тонну мусора.

Убедите, украдите или одолжите, чтобы вместо этого использовать BitVector32. Он имеет хорошую реализацию для GetHashCode(). Если у вас больше 32 бит, подумайте о создании собственного класса, чтобы можно было добраться до основного массива без необходимости копирования.

3
ответ дан 15 December 2019 в 00:50
поделиться
Другие вопросы по тегам:

Похожие вопросы: