Re: Hashing OID's
- From: Aki Tuomi <cmouse@xxxxxxxxxxx>
- Date: Tue, 05 Sep 2006 17:56:38 +0300
Hallvard B Furuseth kirjoitti:
Aki Tuomi writes:
Any suggestions on how to hash SNMP Object ID's? Simple
sum'em'up and modulo or something more sophisticated?
If by sum'em'up you mean the sum of the components, no.
The standard variant would be
unsigned <int or long> hash = 0
for component in (all bytes or integers of the OID):
hash = A * hash + component
for some value of A.
Choosing a good A seems to be more magic than science, but it'll depend
on (at least)
- how your application represents OIDs,
- whether your hash table has size <power of 2> or <prime number> or
something else,
- how important speed vs. quality of the hash function is for you.
With ASCII representation, e.g. "1.3.6.1.4.1.111.4.1.1.1.8", and power
of 2 table size, I guess A=37 (binary 100101) is a good choice for a
reasonably fast hash. The 1 for steady change, the 100 for more rapid
change but still overlapping component values (since you basically have
a base-11 representation), and the 100000 to reach higher values more
quickly.
A typical OID consists of a number of small integers (1-2 digits) and a
few larger ones. So if your OIDs have a binary representation, you'll
want an A which makes small changes in the input cause large changes in
the output. Hopefully someone else can say more than me about that:-)
About OID representations, two common binary ones are:
- an array of integers (1 integer per component),
- or the ASN.1 BER/DER encoding:
a type and a length field, followed by the components in base 128,
big-endian, with bit 8 in each "digit" set if there are more digits
in the component. Also 1st represented component = 40*<1st actual
component> + <2nd actual component>.
Cheers! This helped quite a lot in fact.
Aki Tuomi
.
- References:
- Hashing OID's
- From: Aki Tuomi
- Re: Hashing OID's
- From: Hallvard B Furuseth
- Hashing OID's
- Prev by Date: What's the difference between tree-of-winner and tree-of-loser?
- Next by Date: Re: What's the difference between tree-of-winner and tree-of-loser?
- Previous by thread: Re: Hashing OID's
- Next by thread: Re: Hashing OID's
- Index(es):
Relevant Pages
|
