I am trying to create a hash table…but I can’t seem to get it…can you help me?
Lets say i want to create a key of u32, and a value of an array of u8? how do i do that?
Do I need to allocate a list of u32, and a list of buffer (array of u8) plus the hash table itself (thats 3)…
Hi @f-tuason, welcome to Ziggit!
It seems like you are trying to set up your own from scratch. There are actually a few HashMaps in the std library that you may be able to leverage.
Start with the AutoHashMap or the AutoArrayHashMap
Typical usage is as follows:
const std = @import("std");
pub fn main() !void {
var gpa: std.heap.DebugAllocator(.{}) = .init;
defer _ = gpa.deinit();
const allocator = gpa.allocator();
// If the values are allocated strings, you will need to deallocate them manually.
var map = std.AutoArrayHashMap(u32, []const u8).init(allocator);
defer map.deinit();
try map.put(1, "one");
try map.put(2, "two");
const val = map.get(1) orelse return error.KeyNotFound;
std.debug.print("Value for key 1: {s}\n", .{val});
}
I’ve got a few questions…
I’ve been looking at zigs library (the new .16 version) can you tell me the differences between, HashMap, AutoHashMap, ArrayHashMap and AutoArrayHashMap? Why are there so many?
if I am going to deallocate, do I need to go through all the map and deallocate the buffer (array that holds the buf?) and how do I loop through that?
what if I dont want a buffer but a pointer to a buffer, how can I do that?
this is a sample of what I want in a struct (its not yet finished…)
pub const myhash = struct {
allocator: Allocator,
map: std.ArrayHashMapWithAllocator(u32, []const u8),
pub fn Init(self: *myhash) !void {
var gpa: std.heap.Allocator(.{}) = .init;
const allocator = gpa.allocator();
var map = std.AutoArrayHashMap(u32, []const u8).init(allocator);
}
pub fn DeInit(self: *myhash) !void {
for (self.map.iterator) |iterator| {
//can you help me here?
}
defer self.map.deinit();
defer allocator.deinit();
}
};
std.HashMap requires you to specify your own context - a context is a namespace that contains a hash and eql function, for computing hashes and hash equality.
This is great for custom implementations, but for people who don’t need it, std.AutoHashMap exists which uses a default context.
std.ArrayHashMap is a hash map which guarantees that the keys will all be stored next to each other in memory, (as will the values), so you know everything will be in the hash map in the same order you put it in there, and you can call .keys() and .values() to get a slice of the map’s keys and values, which is nice and convenient compared to std.HashMap where you’re forced to use an iterator type.
std.AutoArrayHashMap is just the same thing as std.AutoHashMap but for array hash maps.
In your case, you’d probably do std.AutoHashMap(u32, []const u8) or std.AutoArrayHashMap(u32, []const u8).
You don’t need to allocate the keys - the hash map will do that for you - but if your values are buffers, and they’re allocated on the heap, you do need to free them; deinitting the hash map won’t do that on its own.
In light of that, your deinit routine might look like this:
/// deinit shouldn't be able to fail
pub fn deinit(self: *MyHash) void {
// If you used an AutoArrayHashMap, you can use the values function
// to get a []const []const u8 slice of all your slices.
// You can then loop over this slice and use your allocator to free each buffer.
for(self.map.values()) |buffer| {
self.allocator.free(buffer);
}
self.map.deinit();
}
If you used a std.AutoHashMap instead of a std.AutoArrayHashMap, it might look like this instead:
pub fn deinit(self: *MyHash) void {
var it = self.map.iterator();
while(it.next()) |entry| {
// entry.value_ptr is a pointer to a []const u8, so we need to
// dereference it to properly free it.
self.allocator.free(entry.value_ptr.*);
}
self.map.deinit();
}
I also feel compelled to point out that your init function is kind of unnecessary.
In the standard library, it’s considered standard for structs to have a pub const init: @This() = .{}; declaration or similar, which is a pre-instantiated instance of the struct with all the desired initial values.
That way, users can instantiate the struct using a pattern like this:
pub var arrl: std.ArrayList(u32) = .empty;
This communicates the user’s intent to create an ArrayList with no items and a starting capacity of 0 items.
Since your init function isn’t actually using any inputs other than the struct itself, it could easily be changed to a declaration of this sort, like so:
pub const init: myhash = .{
.allocator = std.heap.smp_allocator,
.map = .init(std.heap.smp_allocator),
};
okay, okay, I’ll try experimenting with this first…I’m from c/c++, so its confusing to learn this…why is there an allocator here!?
Because the hashmap may grow in size, it may need to reallocate it’s keys and values.
Note that std::unordered_map also takes an allocator, but since there is a default one provided by default you do not always notice. Look at the cpp docs here: std::unordered_map - cppreference.com
Thank you! tholmes and Etienne_Parmentier…