Not N! it's N^2. N! very big values.
1) no, cache used as binary tree search time always log(N), it's only take time to load data and take RAM.
2) reasonable suggestion, we think about "purge cache" button.
3) yes cache uses absolutly pathes, because how we can found file equivalence ? For calculation hash or checksum we need disk access that takes time.