7

I'm re-implementing a hashtable in Rust. Eventually I'd like to make this distributed and have quorums, but for now it's a hashtable on a single system.

I want the size of the table to be passed in as an argument so the table should be dynamically sized. I don't want the table to grow because that will mess with my hash function which works off a modulo operation. I see a couple of options:

  1. Arrays - cannot be dynamically sized
  2. Vectors - can grow
  3. Slices - can be dynamically sized & can't grow, but are just views onto Vecs and arrays, so I'll need a Vec/array anyways?

In C++, I could have just used a dynamically sized array. What's the best choice here?

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
etk1220
  • 197
  • 4
  • 9
  • 2
    `vec![0; n].into_boxed_slice();`? https://www.reddit.com/r/rust/comments/3gp0tl/dynamic_fixed_sized_arrays/ – Andriy Tylychko Jul 28 '17 at 17:04
  • btw, if you don't want vector to grow, why not to not grow it? I suppose your users don't have access to it. also, there's a possibility you'll reconsider this later, I'm really curious what that "not ever growable" vector inside a hashtable stores – Andriy Tylychko Jul 28 '17 at 17:25
  • I could make my own protections, but I thought it would be nice to use a collection that met my requirements if it existed. – etk1220 Jul 28 '17 at 18:42
  • What do you call "dynamically sized array" in C++ by the way? – mcarton Jul 28 '17 at 20:25
  • https://crates.io/keywords/array offers several that appear to match your description, have you tried any? – the8472 Jul 29 '17 at 10:04
  • @mcarton `auto array = new type[dimension]` for example – Boiethios Jul 31 '17 at 07:35
  • @Boiethios that's not idiomatic C++. People have been using RAII for a long time now, and there are no standard RAII wrappers for such arrays that are aware of the array size. – mcarton Jul 31 '17 at 08:31
  • @mcarton I agree, but that is yet C++. Obviously, OP wrote about that, RAII or not. – Boiethios Jul 31 '17 at 08:43

1 Answers1

13

A boxed slice is dynamically sized, the length cannot be changed once created, and it owns the contained data:

let the_vec: Vec<i32> = vec![1, 2, 3];
let the_boxed_slice: Box<[i32]> = the_vec.into_boxed_slice();

The types aren't required here, they are just present for pedagogical reasons.

However, it's dubious whether you will get any performance benefit. A Vec is three pointer sized values (data, size, capacity). A Box<[T]> is only two: data and size. The overhead of having the extra value is minuscule in most cases.

The main benefit is to be statically guaranteed that the size won't change; you won't statically know that it's a certain size. Such a guarantee might happen if type-level numbers ever happen.

See also:

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
  • There's a lot to be said for having the structure that is guaranteed not to change size. So much that it won't fit into the size of the margin here. – WeakPointer Oct 28 '22 at 19:57