Department of Computer Science & Engineering

We present a novel extension to passbits providing significant reduction to unsuccessful search lengths for open addressing collision resolution hashing. Both experimental and analytical results included demonstrate the dramatic reductions possible. This method does not restrict the hashing table configuration parameters and utilizes very little additional storage space per bucket. The runtime performance for insertion is essentially the same as for ordinary open addressing with passbits; the successful search lengths remain the same as for open addressing without passbits; the unsuccessful search lengths can be made to be arbitrarily close to one bucket access for any desired loading factor.

Pre-2018 CSE ID: CS2000-0658