We give two new randomized algorithms for tight renaming, both of which work against an adaptive adversary. The first uses repeated sampling over a sequence of arrays of decreasing size to assign unique names to each of $n$ processes with step complexity $O(\log^3 n)$. The second transforms any sorting network into a tight adaptive renaming protocol, with an expected cost equal to the depth of the sorting network. Using an AKS sorting network, this gives a tight adaptive renaming algorithm with step complexity $O(\log k)$, where $k$ is the contention in the current execution. We show this to be optimal based on a classic lower bound of Jayanti. We also show that any such tight renaming protocol can be used to build a monotone-consistent counter with logarithmic step complexity (at the cost of adding a max register) or a linearizable fetch-and-increment register (at the cost of increasing the step complexity by a logarithmic factor).