Abstract: To accurately and efficiently estimate the network size of distributed Hash table (DHT), an algorithm based on the average interval is proposed. The algorithm makes use of the property that the intervals between nodes obey the exponential distribution to estimate the network size. From the simplest condition, the number of estimated intervals is gradually increased and the probabilistic distribution and the confidential interval of estimating values are quantitatively analyzed. According to the analysis, if we adopt multiple intervals to estimate the networks size, the estimated value of the network size will obey the tail Gamma distribution with the parameter (k,k). Finally, simulations are carried out to verify the validity of the algorithms and the correctness of the analysis.