Closed Addressing vs Open Addressing

comparisonhash

What to prefer

Closed Addressing for efficiency
Open Addressing for local memory management

Dictionary Performances

Here listed below we compare some data structures we saw in this course, and we compare their times of executions for some dictionary-related operations, as dictionaries are indeed a kind of dynamic set.

Just to clarify:

$x$ is the element to which the operations Predecessor and Successor is applied to.
$n$ is the input size of the problems
$m$ is the table size for hash-tables and $α$ is their load factor
$h$ is the height of the tree for the Binary Search Tree

Data Structure	Search	Minimum	Maximum	Predecessor	Successor	Construction	Delete
Closed Address Hashtables (average case)	$Θ (1 + α)$	$Θ (m + n)$	$Θ (m + n)$	$O (m + n)$	$O (m + n)$	$Θ (n)$
Closed Address Hashtables (worst case)	$O (n)$	$Θ (m + n)$	$Θ (m + n)$	$O (m + n)$	$O (m + n)$	$Θ (n)$
Open Address Hashtables (average case)	$O (1 / (1 - α))$	$Θ (m)$	$Θ (m)$	$O (m)$	$O (m)$	$O (n / (1 - α))$
Open Address Hashtables (worst case)	$O (n)$	$Θ (m)$	$Θ (m)$	$O (m)$	$O (m)$	$O (n^{2})$
Non-decreasing Sorted Array	$O (l o g (n))$	$Θ (1)$	$Θ (n)$				$O (n)$
Non-Increasing Sorted Array	$O (l o g (n))$	$Θ (n)$	$Θ (1)$				$O (n)$
Non-decreasing Sorted Double-Linked List with Sentinel	$O (n)$						$Θ (n)$
Non-decreasing Sorted Double-Linked List with Sentinel	$O (n)$						$Θ (n)$
Binary Search Tree	$O (h)$	$O (h)$	$O (h)$	$O (h)$	$O (h)$	$Θ (n l o g (n))$
Balanced Binary Search Tree
Max-Heap	$O (n)$		$Θ (1)$		$O (n)$	$Θ (n)$
Min-Heap	$O (n)$	$Θ (1)$		$O (n)$		$Θ (n)$

Hashtables

As we know, hash-tables do not have any efficient primitive operation to find the Successor or Predecessor. This means:

Closed Address hash-tables must traverse the $m$ cells and examine the $n$ keys in the lists.
Open Address hash-tables must traverse the $m$ cells

In both case we might stop before, so we use a big O notation.

While for the Minimum and Maximum we need to check the whole content of the table, obtaining respectively the same results with $Θ$ notation instead.

For what regards the Construction

For Closed Address hash-tables, this represents $n$ Insertion, which have constant time.
- We insert the elements on top of the list in both cases
For Open Address hash-tables, this represents $n$ Search, which depend on the load factor
- In the average case, it depends on the load factor (see the related theorems)
- In the worst case, for $n$ keys we need to use the Search which has linear time.

Finally the Search depends

For Closed Address hash-tables
- In the average case, it depends on the load factor (see the related theorems)
- In the worst case, it depends on the input size as one list contains all the elements.
For Open Address hash-tables
- In the average case, it depends on the load factor (see the related theorems)
- In the worst case, all the $n$ inspections result in finding an occupied slot. Which means we need to iterate through the $n$ keys.

Closed Addressing vs Open Addressing ​

Dictionary Performances ​

Hashtables ​

Closed Addressing vs Open Addressing

Dictionary Performances

Hashtables