How to avoid creating objects to check or get content from Maps in Java

Question

I am implementing my own Map in Java, using a custom class I made.

I already implemented the hashCode and equals without any problem.

I just have a question more related into performance and stuff like that.

So I will check many times in my application if a specific value is inside the map, for that, for that I have to create a object and then use the methods containsKey of Map.

My question is...

Is there any other way? without being always creating the object??? I cant have all the objects in my context universe, so that isn't a way...

I know I can just point the object to 'null' after using it, but still, it's not so elegant, creating objects just to check if there is the same object inside =S

Are there any other conventions?

Thank you very much in advance!

EDIT:

Stuff typed = new Stuff(stuff1, stuff2, (char) stuff3); 
                        if(StuffWarehouse.containsKey(typed))
                        {
                            //do stuff
                        }

                        //after this I won't want to use that object again so...
                        typed = null;