Repository navigation
Bucket-based API for HashTable #613
Description
I want to propose the following API for HashTable. On OccupiedEntry I would like to add
/// Return in which bucket this entry is located.
///
/// Note: this index is not stable if the hash table is rehashed.
pub fn get_bucket(&self) -> usize;On HashTable itself I would like to add the following four functions:
/// Returns the bucket index an entry in the hash table is located at, or `None` otherwise.
///
/// Note: this index is not stable if the hash table is rehashed.
pub fn find_bucket(&self, hash: u64, eq: impl FnMut(&T) -> bool) -> Option<usize>;
/// Return a reference to the value located at `bucket_idx`, or `None` otherwise.
pub fn at_bucket(&self, bucket_idx: usize) -> Option<&T>;
/// Return an `OccupiedEntry` for the entry located at `bucket_idx`, or `None` otherwise.
pub fn at_bucket_mut(&mut self, bucket_idx: usize) -> Option<OccupiedEntry<T>>;
/// Returns the total number of buckets in this `HashTable`.
pub fn num_buckets(&self) -> usize;There are multiple reasons why I'd like this.
-
It allows incredibly flexible iteration over the hash table. I am aware that this iteration would be suboptimal compared to a SIMD-based iteration which checks the tags of 16 elements in one go, but the flexibility it provides is well worth it. For example: it makes parallel iteration over the hash table trivial, in whatever permutation you'd like.
-
It allows intrusive data structures to interweave with the hash table, so long as you are careful to avoid rehashing.
An example I ran into recently was the writing of a fixed-capacity LRU cache. When the LRU cache wants to evict the least recently used key it has to do a lookup for that key. It could instead simply store the bucket index and use that to directly remove the key, as the hash table never rehashes in this example.(This example did not in fact avoid rehashing, churn leads to rehashing, even with the same capacity.) -
It allows additional algorithms to run safely and soundly (e.g. no pointers into the hash table which requires unsafe code and which may or may not get invalidated with the latest flavor of stacked/tree borrows) while referring into the hash table. For example: sorting the keys of a hash table while not cloning the keys or taking them out of the table.
Activity
cuviper commentedon Mar 22, 2025
I think this would help indexmap's
OccupiedEntryas well, since a bucket index doesn't hold a lifetime. I could store a simpler(&mut IndexMapCore, usize)instead of needing separate references for my other fields. It would also remove the need for the awkwardhash_table::AbsentEntry, because I could just mapfind_entryto an index (i.e.find_bucket) to avoid the NLL limitations.moulins commentedon Mar 24, 2025
This assumes that deleting an element doesn't displace other elements, which is currently true but not technically guaranteed, as far as I can tell?
orlp commentedon Mar 24, 2025
I think that's correct.
cuviper commentedon Mar 24, 2025
In theory, insertions could displace existing items as well.
The standard library definitely shouldn't make any guarantees about this, but would it be so bad if
hashbrowndid?cuviper commentedon Apr 18, 2025
@Amanieu, any thoughts on this proposal?
cuviper commentedon Apr 18, 2025
This will also need a
hashto create anOccupiedEntry.(which only needs that for
remove() -> VacantEntryAFAICS)Maybe this should just return
Option<&mut T>, and a directremove_bucketmight be better for your LRU eviction?orlp commentedon Apr 18, 2025
@cuviper I no longer think this is applicable for LRU eviction. Any purpose where there is key churn will eventually result in rehashing, invalidating bucket indexes.
The iteration usecases are still valid though.
cuviper commentedon Apr 18, 2025
In
indexmap's case, I would also want a way to remove by bucket, but I do have the hash at hand too if needed.Amanieu commentedon Apr 20, 2025
My main concern with exposing such an API is that it forces additional constraints on the shape of the underlying data structure. Specifically:
usizeforces the table layout to be an open addressing table and excludes closed addressing tables based on linked-list. While I don't expect this to change, it is still a limitation on the table layout.In the end, the entire point of the hashbrown 0.15 release was to avoid exposing internal details so that we could modify the table internal more easily. This feels like a step backwards.
orlp commentedon Apr 20, 2025
Even the strictest policy that states any insertion/deletion may invalidate bucket indices would already be sufficient for custom iteration. Regarding the open addressing vs. closed addressing, I don't think that would ever change in the lifetime of
hashbrown, and even if it did I don't think it would be a problem to do a breaking release for it.cuviper commentedon Apr 23, 2025
That would also be fine for
indexmap's potential use.pervognsen commentedon May 23, 2025
Accessing slots by index would also allow an optimization I've used in the past in other contexts. An example: a handle is represented by a key and a speculative slot index. To look up the handle in the table you first try to probe the slot at the speculative index. If the probe fails, you do a normal lookup using the handle's key; afterwards you atomically replace the handle's slot index with wherever you found the key in the table. In addition to the more obvious benefits of avoiding the probe sequence most of the time, it lets you inline the speculative probe check while outlining the fallback lookup code. Also, SIMD-based hash tables generally sacrifice hole-in-one access latency, and this lets you use a lower latency scalar code path for the speculative probe check.
(I'm not saying Hashbrown should implement anything like this, but it's something user code can implement if you allow access by slot index. Invalidating slot indices on every insert/delete is not a correctness problem for this use case, but it would obviously degrade the performance of the speculation to the point where it wouldn't be worth it.)
Amanieu commentedon Oct 20, 2025
I've since changed my opinion and think that this API is most likely the best way forward since it also addresses a lot of a existing issues such as #420 and #382. I would be in favor of adding this API to
HashTable.cuviper commentedon Oct 20, 2025
Note that this one would also require a hash value, only because
OccupiedEntryneeds that forremove() -> VacantEntry. So it might still make sense to have a method that only returns&mut T, no hash necessary.(edit: and scrolling back, I see I already mentioned that, sorry!)
cuviper commentedon Oct 24, 2025
FYI, @moulins figured out the hash isn't needed in
OccupiedEntry: #657 (comment)