Map with different types for values
No Type Safety

Currently your classes provide no type safety:

Cache cache = new Cache();
cache.put("my key", Integer.class, 5);
// ...
String cached = cache.get("my key", String.class);


This compiles but fails at runtime with a ClassCastException thrown by CachedValue.getValue.

What's The Key?

The reason why this can happen is that your class is not clear on the role of the type given to put and get. Considering the internal map, the type is clearly part of the value. But get uses it as it were part of the key. This makes it possible to request a value which is there (considering the string key in the map) but of the wrong type.

Compare this to the typesafe heterogeneous container as defined in Effective Java. There the type is part of the key (actually the only part) so if something is found in the map, it must be of the correct type. It is hence safe to cast to that type.

So in order to make your classes type safe you have to decide on what exactly the key is.

String

If the key is only the string, I see no way to provide type safety. To keep the API from surprising its users you should then simply return Object. This effectively degrades your cache to a map from String to Object, which I guess is not your intention.

String &amp; Class

The other possiblitiy is to make the type a full memeber of the key. There are several ways to implement this and I only present one. It uses nested maps which define this mapping:

String -&gt; (Class -&gt; Object)


This can be interpreted as

(String, Class) -&gt; Object


so the type is part of the key.

public class Cache {

  private final Map&lt;String, Map&lt;Class&lt;?&gt;, Object&gt;&gt; internalMap;

  public Cache() {
    internalMap = new HashMap&lt;&gt;();
  }

  public &lt;T&gt; void put(String textKey, Class&lt;T&gt; typeKey, T chachedValue) {
    Map&lt;Class&lt;?&gt;, Object&gt; mapForTextKey = getMapForTextKey(textKey);
    mapForTextKey.put(typeKey, chachedValue);
  }

  private Map&lt;Class&lt;?&gt;, Object&gt; getMapForTextKey(String textKey) {
    if (!internalMap.containsKey(textKey))
      internalMap.put(textKey, new HashMap&lt;&gt;());
    return internalMap.get(textKey);
  }

  public &lt;T&gt; T get(String textKey, Class&lt;T&gt; typeKey) {
    Object untypedCachedValue = getUntyped(textKey, typeKey);
    // the cast can not fail because:
    // - if there is no value for those keys, the argument is null,
    //      which can always be cast
    // - if there is a value for those keys, `put` made sure that
    //      its type matches the type used as a key
    return typeKey.cast(untypedCachedValue);
  }

  private Object getUntyped(String textKey, Class&lt;?&gt; typeKey) {
    if (internalMap.containsKey(textKey))
      return internalMap.get(textKey).get(typeKey);
    else
      return null;
  }

}


Improvements

My proposal above is only the barebones of an implementation. There is a lot of room for improvements. Some of them are:


handling null aftert answering these questions:

should it be valid for keys? (please not!)
should it be valid for values? (also rather not; doesn't seem to make a lot of sense for a cache)

let get return an Optional&lt;T&gt;
use Map.computeIfAbsent for more concise code
or use Guava's Table instead of the nested maps
designing the class for extensibility or making it final


Furhter Comments After The Update

Looks much better. :) These comments are mostly nitpicking...

Comments regarding the code:


About null:

@NotNull is nice but as far as I know it's purely for tools. To have a runtime guarantee you should add Objects.requireNonNull. On the other hand, you use the HashBasedTable so you're fine  - it's documentation says: "Null row keys, columns keys, and values are not supported.". If you rely on that, you should declare table as that type and make sure do write a comment explaining this unusual decision (normally you declare the interface as you did).
I'd also make typeKey not-nullable.
I like the use of Optional (see here how much). I recommend to use Java 8's version because I expect it to become more common than guava's version.

Since Table.getis so concise, getUntyped looks a little pointless now. I would remove the method.
I like logging the calls. For symmetry I would also add it to put.


On style:


You are very liberal with empty lines. I'd recommend to not do that and only insert an empty line to separate distinct blocks. There seems to be little need for that in the code above.