nicolas - 1 year ago 80
C Question

# hashing of an integer vector for fast querying

I represent a monomial with a 3x2 vector. For example,

``````x y z   : ( (variable id, exponent of variable) )

: ( (1,1) , (2, 1) , (3,1) )

x^2 z^2 : ( (1,2) , (3,2) , (null, null) )
``````

The total number of distinct variable is one million, but a monomial contains at most three distinct variables.

I want to do query like

1. Is
`x`
in the monomial
`y^2 z^2`
?

2. Is the power of
`y`
greater than
`3`
in
`y^2 z^2`
?

Is there a hash function that will answer those question in O(1)?

Or should I just loop over the 3x2 vector?

I ask because I maintain a hash table with 5 millions of such monomial.
So, by default, I must use a hashing structure to do a search.
Maybe there is an hashing scheme that can also answer the two questions above.

Related question: best codebook for manipulation of monomials

• `n` which is the number of variables, and
• `m` which is the number of monomials.
It doesn't matter how big (or small) `m` and `n` are, looping over the vector always takes the same amount of time, so it's technically an O(1) operation.