Additional Context

Each integer requires 4 bytes of space. Can we store them all in memory? If not, how do we sort them if we can’t store all at once?

Discuss. Design your best solution. (5-10 minutes.)

Induction

To prove a statement for every number $n$:

1. Prove that the statement is true when $n=0$. (Base case)
2. Prove that, for any natural number $k$, if the statement is true when $n=k$ (fixed), then the statement still holds for $n=k+1$. (Inductive step)

Base case: h = 0

• Prove that there are $2^1-1$ nodes in a complete binary tree of height $0$, assuming the last level is completely filled.
• What is a tree of height 0?

Inductive step

• Suppose we know that, for some arbitrary $h$, there are $2^{h+1}-1$ nodes in a complete binary tree of height $h$, assuming the last level is completely filled.
• Consider a complete binary tree of height $h+1$. What does that look like?
  • Has a root, which has two subtrees… of height?
  • (Using inductive assumption) How many nodes in those subtrees?
  • Therefore: how many nodes total?
• Conclusion: this tree has $2^{h+2}-1$ nodes.

Set operations

For our perspective, we consider the following operations on a set:

• contains
• insert
• remove
• size

Sometimes “insert” / “remove” are boolean methods, to indicate whether you were able to successfully modify the set (returning false, for example, if you tried to insert a duplicate).

Possible implementations

• ArrayList? Already has these operations. Running times? Can you get $O(1)$ insert if you don’t allow duplicates?
• Tree?
  • Generic type must implement Comparable
  • Trees have contains / insert / remove.
  • We can impelment a “size” easily, just keep track of it whenever we call insert or remove.
  • Our implementation didn’t allow duplicates.
  • Running times?

ArrayList implementation

Exercise: Using an ArrayList, implement the Set interface. Analyze the time complexity of contains / insert / remove.

Starter code?

Better Implementation?

• All we care about: is $x$ in the set or not?
• Do we need to store elements in order?
• Focus on integers:
  • Trade-off: use a huge amount of space.
  • Can we make insert / remove / contains $O(1)$?

Operating?

• Add a data item to the set?
  • Compute $f(item)$, insert item into table[f(item)]
• Check if item is in the set? Check table[f(item)] == null
• Remove?

Hashtables

• This is the idea behind a hashtable.
• Lots of analysis needs to be done
  • How do we define a good hash function?
  • What is the likelihood of a collision?
  • What happens if there are collisions?

Video

Example

• Example (integer keys): $h(x)=x$ mod $s$.
• In what scenarios would this be a good hash function?
• Bad?
• Choose a good table size $s$ to avoid these problems?

String Keys

Simple idea: think of a word as a number in base 27 (“a” represents the digit 1, and “z” represents the digit 27), then convert it to an integer.

• “abc” hashes to ${27}^2\times 1+27\times 2+3$.
• What do we do if this value ends up larger than the hashtable size?
• Any major problem with this approach? (Hint: what characters can make up a String?)

Let’s look at the built-in hash function for Strings in Java.

Video

Probability

Insert $N$ items into a table of size $s$. Suppose the hash function is uniform. What’s the probability of a collision?

• $N=2,s=4$?
  • Two elements: $x$ and $y$.
  • Probability that $h(x)==h(y)$?
  • Probability that $h(x)\ne h(y)$ is 3/4, so probabiliyt of collision is $1/4$.

N = 3, s = 9

• Three: $x,y,z$. Probability that $h(x)==h(y)$ or $h(x)==h(z)$ or $h(y)==h(z)$?
• Maybe easier to solve: probability that $h(x)$, $h(y)$ and $h(z)$ are all different!
• Probability of a collision then is $1-Prob(h(x),h(y),h(z)$ are different$)$.

N = 4, s = 9

• Same idea, first find the probability that all four hash values are different
• Then subtract from 1.

Birthday Problem

• $N=23$, $s=365$ is the famous birthday problem!
• In a room with 23 people, there is a greater than 50% chance that two of them have the same birthday!
• What does this have to do with hash collisions?
  • What’s the “hash function” here?
  • What are the “keys” here?
• In general, if $N>\sqrt{s}$, there is a good chance of a collision.

Video

Think about

As we learn about these, keep this question in mind: in what scenarios (in terms of the table size $s$ and the number of insertions $N$) might we prefer one scheme over the other?

Load Factor

• Let $N$ be number of elements to insert into the table.
• Let $s$ be the size of the table.
• $\lambda ={\displaystyle \frac{N}{s}}$ is called the load factor of the table.
• $\lambda$ small: few collisions, lots of wasted space
• $\lambda$ large: space used efficiently, but high chance of collisions.

Separate Chaining

• Don’t keep a “large array”.
• Instead: keep an array of $s$ lists.
• Think of each list as a “bucket” (or “bin”).
• Elements that hash to the same value go in to the same bucket.

Image

Running times

• Insert $x$: compute hashcode $h(x)$, add $x$ to the $h(x)$-th list.
• Running time of insert?
• contains: compute the hash function, check the relevant list.
• Running time (average case)? Worst case?
• What happens as $\lambda$ increases?
• Can we keep a bound on $\lambda$?

Rehashing

• If we allow $\lambda$ to increase without bound, performance degrades.
• Many implementations (including Java’s) will rehash if it increases too much.
• Increase the size of the table (usually: pick the next prime number $p>2s$).
• Go through each previously inserted item, and re-insert into the new table.
• Should not happen too often, so that we still get (amortized) constant time inserts.

Image

Video