Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve perfect hashing #62

Closed
tdewolff opened this issue Jul 16, 2020 · 1 comment
Closed

Improve perfect hashing #62

tdewolff opened this issue Jul 16, 2020 · 1 comment

Comments

@tdewolff
Copy link
Owner

Quickly map []byte to numbers from 0 to N, for a pre-defined set of N strings. Make []byte => Hash fast. Move the Hasher code into this repository.

Hash the []byte, check if it is lower than N, if so verify that it is the same string using bytes.Equal. The latter could be skipped if we are sure there are no collisions below a certain length of input bytes (can we optimize the search for hash seeds for this?).

Promising hash functions are https://github.com/dgryski/go-metro, https://github.com/dgryski/go-farm, and https://github.com/cespare/xxhash. Especially farm seems to be fast for short strings (len < 50).

See http://aras-p.info/blog/2016/08/09/More-Hash-Function-Tests/ for comparisons.

@tdewolff
Copy link
Owner Author

Moved to tdewolff/minify#411

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant