AutoHashMap
std.AutoHashMap implements a hash table that automatically creates a hash function for the key type. Its main limitation is that it doesn’t work for keys that contain pointers or slices – see StringHashMap and HashMap for alternatives.
const std = @import("std");
const print = std.debug.print;
pub fn main(init: std.process.Init) !void {
const allocator = init.gpa;
// AutoHashMap stores the allocator, so we need to
// provide that here.
var map = std.AutoHashMap(
u64, // key type
u64, // value type
).init(allocator);
defer map.deinit();
// Add an entry with 'put'.
try map.put(2, 4);
print("2 is in map? {}\n", .{map.contains(2)});
print("2 => {?}\n", .{map.get(2)});
print("\n", .{});
// 'put' also updates existing entries.
try map.put(2, 8);
print("2 => {?}\n", .{map.get(2)});
print("\n", .{});
print("entry count: {}\n", .{map.count()});
print("\n", .{});
// 'remove' removes a key. It returns a boolean to
// indicate if the key was there before.
const removed = map.remove(2);
print("removed entry? {}\n", .{removed});
print("2 is in map? {}\n", .{map.contains(2)});
print("2 => {?}\n", .{map.get(2)});
}$ zig run autohashmap.zig
2 is in map? true
2 => 4
2 => 8
entry count: 1
removed entry? true
2 is in map? false
2 => nullThe get method just returns a value, but some methods
give us pointers to keys and values:
const std = @import("std");
const print = std.debug.print;
pub fn main(init: std.process.Init) !void {
const allocator = init.gpa;
// We’ll use a map to count how often each character
// occurs in a string.
var map = std.AutoHashMap(u8, u64).init(allocator);
defer map.deinit();
// getOrPutValue adds a key unless it already
// exists, and returns an 'Entry' with pointers to
// the key and the value.
for ("banana") |c| {
const entry = try map.getOrPutValue(c, 0);
entry.value_ptr.* += 1;
}
// The 'iterator' method gives us an iterator that
// also uses 'Entry'.
print("entries:", .{});
var iterator = map.iterator();
while (iterator.next()) |entry|
print(" {c}=>{}", .{
entry.key_ptr.*,
entry.value_ptr.*,
});
print("\n", .{});
// We can also iterate over just the keys.
print("keys:", .{});
var key_iterator = map.keyIterator();
while (key_iterator.next()) |key|
print(" {c}", .{key.*});
print("\n", .{});
// Or just the values.
print("values:", .{});
var value_iterator = map.valueIterator();
while (value_iterator.next()) |value|
print(" {}", .{value.*});
print("\n", .{});
}$ zig run autohashmap-2.zig
entries: b=>1 a=>3 n=>2
keys: b a n
values: 1 3 2Locking a map
One thing to keep in mind with these methods is that pointers into the map become invalid when the memory for the map is re-allocated. Generally, any methods that add or remove elements invalidate pointers into the map, including iterators.
const std = @import("std");
const print = std.debug.print;
// Zig’s HashMap has a neat feature that can help us
// debug these issues. The idea is to put the map into a
// “locked” state where any method that would invalide
// pointers triggers an assertion.
pub fn main(init: std.process.Init) !void {
const allocator = init.gpa;
var map = std.AutoHashMap(i8, i8).init(allocator);
defer map.deinit();
try map.put(1, 1);
try map.put(2, 4);
try map.put(3, 9);
printKeys(&map);
try addKeys(&map);
}
// This function iterates over the map, so to be safe
// we’ll lock it at the start. We’ll defer a call to
// unlock it.
fn printKeys(map: *std.AutoHashMap(i8, i8)) void {
map.lockPointers();
defer map.unlockPointers();
var iterator = map.keyIterator();
while (iterator.next()) |ptr| {
const key = ptr.*;
print("{}\n", .{key});
}
print("\n", .{});
}
// This function calls `put` to add elements while
// iterating over the map, triggering an assertion.
fn addKeys(map: *std.AutoHashMap(i8, i8)) !void {
map.lockPointers();
defer map.unlockPointers();
var iterator = map.keyIterator();
while (iterator.next()) |ptr| {
const key = ptr.*;
try map.put(-key, key * key); // uh-oh
}
}$ zig run autohashmap-3.zig
2
1
3
thread 123 panic: reached unreachable code
std/hash_map.zig:1101:21: 0x1078e2c in getOrPutContextAdapted__anon_30358 (locking)
if (!gop.found_existing) {
^
locking.zig:40:20: 0x102753b in addKeys (locking)
try map.put(-key, key * key); // uh-oh
^
std/start.zig:190:5: 0x102575d in _start (locking)
asm volatile (switch (native_arch) {
^
AbortedUsing a map as a set
We can use a hash map with value type void as a set.
const std = @import("std");
const print = std.debug.print;
pub fn main(init: std.process.Init) !void {
const allocator = init.gpa;
var set = std.AutoHashMap(u8, void).init(allocator);
defer set.deinit();
// {} is a value of type void.
try set.put(3, {});
try set.put(7, {});
try set.put(31, {});
print("3 is in set? {}\n", .{set.contains(3)});
print("4 is in set? {}\n", .{set.contains(4)});
print("items in set:", .{});
var key_iterator = set.keyIterator();
while (key_iterator.next()) |key|
print(" {}", .{key.*});
print("\n", .{});
}$ zig run autohashmap-4.zig
3 is in set? true
4 is in set? false
items in set: 31 7 3std.hash_map.AutoHashMapUnmanaged
AutoHashMapUnmanaged
is a variant of AutoHashMap that doesn’t store the
allocator:
const std = @import("std");
const print = std.debug.print;
pub fn main(init: std.process.Init) !void {
const allocator = init.gpa;
// We don’t need to provide an allocator to 'init'.
var map = std.AutoHashMapUnmanaged(u8, u8).empty;
defer map.deinit(allocator);
// But we do for every call to 'put'.
try map.put(allocator, 2, 4);
try map.put(allocator, 3, 9);
try map.put(allocator, 4, 16);
print("entries:", .{});
var iterator = map.iterator();
while (iterator.next()) |entry|
print(" {}=>{}", .{
entry.key_ptr.*,
entry.value_ptr.*,
});
print("\n", .{});
}$ zig run autohashmap-5.zig
entries: 2=>4 4=>16 3=>9std.array_hash_map.Auto
std.array_hash_map.Auto is an implementation of a hash map that stores keys and values sequentially. It preserves the order of entries, so iteration will produce keys in the order that they were added.
const std = @import("std");
const print = std.debug.print;
pub fn main(init: std.process.Init) !void {
const allocator = init.gpa;
var map = std.array_hash_map.Auto(u8, u8).empty;
defer map.deinit(allocator);
try map.put(allocator, 2, 4);
try map.put(allocator, 3, 9);
try map.put(allocator, 4, 16);
print("entries:", .{});
var iterator = map.iterator();
while (iterator.next()) |entry|
print(" {}=>{}", .{
entry.key_ptr.*,
entry.value_ptr.*,
});
print("\n", .{});
}$ zig run autohashmap-6.zig
entries: 2=>4 3=>9 4=>16Next example: StringHashMap.