Какой лучший способ создать короткий хеш, подобный тому, что делает крошечный URL?

Question

В настоящее время я использую хэши MD5, но я хотел бы найти что-то, что создаст более короткий хеш, который использует только [a-z] [A-Z] [0-9]. Это должно быть около 5-10 символов.

Есть ли что-то, что уже делает это?

Обновление:

Мне нравится хэш CRC32. Есть ли чистый способ расчета в .NET?

Обновление2:

Я использую функцию CRC32 по предоставленной Джо ссылке. Как я могу преобразовать UInt в символы, определенные выше?

Answer 1

.NET строковый объект имеет функцию GetHashCode (). Возвращает целое число. Преобразуйте его в гекс, а затем в строку длиной 8 символов.

Вроде так:

string hashCode = String.Format("{0:X}", sourceString.GetHashCode());

Подробнее об этом: http://msdn.microsoft.com/en-us/library/system.string.gethashcode.aspx

ОБНОВЛЕНИЕ: Добавлены замечания по ссылке выше к этому ответу:

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

Если два строковых объекта равны, метод GetHashCode возвращает одинаковые значения. Тем не менее, не существует уникального значения хэш-кода для каждое уникальное строковое значение. Разные строки могут возвращать один и тот же хеш Код.

Примечания для абонентов

Значение, возвращаемое GetHashCode, зависит от платформы . Отличается по 32-разрядные и 64-разрядные версии .NET Framework.

Answer 2

Ваша цель - сократить URL или создать хеш-функцию?

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

Вы можете сделать это, используя код как:

using System.Security.Cryptography;

const int numberOfNumbersNeeded = 100;
const int numberOfBytesNeeded = 8;
var randomGen = RandomNumberGenerator.Create();
for (int i = 0; i < numberOfNumbersNeeded; ++i)
{
     var bytes = new Byte[numberOfBytesNeeded];
     randomGen.GetBytes(bytes);
}

Использование генератора криптографических чисел очень затруднит прогнозирование генерируемых вами строк, что, я полагаю, важно для вас.

Затем вы можете преобразовать 8-байтовое случайное число в строку, используя символы в вашем алфавите. Это в основном смена базового расчета (с базы 256 на базу 62).

Answer 3

Я не думаю, что сервисы сокращения URL используют хэши, я думаю, что у них просто есть бегущая буквенно-цифровая строка, которая увеличивается с каждым новым URL и сохраняется в базе данных. Если вам действительно нужно использовать хеш-функцию, посмотрите эту ссылку: некоторые хеш-функции Кроме того, немного оффтоп, но в зависимости от того, над чем вы работаете, это может быть интересно: Статья ужасов кодирования

Answer 4

Просто возьмите Base36 (без учета регистра) или Base64 идентификатора записи.

Итак, допустим, я хотел использовать Base36:

(ID - Base36)
1 - 1
2 - 2
3 - 3
10 - A
11 - B
12 - С
...
10000 - 7PS
22000 - GZ4
34000 - Q8C
...
1000000 - LFLS
2345000 - 1E9EW
6000000 - 3KLMO

Вы могли бы сохранить их еще короче, если бы использовали base64, но тогда URL-адреса будут чувствительны к регистру. Вы можете видеть, что вы все еще получаете свой красивый, аккуратный буквенно-цифровой ключ и с гарантией того, что столкновений не будет!

Answer 5

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

TinyURL.com , похоже, использует инкрементное число, которое преобразуется в База 36 (0-9, A-Z).

Answer 6

Сначала я получаю список случайных различных чисел. Затем я выбираю каждый char из базовой строки, добавляю и возвращаю результат. Я выбираю 5 символов, что составит 6471002 перестановок из базовой 62. Вторая часть - проверка по db, чтобы увидеть, существует ли какой-либо, если не сохранить короткий URL.

 const string BaseUrlChars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

 private static string ShortUrl
 {
     get
     {
         const int numberOfCharsToSelect = 5;
         int maxNumber = BaseUrlChars.Length;

         var rnd = new Random();
         var numList = new List<int>();

         for (int i = 0; i < numberOfCharsToSelect; i++)
             numList.Add(rnd.Next(maxNumber));

         return numList.Aggregate(string.Empty, (current, num) => current + BaseUrlChars.Substring(num, 1));
      } 
  }

Answer 7

Вы можете уменьшить количество символов в хеше MD5, кодируя их в виде буквенно-цифровых символов. Каждый символ MD5 обычно представлен в шестнадцатеричном формате, так что это 16 возможных значений. [a-zA-Z0-9] включает в себя 62 возможных значения, поэтому вы можете кодировать каждое значение, принимая 4 значения MD5.

EDIT:

вот функция, которая принимает число (длиной 4 шестнадцатеричных числа) и возвращает [0-9a-zA-Z]. Это должно дать вам представление о том, как это реализовать. Обратите внимание, что могут быть некоторые проблемы с типами; Я не проверял этот код.

char num2char( unsigned int x ){
    if( x < 26 ) return (char)('a' + (int)x);
    if( x < 52 ) return (char)('A' + (int)x - 26);
    if( x < 62 ) return (char)('0' + (int)x - 52);
    if( x == 62 ) return '0';
    if( x == 63 ) return '1';
}

Answer 8

Если вы ищете библиотеку, которая генерирует крошечные уникальные хэши из inters, я настоятельно рекомендую http://hashids.org/net/. Я использую ее во многих проектах, и она работает фантастически. Вы также можете указать свой собственный набор символов для пользовательских хешей.

Answer 9

Вы можете использовать CRC32, он имеет длину 8 байт и похож на MD5. Уникальные значения будут поддерживаться путем добавления метки времени к фактическому значению.

Так будет выглядеть http://foo.bar/abcdefg12.

Answer 10

Есть замечательная, но древняя программа под названием btoa, которая преобразует двоичный файл в ASCII, используя буквы верхнего и нижнего регистра, цифры и два дополнительных символа. Есть также кодировка MIME base64; большинство систем Linux, вероятно, имеют программу под названием base64 или base64encode. Любой из них даст вам короткую читаемую строку из 32-битного CRC.