index = hashtable.search(data)
if (index != -1):
hashtable[index] = none
SHORT EXPLANATION
1. Find the index of the data which is to be deleted.
2. Set the data on the previously found index to none.
switch(hashtable.collisionResolution)
case "linear_probing":
key = data % hashtable.length
start = key
while(hashtable[key] != none)
key = (key + 1) %
hashtable.length
if(key == start)
return error
hashtable[key] = data
case "quadratic_probing":
step = 0
key = data % hashtable.length
while(hashtable[key] != none)
step += 1
key = (data +
step * step) % hashtable.length
if(step == hashtable.length)
return error
hashtable[key] = data
---------------------
| SHORT EXPLANATION |
---------------------
1. Determine which method of collision resolution the
hashtable (HT) uses. (There's usually just one.)
- no matter the method of collision resolution, the first
tested index gets calculated with: data % length of HT.
2. If there's already data stored at the previously
calculated index, calculate the next index where the data
can be stored.
- if the HT uses linear probing, the next possible index is
simply: (current index + 1) % length of HT.
- for quadratic probing, the index gets calculated like
this: (data + number of tries²) % length of HT
3. Repeat step 2 until the data was either inserted
successfully or
a) you've looped through the whole HT (linear
probing)
b) the number of tries = length of HT
(quadratic probing)
Time complexity:
Average case: O(1)
Worst case: O(n)
switch(hashtable.collisionResolution)
case "linear_probing":
key = data % hashtable.length
start = key
if(hashtable[key] == none)
return -1
while(hashtable[key] != data)
key = (key + 1) %
hashtable.length
if(key == start || hashtable[key] == none)
return -1
return key
case "quadratic_probing":
step = 0
key = data % hashtable.length
if(hashtable[key] == none)
return -1
while(hashtable[key] != data)
step += 1
key = (data +
step * step) % hashtable.length
if(step == hashtable.length || hashtable[key] == none)
return -1
return key
---------------------
| SHORT EXPLANATION |
---------------------
1. Determine which method of collision resolution the
hashtable (HT) uses. (There's usually just one.)
- no matter the method of collision resolution, the first
tested index gets calculated with: data % length of HT.
2a). There's nothing at the previously calculated index,
the searched data is not stored in the HT -> return
-1.
2b.) The searched data is stored at that index, return the
index.
2c). There is some data at the the index but it's not the
one you're looking for, proceed to step 3.
3. Calculate the next index to check in the same way it's
done when inserting data.
4. Repeat steps 2 and potentially 3 until the data has been
found, or until the abort criteria are met.
- the abort criteria are the same as when inserting data,
plus aborting when there's no data stored at an index.
Time complexity:
Average case: O(1)
Worst case: O(n)