A verificação da existência de chaves no HashMap é sempre necessária?

Eu tenho um HashMap com, digamos, 1000 entradas e estou procurando melhorar a eficiência. Se o HashMap estiver sendo acessado com muita frequência, verificar a existência da chave em cada acesso levará a uma grande sobrecarga. Em vez disso, se a chave não estiver presente e, portanto, ocorrer uma exceção, eu posso capturar a exceção. (quando eu sei que isso acontecerá raramente). Isso reduzirá os acessos ao HashMap pela metade.

Isso pode não ser uma boa prática de programação, mas me ajudará a reduzir o número de acessos. Ou estou faltando alguma coisa aqui?

[Atualizar] Eu não tenho valores nulos no HashMap.