Comments (3)
While looking for a fast hash designed for 64-bit integer data, I stumbled across Thomas Wang's hash.
Thomas Wang's hash for 64-bit integers
uint64_t hash(uint64_t key) {
key = (~key) + (key << 21); // key = (key << 21) - key - 1;
key = key ^ (key >> 24);
key = (key + (key << 3)) + (key << 8); // key * 265
key = key ^ (key >> 14);
key = (key + (key << 2)) + (key << 4); // key * 21
key = key ^ (key >> 28);
key = key + (key << 31);
return key;
}
from atree.
Using a non-compatible 8-byte input hasher can increase hash collisions with other input sizes.
There's no need to use a non-compatible 8-byte input hasher if we use a fast non-crypto hash for level 1.
On Intel Haswell CPUs with Go 1.16, my CircleHash functions (which pass Strict Avalanche Criterion, Bit Independence Criterion, and etc.) are able to perform faster than one call to the assignment:
foo := uint64_a % uint64_b // slower than fast non-crypto hash function that passes SMHasher
I just need to write the README explaining why it should be used instead of current non-crypto fast hashes, add more tests, etc. before making it public (maybe this weekend).
from atree.
This issue is closed by PR #145. CircleHash64 is faster than foo = uint64_a % uint64_b
on Haswell CPU and within about 1 ns per hash on newer Intel CPU models (around 3.5 ns/op for short inputs).
CircleHash64 is currently written to be an easy-to-audit reference, so there's room for optimization if it becomes a bottleneck.
from atree.
Related Issues (20)
- Enable additional lint checkers in golangci-lint
- Update README to center the logo and badges
- Bump golangci-lint to 1.43.0
- Specify seed for prng when generating code coverage report
- Add Array.IterateRange and Array.RangeIterator for range iteration
- Fix handling of edge case involving error that can cause a "send on closed channel" panic
- Upgrade or replace BLAKE3 package which is returning nonstandard BlockSize() HOT 1
- Update to latest version of CircleHash64 for faster speed HOT 1
- Add regression test for CircleHash64 to detect breaking changes after updates
- Add regression test for BLAKE3 to detect breaking changes after updates
- Update CBOR and CircleHash libraries to latest versions
- Bump BLAKE3 to v0.2.3
- Question about design considerations HOT 8
- Change digest level from int to uint
- Add extra comment for typicalRandomConstant (NCC-E003763-27A)
- Update CI workflows to remove default permissions at top level, add workflow_dispatch, bump versions, etc.
- Provide exported function to return number of uncommitted slabs
- Goroutine creation in FastCommit() HOT 3
- Enable extra linters and resolve reported issues
- Refactor error handling to user, fatal, and external errors
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from atree.