Consistent hashing minimizes remapping when servers change. Servers and request keys are hashed onto a ring. Each request goes to the next server clockwise from its position.
When you add a server, only requests between it and the previous server remap. When you remove one, only that server's requests move. Most clients stay on their original servers.
Time complexity is using a balanced tree to find the next server. Space is for the ring.
Use consistent hashing for caching layers where remapping causes cache misses.