math - Why using powers of 2 as the hash size makes a hash table considerably worse than using primes? -



math - Why using powers of 2 as the hash size makes a hash table considerably worse than using primes? -

i'm implementing hash table supposed store pairs of 32-bit values. considering elements fixed size, i'm using simple hashing function:

hash(a,b) = asuint64(a) + (asuint64(b) << 32)

with that, index of element in hash table (that is, corresponding bucket) with:

index(a,b) = hash(a,b) % hash_size

where hash_size number of entries/buckets on table. i've realized, though, speed implementation little bit if replaced "modulus" operator bitwise mod of 2, fixing hash_size powerfulness of 2. except, when that, of pairs end on first bucket! why happening?

my guess info not evenly distributed in a. consider concatenation of a , b hash code:

b31b30...b1b0a31a30...a1a0, ai, bi ith bit of a,b

suppose have table 1000000 entries, hash index

a9a8...a1a0 (as integer)

worse, suppose a ever ranges 1 100. have less dependence on higher order bits of a.

as can see, if hash table doesn't have @ to the lowest degree 4 billion entries, hashcode has no dependence on b @ all, , hash(x, a) collide x.

math hash language-agnostic hashtable bit-manipulation

Comments

Post a Comment

Popular posts from this blog

java Multi query from Mysql using netbeans -

java Multi query from Mysql using netbeans - i have java code retrieve info mysql appropriate code in netbeans.the code below. want multi query such illustration finding total number of products , on.could help me please. in advance import java.sql.*; public class javamysqlselectexample { public static void main(string[] args) { seek { string mydriver = "com.mysql.jdbc.driver"; string myurl = "jdbc:mysql://localhost/sample"; class.forname(mydriver); connection conn = drivermanager.getconnection(myurl, "root", "mypasscode1"); string query = "select * products"; statement st = conn.createstatement(); resultset rs = st.executequery(query); while (rs.next()==true) { int code = rs.getint("code"); string productname = rs.getstring("product_name"); string producttype = rs.getstring("product_type"); system.out.format(" %d, %s, %s\n", code, pr
Read more

c# - DotNetZip fails with "stream does not support seek operations" -

c# - DotNetZip fails with "stream does not support seek operations" - i using dotnetzip in c# unzip stream follows: public static void unzipfromstream(stream stream, string outdir) { //omit seek grab block using (zipfile zip = zipfile.read(stream)){ foreach (zipentry e in zip){ e.extract(outdir, extractexistingfileaction.overwritesilently); } } } stream obtained using webclient client = new webclient(); stream fs = client.openread(url); however, got next exception exception during extracting zip stream system.notsupportedexception: stream not back upwards seek operations. @ system.net.connectstream.get_position() @ ionic.zip.zipfile.read(stream zipstream, textwriter statusmessagewriter, encoding encoding, eventhandler`1 readprogress) on server side(asp.net mvc 4), returning filepathresult or filestreamresult both caused exception. should obtain stream differently on client side? or how create server homec
Read more

c++ - StartServiceCtrlDispatcher don't can access 1063 error -

c++ - StartServiceCtrlDispatcher don't can access 1063 error - i write on c++ service , have error, , don't can fixed it. my service main function int main (int argc, tchar *argv[]) {dword f; for(int i=0;i<113;i++) f = getlasterror(); servicepath = lptstr(argv[0]); outputdebugstring(_t("my sample service: main: entry")); //installservice(); service_table_entry servicetable[] = { {service_name, (lpservice_main_function) servicemain}, {null, null} }; // startservice(); if(!startservicectrldispatcher(servicetable)) { f = getlasterror(); //addlogmessage("error: startservicectrldispatcher"); } else if( memcmp(argv[argc-1],"install",7)) { installservice(); } else if( memcmp(argv[argc-1],"remove",6)) { removeservice(); } else if( memcmp(argv[argc-1],"start",5)) { startservice(); } else if( memcmp(argv[argc-1],"stop",4))
Read more