# LinearHashTable: Linear Probing

Learn to implement a LinearHashTable.

## Open addressing

The `ChainedHashTable`

data structure uses an array of lists, where the
$i^{th}$ list stores all elements `x`

such that `hash(x) = i`

. An alternative, called **open addressing**, is to store the elements directly in an array, `t`

, with each array location in `t`

storing at most one value. This approach is taken by the `LinearHashTable`

described in this section. In some places, this data
structure is described as open addressing with linear probing.

## Structure of `LinearHashTable`

The main idea behind a `LinearHashTable`

is that we would, ideally, like to store the element `x`

with hash value `i = hash(x)`

in the table location `t[i]`

. If we cannot do this (because some element is already stored there) then we try to store it at location `t[(i + 1) mod t.length]`

; if that’s not possible, then we try `t[(i+ 2) mod t.length]`

, and so on, until we find a place for `x`

.

There are three types of entries stored in `t`

:

- Data values: Actual values in the USet that we are representing;
`null`

values: At array locations where no data has ever been stored; and`del`

values: At array locations where data was once stored but that has since been deleted.

In addition to the counter, `n`

, that keeps track of the number of elements
in the `LinearHashTable`

, a counter, `q`

, keeps track of the number of elements of Types 1 and 3. That is, `q`

is equal to `n`

plus the number of del
values in `t`

. To make this work efficiently, we need t to be considerably
larger than `q`

, so that there are lots of null values in `t`

. The operations on
a `LinearHashTable`

therefore maintain the invariant that $\text{t.length} \ge 2q$.

To summarize, a `LinearHashTable`

contains an array, `t`

, that stores
data elements, and integers `n`

and `q`

that keep track of the number of
data elements and non-`null`

values of `t`

, respectively. Because many hash
functions only work for table sizes that are a power of $2$, we also keep an
integer `d`

and maintain the invariant that $\text{t.length} = 2^{d}.$

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy