3 ms·

Here are a few questions that are not explicitly answered in your post. How is the index into the array determined? What are the best and worst cases for algo

by tjalfi 9y ago

Here are a few questions that are not explicitly answered in your post. How is the index into the array determined? What are the best and worst cases for algorithmic complexity of a hash table? Disclaimer: I don't conduct interviews at my employer. If I did, I wouldn't ask about hash tables. I was asked to talk about hash tables in a Microsoft interview years ago and my accepted answer was much less detailed than yours. Edited to add an adjective.

thaumasiotes 9y ago
> How is the index into the array determined? Odd question. Theoretically, that choice is unique to the individual hash table, not a property of hash tables in general. I believe languages with default hash table implementations often use the machine address of the key, although obviously that won't work for keys that are compared by value, like integers and strings. I know there has been research into how to hash strings well, and I wouldn't be surprised if such research is still happening today. > What are the best and worst cases for algorithmic complexity of a hash table? What's a realistic worst case? A bucket-style table using linked list buckets will perform, at worst, as a linked list, except that if you add too much the backing store will be resized and everything will be rehashed. It would be quite a challenge to provide a large number of keys that all collided with each other for multiple sizes of backing array, assuming the hash function was decent. If you limit yourself to a small number of keys, the fact that you're seeing "worst-case" performance probably doesn't really matter.
- tjalfi 9y ago
  I'll try being explicit with my first question. What is a hash function? Edited to omit needless words.
  - hysan 9y ago
    Isn't that a bit of strange question to ask if you wanted someone to explain hash tables? If I brought in a candidate to interview for hash tables, I would probably expect them to already have a base covering hash functions. Otherwise, if you go down this rabbit hole, how deep does your knowledge about the basics have to be? Do you need to know every possible hash function? Their tradeoffs? Their probability distributions? The uses for each? Implementation details?

by tjalfi 9y ago

thaumasiotes 9y ago

> How is the index into the array determined? Odd question. Theoretically, that choice is unique to the individual hash table, not a property of hash tables in general. I believe languages with default hash table implementations often use the machine address of the key, although obviously that won't work for keys that are compared by value, like integers and strings. I know there has been research into how to hash strings well, and I wouldn't be surprised if such research is still happening today. > What are the best and worst cases for algorithmic complexity of a hash table? What's a realistic worst case? A bucket-style table using linked list buckets will perform, at worst, as a linked list, except that if you add too much the backing store will be resized and everything will be rehashed. It would be quite a challenge to provide a large number of keys that all collided with each other for multiple sizes of backing array, assuming the hash function was decent. If you limit yourself to a small number of keys, the fact that you're seeing "worst-case" performance probably doesn't really matter.

tjalfi 9y ago
I'll try being explicit with my first question. What is a hash function? Edited to omit needless words.
- hysan 9y ago
  Isn't that a bit of strange question to ask if you wanted someone to explain hash tables? If I brought in a candidate to interview for hash tables, I would probably expect them to already have a base covering hash functions. Otherwise, if you go down this rabbit hole, how deep does your knowledge about the basics have to be? Do you need to know every possible hash function? Their tradeoffs? Their probability distributions? The uses for each? Implementation details?