Extend HashTable's bucket API to support insertion ?

[eggyal]

When one wishes to "get or insert" from/into a HashTable that is behind a RwLock, one typically first attempts to "get" with only a read lock (via the .find API), and only if that fails fallback to a "get or insert" with a write lock (via the .entry API).

However, the .entry call repeats the probing that was undertaken during the .find call: this is necessary because the table could have been modified between release of the read lock and acquisition of the write lock.

But in some cases, one might be able to determine whether the table was modified in the interim and thus avoid such duplicate probing. For example, if the table is append-only and its length has not changed.

The new bucket API almost exposes such an ability, but not quite. Is there any interest it being extended to support this use case, or is this perhaps too niche for hashbrown?

[clarfonthey]

The problem with making an "extend-only" table is that you need to rehash and move everything around once the table gets larger. You could try and plan for this in advance by allocating a very large table, but even this has its limits.

I'm not 100% sure it would be possible to actively reserve spots in the table reliably in these cases without at least atomics and I'm not sure that hashbrown necessarily is going to be the place for it.

[eggyal]

Can't the probe result of a .find type call later be passed into an .entry type call to avoid duplicate probing (assuming the user asserts the table has not been mutated in the interim - hence no reallocation/rehashing has occurred)?

[cuviper]

We could support this via VacantEntry, since that already has a reserved insertion index. Safe insertion is then easy enough, as we would just need to validate that the given index is in range and not already full. However, it's still a logic hazard if you insert a hash that's mismatched for that probe location, like I mentioned in #657 (comment).

Possible usage example:

let index = match table.entry(hash, eq, hasher) {
    Occupied(entry) => return (...),
    Vacant(entry) => entry.bucket_index(), // self.index
}
// ... time passes without mutation
table.insert_entry(hash, index, value);

[cuviper]

OTOH, if you want an immutable &self lookup first, it would have to allow the possibility that there is no available insertion index.

[eggyal]

OTOH, if you want an immutable &self lookup first, it would have to allow the possibility that there is no available insertion index.

In my case I can guarantee available capacity by always reserving extra space after insertion; but yeah, I appreciate that a lack of available insertion index would necessitate reallocation and fresh probing.