Deduplicating a Slice in Go

• unique

  1 22 10.0 Go

  Package unique provides primitives for finding unique elements of types that implement sort.Interface. (by mpvl)

• Folly

  90 27,072 9.8 C++

  An open-source C++ library developed and used at Facebook.

  

Most modern hash map designs don't do this weird shuffle with buckets and linked lists because pointer chasing is super expensive.

https://doc.rust-lang.org/std/collections/struct.HashMap.htm...

Because it's documenting the actual API in the standard this even spells out that the result has "at least the specified capacity"

https://github.com/facebook/folly/blob/main/folly/container/...

F14 is a linear map but I couldn't immediately find actual API documentation, however it should have the same property where if you ask for an F14 with specific capacity or you reserve enough capacity, that's an "at least" promise not an approximate one.

• WorkOS

  workos.com sponsored

  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.

  

• hashbrown

  22 2,261 8.2 Rust

  Rust port of Google's SwissTable hash map

  

I believe Rust uses hashbrown as the underlying implementation now. This just calculates the number of buckets based on the number of items requested:

https://github.com/rust-lang/hashbrown/blob/009969a860290849...

Is it really the case that rehashing can guarantee that the number of buckets allocated will be sufficient for any given set of keys? In principle you could fail to rehash in a way that reduces collisions after k attempted rehashings.

Suggest a related project