Tables Within Tables: C++ and Brent's Technique

One of the primary goals of object-oriented programming is to enable programmers to create code that is reusable and applicable to more than one project. The C++ class facility is one way to address that goal. This article explores the use of the class facility in C++ to write generic code and shows an implementation of an interesting variation on hashing known as "Brent's technique."

Brent's technique was invented by R.P. Brent, a computer scientist and mathematician about whom I know little other than his citations in Donald Knuth's The Art of Computer Programming, Vol 3: Sorting and Searching. Brent's technique is a variation on the primary/secondary hashing technique Knuth calls "Algorithm D" (Listing One).

INSERT IS
  address = H1(data)
  if table[address] is empty
    insert data in table[address]
  else
    address = H1(data) + H2(data)
    while table[address] isn't empty
      address = address + H2(data)
    end while
  end if
  insert data in table[address]

LOOKUP IS
  address = H1(data)
  if table[address] isn't equal to data then
    address = H1(data) + H2(data)
    while table[address] isn't equal to data and
      table[address] isn't empty
      address = address + H2(data)
    end while
  end if
  if table[address] is empty then
    return empty
  else
    return table[address]
  end if