4 ms·

Plus you're just testing the standard library implementations. If the hash lookup was the major focus for your program, you would be using a specialized hash ma

by RyanZAG 13y ago

Plus you're just testing the standard library implementations. If the hash lookup was the major focus for your program, you would be using a specialized hash map implementation. eg, http://trove.starlight-systems.com/ http://trove.starlight-systems.com/ or http://acs.lbl.gov/software/colt/ http://acs.lbl.gov/software/colt/ in the case of the Java version. EDIT: Here is the kind of performance differences you get between hash implementations to demonstrate why you wouldn't just use the standard implementations if it's a performance critical part: http://b010.blogspot.com/2009/05/speed-comparison-of-1-javas-built-in.html http://b010.blogspot.com/2009/05/speed-comparison-of-1-javas... Shows Colt int map running 3.5x faster and with 65% of the ram usage as the standard hashmap.

plorkyeran 13y ago
And for C++, http://bannalia.blogspot.com/2014/01/a-better-hash-table-gcc.html http://bannalia.blogspot.com/2014/01/a-better-hash-table-gcc... shows significant differences between 3 different implementations of the same API (and which one is fastest varies between operations, as they're optimized for different things).
JoshTriplett 13y ago
> Plus you're just testing the standard library implementations. If the hash lookup was the major focus for your program, you would be using a specialized hash map implementation. If there's a better general-purpose hash table, the standard library hash should be using it. (Special-purpose, sure, use a custom data structure.)
- RyanZAG 13y ago
  In the case of Java, there is a lot of inefficiency in the standard hash table in the form of Entry<T, K> objects for making it a bit nicer to use. There is also a lot of extra state stored for some of the extra features offered. Everything has a cost. If you just need a straight Int->Int or Int->Object map, there are a lot of ways to make it far more efficient. The standard library doesn't contain these, because in 99% of apps, the actual performance of the hash table is a very minor part and a small bit of overhead for added convenience is worth it. However in a program where the hashmap is the key point, you'd obviously choose to optimize it to fit your goals.
lonewolfer 13y ago
Not true here: http://savedbythegoog.appspot.com/?id=e7d8313105c90e105dbbf2a1f230b65ce511bcaf http://savedbythegoog.appspot.com/?id=e7d8313105c90e105dbbf2...

by RyanZAG 13y ago

plorkyeran 13y ago

And for C++, http://bannalia.blogspot.com/2014/01/a-better-hash-table-gcc.html http://bannalia.blogspot.com/2014/01/a-better-hash-table-gcc... shows significant differences between 3 different implementations of the same API (and which one is fastest varies between operations, as they're optimized for different things).

JoshTriplett 13y ago

> Plus you're just testing the standard library implementations. If the hash lookup was the major focus for your program, you would be using a specialized hash map implementation. If there's a better general-purpose hash table, the standard library hash should be using it. (Special-purpose, sure, use a custom data structure.)

RyanZAG 13y ago
In the case of Java, there is a lot of inefficiency in the standard hash table in the form of Entry<T, K> objects for making it a bit nicer to use. There is also a lot of extra state stored for some of the extra features offered. Everything has a cost. If you just need a straight Int->Int or Int->Object map, there are a lot of ways to make it far more efficient. The standard library doesn't contain these, because in 99% of apps, the actual performance of the hash table is a very minor part and a small bit of overhead for added convenience is worth it. However in a program where the hashmap is the key point, you'd obviously choose to optimize it to fit your goals.

lonewolfer 13y ago

Not true here: http://savedbythegoog.appspot.com/?id=e7d8313105c90e105dbbf2a1f230b65ce511bcaf http://savedbythegoog.appspot.com/?id=e7d8313105c90e105dbbf2...