sunnygleason / g414-hash Goto Github PK
View Code? Open in Web Editor NEWCollection of useful 64-bit hash utilities including Bloom filter and HashFile (64-bit CDB clone) implementation
Collection of useful 64-bit hash utilities including Bloom filter and HashFile (64-bit CDB clone) implementation
Hi,
It seems that the size of HashFile2s is limited by Integer.MAX_VALUE --
/**
* Advances the file pointer by <code>count</code> bytes, throwing an
* exception if the postion has exhausted a long (hopefully not likely).
*/
private static long advanceBytes(long pos, long count, boolean isLongPos)
throws IOException {
long newpos = pos + count;
if (newpos < count || newpos > Integer.MAX_VALUE)
throw new IOException("HashFile is too big.");
return newpos;
}
All of the arguments are lovingly created as longs, but if the position ever grows past Integer.MAX_VALUE (which is only ~2GB) then a "HashFile too big" exception is thrown.
when size is too big, lose track of elements. possible signed/unsigned issue
There are couple of places where Strings are converted to byte[] without specifying encoding.
This is risky, since default is to use platform-specific default encoding, which varies from system to system (typically it's either Latin-1 or UTF-8; nowadays more commonly UTF-8).
It would probably make most sense to just use UTF-8; if caller wants other encoding, she can just get bytes explicitly, calc hash on byte array.
Suggested by the illustrious David Stryker -- I think it's a fine idea
from jfarcand ...
Given that time to produce 64-bit hashes is probably not much less than equivalent for producing 2 32-int hashes, it would be useful to also have 32-bit versions. Specific use case is that of building Bloom filters, where number of bits needed is variable; so when, say, 80 bits are needed (8 hash functions over 1024 bit mask), it would be enough to calculate 3 32-bit hashes instead of 2 64-bit hashes.
brianm@ rightly states that union is a funky name for that method...
Hi again,
I've come to bother you with what I presume is another bug :-)
https://github.com/stevenschlansker/g414-stress-test
I did not submit this one as a patch since the test dataset is 15MB compressed, feel free to take any or all of the repo that you like and use it as you please (including integrating it into the core if you think it is a good regression test)
Short version:
For 600K keys, the HashFile contains some data that cannot be fetched yet shows up via the iterator. About 40k keys are affected with the test data set.
I've included a bonus test showing that HashFile2 does not have this problem.
The test data is a scrubbed version of my production data, which is how I noticed this problem.
Should this be k.length instead of k.length<<2?
https://github.com/sunnygleason/g414-hash/blob/master/src/main/java/com/g414/hash/impl/JenkinsHash.java#L243
Should k.length be added to c here?
https://github.com/sunnygleason/g414-hash/blob/master/src/main/java/com/g414/hash/impl/JenkinsHash.java#L268
From Tatu...
tatu: instead of getBytes() ; latter uses whatever platform default is, which is system-dependant
[6:04pm] tatu: could also use ISO-8859-1 or such. but utf-8 is probably better. or utf-16
[6:04pm] tatu: also I think it'd be good to expose variant that takes byte[]... or maybe super-class has that?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.