Is there any way how to get the key (or the whole entry) from a `Map`?

NavigableMap has ceilingKey, which would let you use equals on the returned Key to see if there is an entry for that exact key. But you couldn't use HashMap, you'd need TreeMap or something, which might negate any memory performance benefits (and your keys would need to implement Comparable). Also, the javadoc doesn't say whether the returned key is the exact same object used in the Map, so it might be implementation specific.

How much evil are you prepared to commit in order to do this?

The Map interface does not let you retrieve a key or an entry. Nor does the Set interface. Nor does HashMap's public interface.

But HashMap's package interface does (in the Sun JDK, at least). Have a look at the source code; at line 355, there is a method called getEntry which starts like this:

  /**
   * Returns the entry associated with the specified key in the
   * HashMap.  Returns null if the HashMap contains no mapping
   * for the key.
   */
  final Entry<K,V> getEntry(Object key) {

I believe that is exactly what you need. You can call this with reflection, or by sneaking a class of your own into the java.util package. The Java maintainers could take this method away in the future, and it might not be present on all platforms, but if you're prepared to hold your nose and take the risk, it's a simple solution.

I found another workaround, taking advantage of the implementation of the elements (or keys) comparisons in the Collections (or maps).

All collections (or maps) implementations in java.util (as far as I know) are comparing elements by o.equals(e) when o is the user searched object. So I came up with the following solution:

public static <K> K getOriginalKey(final Map<K, ?> map, final K key) {
    OriginalElementExtractor extractor = new OriginalElementExtractor(key);
    map.containsKey(extractor);
    return (K) extractor.result;
}

public static <E> E getOriginalElement(final Collection<E> coll, final E element) {
    OriginalElementExtractor extractor = new OriginalElementExtractor(element);
    coll.contains(extractor);
    return (E) extractor.result;
}

private static class OriginalElementExtractor {

    final Object key;
    final int hash;
    Object result;

    OriginalElementExtractor(final Object key) {
        this.key = key;
        hash = key.hashCode();
    }

    @Override
    public boolean equals(final Object o) {
        boolean eq;
        if (eq = key.equals(o))
            result = o;
        return eq;
    }

    @Override
    public int hashCode() {
        return hash;
    }
}

The Collection (or map) will invoke the OriginalElementExtractor.equals(Object) method to check for equality, and the original element will be passed.