Anti-jamming communication without pre-shared secrets has gained increasing research interest recently and is commonly tackled by utilizing the technique of uncoordinated frequency hopping (UFH). Existing researches, however, are almost all based on ad hoc designs of frequency hopping strategies, lacking of theoretical foundations for scheme design and performance evaluation. To fill this gap, this paper introduces the online optimization theory into the solution and, for the first time, makes thorough quantitative performance characterization possible for UFH-based anti-jamming communications. Specifically, we propose an efficient online UFH algorithm achieving asymptotic optimum and analytically prove its optimality under different message coding scenarios. Extensive simulative evaluations are conducted to validate our theoretical analysis under both oblivious and adaptive jamming strategies.