В WeakHashMap используются WeakReferences. А почему бы не создать SoftHashMap на SoftReferences? SoftHashMap представлена в сторонних библиотеках, например, в Apache Commons.