It all depends on what you want to do with your matrices. Various operations have various costs in different sparse matrix formats. The standard ones are COO or coordinate format: a list of triples (i, j, val); DOK or dictionary of keys format: the hashmap you are thinking of; LIL or list of lists format: a list for each row and a list if pairs (j, val) in each list entry; CSR/CSC or compact sparse row/column: an array of indices where each row starts, an array of column indices and an array of values.
COO and DOK are great for changing sparsity structure; LIL is very useful if you have a lot of row-wise (or column-wise) operations, or need to manipulate rows regularly. CSR is great for matrix operations such as multiplication, addition etc. You use what suits your usecase, or change between formats (relatively cheap) as needed.