Является ли эта функция хэшей уникальной?

Будет ли следующий сгенерированный хеш всегда отличаться для разных ключей, если предположить, что целое число хешей никогда не переполняется? Ключ должен содержать символы, кодированные ascii.Является ли эта функция хэшей уникальной?

Я думаю, что это так, поскольку я не могу придумать исключительный случай.

char[] arr = "abcd" 
int hash = 0 
for (int i=0; i<arr.size; i++) { 
    hash += (i+1) * arr[i] 
}

EDIT1: Хотя нижеследующее технически правильные ответы на мой первоначальный вопрос, я должен отметить, что область ключей является то, что действительных почтовых идентификаторов. Таким образом, некоторые символы ascii не включены. Тем не менее, я проведу несколько тестов и отчитаюсь. Единственная проблема - перечислить все perms возможно только до небольшой длины.

В любом случае, мое требование состоит в том, чтобы создавать уникальные идентификаторы на основе идентификаторов электронной почты и использовать их в качестве первичных ключей в db. Просто не хотите использовать сами идентификаторы почты.

EDIT2: Хорошо, видимо, есть множество столкновений. для например, хэш [email protected] == хэш [email protected]

... 
040 == 012 
041 == 013 
042 == 014 
043 == 015 
044 == 016 
045 == 017 
046 == 018 
047 == 019 
048 == 01: 
...

мне нужен другой алгоритм хэширования. Можете ли вы предложить какие-либо?

источник

2016-08-04 DebD

«Будет ли следующий сгенерированный хэш всегда отличаться для разных клавиш?» По определению «хэш-функция» ответ «нет». Если ответ «да» - не называйте его хэш-функцией. –

вы занимаете большое пространство значений и «сжимаете» его на меньшее пространство. по определению там должно быть не менее 2 входных значений, которые отображаются на один и тот же вывод. –

Должно быть хотя бы одно столкновение – xdevs23

No: 1 * 2 + 2 * 2 = 1 * 4 + 2 * 1 например.

(char[] arr = {'\u0002','\u0002'} и char[] arr = {'\u0004','\u0001'})

источник

2016-08-04 15:26:15

Эти две строки будут генерировать одинаковые хэши:

"~ " 
"@?"

выше полностью состоят из печатаемых символов ASCII.

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

char key[5] = {0}; 
bool used[65536] = {0}; 
for (key[0] = " "; key[0] < 128; key[0]++) 
    for (key[1] = " "; key[1] < 128; key[1]++) { 
     if (used[hashcode(key)]) { 
      printf("failed %s", key); 
     else 
      used[hashcode(key) = true; 
     }

источник

2016-08-04 15:33:31

Два значения, упомянутые вами, производят 190 и 253 соответственно. – DebD

К сожалению, извините @DebD.Я думаю, что это должно быть –

Хороший улов, @DebD. Мой плохой для того, чтобы не проверять таблицу ASCII внимательно, прежде чем вводить текст, должен был прочитать восьмеричную ценность или что-то еще. Я попытаюсь исправить второй, чтобы «@?» вместо ошибочного "{A" –

Отвечая на ваш дополнительный вопрос в вашем редактировать о стремлении улучшить свой хэш-функцию, небольшое изменение, которое вы могли бы сделать было бы умножить каждый символ простого числа перед добавлением к общей сумме. Это не гарантирует никаких столкновений, но должно сократить их, так как каждый новый термин, который вы добавите, будет разнесен больше и будет кратным простому. Я бы пропустил первые несколько простых чисел, чтобы получить лучший интервал, поэтому, возможно, умножьте первый символ на 11, второй на 13, третий на 17, на 4 на 19 и так далее. Если ваши строки не слишком длинны, вам не понадобится очень большая таблица простых чисел.

Если вы действительно хотели получить фантазию, вы могли бы изучить создание CRC или использовать метод регистрового сдвига с линейной обратной связью для генерации подписи. В последнем случае вы должны XOR новый символ (или выбранные биты нового символа) в самые младшие 8 бит общего числа, а затем поверните всю сумму на несколько бит.

источник

2016-08-05 04:09:11

Является ли эта функция хэшей уникальной?

ответ

Смежные вопросы