You could attempt to mix both 1 and 2.
Instead of creating 1000 maps, create, say, 64 and apply a partitioning scheme based on (the hash of) tenant key, like
IMap<Object,Object>[] caches = ...
public <T> void put(T tenant,Object key,Object value){
IMap<Object,Object> cache = cacheFor(tenant);
cache.put(tenantKey(tenant,key),value);
}
public <T> Serializable tenantKey(T tenant,Object key){
//Any class representation suitable for searching by the tenant key. Usually, implement IdentifiedDataSerializable instead
}
IMap<Object,Object> cacheFor(T tenant){
return caches[hash(tenant) & (caches.length - 1)]; //only works for power of two arrays.
}
<T> int hash(T tenant){
return tenant.hashCode(); //Or apply any suitable normalization for better hashing
}
Search by tenant id will be amortized amongst the caches, since ideally, each cache will hold 1/64 of the tenant-aware keys, compared to having a single cache.