My question was more along the lines of "there's a lot about red-black trees that I could know, but don't. What does he expect me to know about hash tables that I hadn't already told him?"
It's helpful to remember that nobody knows how to hire good candidates (it's an unsolved problem) so everyone has their own favorite, ineffective techniques. This results in a lot of puzzling behavior, like being told you need more red-black tree knowledge.
There's probably no way to know what they were looking for, short of asking them directly. But you have at least two options: (a) roll your eyes at anyone who tells you that you need more knowledge about red-black trees or hash tables to be an excellent engineer, or (b) realize it's a game, and play it with a passion.
Both routes are perfectly valid, and personally I prefer route (a). But if you're deciding to do route (b), you could study as much as you can on the subjects, quiz yourself on various trivia related to red-black trees, look up related interview questions, etc.
This is a bit of a tangent, but from a motivation standpoint, I've found it's optimal to think of interviews as a lottery ticket with 10% chance of winning regardless of your ability, rather than an as an obstacle that can be failed due to lack of ability. There's no reason to be discouraged when someone rejects you in a world where people reject engineers for reasons that are essentially random.
