5 ms·

Just my two cents, Well hash tables might be O(1), but depending on the circumstance they are used in, how they handle collisions, implementation details and th

Just my two cents, Well hash tables might be O(1), but depending on the circumstance they are used in, how they handle collisions, implementation details and the quality of the hashing algorithm they can see real world performance that is not O(1). Inserting into a hash table can cause the hash table to expand, if the hash table is too small you will get collisions, etc. etc. Some choices of hash functions are actual O(n) instead of O(1). Sometimes hash tables are not appropriate due to the memory requirements. You get the idea. I actually like people to point these things out, even if the amortized cost is constant in lots of real world usage. When talking about time complexity I appreciate attention to detail, rather then just hand waving and saying its constant. My answer is always, 'well it depends'. Be careful though, back up your answers in a way that shows you do know what you are doing. Otherwise you can come off as blowing smoke. Truly understanding writing performance critical code is a black art, and you need to understand more then just the big O of some common algorithms. Showing that you know that performance and complexity are hard and you know there are hidden costs that can bite you and tradeoffs you have to take into account shows maturity.

Swizec 14y ago
Yes yes, of course. But the answer most certainly isn't "Well I don't know _exactly_ how python does dictionaries, but I would implement them with a prefix tree and there is nothing better". Which is roughly the answer I gave, in different settings. To five interviewers.
haberman 14y ago
> Some choices of hash functions are actual O(n) instead of O(1) I think you're getting your n's confused. O(n) in the context of a collection applies to the size of the collection, not the size of the keys. Nearly all hash functions for strings are O(n) in the size of the string. This doesn't mean the hash table is O(n) for lookups.
- jhartmann 14y ago
  My point is the whole process needs to be taken into consideration when talking about performance and runtime complexity. If you just use the address of an object for the hash, that has a implication to performance. If you choose a cryptographic function, that has another implication. If you use something like cityhash, that has yet another. If you use rehashing or a linked list to handle collisions that has another impact on the performance depending on what is going on. If you choose to auto grow the hash table upon a certain number of collisions, this is another thing you have to worry about. The process of lookup might use a precalculated cache of the hash code calculation if it is expensive and sacrifice some memory for this storage. My point of all these examples is that the simple runtime of the collection isn't the whole story and lots of crap can happen under the covers. We stand on the shoulders of giants, but we have to know what weaknesses and strengths we are exploiting. While just picking the right data (or wrong) structure makes a huge impact, you need a lifetime of experience to really know what matters, and what the trade off of one or another is in a given scenario. Hard to test for that intuition and I always like people that interview with me that start talking about these sorts of issues.
  - haberman 14y ago
    I understand and agree with your point. I was just making one small correction.

Swizec 14y ago

Yes yes, of course. But the answer most certainly isn't "Well I don't know _exactly_ how python does dictionaries, but I would implement them with a prefix tree and there is nothing better". Which is roughly the answer I gave, in different settings. To five interviewers.

haberman 14y ago

> Some choices of hash functions are actual O(n) instead of O(1) I think you're getting your n's confused. O(n) in the context of a collection applies to the size of the collection, not the size of the keys. Nearly all hash functions for strings are O(n) in the size of the string. This doesn't mean the hash table is O(n) for lookups.

jhartmann 14y ago
My point is the whole process needs to be taken into consideration when talking about performance and runtime complexity. If you just use the address of an object for the hash, that has a implication to performance. If you choose a cryptographic function, that has another implication. If you use something like cityhash, that has yet another. If you use rehashing or a linked list to handle collisions that has another impact on the performance depending on what is going on. If you choose to auto grow the hash table upon a certain number of collisions, this is another thing you have to worry about. The process of lookup might use a precalculated cache of the hash code calculation if it is expensive and sacrifice some memory for this storage. My point of all these examples is that the simple runtime of the collection isn't the whole story and lots of crap can happen under the covers. We stand on the shoulders of giants, but we have to know what weaknesses and strengths we are exploiting. While just picking the right data (or wrong) structure makes a huge impact, you need a lifetime of experience to really know what matters, and what the trade off of one or another is in a given scenario. Hard to test for that intuition and I always like people that interview with me that start talking about these sorts of issues.
- haberman 14y ago
  I understand and agree with your point. I was just making one small correction.