CMPT280 Trees and Hashing

Open Addressing

If a collision occurs, algorithm searches for alternative index to store the item.

Linear Probing

The algorithm checks subsequent indices (modulo N) until a spot is found. A form of open addressing.

Quadratic Probing

Rather than checking subsequent indices sequentially, it checks indices at increasing quadratic intervals to prevent clustering.

Double Hashing

Uses a second hash function to determine the step size for probing, further reducing clustering.

Separate Chaining

Rather then storing colliding items into the array itself, each array index contains a list to store all items that hash to the same index.

Load Factor

A measure of how full a hash table is, calculated as the number of entries divided by the number of slots. It influences the performance of insertions, deletions, and lookups.

Hash tables store records that are ______

keyed data items implemented using arrays. the hash function determines where this goes.

As long as the algorithm used to hash keys into array indexes is _______, then insertion operations searching the hash table are also _____

constant time

Collision

hash function hashing two different keys to the same index

Linear Probing

probing forwards or backwards through the array at a fixed interval. We do a linear search for an available index forward through the array, wrapping around the beginning if we reach the end, which is modulo N. (Modulo being the leftover).

Using Quadratic Probing, where do we go if the hash index 8 is occupied?

If the hash index 8 is occupied, we check index 8 + 1 mod 10 = 9. If that is also occupied, we proceed to index 8 + 2^2 mod 10 = 2, then 8 + 3^2 mod 10 = 7, and so on until we find an open index.

What is linear search’s time complexity in the worst case for searching arrays?

O(n)

What is binary search’s worst time complexity for searching arrays?

O(logn)

Insertion of items into hash tables is achieved by

obtaining an item’s key, hashing it to the array index, then it’s placed into that location.

Double Hashing

A variation of linear probing where the probe increment p(j) depends on the key being hashed.

What are the two hash functions?

Primary Hash Function h(k): Standard has function used to determine intial index for key k in hash table.

Secondary Hash Function h2(k): Different hash function used to determine probe increment p(j).

Separate Chaining

When used, the items to be inserted into hash table are not stored in the array. Instead, each entry in the array refers to a container ADT that holds all of the items that hashed to that array. Most efficient to use a list, linked lists are usually used and resemble chains.

For a small load factor, what’s the time complexity?

O(1)

Why lists for hash? Why not AVL trees?

• The number of different items hashing to one single index is usually quite small relative to the number of entries in the entire hash table.

• For very small collections, the overhead of the AVL trees makes them slower than just doing a linear search of a small list.

• Separate chaining gets its name because linked lists are usually used and they resemble chains.

If the load factor is 2, there must be __ items on each linked list on average

2. So we only need to ever search one list.

If the load factor is 5, there must be ____ items on each linked list on average

5. To search one list, we will have to examine with equal probability either 1, 2, 3, 4, or 5 items.

Thus, the average number of items examined on a list of average length will be:
(1+2+3+4+5)/5 = 15/5 = 3

It takes only ____ to remove the item from the linked list.

O(1)

For finding the item we want to delete, the average case time complexity is the same as for searching; ____ where ___ is the load factor.

O(LF), LF

For finding the item we want to delete, the average worst case is that all items are on the same list and we have to search through all of them: _____, where ____ is the number of items in the hash table

O(k), k

For finding the item we want to delete, the best case is that we find the item to be deleted right away: ______

O(1).

The search and inert operations of a hash table are _____, if hash table’s load factor is small (less than 1).

O(1)

When the load factor is small, insertion shouldn’t have more than two or three items hashing to any given index: _____

O(1).

Searching for alternate indices we will only have to look at a small, fixed number of indices

O(1)

How do we keep the load factor small in order to increase performance for search and insert operations?

Increasing the size (doubling) the table array when the load factor gets too high.

• When the load factor exceeds 0.75, a new larger array is created, and all items already in the hash table are re-hashed to locations in the new array.

In general, the average number of items hashing to the same index is equal to the load factor, and searching of alternate indices becomes _____

O(LF), with LF being load factor.