3 ms·
Hard to imagine a hashmap is less complicated than a singly linked list under the hood.
by jandrese 8y ago
Hard to imagine a hashmap is less complicated than a singly linked list under the hood.
- joshuamorton 8y agoFrom a memory management perspective, a probing hashmap is just a vector/array. All of the bookkeeping is "safe" from a memory perspective.
- the_mitsuhiko 8y agoA hashmap is in its simplest form just an array.
- oconnor663 8y agoThey're roughly equal if the singly-linked list is just a head pointer, because the "each object is only reachable through a single path, which owns it" property means the compiler can reason about what's going on. It's when you add a tail pointer (or go whole hog and make it doubly-linked) that you lose that property and have to use unsafe code (or heavyweight things like Arc<Mutex<...>>) to get the compiler off your back.