Locality-sensitive hashing (LSH) is an effective randomized technique widely used in many machine learning tasks for Case-Based Reasoning community, such as outlier detection, neural network training and nearest neighbor search, all of which are important to the Case-Based Reasoning (CBR) community. The cost of hashing is the main performance bottleneck of these applications because the index construction functionality, a core component dominating the end-to-end latency, involves the evaluation of a large number of hash functions. Surprisingly, however, little work has been done to improve the efficiency of LSH computation. In this paper, we design a simple yet efficient LSH scheme, named FastLSH, by combining random sampling and random projection. FastLSH reduces the hashing complexity from O(n) to O(m) ( $$m