Storing recent search phrases
A LinkedHashSet would be simpler:


When the size reaches the limit, simply remove the first entry, no need to iterate
When adding an entry, if it already exists, you'd have to reinsert it to update the order: remove and then add
No more need to worry about the time of insert


Another advantage of this method is that the entries will be naturally ordered. In your current solution they are unordered, which could appear odd to users. This is not a big advantage though, because you could easily sort before returning the collection.