> This is how

    Open a Type Hierarchy
    Expand a node that starts a background job
    Before the Job has finished, select a new entity for the Type Hierarchy (this will invoke inputChanged)
    Now when the background job finishes it will update the cache with nodes that are entirely unrelated to the current hierarchy!

Yeah! I'm glad we agree :)

> So it seems that the main culprit is the background job. What if we change the findInBackground method such that it only updates the cache if the input is the same as when the job started?

This could work, but you likely need to make sure the compare-and-set is atomic. Give it a try and push a further commit, I'll happy to look at it :)