Searching a "multimap" in C

[Jared T]

So I am working on extending the CSPARSE library, and I'm having some trouble. I need to be able to access the sparse matrix at random positions throughout my program in fast time. The author does this by converting the matrix to a compressed column matrix. However the conversion process takes several loops and so converting back would be the same. The other option is to use the matrix in triplet form, which is a linear indexed array

i j x | n

so to find x, we must linearly search all n for both i and j. This runs in O(N) time.
Of course this is very simple to write, but it can't be the most efficient way. I have thought of doing a binary search, but there's no way I can think of that doesn't do the search twice or involve copying and storing.

I thought of sorting the matrix, but doing this every time I want to access it is way too slow.

Does anyone have a smarter idea?

[weaknessforcats]

Can you use a chain-link table?

You hash the data value to an array location. That location is the start of a linked list for other data that also hashes to that location. With a good hash (or an algorithm) you mght be able to minimize the use of the linked list.

Sedgewick had a reasonable write-up on this.

Being able to calculate the array location from the data saves all the search time.