In wireless communication systems, the accurate and reliable evaluation of channel capacity is believed to be a fundamental and critical issue for terminals. However, with the rapid development of wireless technology, large-scale communication networks with significant random interference have emerged, resulting in extremely high computational costs for capacity calculation. In ultra-dense wireless networks with extremely large numbers of base stations (BSs) and users, we provide fast estimation methods for determining the capacity. We consider two scenarios according to the ratio of the number of users to the number of BSs, $β_m$. First, when $β_m\leq1$, the FIsher-Spiked Estimation (FISE) algorithm is proposed to determine the capacity by modeling the channel matrix with random interference as a Fisher matrix. Second, when $β_m>1$, based on a closed-form expression for capacity estimation requiring solely simple computations, we prove that this estimation stabilizes and remains invariant with increasing $β_m$. Our methods can guarantee high accuracy on capacity estimation with low complexity, which is faster than the existing methods. Furthermore, our approaches exhibit excellent generality, free of network area shapes, BS and user distributions, and sub-network locations. Extensive simulation experiments across various scenarios demonstrate the high accuracy and robustness of our methods.