хэш для интов это id

реаллокаций нет

это буквально посмотреть на каждый 1 раз и засунуть в нужный бакет

А бакеты?

предполагается что ты сразу сделал хэшсет нужного размера

О, опять.
А какие бакеты в растовом хешсете?

Это с хешером из FxHashSet. С id хэшером (hashers::null::PassThroughHasher), почему-то намного хуже.

Код функций

fn sort_dedup<T: Ord + Eq>(vs: &mut Vec<T>) {
    vs.sort_unstable();
    vs.dedup();
}

fn hashmap_dedup<T: std::hash::Hash + Eq>(vs: &mut Vec<T>) {
    let set: FxHashSet<_> = vs.drain(..).collect();
    vs.extend(set.into_iter());
}

fn sort_dedup<T: Ord + Eq>(vs: mut Vec<T>) -> impl Iterator {
    vs.sort_unstable();
    vs.dedup();
    vs
}

fn hashmap_dedup<T: std::hash::Hash + Eq>(vs: &[T]) -> impl Iterator {
    let set = HashSet::with_capacity(vs.len());
    set.extend(vs);
    set
}

я

думал скорее что-то такое

``` /// Non-generic part of RawTable which allows functions to be instantiated only once regardless
/// of how many different key-value types are used.
struct RawTableInner<A> {
   // Mask to get an index from a hash value. The value is one less than the
   // number of buckets in the table.
   bucket_mask: usize,

   // [Padding], T1, T2, ..., Tlast, C1, C2, ...
   //                                ^ points here
   ctrl: NonNull<u8>,

   // Number of elements that can be inserted before we need to grow the table
   growth_left: usize,

   // Number of elements in the table, only really used by len()
   items: usize,

   alloc: A,
} ```

Ну какие-то видать есть

А как

Ну я просто не понимаю терминологию (и алгоритмы, видимо), пытаюсь разобраться.

Для меня бакет в хеш таблице — элемент у array, куда мы сваливаемся, вычисляя оффсет от хеша элемента хеш таблицы.
В этом бакете — LinkedList/BinaryTree с элементами, для которых сие смещение одинаково.

А в Расте же swiss table, просто длиннющий массив, в котором пары ключ-значение и никаких листов/деревьев нет: для поиска элементов вычисляется range по хешу, а не один оффсет.

Тогда там не надо дофига памяти сразу аллокнуть?

С виду, наоборот, всего один кусок непрерывно в памяти держать, а не кучу ссылок на ноды и врапперы, как в линкедлистах всяких.

Как вставить в середину?

по идее там сквозная адресация: вычислили хэш а потом имщем ближайший свободный от него

И при реаллоке что делать?

то же что и всегда - то же самое что при вставке)

shift элементов массива же

Жестоко. Сет на чтение быстрый, а на запись не оч?

я может чего-то не знаю про хэшсеты растовыЕ, но по идее там не так уж все дорого. У сэта нет никакой "середины"