Our great sponsors
-
-
WorkOS
The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.
-
Lua
Lua is a powerful, efficient, lightweight, embeddable scripting language. It supports procedural programming, object-oriented programming, functional programming, data-driven programming, and data description.
-
Note that if you have untrusted input, you may want to use a defensive option for hashing involving a private key, such as SipHash[1]. Otherwise, an attacker who knows your hash functions can just pre-generate a large number of colliding elements and reduce your hash function to a linked list; given enough attacker-controlled elements, this can effectively amount to a DoS attack[2].
[1] https://github.com/veorq/SipHash
[2] https://www.aumasson.jp/siphash/siphashdos_29c3_slides.pdf
Lua uses "chained scatter" (linked list, but links point to other entries in the same table, to maintain locality): https://github.com/lua/lua/blob/master/ltable.c
This is a good visual depiction of chained scatter: https://book.huihoo.com/data-structures-and-algorithms-with-...
Inspired by Lua, I did the same for upb (https://github.com/protocolbuffers/upb). I recently benchmarked upb's table vs SwissTable for a string-keyed table and found I was beating it in both insert and lookup (in insert upb is beating SwissTable by 2x).
Lua uses "chained scatter" (linked list, but links point to other entries in the same table, to maintain locality): https://github.com/lua/lua/blob/master/ltable.c
This is a good visual depiction of chained scatter: https://book.huihoo.com/data-structures-and-algorithms-with-...
Inspired by Lua, I did the same for upb (https://github.com/protocolbuffers/upb). I recently benchmarked upb's table vs SwissTable for a string-keyed table and found I was beating it in both insert and lookup (in insert upb is beating SwissTable by 2x).