salmagundi
Languages and libraries
c hash map library
SHOW HN2024
176points
90comments
#457of 3,515 in 2024
Top 14%of 2024 by points
How HN took it
CuriousMostly questions and neutral comments
2 positive, 24 neutral or asking, 1 mixed, 10 critical, out of 37 comments about the project. Thread score -0.22.
Execution: 0 for, 6 againstDesign: 1 for, 2 againstPerformance: 0 for, 1 againstDocs: 0 for, 1 against
The thread, comment by comment
Each row is a top-level comment and its replies, in HN's order. Select a cell to open that comment on HN.
positive neutral or mixed critical about another commenter or something else the maker
What HN said
What people liked
Simple and remarkably small implementation
From 1 comment
This is neat, and remarkably small. I personally need more comments in order to follow, say, the growth logic. I see it rehashes but I don't see how it doesn't potentially…
vintagedave on HN
Name is a nice word choice
From 1 comment
This is neat, and remarkably small. I personally need more comments in order to follow, say, the growth logic. I see it rehashes but I don't see how it doesn't potentially…
vintagedave on HN
Objections
Deletion is broken: deleting a colliding item makes later items unfindable
From 3 comments
A bug, I believe: If you "put" three colliding strings A and then B and then C, and then "delete" B, you won't be able to find C anymore.
drfuchs on HNYou are implementing a closed hash table with linear probing. You need tombstones to mark deleted items, or better, move other items to replace deleted items [1]. Currently your…
attractivechaos on HNRow 100 of hm_put() clears all contents of the item struct, thus losing the pointer to where the previous value was stored. But then row 107 needs this pointer to pass it to…
teo_zero on HN
Memory bugs in hm_put including lost pointers and key leaks
From 3 comments
Row 100 of hm_put() clears all contents of the item struct, thus losing the pointer to where the previous value was stored. But then row 107 needs this pointer to pass it to…
teo_zero on HNMy C is quite rusty, so apologies for stupid questions. In the hm_put function, when you overwrite, why do you malloc and copy the key again, and what happens with the old key…
tralarpa on HNIn reviewing hm_put, a few things stand out in the area of handling cases where memory allocation fails. The first problems are at lines 113-116 where memory is allocated and…
ms9598 on HN
Many mallocs hurt performance
From 2 comments
I'm curious about the #ifdef guard, which is of a form I've never encountered. ``` #ifndef BD9DF82A4540BB19368E48E4747C0706 #define BD9DF82A4540BB19368E48E4747C0706 ``` Does some…
cozzyd on HNThanks for sharing. Simplicity is a good thing. In order to speed it up by reducing the number of malloc() calls, it may be worth adding a simple arena memory allocation measure:…
jll29 on HN
Missing comments make the code hard to follow
From 1 comment
This is neat, and remarkably small. I personally need more comments in order to follow, say, the growth logic. I see it rehashes but I don't see how it doesn't potentially…
vintagedave on HN
Requests
Fix deletion using tombstones or slot shifting
From 2 comments
You are implementing a closed hash table with linear probing. You need tombstones to mark deleted items, or better, move other items to replace deleted items [1]. Currently your…
attractivechaos on HNAnother solution could be tombstones: When a slot gets cleared and the next slot has an item, insert a placeholder value. During linear probing, treat the placeholder as a normal…
skitter on HN
Add fuzz tests or valgrind testing
From 2 comments
I recently coded a linear-probing hash map in C and I highly recommend you to use fuzz tests. These evolve naturally from unit tests: next step table unit tests, next step…
gritzko on HNConsidering there seems to be at least a one memory bug (hm_put/key from another comment), I would strongly recommend running the tests in valgrind or similar if you haven't…
codr7 on HN
Use an arena allocator to reduce mallocs
From 1 comment
Thanks for sharing. Simplicity is a good thing. In order to speed it up by reducing the number of malloc() calls, it may be worth adding a simple arena memory allocation measure:…
jll29 on HN
Questions
Why unused parameters and (void) casts in hash functions
From 2 comments
Purely out of interest, and probably my bad, but what is: ``` (void)k_sz; ``` doing? I've seen fussy people doing: ``` (void) printf( "hello" ); ``` but not what you have…
zabzonk on HNOK, thank you. But why do the functions have those unused parameters?
zabzonk on HN
Why use an MD5-length random include guard instead of pragma once
From 2 comments
I'm curious about the #ifdef guard, which is of a form I've never encountered. ``` #ifndef BD9DF82A4540BB19368E48E4747C0706 #define BD9DF82A4540BB19368E48E4747C0706 ``` Does some…
cozzyd on HNWhat's wrong with `#pragma once`? (honest question, i only do C and C++ as a hobby)
tobyhinloopen on HN
How to handle padding bytes when hashing structs
From 1 comment
Here's some food-for-thought questions: First, a correctness question: - if a struct contains padding, the value of these padding bytes is undefined. What happens if you use such…
eqvinox on HN
Alternatives named
Chained hash maps, which make deletion simpler
From 1 comment
> Finally, deletes are hard in hash maps. Deletes are hard in open hash maps like here; they're trivial in chained hash maps. (I'm only posting this because this seems to be an…
eqvinox on HN
Crafting Interpreters hash table chapter
From 1 comment
If it helps, my book Crafting Interpreters walks through a linear probing hash table implementation in C including handling deletion:…
munificent on HN