Link prediction has a variety of applications in real world such as social tie prediction, e-commerce recommendation and protein-protein interaction prediction in biological networks. For example, in social networks, social actors and their ties (friendship or collaboration) are represented as nodes and links, and link prediction can be applied to predict new ties to be formed in the future. Most classical approaches predict links by computing some notion of ``similarity'' between nodes based on graph topological structure but few consider node attributes (e.g. researcher's affiliation or research interest in co-authorship network), which also contain critical information for link prediction. Additionally, since links can form based on different types of relationships, similarities across different relationships may be non-transitive--meaning, similarity based on one type of relationship does not necessarily consistent with similarity in another type of relationship. However, existing link prediction methods do not consider the non-transitive similarity, which leads to poor prediction results when considering multiple relationships. In this paper, we developan semi-supervised link prediction method via a Multi-Component Hashing framework. We derive multiple hashing tables for nodes in the network with each hash table corresponding to a particular type of similarity aspect such as pre-existing collaboration or topical interest. New links could be predicted based on whether nodes are closer in the hashing tables. Results on several datasets show that our approach outperforms the state-of-art unsupervised and supervised methods. The results also show superior performance of our method in cold-start link prediction setting, where we have no knowledge of network topology.