Parallel binary searches on lengths using hash tables is described. The parallel search uses more than one search instance. The search instances probe in parallel mutually different contiguous ranges of a search area during each round of searches. After each round, a new search area is defined and one or more search instances are redeployed into the new search area. The search instance for a range of shorter lengths can be redirected to help those of the longer lengths. Due to the help from other search instances, some ranges can be made large without sacrificing the performance. The invention realizes faster address lookups even for longer address lengths.