Thread

Needed 1+1, built a functional programming language

151 points · 80 comments · birdculture

ancientstraits · 1790728534 · focus · HN ↗
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.
1. dprkh · 1790729301 · focus · HN ↗
  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?
  1. fodkodrasz · 1790749397 · focus · HN ↗
    > Arrays are hash tables.
    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 · 1790753148 · focus · HN ↗
    In a trivial sense, arrays are hash tables with a hash function of the identity f(x)=x.
    It’s just not particularly common (or helpful) to view them that way.
    dprkh · 1790893688 · focus · HN ↗
    In LeetCode, it's a very common optimization. If your key values are dense, you use an array. If your key values are sparse, you use a dict.
    pjmlp · 1790758546 · focus · HN ↗
    Besides the sibling comment, you can used closed hash tables algorithm (open addressing), which is fully based on a single array.
    <a href="https://en.wikipedia.org/wiki/Open_addressing" rel="nofollow">https://en.wikipedia.org/wiki/Open_addressing

Open on Hacker News to reply ↗

Unofficial Hacker News client; not affiliated with Y Combinator.