A protein contact map is a simplified, two-dimensional version of the three-dimensional protein structure. Protein contact map is proved to be crucial in forming the three-dimensional structure. Contact map prediction has now become an indispensable and promising intermediate step towards final three-dimensional structure prediction, while directed sequence-structure prediction hits its bottlenecks. In this article, different evaluation scores of prediction efficiency are compared. Next, the state of the art and future perspectives of contact map methods are reviewed and special attention is paid to those relying on machine learning algorithms. Details of neural network based methods as well as a list of machine learning based methods are given. Finally, bottlenecks and potential improvements of contact map predictions are discussed.