Knowing how binary heaps and hash maps work is great, because binary heaps and hash maps are very useful data structures, but knowing the fundamental reasons behind them in a way that composes to building new things is much more useful. What happens when you want properties that someone hasn't already built a data structure for, at least as far as you can find? (Pet example: ordered container with efficient append and the ability to query the maximum of any subslice length k in O(log k). Extension: what are the minimal assumptions you need to do better, eg. amortized O(1)?)

I think this contributes to the attitude where programs are built out of monolithic, ill-fitting parts rather than actually looking at the problem and building the solution which does the right thing, the right way. (Pet example: if you designed websites as data structures and the browser to support doing so efficiently, 90% of requests on a site like Reddit would be a single `memcpy`.)

What I would attempt is rather than saying

"Here's one way we could do it: <explaination of pre-baked hash table>."

talk about the underlying tool first

"One tool that can help us is hashing: <explaination of general technique and why its properties are useful>. In this example we want <these properties> but can't immediately get it because our data has <these properties>. But we can apply hashing to get <technique that looks decent but has caveats>. Handling the caveats by doing <hash table things> gives us a data structure called a hash table."

Yes, this is probably a harder way to handle things, but I'd like to think it'd be worth the trouble.