Кто-нибудь понимает качество хэша? - PullRequest
2 голосов
/ 27 июля 2011

«Качество» хэша определяется как общее количество сравнений, необходимых для доступа к каждому элементу один раз, относительно ожидаемого числа, необходимого для случайного хэша.Значение может превышать 100%.

Общее количество сравнений равно сумме квадратов количества записей в каждом сегменте.Для случайного хэшаключи в "ведра, ожидаемое значение:

n + n ( n - 1 ) / 2 * k

Что такое качество хеш-функции?

1 Ответ

4 голосов
/ 27 июля 2011

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

Производительность хэша (в идеале просто поднимаясь вверх по корзине и просматривая отдельный элемент в ней) ухудшается, когда у вас есть ячейки со многими элементами в них: если это произойдет, вы должны линейно пройти все из них.

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...