String hash

[arumad]

вкотре пролунало питання чому String використовує множення на 31, коли сумує hash.

інет не поможе:
- більшість пишуть просто про hash,
- хтось констатує що таки 31
- Блох некритично помиляється
- StackOverflow бреше, бо це попсовий ресурс, що вірить інету.

тому викладаю посилання на правду, аби воно піднялося (:
How the String hash function works (1) (2)

Comments

[perepertoz]

а всё потому, что этот бит - это разница между большой и малой английскими буквами в ASCII ;)

[tasmanj]

любопытно. да и вообще - интересный сайт, надо глянуть, спасибо.
пиши ещё :)

насчёт StackOverflow

[tasmanj]

гр**ный жж.

насчёт StackOverflow: как и на любом сайт с генерёным юзверями контентом, к этому контенту надо относится с подозрением. но там, судя по всему, сидит много адекватных людей

[arumad]

що писати ще?
про "прості числа яких ми не розуміємо"?
да ви батєнька ізвращєнєц.
чи я.

хочеш зламати мозок -
зрозумій, чому trove використовує rehash по простим числам.
(це PrimeFinder.nextPrime та його виклик з THash)
хоча тобі може це й не грозить - ти ж в алгоритмах шариш, писав олімпійські задачки..
тоді мені поясни, на пальцях :)
що висока вірогідність попасти в той самий букет при фіговому хеші - розумію,
що вона падає при діленні на просте - теж,
і чому вибирають не всі прості;
але не розумію, чому має бути прив'язка до ступенів двійки,
і як їх формують у десять-одинадцять кусків.