Week 8. Maps and Dictionaries

Map

Map

A map models a searchable collection of key-value entries. The main operations consist of searching, inserting and deleting items. Multiple entries with the same key are not allowed.

Link to original

Map ADT

Map (ADT)

The Map ADT consists of the methods:

• get(k): if map $M$ has an entry $e=(k,v)$, return $v$; else null.
• put(k,v): if $M$ does not have an entry $(k,v)$ then add it to the map $M$ and return null; otherwise, replace $v$ with the new value and return the old value.
• remove(k): if the map $M$ has entry with key $k$, remove it from $M$ and return associated value otherwise return null.
• size(): return number of entries in $M$
• isEmpty(): test whether $M$ is empty
• entrySet(): return an iterable collection of entries in $M$
• keySet(): return an iterable collection of keys in $M$
• values(): return an iterator of the values in $M$

Link to original

List-based Map Implementation

We can implement a map using an unsorted list. We store the items of the map in a double-linked list $S$.

Pseudo-code implementations of common operations:

def get(k):
	B = S.positions() # iterator over positions
	while B.hasNext():
		p = B.next()
		if p.element().getKey() == k:
			return p.element().getValue()
	
	return null
 
def put(k,v):
	B = S.positions()
	while B.hasNext():
		p = B.next()
		if p.element().getKey() == k:
			# if it's in map, return and replace
			t = p.element().getValue()
			p.element().setValue(v)
			return t
 
	# if key is not in map, append
	S.append((k,v))
	n += 1 # increment no. of entries
	return null
 
def remove(k):
	B = S.positions()
	while B.hasNext():
		p = B.next()
		if p.element().getKey() == k:
			t = p.element().getValue()
			S.remove(p)
			n -= 1
			return t
 
	return null

In terms of performance, all of these methods take $O(n)$ time since in the worst case, the item is not found and we traverse the entire list to look for an item with the given key. This implementation is only effective for maps of small size.

Hash Table

Hash Table

Hash Tables are used to implement a Map, they consist of two main components:

• Bucket Array

  Bucket Array: array $A$ of size $N$ where each cell of $A$ is thought of as a “bucket” (collection of key-value pairs)

  Link to original

• Hash Function

  A hash function $h(x)$ has the properties:

  • Compression: $h$ maps an input of $x$ of arbitrary bit length to an output $h(x)$ of fixed bit length $n$ which may be smaller
  • Polynomial time computable

  Link to original

When implementing a map with a hash table, we store the item $(k,v)$ at the index $i=h(k)$.

Link to original

Hash Functions

A Hash Function is usually specified as the composition of two functions:

• Hash Code

  Hash Code $h_1$: $\text{keys}\to \text{integers}$ There are quite a few ways we can convert keys:

  • Memory address: we reinterpret the memory address of the key object as an integer (default hash code for Java objects)
  • Integer cast: we reinterpret the bits of the key as an integer
  • Component sum: we partition the bits of the key into fixed length components, and sum the components (ignoring overflow)

  Link to original

• Compression Function

  Compression function $h_2$: $\text{integers}\to [0,N-1]$ We need to ensure the probability of two different keys getting hashed to the same bucket is $\frac{1}{N}$. We can use:

  • Division: $h_2(y)=y\mathrm{mod}N$ where $N$ is usually chosen to be a prime
  • Multiply, Add and Divide: $h_2(y)=[(ay)+b)\mathrm{mod}p]\mathrm{mod}N$ Where $N$ is the size of the bucket array, $p$ is a prime number greater than $N$, and $a$ / $b$ are integers chosen at random from the interval $[0,p-1]$ with $a>0$.

  Link to original

The hash function applies the hash code function then the compression function; $h(x)=h_2(h_1(x))$.

Collision Handling

Collisions occur when different elements are mapped to the same bucket, there are different ways we can handle collisions:

• Separate Chaining

  Separate Chaining: let each cell in the table point to a linked list of entries. This is simple but required additional memory outside of the table.

  

  Link to original

• Open Addressing

  Open addressing: the colliding item is placed in a different cell of the table, each table cell inspected is referred to as a “probe”. Colliding items lump together, causing future collisions to cause a longer sequence of probes. There are three different ways we can handle this:

  • Linear Probing

    Linear Probing: handles collisions by placing the colliding item in the next (circularly) available table cell. If we try to insert a key $(k,v)$ into a cell $i$ that is already occupied, we try again at $(i+1)\mathrm{mod}N$ (and repeat until we find an empty cell to insert into).

    In order to get(k):

    • We start at cell $h(k)$
    • Probe consecutive locations until one of the following occurs:
      • item with key $k$ is found
      • empty cell is found
      • $N$ cells have been unsuccessfully probed

    Example pseudo-code:

    def get(k):
    	i = h(k)
    	p = 0
    	repeat:
    		c = A[i]
    		if c == null:
    			return null
    		else if c.getKey() == k:
    			return c.getValue()
    		else:
    			i = (i + 1) mod N
    			p += 1
    	until p == N
    	return null

    In order to remove(k):

    • search for an entry with key $k$
    • if such an entry $(k,v)$ is found, replace it with special item “available” and we return element $v$
    • else, return $null$

    In order to put(k,v):

    • throw an exception if the table is full
    • start at cell $h(k)$
    • probe consecutive cells until:
      • a cell $i$ is found that is either empty or stores “available”
      • or until $N$ cells have been unsuccessfully probed
    • we store $(k,v)$ in cell $i$

    Link to original

  • Double Hashing

    Double Hashing: we use a secondary hash function $h^{\prime }(k)$. If $h$ maps some key $k$ to a cell $A[i]$ with $i=h(k)$, that is already occupied, then we iteratively try the buckets:

    $$A[(i+f(j))\text{ mod }N]\text{ for }j=1,2,\dots ,N-1$$

    Where $f(j)=j\cdot h^{\prime }(k)$.

    The secondary hash function $h^{\prime }(k)$ cannot have zero values. The table size $N$ must be prime to allow probing of all of the cells.

    A common choice of compression function for the secondary hash function:

    $$h^{\prime }(k)=q-k\text{ mod }q$$

    Where $q<N$ and $q$ is prime.

    Link to original

  • Quadratic Hashing: (not incl., p.396, individual study)

  Link to original

Hash Performance

In the worst case: searches, insertions and removals on a hash table take $O(n)$ time. The worst case occurs when all keys inserted into the map collide.

Load Factor (Hashing)

The load factor $\alpha =\frac{n}{N}$ affects the performance of a hash table. Assuming that the hash values are like random numbers, it can be shown that the expected number of probes for an insertion with open addressing is $\frac{1}{1-\alpha }$.

Link to original

Rehashing (Hashing)

To keep hashing performance up, we need to keep the load factor $\alpha$ low. We use rehashing to do so:

• whenever the load factor becomes too large (e.g. greater than 0.5):
• create a new bucket approx. double the size of the old one
• iterate all elements in old bucket array and put them in the new bucket

Link to original

Dictionary

Dictionary

A dictionary models a searchable collection of key-value entries. The main operations of a dictionary are searching, inserting and deleting items. Multiple items with the same key are allowed.

Link to original

Dictionary ADT

Dictionary (ADT)

A dictionary typically implements the methods:

• get(k): if the dictionary $D$ has an entry with key $k$, return it otherwise null
• getAll(k): returns an iterable collection of all entries with key $k$
• put(k,v): inserts into the dictionary $D$ and returns entry $(k,v)$
• remove(e): removes the entry $e$ from the dictionary and returns the removed entry; an error occurs if entry is not in the dictionary $D$
• entrySet(): returns an iterable collection of the entries in the dictionary
• Additional methods: size(), isEmpty().

Link to original

Dictionary Implementations

There are different ways we can implement a dictionary:

• List-Based Dictionary: usually a log file or audit trail is a dictionary backed by an unsorted sequence; we store the items in an array or doubly-linked list in any arbitrary order. Performance:

  • put takes $O(1)$ time since we can insert the new item at the beginning or the end of the sequence
  • get and remove take $O(n)$ time since in the worst case, we traverse the entire sequence to look for an item with the given key

• Hash Table Implementation: we can also create a hash-table backed dictionary; if we used separate chaining to handle collision: then each operation can be delegated to a list-based dictionary stored at each hash table cell

• Ordered Search Table: we can also choose to back the dictionary using a sorted / ordered array; we store the items of the dictionary in an array-based sequence sorted by the key.

  A search table is only effective for dictionaries of small size or where searches are the most common operations while changes are uncommon.

  Performance:

  • get takes $O(\log n)$ time using binary search
  • put takes $O(n)$ time since in the worst case, we may have to shift $\frac{n}{2}$ items to make room for the new item
  • remove has the same time as put