The "how to implement a hash table" article <a href="https://benhoyt.com/writings/hash-table-in-c/" rel="nofollow">https://benhoyt.com/writings/hash-table-in-c/ was really helpful for me. I thought that hash tables were something that were basically impossible to make in C, but this showed that it was simpler.
Arrays are hash tables. You can implement a very simple hash table from a tutorial, but can you implement a sophisticated one? What about a concurrent hash table?
Yeah, I'm pretty sure we made hash tables in the first C class I took in college in my second semester freshman year. If you can make a linked list, and then make an array of them, and a function to map keys to array indexes, you have a hash table. Whether it's actually performant is entirely a separate question, but a naive hash table is still a hash table.
Hash tables are awesome. They are both an incredibly simple data structure and a seriously deep rabbit hole. Most of the complexity comes from collision resolution [1], and how you handle resolution largely determines what kind of hash table you have. There are at least dozens of collision resolution approaches. The simplest, and probably the one you implemented in your undergrad C class was open addressing. That’s also what I implemented as an undergrad. But there are many more approaches, some quite a bit more complicated, and many of them let you continue to shave off asymptotic costs when you run collision resolution, or they improve locality for typical lookups, allowing better cache utilization, etc. Hash tables are super fun to play with, and for full effect, you really do need to implement them in something like C.
I only skimmed the linked article, but I do wonder whether the author ever realized that they needed to think about scope rules. I searched for the word “scope” but never found it. Closures seriously complicate language design and things get painful and counterintuitive unless you use lexical scope (or… you know… you like pain).
Yeah, I learned about a bunch of the other algorithms later (forgetting the names, but stuff like "move to the next slot rather than putting collisions into buckets" and "hash a second time if you hit a collision"; I'm sure I'm forgetting some of the nuances).
> Closures seriously complicate language design and things get painful and counterintuitive unless you use lexical scope (or… you know… you like pain)
Well if you like both lexical scope and pain, there's always lisp!
You might end up founding one of the first e-commerce sites, sell it for a handsome payday, and then create the first startup accelerator and make insane amounts of money while transforming the industry.
Maybe in JavaScript... but there is a topic called datastructures, where arrays are arrays, and hashtables are hastables. If people say this without a flip of an eye I'm not surprised why people write stuff like
> I thought that hash tables were something that were basically impossible to make in C
SDL3's properties API uses an internal hashtable I'm waiting for them to make public.
I also like <a href="https://github.com/tidwall/hashmap.c" rel="nofollow">https://github.com/tidwall/hashmap.c for general use.
Yeah it's a strange assumption, as this was taught in basic data structures class years ago and any language can implement any data structure, technically speaking. C especially is a weird assumption because lots of foundational software is written in C including hash tables.
When I was in university, hash tables were definitely among the things we had to learn about and then implement in C, probably in first year. Per Wikipedia, the concept dates to 1953 (with an implementation in assembly); of course people made them in C once that was an option.
I always liked that idea of just doing a linear wrap-around sweep through an array that holds (key, value) pairs, until you find the pair with the key you're looking for (for 'get' or 'contains?') or an empty spot (for 'put'). The trick to make this fast is that the hash function (key -> int) tells you at which index to start the sweep.
No secondary data structures, super simple to implement, and it works great for small use cases.
This isn't great though if you need to find out if an element exists in the table, and you have the ability to remove elements from it. I suppose you could optimize the hash table after deletions, but that again would be slow.. ?
Btw, this reminds me a bit of Cuckoo hashes. Never used them but seems like a nice idea.
The expected or amortized complexity of the standard hash table operations (put, get, contains, remove) are all O(1) for linear probing (under the usual assumptions for the hash function and as long as the table does not get too full). Of course that doesn't shield a single operation from being O(n) in the worst case.
The standard hash table has buckets, though, not just a single array that is probed through in case there's no space for a value in the slot determined by the hash function?
Right, that's the beauty of this simple approach: there's only one array and it doubles as the storage for buckets. But yes, the table will have a maximum size after which you cannot add more entries. That is, in practice you would create a new hashtable with a larger capacity and rehash all the existing entries into the new, bigger table (in practice, you would do that even sooner than that, namely when a certain load factor is passed - see my previous comment where I alluded to the role of the load factor).
The cool thing, however, is: if the size of the new hashtable is double the size of the old hashtable, your amortized insertion costs are still only O(1)!
(And you don't just have to take my word for it: take my original comment and paste it into the AI interface of your choice and have it create a concrete implementation. Ask it to add a remove operation, and an automatic doubling of the array size + rehashing when the table reaches a load factor of, say, 0.7 -- the resulting code should be very manageable, and then you can run your own tests and measure times!
This is maybe not the smartest way to do hashing, but its appeal lies in its simplicity and hence compactness of implementation. There are many cases where you don't even need a 'remove' operation, and where you never have to worry about growing the array because you know that you're only ever going to hash a certain number of elements at most.)
Let's say we have removed all elements from the hash. Then all following contains -calls will need to be O(n), if I understood correctly? They need to check every slot in the array to confirm inexistence, rather than just one bucket.
There are different ways on how to implement remove, but one way to do it is to overwrite the (key, value) pair to be removed with a special "tombstone" symbol that is different from null. Another way is to shift all elements with the same hash value as the one to be removed one index to the left, and null the final position.
There are cases where contains or get would have to iterate over the whole array, basically when all the previously added elements hash-collide, i.e., are mapped to the same start-index. But every hash-implementation has pathological cases where the access methods get slow -- but if the keys are sufficiently random, you don't expect such cases to occur in practice.
IIRC, the first edition of the book "The C Programming Language" (aka K&R), by Kernighan and Ritchie, had a simple example of how to create a hash table in C, including with buckets to handle collisions. It was a simple algorithm. It simply added up the ASCII values of all the characters in the key, modulo some number.
If hash tables were impossible to make in C, then it would be impossible to make them in Python, because it is a higher level language than C.
(Almost by definition, anything doable in a higher level language is doable in a lower level language, but not necessarily vice versa. In fact, many higher level languages are themselves written in lower level languages, e.g. Python is written in C.)
But Python has got dicts built into it, which are nothing but hash tables, and they are almost certainly written in C.
Google for some videos by Raymond Hettinger about Python dictionaries.
Or look at the source code of the Python interpreter.
> But Python has got dicts built into it, which are nothing but hash tables, and they are almost certainly written in C.
In CPython they are written in C (at the moment). Other Python implementations are written in other languages.
> (Almost by definition, anything doable in a higher level language is doable in a lower level language, but not necessarily vice versa. In fact, many higher level languages are themselves written in lower level languages, e.g. Python is written in C.)
It depends on what you mean by 'anything doable'. Eg Haskell compilers can in principle do lots of crazy optimisations that a C compiler would not be able to safely do, just because they don't have enough information. Even more so for Lean compilers, which can _know_ which of your loops are terminating, instead of making crude assumptions like C compilers.
Btw, higher level languages being implemented in lower level languages is mostly something for interpreters. Writing a C interpreter in Python is pretty much futile, if you care about speed. But writing a C compiler in Python is perfectly fine. And writing a Python compiler in Python is also fine. Many languages self-host (at least some of) their compilers.
The article says the last release of Jython was 2 years ago. I wonder how much it is used these days. It did seem like a good idea when it was first released. I had only tried it out a little at that time.
>It depends on what you mean by 'anything doable'. Eg Haskell compilers can in principle do lots of crazy optimisations that a C compiler would not be able to safely do, just because they don't have enough information. Even more so for Lean compilers, which can _know_ which of your loops are terminating, instead of making crude assumptions like C compilers.
Interesting. What are some of those optimisations that Haskell and Lean can do, that a C compiler would not be able to safely do?
A very simple one: in Haskell the compiler has knowledge about which functions cause side-effects and which don't. The compiler can skip calling pure functions whose return value ain't used; similarly, the compiler can call a pure function multiple times, instead of saving the return value in memory.
The Haskell compiler can also fairly freely re-arrange in what order things are computed.
A fairly common idiom in Haskell is to just return a tuple of two values, if they are 'thematically' linked; even if computing one is much more expensive than the other. The compiler is smart enough, to only compute one of the values, if you only use one of them. (When I say 'tuple', it could be literally (a, b), or it could be in a struct or whatever.)
Lean knows even more about your code, so you could do more optimisations. But you need to ask Claude for details, I haven't used it as much nor thought as much about it.
ancientstraits · · focus · HN ↗
dprkh · · focus · HN ↗
saghm · · focus · HN ↗
raddan · · focus · HN ↗
I only skimmed the linked article, but I do wonder whether the author ever realized that they needed to think about scope rules. I searched for the word “scope” but never found it. Closures seriously complicate language design and things get painful and counterintuitive unless you use lexical scope (or… you know… you like pain).
[1] <a href="https://en.wikipedia.org/wiki/Hash_table#Collision_resolution" rel="nofollow">https://en.wikipedia.org/wiki/Hash_table#Collision_resolutio...
saghm · · focus · HN ↗
> Closures seriously complicate language design and things get painful and counterintuitive unless you use lexical scope (or… you know… you like pain)
Well if you like both lexical scope and pain, there's always lisp!
jimbokun · · focus · HN ↗
You might end up founding one of the first e-commerce sites, sell it for a handsome payday, and then create the first startup accelerator and make insane amounts of money while transforming the industry.
Safer to stick to Blub.
saghm · · focus · HN ↗
fodkodrasz · · focus · HN ↗
Maybe in JavaScript... but there is a topic called datastructures, where arrays are arrays, and hashtables are hastables. If people say this without a flip of an eye I'm not surprised why people write stuff like
> I thought that hash tables were something that were basically impossible to make in C
moregrist · · focus · HN ↗
It’s just not particularly common (or helpful) to view them that way.
dprkh · · focus · HN ↗
pjmlp · · focus · HN ↗
<a href="https://en.wikipedia.org/wiki/Open_addressing" rel="nofollow">https://en.wikipedia.org/wiki/Open_addressing
eru · · focus · HN ↗
krapp · · focus · HN ↗
I also like <a href="https://github.com/tidwall/hashmap.c" rel="nofollow">https://github.com/tidwall/hashmap.c for general use.
fuzztester · · focus · HN ↗
<a href="https://news.ycombinator.com/item?id=49913084">https://news.ycombinator.com/item?id=49913084
applfanboysbgon · · focus · HN ↗
Why would you believe this in the first place?
satvikpendem · · focus · HN ↗
zahlman · · focus · HN ↗
kleiba2 · · focus · HN ↗
No secondary data structures, super simple to implement, and it works great for small use cases.
_flux · · focus · HN ↗
Btw, this reminds me a bit of Cuckoo hashes. Never used them but seems like a nice idea.
kleiba2 · · focus · HN ↗
_flux · · focus · HN ↗
kleiba2 · · focus · HN ↗
The cool thing, however, is: if the size of the new hashtable is double the size of the old hashtable, your amortized insertion costs are still only O(1)!
(And you don't just have to take my word for it: take my original comment and paste it into the AI interface of your choice and have it create a concrete implementation. Ask it to add a remove operation, and an automatic doubling of the array size + rehashing when the table reaches a load factor of, say, 0.7 -- the resulting code should be very manageable, and then you can run your own tests and measure times!
This is maybe not the smartest way to do hashing, but its appeal lies in its simplicity and hence compactness of implementation. There are many cases where you don't even need a 'remove' operation, and where you never have to worry about growing the array because you know that you're only ever going to hash a certain number of elements at most.)
_flux · · focus · HN ↗
kleiba2 · · focus · HN ↗
There are cases where contains or get would have to iterate over the whole array, basically when all the previously added elements hash-collide, i.e., are mapped to the same start-index. But every hash-implementation has pathological cases where the access methods get slow -- but if the keys are sufficiently random, you don't expect such cases to occur in practice.
zahlman · · focus · HN ↗
I suppose that would work, but I can't recall ever hearing of an implementation that actually does that.
pjmlp · · focus · HN ↗
Which during my degree, the lab deliverables were 100% C code.
Here, one possible book:
Data Structures, Algorithms, and Software Principles in C (1994 edition)
<a href="https://www.amazon.com/dp/0201591189" rel="nofollow">https://www.amazon.com/dp/0201591189
fuzztester · · focus · HN ↗
fuzztester · · focus · HN ↗
(Almost by definition, anything doable in a higher level language is doable in a lower level language, but not necessarily vice versa. In fact, many higher level languages are themselves written in lower level languages, e.g. Python is written in C.)
But Python has got dicts built into it, which are nothing but hash tables, and they are almost certainly written in C.
Google for some videos by Raymond Hettinger about Python dictionaries.
Or look at the source code of the Python interpreter.
eru · · focus · HN ↗
In CPython they are written in C (at the moment). Other Python implementations are written in other languages.
> (Almost by definition, anything doable in a higher level language is doable in a lower level language, but not necessarily vice versa. In fact, many higher level languages are themselves written in lower level languages, e.g. Python is written in C.)
It depends on what you mean by 'anything doable'. Eg Haskell compilers can in principle do lots of crazy optimisations that a C compiler would not be able to safely do, just because they don't have enough information. Even more so for Lean compilers, which can _know_ which of your loops are terminating, instead of making crude assumptions like C compilers.
Btw, higher level languages being implemented in lower level languages is mostly something for interpreters. Writing a C interpreter in Python is pretty much futile, if you care about speed. But writing a C compiler in Python is perfectly fine. And writing a Python compiler in Python is also fine. Many languages self-host (at least some of) their compilers.
fuzztester · · focus · HN ↗
True. E.g.:
1. PyPy:
<a href="https://en.wikipedia.org/wiki/PyPy" rel="nofollow">https://en.wikipedia.org/wiki/PyPy
>The PyPy interpreter itself is written in a restricted subset of Python called RPython (Restricted Python).
2. Jython:
<a href="https://en.wikipedia.org/wiki/Jython" rel="nofollow">https://en.wikipedia.org/wiki/Jython
>Implementation language: Python, Java
The article says the last release of Jython was 2 years ago. I wonder how much it is used these days. It did seem like a good idea when it was first released. I had only tried it out a little at that time.
fuzztester · · focus · HN ↗
Interesting. What are some of those optimisations that Haskell and Lean can do, that a C compiler would not be able to safely do?
eru · · focus · HN ↗
The Haskell compiler can also fairly freely re-arrange in what order things are computed.
A fairly common idiom in Haskell is to just return a tuple of two values, if they are 'thematically' linked; even if computing one is much more expensive than the other. The compiler is smart enough, to only compute one of the values, if you only use one of them. (When I say 'tuple', it could be literally (a, b), or it could be in a struct or whatever.)
Lean knows even more about your code, so you could do more optimisations. But you need to ask Claude for details, I haven't used it as much nor thought as much about it.
fuzztester · · focus · HN ↗