All geek questions in one place

Perfect hash functions

Recently, I was given homework in which they asked if there is a list of keys, whether it is possible to make a hash function that does not have any collisions. After some research, I found out that given a pre-ordered list of keys, perfect hash functions are possible.

However, I'm not quite sure what to say next. Can someone give me some tips on how perfect hash functions are, or what exactly gives a predefined list for a hash function creator that allows an excellent function?

Thanks for any help.

+6
source share
1 answer

The only way to avoid collisions is to have a 1 to 1 relationship between the key and the hash value. The hash value range must be at least equal to the number of keys, and the mapping function must convert each key to a unique value. Much more information here: http://en.wikipedia.org/wiki/Perfect_hash

+8
source

Source: https://habr.com/ru/post/902156/

More articles:


All Articles