HASH-BASED TRANSLATION METHOD AND APPARATUS WITH MULTIPLE LEVEL COLLISION RESOLUTION

摘要

A translation is performed by using a programmable hashing technique on an input number to generate a hashed number (408). A subset (410) of the hashed number bits are used to index a first hash table (420). In first hash table locations (426) where a hash collision does not occur, the first hash table entry (426) contains an index (for IDX) into an output (438) table which contains the desired translated output number (436). In first hash table locations where a hash collision occurs (424), the first hash table entry (494) contains a pointer (NTI) to a first resolution table area in a second hash table. The first resolution table area contains entries which are indexed by additional bits selected from the hashed number in accordance with a mask field in the first hash table location. If collisions occur in the resolution table a new resolution table is created and the process is repeated. The resolution process thus proceeds in stages until all input numbers have been translated.