Good read, Great papers, but I would like to add some points.
We prefer balanced BST (red-black, AVL, or any other) because of its efficient successor lookup guarantees. HashMap, due to its unordered nature can provide only O(n) successor lookup, while balanced BST can do it in O(logN)
Why do we need successor/predecessor? In order to find the node to which the request should be directed we hash it and check the successor node (for the hashed id) in the consistent hashing ring.