Anomaly detection has practical signifi-cance for finding unusual patterns in time series.How-ever,most existing algorithms may lose some im-portant information in time series presentation and have high time complexity.Another problem is that privacy-preserving was not taken into account in these algorithms.In this paper,we propose a new data struc-ture named Interval Hash Table (IHTable) to capture more original information of time series and design a fast anomaly detection algorithm based on Inter-val Hash Table (ADIHT).The key insight of ADIHT is distributions of normal subsequences are always similar while distributions of anomaly subsequences are different and random by contrast.Furthermore,to make our proposed algorithm fit for anomaly de-tection under multiple participation,we propose a privacy-preserving anomaly detection scheme named OP-ADIHT based on ADIHT and homomorphic en-cryption.Compared with existing anomaly detection schemes with privacy-preserving,OP-ADIHT needs less communication cost and calculation cost.Secu-rity analysis of different circumstances also shows that OP-ADIHT will not leak the privacy information of participants.Extensive experiments results show that ADIHT can outperform most anomaly detection algo-rithms and perform close to the best results in terms of AUC-ROC,and ADIHT needs the least time.