#Feedback on extremely simple HashTable implementation

20 messages · Page 1 of 1 (latest)

coral vessel
#

Feedback on extremely simple HashTable implementation

dull remnant
#

by coincidence I shared my own hashmap implementation here a few days ago
#rust-help-2 message

#

@coral vessel what you have implemented is not a hashmap but rather a hashset since there is no method insert(key, value)

#

similarly you don't have a get(key)

#

But my suggestions are:

  1. I would recommend separating Hash into its own trait since it makes it easier to implement it for various types
  2. Add a way for the table to grow if it gets full
  3. Make it generic for any types rather than only u32
  4. search() should return an Option instead of a Result
  5. remove() shouldn't error if there's no value, it would make more sense if it just did nothing (since the value has already been removed)
  6. Your size value is kind of redundant since it seems to just be the same as table.len()
dull remnant
#

So in many implementations, the data is stored in an array of a particular length, and when the number of items reaches a certain amount (when the array is 75% full, for example) you move the items to a new array which is twice as long

paper fjord
#

I would expect a behaviour of

let mut table = HashTable::<3>::new();
table.add(10);
table.get(10); // Some
table.remove(10); // What I put in
table.get(10); // None

But the remove method will remove the 10th element and is not guaranteed to remove the 10 put in

dull remnant
#

yeah it's the same idea

#

if you want an educational experience try implementing Vector in C

#

well, in Rust it's tougher since you're not "supposed" to be managing memory yourself (hence unsafe)

#

C is actually really simple and can help you understand Rust better btw

char* kilobyte = malloc(1000);
// put some stuff in there
free(kilobyte); // delete everything
#

learning Rust in high school is pretty elite ngl

#

did they let you use any language?

#

well that disqualifies C which is interesting

paper fjord
#

We don't do OOP in rust...

dull remnant
wanton herald
#

https://github.com/cobrexus/rust-projects/blob/8c5f2981604bc2e4da863883bbb4b9021b6c8314/hash-set/src/main.rs#L34-L41 seems oddrust self .array .iter() .enumerate() .cycle() .skip(key) .take(self.array.len()) .find(|x| *x.1 == Item::Empty || *x.1 == Item::Deleted) if the goal is to iterate over self.array[key..] and then self.array[..key], you should be able to just do that, using <[T]>::split_at_mut and Iterator::chain. that will yield &mut Item<'a>s which you can assign through, so you should be able to replacerust if let Some(x) = (/* .. */) { let pos = x.0; self.array[pos] = (/* .. */); } with```rust
if let Some(item) = (/* .. */) {
item = (/ .. */);
}

the same applies to `search`, with [`<[T]>::split_at`](<https://doc.rust-lang.org/1.83.0/std/primitive.slice.html#method.split_at>) instead. there's no bounds check to skip here, but the optimizer should handle the simpler types better.
# 
let mut set = HashSet::<10>::new();
set.add("same string").unwrap();
set.add("same string").unwrap();
```what does your set do here? what should it do?
subtle ember
#

@coral vessel nice pig latin project