Anomaly detection is one of the most important data mining tasks in many real-life applications such as network intrusion detection for cybersecurity and medical diagnosis for healthcare. In the big data era, these applications demand fast and versatile anomaly detection capability to handle various types of increasingly huge-volume data. However, existing detection methods are either slow due to high computational complexity, or unable to deal with complicated anomalies like local anomalies. In this paper, we propose a novel anomaly detection method named OPHiForest with the use of the order preserving hashing based isolation forest. The core idea is to learn the information from data to construct better isolation forest structure than the state-of-the-art methods like iForest and LSHiForest, which can achieve robust detection of various anomaly types. We design a fast two-step learning process for the order preserving hashing scheme. This leads to stronger order preservation for better hashing, and therefore enhances anomaly detection robustness and accuracy. Extensive experiments on both synthetic and real-world data sets demonstrate that our method is highly robust and scalable.