  For any forest $G = (V, E)$ it is possible to orient the edges $E$ so that no
vertex in $V$ has out-degree greater than $1$. This paper considers the
incremental edge-orientation problem, in which the edges $E$ arrive over time
and the algorithm must maintain a low-out-degree edge orientation at all times.
We give an algorithm that maintains a maximum out-degree of $3$ while flipping
at most $O(\log \log n)$ edge orientations per edge insertion, with high
probability in $n$. The algorithm requires worst-case time $O(\log n \log \log
n)$ per insertion, and takes amortized time $O(1)$. The previous state of the
art required up to $O(\log n / \log \log n)$ edge flips per insertion.
  We then apply our edge-orientation results to the problem of dynamic Cuckoo
hashing. The problem of designing simple families $\mathcal{H}$ of hash
functions that are compatible with Cuckoo hashing has received extensive
attention. These families $\mathcal{H}$ are known to satisfy \emph{static
guarantees}, but do not come typically with \emph{dynamic guarantees} for the
running time of inserts and deletes. We show how to transform static guarantees
(for $1$-associativity) into near-state-of-the-art dynamic guarantees (for
$O(1)$-associativity) in a black-box fashion. Rather than relying on the family
$\mathcal{H}$ to supply randomness, as in past work, we instead rely on
randomness within our table-maintenance algorithm.
