Другой класс вместо SHA1Устраивается для создания контрольной суммы с длиной байтов менее 128 - PullRequest
Новая
       3

Другой класс вместо SHA1Устраивается для создания контрольной суммы с длиной байтов менее 128

1 голос
/ 27 сентября 2010

У меня есть таблица с одним столбцом (AbsoluteUrl NVARCHAR (2048)), и я хочу сделать запрос к этому столбцу, поэтому для сравнения каждой записи с моей собственной строкой потребовалось много времени. хотя бы в этой таблице 1000000 записей.

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

public static byte[] GenerateChecksumAsByte(string content)
    {
        var buffer = Encoding.UTF8.GetBytes(content);
        return new SHA1Managed().ComputeHash(buffer);
    }

И подходит ли этот подход для моей работы?

UPDATE

Согласно ответам, я хочу объяснить более подробно. так что на самом деле я работаю над очень простой системой веб-поиска. Если я хочу кратко объяснить, что я должен сказать, когда будут извлечены все URL-адреса веб-страницы (коллекция найденных URL-адресов), то я собираюсь проиндексировать это в таблице Urls.

Уникальный идентификатор UrlId Первичный ключ NotNull (кластерный индекс) AbsoluteUrl nvarchar (2048) NoyNull Контрольная сумма varbinary (128) NotNull

Итак, сначала я ищу в таблице, есть ли у меня тот же URL, который был проиндексирован ранее или нет. если нет, то создайте новую запись. 

public Url Get(byte[] checksum)
    {
        return _dataContext.Urls.SingleOrDefault(url => url.Checksum == checksum);
        //Or querying by AbsoluteUrl field
   }

И метод сохранения. 

public void Save(Url url)
    {
        if (url == null)
            throw new ArgumentNullException("url");
        var origin = _dataContext.Urls.GetOriginalEntityState(url);
        if (origin == null)
        {
            _dataContext.Urls.Attach(url);
            _dataContext.Refresh(RefreshMode.KeepCurrentValues, url);
        }
        else
            _dataContext.Urls.InsertOnSubmit(url);
        _dataContext.SubmitChanges();
    }

Например, если на одной странице я нашел 2000 URL, я должен искать 2000 раз.

Ответы [ 3 ]

2 голосов
/ 27 сентября 2010

Вы хотите использовать хеш размера (p) в качестве ключа, ожидая максимум 1м записей (u).Чтобы ответить на этот вопрос, вы должны сначала выполнить математику ...

Решите следующее для каждого размера хэша, чтобы рассмотреть: 1 - e ^ (-u ^ 2 / (2 * p))

  • 32-разрядная: 100% -ная вероятность столкновения
  • 64-разрядная: 0,00000271% -ная вероятность столкновения
  • 128-разрядная: 0% (слишком мала для вычисления с двойной точностью)

Теперь у вас должно быть достаточно информации, чтобы принять обоснованное решение.Вот код для выполнения вышеуказанного вычисления на 64-битном ключе: 

double keySize = 64;
double possibleKeys = Math.Pow(2, keySize);
double universeSize = 1000000;
double v1, v2;
v1 = -Math.Pow(universeSize, 2);
v2 = 2.0 * possibleKeys;
v1 = v1 / v2;
v1 = Math.Pow(2.718281828, v1);
v1 = 1.0 - v1;
Console.WriteLine("The resulting percentage is {0:n40}%", v1 * 100.0);

Лично я сам придерживался бы по крайней мере 128-битного хэша.Более того, если коллизии могут вызвать какую-либо дыру в безопасности, вам нужно использовать хотя бы хэш v2 SHA (SHA256 / SHA512).

Теперь, если это всего лишь оптимизация для базы данных, рассмотрите следующее:

  1. добавьте в таблицу 32-битный хэш-код.
  2. создайте составнойключ, содержащий как 32-битный хеш, так и исходную строку.
  3. ВСЕГДА ищите как по хешу, так и по исходной строке.
  4. Предположим, что хэш является только оптимизацией и никогда не уникален.
2 голосов
/ 27 сентября 2010

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

Однако, в зависимости от вашей базы данных, индексирование NVARCHAR (2048) может оказаться невозможным и действительно может стать узким местом. В этом случае создание контрольных сумм фактически может улучшить производительность поиска, если:

  1. Вы делаете намного больше сравнений, чем вставок.
  2. Сравнение контрольной суммы быстрее, чем сравнение NVARCHAR.
  3. Большинство ваших контрольных сумм разные.

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

В этом случае криптографическая контрольная сумма не требуется, вы можете использовать меньший, более быстрый алгоритм контрольной суммы, такой как CRC64 .

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

1 голос
/ 27 сентября 2010

Нет, это не очень хороший подход.

Миллион записей не имеет большого значения для индексированного поля. С другой стороны, любая контрольная сумма / хэш / что-либо, что вы генерируете, может давать ложные срабатывания из-за принципа голубиных отверстий (парадокс дня рождения). Увеличение его уменьшает, но не устраняет этот шанс, но замедляет процесс до такой степени, что не будет увеличения скорости.

Просто нажмите индекс на поле и посмотрите, что произойдет.

...