Yeah I get the same feelings, in C# a dictionary is common for me, but I never use std::map in C++, and a hash-table is almost always implemented on top of a flat array... but this is because I'm writing real-time systems in C++ and bloated tools in C#.
It's funny, because ,y gut feel puts me in the same position with many constructs. Using dictionaries or regular expressions in Python, for example, is normal but in C++ I tend to avoid them because they're expensive.
No, exceptions in C++ are a fundamentally different construct than exceptions in Java, they just happen to share terminology. Plus most C++ compilers suck at implementing their flavour of them, while the JVM is good at it's flavour. If you port my benchmarks to Java, there's no way the throw version of the double-break idiom will be 2000x slower than the other implementations.
Any performance barrier is psychological: Java forces you to pay the cost always by design, C++ allows you to pay only for what you use, and you can avoid using exceptions, so you feel guilty about waste.