Yes, the free spaces remain and they add up to the used memory of a map. It becomes worse the bigger a map is- but then again, big maps aren't very performant anyway. I talked about this issue with Cvet some years ago, he considered this for future optimization, but it doesn't have a very high place on a "stuff to do"-list (and I doubt that it's easy to do).