3 ms·

I suppose this isn't a bad introduction to hash tables, but I would assume that most HN readers know how to implement a hash table. It seems like talking about

by smabie 6y ago

I suppose this isn't a bad introduction to hash tables, but I would assume that most HN readers know how to implement a hash table. It seems like talking about fundamental CS concepts in.. Python is a perennial source of quick and easy blog posts for a lot of people.

nepthar 6y ago
Something strikes me as out of place with this kind of post. On one hand, I want to encourage people to write posts about common concepts, but on the other hand, this is a fairly commonly written about concept, posted by the author, on a site with significant numbers of ads. I guess this seems like some people might have started to use HN as a way to click farm or something.
- smabie 6y ago
  The author has a lot of very similar and very trivial posts. I agree that it seems sketchy.
  - mastro35 6y ago
    Some are trivial, some a little less... I'm trying to find the best format for the site
  - solarkraft 6y ago
    Trivial posts have a great introductory value. Especially in Python I imagine there to be a lot of people using hash tables without actually knowing how they work, or maybe even never having heard of hashes. Of course it's arguable whether such a post belongs here, but a bunch of other introductory ones have been popular here before.
labster 6y ago
Anecdata: I don’t know how to implement a hash table, but I know how to use them. Not everyone here has a CS education background.
- tmh88j 6y ago
  If you're interested in implementing a hash table I would assume you're also generally interested in data structures and algorithms. I'd highly suggest the Algorithms, Part 1 class on Coursera. It's totally free and offered through Princeton. It covers hash tables in the last segment, albeit implemented in Java, but still very thorough and is a great introduction to common data structures/algorithms and analysis, like linked lists, union find, trees, quick sort and time/space complexity. https://www.coursera.org/learn/algorithms-part1 https://www.coursera.org/learn/algorithms-part1
  - prad9104 6y ago
    What level of math does one need to understand to take this course?
    - smabie 6y ago
      I've ignored math prereqs my entire life and turned out fine. If you're genuinely interested, it's not too hard to learn the math as needed. It might actually be a better way to learn, because you're learning is always in service of other learning. I haven't taken that Coursera course, but in college, I believe only calc I and II are the prereqs for intro to data structures and algorithms. Though I know solid engineers who understand applied CS who don't have a good grasp of math at all.
      - labster 6y ago
        > It might actually be a better way to learn, because you're learning is always in service of other learning. Me in freshman calculus: Why are we learning these Taylor series? It's so boring, and I'll never need to use it Me three years later in upper-division meteorology: It turns out 90% of what we do is numerical methods because fluid dynamics is hard with limited data. It's definitely easier for me to learn things when I have an application for it.
    - formerly_proven 6y ago
      For the data structure & algorithm courses I've seen, basically none.
pdonis 6y ago
IMO a better thing to focus on in Python would be how heavily optimized the Python dict implementation is, as compared with other hash table implementations out there. There used to be a good article online by Tim Peters about this, but I haven't been able to find it.
- xapata 6y ago
  Raymond Hettinger designed the latest implementation, more or less. He's given some talks about it.
deleted 6y ago
[deleted]
rurban 6y ago
Well, if you know hash tables you will still need some education on the special quirks of python hash tables. They are in no way related to CS hash tables. And you should not base your own hash table on the python architecture. They are sorted. Normal hash tables are unsorted, sorting needs lot of time and space. Nobody but python would do that. (ignoring PHP here). But once you went down this path, users start relying on this quirks and you cannot get away from that. They feature special values for ints. 1 hashes to 1, 4 to 4 and so on. This looks like Lua arrays, which are either arrays or hashtables under the hood, and allows efficient switches from dense to sparse arrays. But mostly it costs time in the most critical fast path. And it doesn't help in security at all. They are insecure by default. Only with some special cmdline flag they feature a randomized seed. Which is still insecure because the seed can be easily exposed by reading the memory of the seed. They are extremely slow. They are using siphash. Everybody using siphash is immediately exposed as having no idea about hash table security.
- formerly_proven 6y ago
  > They are sorted. Normal hash tables are unsorted, sorting needs lot of time and space. Nobody but python would do that. But once you went down this path, users start relying on this quirks and you cannot get away from that. They most definitely aren't sorted. It's not a quirk either. Python dicts are essentially a tiny hashtable of pointers into an array of objects. For iteration, that array is traversed directly. That's where the insertion-order preservation comes from. It's cheap. It doesn't involve sorting. > They are insecure by default. Only with some special cmdline flag they feature a randomized seed. Hashes are randomized since Python 3.2 or so. > Which is still insecure because the seed can be easily exposed by reading the memory of the seed. Obviously. > They feature special values for ints. 1 hashes to 1, 4 to 4 and do on. That's a quirk of the hash function (which is a reduction modulo a prime), not the hashtable. > Everybody using siphash is immediately exposed as having no idea about hash table security. Well...
- dragonwriter 6y ago
  > They are sorted. No, they are insertion-ordered. > Nobody but python would do that. Ruby Hashes are insertion-ordered; JavaScript objects have numeric properties ordered numerically (so, in a sense, are sorted), but other propertied in insertion order.

by smabie 6y ago

nepthar 6y ago

Something strikes me as out of place with this kind of post. On one hand, I want to encourage people to write posts about common concepts, but on the other hand, this is a fairly commonly written about concept, posted by the author, on a site with significant numbers of ads. I guess this seems like some people might have started to use HN as a way to click farm or something.

smabie 6y ago
The author has a lot of very similar and very trivial posts. I agree that it seems sketchy.
- mastro35 6y ago
  Some are trivial, some a little less... I'm trying to find the best format for the site
- solarkraft 6y ago
  Trivial posts have a great introductory value. Especially in Python I imagine there to be a lot of people using hash tables without actually knowing how they work, or maybe even never having heard of hashes. Of course it's arguable whether such a post belongs here, but a bunch of other introductory ones have been popular here before.

labster 6y ago

Anecdata: I don’t know how to implement a hash table, but I know how to use them. Not everyone here has a CS education background.

tmh88j 6y ago
If you're interested in implementing a hash table I would assume you're also generally interested in data structures and algorithms. I'd highly suggest the Algorithms, Part 1 class on Coursera. It's totally free and offered through Princeton. It covers hash tables in the last segment, albeit implemented in Java, but still very thorough and is a great introduction to common data structures/algorithms and analysis, like linked lists, union find, trees, quick sort and time/space complexity. https://www.coursera.org/learn/algorithms-part1 https://www.coursera.org/learn/algorithms-part1
- prad9104 6y ago
  What level of math does one need to understand to take this course?
  - smabie 6y ago
    I've ignored math prereqs my entire life and turned out fine. If you're genuinely interested, it's not too hard to learn the math as needed. It might actually be a better way to learn, because you're learning is always in service of other learning. I haven't taken that Coursera course, but in college, I believe only calc I and II are the prereqs for intro to data structures and algorithms. Though I know solid engineers who understand applied CS who don't have a good grasp of math at all.
    - labster 6y ago
      > It might actually be a better way to learn, because you're learning is always in service of other learning. Me in freshman calculus: Why are we learning these Taylor series? It's so boring, and I'll never need to use it Me three years later in upper-division meteorology: It turns out 90% of what we do is numerical methods because fluid dynamics is hard with limited data. It's definitely easier for me to learn things when I have an application for it.
  - formerly_proven 6y ago
    For the data structure & algorithm courses I've seen, basically none.

pdonis 6y ago

IMO a better thing to focus on in Python would be how heavily optimized the Python dict implementation is, as compared with other hash table implementations out there. There used to be a good article online by Tim Peters about this, but I haven't been able to find it.

xapata 6y ago
Raymond Hettinger designed the latest implementation, more or less. He's given some talks about it.

deleted 6y ago

[deleted]

rurban 6y ago

Well, if you know hash tables you will still need some education on the special quirks of python hash tables. They are in no way related to CS hash tables. And you should not base your own hash table on the python architecture. They are sorted. Normal hash tables are unsorted, sorting needs lot of time and space. Nobody but python would do that. (ignoring PHP here). But once you went down this path, users start relying on this quirks and you cannot get away from that. They feature special values for ints. 1 hashes to 1, 4 to 4 and so on. This looks like Lua arrays, which are either arrays or hashtables under the hood, and allows efficient switches from dense to sparse arrays. But mostly it costs time in the most critical fast path. And it doesn't help in security at all. They are insecure by default. Only with some special cmdline flag they feature a randomized seed. Which is still insecure because the seed can be easily exposed by reading the memory of the seed. They are extremely slow. They are using siphash. Everybody using siphash is immediately exposed as having no idea about hash table security.

formerly_proven 6y ago
> They are sorted. Normal hash tables are unsorted, sorting needs lot of time and space. Nobody but python would do that. But once you went down this path, users start relying on this quirks and you cannot get away from that. They most definitely aren't sorted. It's not a quirk either. Python dicts are essentially a tiny hashtable of pointers into an array of objects. For iteration, that array is traversed directly. That's where the insertion-order preservation comes from. It's cheap. It doesn't involve sorting. > They are insecure by default. Only with some special cmdline flag they feature a randomized seed. Hashes are randomized since Python 3.2 or so. > Which is still insecure because the seed can be easily exposed by reading the memory of the seed. Obviously. > They feature special values for ints. 1 hashes to 1, 4 to 4 and do on. That's a quirk of the hash function (which is a reduction modulo a prime), not the hashtable. > Everybody using siphash is immediately exposed as having no idea about hash table security. Well...
dragonwriter 6y ago
> They are sorted. No, they are insertion-ordered. > Nobody but python would do that. Ruby Hashes are insertion-ordered; JavaScript objects have numeric properties ordered numerically (so, in a sense, are sorted), but other propertied in insertion order.