Consistent Hashing PseudoCode

Consideration

LinkedList

We can choose to use a linkedlist to represent a cycle. However the complexity will be high since we want to have a sorted list for quick lookup.

Time complexity

• Add: $O(n)$ — since needs to add in the correct index
• Hash: $O(n)$ — since needs to traverse through each index to find the correct index (hash)

SkipList

Skiplist would be an improvement from linkedlist because now we can have quick lookup and search.

Time complexity

• Add: $O(logn)$
• Hash: $O(logn)$

SortedMap

Sorted map would be a better datastructure since we can have $O(1)$ access.

Time complexity:

• Add: $O(logn)$
• Hash: $O(1)$

Implementation

Ring = TreeMap<>(String, Server) // key: Hash value: Server

replicateNumber = 5

Function add(Server server):
	For i in range(0, replicateNumber):
	serverId = hash(server, i)
	ring.put(serverId, server)

Function remove(Server server):
	// we don’t need to worry about rehashing other items because that should be the job of the client 
	For i in range(0, replicateNumber):
			serverId = hash(server, i)
	ring.remove(serverId)

Function hash(item): // return the corresponding correct server for that item
	itemId = hash(item)
	
	serverId = ring.tailMap(itemId).firstKey():
	
	If serverId == null:
		serverId = ring.firstKey() // map back to the beginning of the ring
	
	Return ring.get(serverId)