Open addressing

With this method a hash collision is resolved by probing, or searching through alternative locations in the array (the probe sequence) until either the target record is found, or an unused array slot is found, which indicates that there is no such key in the table.

[2][3][4][5][6] A critical influence on performance of an open addressing hash table is the load factor; that is, the proportion of the slots in the array that are used.

As the load factor increases towards 100%, the number of probes that may be required to find or insert a given key rises dramatically.

The methods above provide O(1) updating and removal of existing records, with occasional rebuilding if the high-water mark of the table size grows.

The O(1) remove method above is only possible in linearly probed hash tables with single-slot stepping.