5 ms·

While the article is a bit polemic, I really wish more people knew how hash tables work under the hood. When I was looking for a job, I flunked out of one inte

by Udo 10y ago

While the article is a bit polemic, I really wish more people knew how hash tables work under the hood. When I was looking for a job, I flunked out of one interview where I got into an argument with an interviewer about the runtime properties of hash tables - more specifically: the interviewer was adamant their access time was always O(1), wanted me to admit my "mistake" and move on, but I just couldn't ;) It was one of those rare cases where they give you feedback on why you're not being hired, too. The lady on the phone said my "technical knowledge" was not up to par with what they needed for the position. Yeah, I'm still salty about that.

arethuza 10y ago
Sounds to me more like the interviewer/company flunked you're test rather than you flunking - you might have dodged a bullet there.
- Udo 10y ago
  I wouldn't have worked for the interviewer, it's often just a gatekeeper you need to overcome. Also, when you don't know how to make rent next month and the company seems pretty cool (apart from that person), it's hard to see at the time how you dodged any bullets...
  - arethuza 10y ago
    If someone reacts badly when you know more than they do then that's not a great bit of behaviour, if a company chooses such a person as an interviewer then that's a bit of a red flag to me - an interview should be as much about trying to present a positive image of the company as much as testing the interviewer. Sorry to hear about the rent situation - I take that worked out OK eventually?
    - Udo 10y ago
      > if a company chooses such a person as an interviewer then that's a bit of a red flag to me I think the basic corporate rules of signalling competence apply here. Assuming that person was both technologically and socially incompetent (which might be too harsh of a judgement), some people still have a way of getting promoted into valuable positions by appearing to do a great job. > Sorry to hear about the rent situation - I take that worked out OK eventually? Thankfully that was some years back, I'm doing okay today :)
      - arethuza 10y ago
        "which might be too harsh of a judgement" Not sure it is - the usual advice is "if in doubt then don't hire" so why not apply that to employers as well as employees? Of course, if there is an element of desperation involved then I can understand it. But I have walked away from interview processes (or turned down offers) when I had some worries and never really regretted it. Harshness both ways would seem to be fair.
- marklgr 10y ago
  Something could be said for being able to convincingly explain why you're right to your coworkers/manager, without hurting their feelings (even though they might be stubborn about it at first). That's a precious soft skill.
hvidgaard 10y ago
It would be fairly simple to create an argument he cannot refute. Make a hashtable with 4 slots, put 16 elements in it, even with perfect distribution it would have to look through 4 elements to find the last one. This means it takes O(1/4n), or, since constants doesn't matter O(n). If he cannot accept that I would simply walk out and inform them that I could not take the job seriously, when the interviewer don't know such a basic thing.
- hthh 10y ago
  Dynamic resizing fixes this, although hash collisions can still be a problem (albeit a very unlikely one if your hash is secure). https://en.wikipedia.org/wiki/Hash_table#Dynamic_resizing https://en.wikipedia.org/wiki/Hash_table#Dynamic_resizing
  - wongarsu 10y ago
    Yes, there are implemenations of hash tables that solve this problem. Hash collisions still ruin your worst case performance, but as long as nobody is asking how long you spend on inserts you can solve that too. As a trivial example, on each insert make the hashtable larger and change the hash function randomly until you found a solution that has O(1) lookup for all elements. But now we're far outside the realm of "properties of hash tables" and instead inside "properties of my hash table", and any decent interviewer should recognize that.
    - lorantt 10y ago
      I think people here seem to implicitly assume linked buckets, those are bad on modern architectures for several reasons. Look at (Hopscotch,) Robin Hood or Cuckoo Hashing for hashing with linear probing, high fill factor (~0.9) and _amortized_ O(1). I've seen a paper somewhere that proved Robin Hood worst-case O(log log n) afair. http://www.sebastiansylvan.com/post/robin-hood-hashing-should-be-your-default-hash-table-implementation/ http://www.sebastiansylvan.com/post/robin-hood-hashing-shoul... https://en.m.wikipedia.org/wiki/Hopscotch_hashing https://en.m.wikipedia.org/wiki/Hopscotch_hashing You can make open probing performantly concurrent with 2 bytes of memory overhead per key/value too: http://preshing.com/20160314/leapfrog-probing/ http://preshing.com/20160314/leapfrog-probing/
grosbisou 10y ago
These are my favorite interviews. I can't just let the interviewers go when I sense some bullshit... I mean if you want to drill people on something it should be expected you know everything about it. No surprise I fail most interviews! Like the CTO of a famous startup who didn't understand that the order of a multicolumn index has some importance. I died a few minutes later when he told me I should add an index on a boolean (whereas the queries didn't use it) because it would speed up the queries by 2. Best day of my life.
quickben 10y ago
The rule is that you ignore the constant. O(5) is still O(1). It is not 1 but that's the agreement. In your specific case maybe you both weren't aware of the nomenclature? In any case, they did you a favor. If you are arguing about hash tables from the start, who knows how it will be when you ask for vacation or sick days.
- Udo 10y ago
  > In your specific case maybe you both weren't aware of the nomenclature? Well, "always O(1)" is simply wrong in my opinion. This may be a cultural thing, but I'm used to referring to the worst case behavior in big O as a default, so I would have said something along the lines of "the worst case is O(n) and that can turn out to be problematic in some cases". And normally interviewers do want you to talk about these kind of corner cases. I don't think I'm using the nomenclature wrong, and I certainly didn't ever refer to something as O(5) which as far as I can tell is not and should never a thing... To my best recollection, the question came up as a dynamic language issue. Specifically what the interviewer wanted to hear is that accessing (both read and write) an object property in JavaScript is always O(1), since it's a hash map access under the hood. Leaving aside for a moment that this is fuzzily untrue in a typically JITed environment, it's also untrue in general. You could try to make a case for that when doing a read on a specially optimized hash table, but it would certainly not be true in the general case where you also add things to the table. But all of these considerations are already way too detailed and far beyond what the interviewer wanted to talk about. They just wanted to check off "knows it's a hash table under the hood" and "knows that hash tables are always O(1)", even though both of these are untrue in my opinion.
  - zzzcpan 10y ago
    Isn't it too implementation specific to simply claim worst-case as O(1) or O(n)? Depending on how much memory is acceptable to waste and how fast insertions should be worst-case could range from O(1) to O(n).
    - Udo 10y ago
      I would not consider a table where the data size of the hashed keys equals the data size of the unhashed keys a hash map. If you got, say, a u8 as a key, and your lookup table uses u8s for keys internally, that's not what most people would refer to as a hash table. It's simply a lookup array. In all the usual cases, the hashed key size is way less than the unhashed key size, and you need to pay the price for collisions somewhere.

by Udo 10y ago

arethuza 10y ago

Sounds to me more like the interviewer/company flunked you're test rather than you flunking - you might have dodged a bullet there.

Udo 10y ago
I wouldn't have worked for the interviewer, it's often just a gatekeeper you need to overcome. Also, when you don't know how to make rent next month and the company seems pretty cool (apart from that person), it's hard to see at the time how you dodged any bullets...
- arethuza 10y ago
  If someone reacts badly when you know more than they do then that's not a great bit of behaviour, if a company chooses such a person as an interviewer then that's a bit of a red flag to me - an interview should be as much about trying to present a positive image of the company as much as testing the interviewer. Sorry to hear about the rent situation - I take that worked out OK eventually?
  - Udo 10y ago
    > if a company chooses such a person as an interviewer then that's a bit of a red flag to me I think the basic corporate rules of signalling competence apply here. Assuming that person was both technologically and socially incompetent (which might be too harsh of a judgement), some people still have a way of getting promoted into valuable positions by appearing to do a great job. > Sorry to hear about the rent situation - I take that worked out OK eventually? Thankfully that was some years back, I'm doing okay today :)
    - arethuza 10y ago
      "which might be too harsh of a judgement" Not sure it is - the usual advice is "if in doubt then don't hire" so why not apply that to employers as well as employees? Of course, if there is an element of desperation involved then I can understand it. But I have walked away from interview processes (or turned down offers) when I had some worries and never really regretted it. Harshness both ways would seem to be fair.
marklgr 10y ago
Something could be said for being able to convincingly explain why you're right to your coworkers/manager, without hurting their feelings (even though they might be stubborn about it at first). That's a precious soft skill.

hvidgaard 10y ago

It would be fairly simple to create an argument he cannot refute. Make a hashtable with 4 slots, put 16 elements in it, even with perfect distribution it would have to look through 4 elements to find the last one. This means it takes O(1/4n), or, since constants doesn't matter O(n). If he cannot accept that I would simply walk out and inform them that I could not take the job seriously, when the interviewer don't know such a basic thing.

hthh 10y ago
Dynamic resizing fixes this, although hash collisions can still be a problem (albeit a very unlikely one if your hash is secure). https://en.wikipedia.org/wiki/Hash_table#Dynamic_resizing https://en.wikipedia.org/wiki/Hash_table#Dynamic_resizing
- wongarsu 10y ago
  Yes, there are implemenations of hash tables that solve this problem. Hash collisions still ruin your worst case performance, but as long as nobody is asking how long you spend on inserts you can solve that too. As a trivial example, on each insert make the hashtable larger and change the hash function randomly until you found a solution that has O(1) lookup for all elements. But now we're far outside the realm of "properties of hash tables" and instead inside "properties of my hash table", and any decent interviewer should recognize that.
  - lorantt 10y ago
    I think people here seem to implicitly assume linked buckets, those are bad on modern architectures for several reasons. Look at (Hopscotch,) Robin Hood or Cuckoo Hashing for hashing with linear probing, high fill factor (~0.9) and _amortized_ O(1). I've seen a paper somewhere that proved Robin Hood worst-case O(log log n) afair. http://www.sebastiansylvan.com/post/robin-hood-hashing-should-be-your-default-hash-table-implementation/ http://www.sebastiansylvan.com/post/robin-hood-hashing-shoul... https://en.m.wikipedia.org/wiki/Hopscotch_hashing https://en.m.wikipedia.org/wiki/Hopscotch_hashing You can make open probing performantly concurrent with 2 bytes of memory overhead per key/value too: http://preshing.com/20160314/leapfrog-probing/ http://preshing.com/20160314/leapfrog-probing/

grosbisou 10y ago

These are my favorite interviews. I can't just let the interviewers go when I sense some bullshit... I mean if you want to drill people on something it should be expected you know everything about it. No surprise I fail most interviews! Like the CTO of a famous startup who didn't understand that the order of a multicolumn index has some importance. I died a few minutes later when he told me I should add an index on a boolean (whereas the queries didn't use it) because it would speed up the queries by 2. Best day of my life.

quickben 10y ago

The rule is that you ignore the constant. O(5) is still O(1). It is not 1 but that's the agreement. In your specific case maybe you both weren't aware of the nomenclature? In any case, they did you a favor. If you are arguing about hash tables from the start, who knows how it will be when you ask for vacation or sick days.

Udo 10y ago
> In your specific case maybe you both weren't aware of the nomenclature? Well, "always O(1)" is simply wrong in my opinion. This may be a cultural thing, but I'm used to referring to the worst case behavior in big O as a default, so I would have said something along the lines of "the worst case is O(n) and that can turn out to be problematic in some cases". And normally interviewers do want you to talk about these kind of corner cases. I don't think I'm using the nomenclature wrong, and I certainly didn't ever refer to something as O(5) which as far as I can tell is not and should never a thing... To my best recollection, the question came up as a dynamic language issue. Specifically what the interviewer wanted to hear is that accessing (both read and write) an object property in JavaScript is always O(1), since it's a hash map access under the hood. Leaving aside for a moment that this is fuzzily untrue in a typically JITed environment, it's also untrue in general. You could try to make a case for that when doing a read on a specially optimized hash table, but it would certainly not be true in the general case where you also add things to the table. But all of these considerations are already way too detailed and far beyond what the interviewer wanted to talk about. They just wanted to check off "knows it's a hash table under the hood" and "knows that hash tables are always O(1)", even though both of these are untrue in my opinion.
- zzzcpan 10y ago
  Isn't it too implementation specific to simply claim worst-case as O(1) or O(n)? Depending on how much memory is acceptable to waste and how fast insertions should be worst-case could range from O(1) to O(n).
  - Udo 10y ago
    I would not consider a table where the data size of the hashed keys equals the data size of the unhashed keys a hash map. If you got, say, a u8 as a key, and your lookup table uses u8s for keys internally, that's not what most people would refer to as a hash table. It's simply a lookup array. In all the usual cases, the hashed key size is way less than the unhashed key size, and you need to pay the price for collisions somewhere.