Complicated question. Let's see what happens.
You instantiate a new instance, which is backed with new array. So, garbage collector should clear all the key and values from the previous map, and clear the reference to itself. So O(n) algorithm is executed anyway, but in the garbage collector thread. For 1000 records you won't see any difference.
BUT. The performance guide tells you that it is always better not to create new objects, if you can. So I would go with clear()
method.
Anyway, try both variants and try to measure. Always measure!
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…