SI-7445 ListMap.tail is returning wrong result

Reverted the commit that introduced the bug, and modified HashMap to no
longer assume that tail is O(1).

Review by @Ichoran, @soc