improving perfect #hashing #algorithms
on 02025-11-11perfect #hashing
on 02025-10-24linear-probing #hashing that tries to keep probe sequences short by fancy insertion? #performance #algorithms #toread
on 02025-09-11#ByteDance proposed that #Golang use #Swiss-Tables for #hashing, apparently accepted in Go 1.24
on 02025-09-07“We are extremely pleased to announce the availability of the new “Swiss Table” family of hashtables in Abseil and the absl::Hash #hashing framework that allows easy extensibility for user defined types. Last year at CppCon, We presented a talk on a new hashtable that we were rolling out across #Google’s codebase.” #C++ #Swiss-tables #performance
on 02025-09-07#video of a talk by Kulukundis at cppcon 2017. Kip says, “Presentation about the latest tricks in hash tables. Uses SSE instructions and man is it fast. Good benchmarks against the standard C routines.” Heh: “As with anything like this, benchmarks are the only source of truth you will ever get, and they are lies.” Called "Swiss tables" (because Alkis and Roman, its primary developers, “are in the Zurich office”, and it’s “closed hashing”), supposedly the fastest hash table in the world. “What did we gain? (...) the vague feeling of superiority when we force a difficult decision onto the user. And that is the #C++ way.” You put metadata about which array elements are full or deleted into a separate byte array, along with truncated-to-7-bits hash values, to avoid needing magic sentinel values for your key type. By using SSE matching to look for truncated-hash matches in a 16-bucket group, you can find the candidates in three instructions, which also means that your erase function can avoid inserting tombstones “if any other element in the group was empty”, which seems like a pretty big win actually. Also he mentions “other sizes [than power of 2] with fast modulus”. #algorithms #performance #hashing
on 02025-09-06#Hashing #algorithms in the CPython dict implementation; by adding a level of indirection to the (hashval, key, value) tuples, you can greatly reduce the amount of space used, thus improving #performance. As a side effect, you can iterate over entries in insertion order.
on 02024-08-31a comparison of #hashing #algorithms #performance in 02012
on 02024-08-20discussion from 01991 of #hashing #algorithms on comp.lang.c between Henry Spencer (who says C News could just as well have used strlen() like PHP later did), Chris Torek, Dan Bernstein, Dave Harris, Richard Harter, Rich Salz, Phong Vo, et al. Title “hash function for mac needed”.
on 02024-08-20The so-called "djb2" hash function is indeed by Dan Bernstein, but it’s from 01991: hash = 5381; while ((c = *s++)) h = (h << 5) + h + c; #hashing #algorithms
custom hash tables can have #performance an order of magnitude better than generic ones, as Chris #Wellons demonstrates here #hashing in Golang
on 02023-07-05“Linear Probing Revisited: Tombstones Mark the Death of Primary Clustering, by Michael A. Bender, Bradley C. Kuszmaul, and William Kuszmaul” #PDF #paper on #hashing #algorithms #performance with "graveyard hashing"
on 02023-07-03building a hash table in MIDAS #asm #macros for PDP-6 Lisp. #retrocomputing #hashing
on 02023-07-02where Rasmus confesses that in 1994 PHP used strlen() as its hash function for function names :) #hashing #algorithms
on 02020-10-10#hashing #source-code for the identityHashCode function has several possible methods for hashing, some of which use the object’s current address. Since Java uses a copying collector, it then has to save the hash value into the object’s header so that it won’t change when the object is moved.
on 02016-08-03The #source-code of #Java HashMap, used for most #hashing in Java; now uses tree bins instead of randomization to prevent #HashDoS #security problems
on 02016-08-03the proposal to mitigate #security DoS problems (#HashDoS: deliberate hash collisions, Crosby and Wallach 2003) in #Java 7 by giving String a new randomized hash32 method for and #hashing with it in all the built-in hash tables
on 02016-08-03