Зачем тут сдвиг влево (хеш)?

Question

[sddvxd]

Здравствуйте! Ниже представлена конструкция для построения хеша из строки, мне непонятно, зачем нужен сдвиг:

int hash = 0;
    char* string = "abc";
    const char* pchar = string;
    while(*pchar){
        hash <<= 1;
        hash ^= *pchar++;
    }

Есть догадки, что если бы не сдвиг, хеш получился бы не уникальным:

//Без сдвига
abc = 97, 98, 99
хеш = 0 XOR 97 = 97
хеш = 97 XOR 98 = 3
хеш = 3 XOR 99 = 96

//Со сдвигом
хеш = 0 XOR 97 = 97
хеш << 1 = 194
хеш = 194 XOR 98 = 160
хеш << 1 = 320
хеш = 320 XOR 99 = 291

со сдвигом число получилось больше и оно больше не встречается, если я введу другую строку, нежели со случаем без сдвига. может поэтому?

Answer 1

[longclaps]

Если ксорить чар и чар - выйдет чар.
Если вам достаточно 256 уникальных значений хэша - и так сойдёт.

Comments

[sddvxd]

выходит, сдвигая хеш влево, создается дополнительный разряд для 'унифицирования' строки?

[sddvxd]

да, действительно! если взять строку ab и ac то для первой хеш будет (97 << 1) xor 98 а для второй (97 << 1) xor 99, это значит будет всегда уникальное значение для разных строк!

[devalone]

sddvxd,

это значит будет всегда уникальное значение для разных строк

нет, коллизии по прежнему никуда не денутся,

[sddvxd]

devalone, а для случая с ASCII? если я только их использую, коллизий же не должно быть

[sddvxd]

devalone, или вы говорите про то, что длина символов сыграет свою роль, ведь int имеет 32 бита и рано или поздно будет потеря

[jcmvbkbc]

а для случая с ASCII? если я только их использую, коллизий же не должно быть
или вы говорите про то, что длина символов сыграет свою роль, ведь int имеет 32 бита и рано или поздно будет потеря

sddvxd, и без потерь будут коллизии: hash("$I2") == hash("0")

[devalone]

sddvxd, с ASCII тоже будут, невозможно множество строк различной длины превратить в множество строк фиксированной длины без коллизий.

[sddvxd]

jcmvbkbc, а, вы воспользовались хитростью, ведь символ 'I' имеет число длиной на 1 бит больше, чем у '$' и так сошлось, что (I << 1) xor $ = 1. не подскажите, как вы такое нашли? каждый символ считали?

[jcmvbkbc]

и так сошлось

lol

не подскажете, как вы такое нашли? каждый символ считали?

sddvxd, что там считать-то, особенно с ascii-таблицей под рукой.