3 ms·
> bsearch + qsort is a great way to implement associative tables Only if you write/read your table in two separate passes. A tally needs mixed read/write to in
by a-french-anon 2y ago
> bsearch + qsort is a great way to implement associative tables
Only if you write/read your table in two separate passes. A tally needs mixed read/write to increment a counter, not just insertion, so it must be kept sorted during the table creation. Some kind of tree or linked list is probably better in this case.
> you can implement a hash table in C in about 125 LOC and reuse it.
I know. Anyone who uses C and never made at least a basic FNV1A/bucket-based hash table must be insane. But I wanted a small self-contained .c here and have become allergic to (void *); if I were to use C seriously, I'd fix it using a better preprocessor (à la https://github.com/etwyniel/c-generics https://github.com/etwyniel/c-generics).
> hash tables are not the only way to solve problems. hammer/nail
Eh, a tally seemed the most intuitive way for the 2nd part.
- liontwist 2y ago> incremental insert vs two pass Insert each element in its sorted position. It will only degenerate if there are many more inserts than lookups, in which case a hash table would do nothing for you. This could also be a good case for a radix structure. > void* hash table I would stay far from poor implementations of high level languages. Why use C if you want generics? A reusable hash table can be implemented by implementing open addressing with 64 bit integer keys. Then if you have a fancy type you write a hash function and perform linked list chaining on the values. Another way is to treat the keys as byte arrays. > seemed the most intuitive way for the 2nd part. Intuition is a kind of familiarity. There is no reason to learn C if you just write the techniques you already know in a less safe and more verbose way. You instead should be learning a new way to think about problems.