DSA - Hash Tables

Question 1

What is a Hash Function?.

Answer 1

hash(key) computes the location from a KEY

Question 2

Does it matter what Data Type is when we use the hash function?

Answer 2

NO

Question 3

How Does a Hash Table Work?

Answer 3

Take the key calculate some number without referencing the key or record, use the number for a index in the array.

Get Us Immediately in 1 step where we want to be

Question 4

Where do you store KEY?

Answer 4

Store it in Linked List/ Tree/ Hash Table

Question 5

Describe assignments in Hash Table ?

Answer 5

-It is O(1) time complexity
- Very Memory Inefficient
==> Need an Array of size 10^7, if we only use 500 spaces it
still keeps the rest thus very inefficient.

Question 6

Define Hash/Data Collison:

Answer 6

2 Different Keys with same number of finding remainder to place in that index

• Increasing array length may cause an decrease in the
  likeness of collisions. (Does Not Fully Remove Them)
• Require a robust & reliable solution to resolve collisions

Question 7

What Does Hash Table Consists of:

Answer 7

• Array arr for storing the values
• hash function hash(KEY) => turns Key into index of array
• Mechanism for dealing with the collisions

Question 8

What are the 2 Types of solutions of hash Collisions?

Answer 8

-Chaining Strategy
- Open Addressing Strategy

Question 9

What does Chaining Strategy do?

Answer 9

Use another data structure on each position of the hash tables
-Only Chaining Strategy is Direct Chaining
- Use Linked List to store the values with the
same hash(code)

Question 10

What does Addressing Strategy do?
GIVE THE 2 EXAMPLES ?

Answer 10

Finding a different address in the same array for the colliding value to be stored
(ADDRESS MUST BE UNUSED or OPEN)
- Two Strategy are Linear Probing & Double Hashing

Question 11

How to Insert with Direct Chaining?

Answer 11

• Always check if the key which we are inserting is in the LL on position hash(key)
• If isn’t insert key at BEG of list

// DOES NOT NEED TO INSERT KEY IN BEG, BUT IN PRATICE IT IS IDEAL AS THE KEY IS MORE LIKELY TO BE ACCESSED SOON

TAKE O(n) = need to go through all elements already stored in hash table

Question 12

How to Delete with Direct Chaining?

Answer 12

To delete(key) we delete key from LL stored in Position hash(key)

Takes O(n)

Question 13

How to do Lookup in Direct Chaining?

Answer 13

lookup(key) return TRUE/FALSE, depending if key is stored in the list on position hash(key)

Question 14

What is a Bad Hash Function?

Answer 14

-All entries have the same hash value
- 1 LARGE Linked List (LL)

Question 15

Why is a Bad Hash Function BAD?

Answer 15

Has LARGE linear search through those links

Question 16

What makes a GOOD Hash Function?

Answer 16

• Uniformly distributes keys among positions
• Given a Random key it has to have the same probability of being stored on every position
• location given by hash has the expected number of entries stored there equal to n/T.

Question 17

What is the Load Factor?

Answer 17

AVG. NO. of entries stored on a Location
n/T
n = total number of store entries
T = size of hash table

REPRESENTS HOW FULL THE HASH TABLE IS

Question 18

What is Unsuccessful lookup of a Key?

Answer 18

• Key is not in the table
• Location hash(key) stores n/T entries on AVG.
  (Have TRAVERSE them all, LINEAR SEARCH on
  n/T entries )

Question 19

What is a Successful Lookup for a key?

Answer 19

• Location hash(key) stores k = n/t entries on AVG
• AVG. a linear search in LL of k elements takes
  1/k(1+2+…+k) = k(k+1)/2k = (k+1)/2 comparisons
• ASSUME MAX load Factor λ that is, n/T <= λ

Question 20

What is AVG case time complexity of unsuccessful lookup?

Answer 20

n/T <= λ comparisons O(1)

Question 21

What is AVG case time complexity of successful lookup?

Answer 21

1/2(1+n/T) <= 1/2(1+λ) Comparisons O(1)

λ is constant

Question 22

Time Complexity of insert(key)?

Answer 22

• Same as unsuccessful lookup
  O(1)
• First Check if the key is stored in the table
• Otherwise insert key at BEG of list stored on hash(key)

Question 23

Time Complexity of delete(key)?

Answer 23

Same as Successful Lookup
O(1)

Question 24

Time Complexity of Insert?

Answer 24

O(1)

Question 25

What 2 Assumptions are made for Direct Chaining?

Answer 25

1. We have a good Hash function - Expected Length of chains is n/T 2. We assume a maximal load Factor - n/T < λ, constant λ (MAKE SURE LOAD FACTO IT IS BOUNDED BY SOME λ) Assume the 2 Conditions , computed that the operations of Hash Table are ALL O(1). Good Hash Function Depends on Distribution of data - CONSTANT TIME COMPLEXITY WILL BE AMORTIZED ONLY

Question 26

Disadvantage of Chaining Strategies?

Answer 26

1) Lot of hash collisions, therefore lots of unused space - Good Performance maintain a low Load Factor {Between 0.25-0.75} - At 0.25 you are using an array 4x the entries you are going to store in hash table (A LOT OF UNUSED SPACE) 2) LL require a lot of allocation (ALLOCATE MEMORY), which is slow - Every Insert you need to allocate Memory - Not only using space in the array, but allocating memory is a heavy method to call.

Question 27

What is the Idea of Insertion in LINEAR PROBING?

Answer 27

If primary position hash(key) is occupied, search for 1st available position to the right of it. REACH END WRAP AROUND

Question 28

How to compute the Fallback Positions For LINEAR PROBING?

Answer 28

- Increment the value of hash(key) by 1 MOD the value by size of the array. Repeat until you find FREE SPACE - E.g => hash(key) + 1 mod T T = size of the array

Question 29

Idea of Deleting using Linear Probing?

Answer 29

1- Find the key stored in table: - Start from primary position hash(key) go right until key or empty position is found. 2- Key is stored in the table, replace it with a marker value (TOMBSTONE = #) DO Probing until you find # or empty space and replace it with new value

Question 30

Issue With Deleting in LINEAR PROBING?

Answer 30

Delete Data Collision value, the one stored in the correct hash position, when searching for element in that hash position will return false as nothing is there for key value. Untrue as we had to move the data collision to next free space. This leads to error as we don't find key value from the data collision

Question 31

Linear Probing Searching?

Answer 31

- Start from Primary Position hash(key) - Search for key to the right. - Skip over # TOMBSTONES - If we reach Empty Position, key is not in table

Question 32

Linear Probing Inserting MORE ACCURATE

Answer 32

- Search for hash(key) like Searching - NOTE first Tombstone Position we find - Find the Key signal ERROR - Reach Empty position, key not in table - Insert key into 1st Tombstone, if any - Otherwise, insert into Empty position found CAN'T INSERT TILL WE KNOW THAT THE KEY IS NOT ALREADY IN THE HASH TABLE.

Question 33

Time Complexity of Linear Probing?

Answer 33

Insert , Search & Delete ARE ALL O(1)

Question 34

Primary Cluster in LP ?

Answer 34

Clusters caused by entries with the same hash code.

Question 35

Secondary Clusters in LP?

Answer 35

When the Collision handling strategy causes different entries to check the same sequence of locations when they collide

Question 36

LP Problem with Clustering?

Answer 36

Clusters are more likely to get bigger and bigger, even if small load factor, Lots of Clusters means more probing, thus longer time taken USE DOUBLE HASHING TO MAKE CLUSTERING LESS LIKELY TO OCCUR

Question 37

What is Double Hashing?

Answer 37

Use a Primary & Secondary hash function Primary Hash: Landing place in our Array(Hash Value we go to in the array) - SPACE IS EMPTY OR # CAN USE IT Secondary Hash: add this result to primary key as an offset to find free space, repeat till we find free space. REDUCE PROBLEMS WITH SECONDARY CLUSTERS, SO FEWER COLLISIONS Different key values the offset will be different

Question 38

Difference Between Linear Probing and Double Hashing?

Answer 38

- Difference is that for different key values in DOUBLE HASHING the offset will also be different for every key value, due to secondary hash function ALL OPERATION WORK THE SAME WAY FOR BOTH

Question 39

Insertion Double Hashing?

Answer 39

Try Primary Position hash1(key) first and, if it fails, we try fallback positions: 1) hash1(key) + 1*hash2(key) MOD T 2) hash1(key) + 2*hash2(key) MOD T 3) hash1(key) + 3*hash2(key) MOD T REPEAT TILL WE FIND EMPTY SPACE T = size of the ARRAY

Question 40

Linear Probing Fallback Calculation?

Answer 40

(hash(key) + i) mod T i=1,2,3...

Question 41

Double Hashing Fallback Calculation?

Answer 41

(hash1(key) + i*hash2(key)) mod T i = 1,2,3,...

Question 42

Problem with Double Hashing?

Answer 42

Can have Short Cycles

Question 43

What are short cycles in Double Hashing?

Answer 43

Short cycle is a loop that occurs where after a few probes you get back to already visited block CAN'T FIT ANYMORE VALUES, MAYBE Spaces in odd Index Locations

Question 44

How to Fix Short Cycles?

Answer 44

Table Size T & hash2(key) are COPRIME 2 SOLUTIONS: 1) T is PRIME - Array is Prime, Won't get common Divisor - But, Difficult when growing array 2) T= 2^k and hash2(key) is ODD - Test if hash2(key) is ODD, if EVEN +1 - Just Setting Least Significant Bit so it is ODD - Works as no Common divisor between hash2 & T

Question 45

What is the problems with Large Common Divisor?

Answer 45

Worse it gets for missing values

Question 46

What does Coprime mean?

Answer 46

If no number other than 1, divides both a & b Prime numbers are the numbers which are divisible only by 1 and themselves

Question 47

For 2nd Solution for short cycles, why is the array of size 2^k?

Answer 47

-2^k therefore doubles it - Less fragmentation, however make sure Hash key values don't crash with Array Length DOUBLING THE SIZE OF THE ARRAY WHEN IT GETS FULL ENSURES T + 2^k

Question 48

What happens when table is Full?

Answer 48

Hash Table is full : n/T > λ If n/T is larger than λ does not meant it is not a full table

Question 49

What does n/T > λ mean?

Answer 49

If True allocate a new table twice the size and allocate values into new table

Question 50

The Idea of Rehashing?

Answer 50

Table becomes full after an insertion, allocate new table twice the size and INSERT all elements from old table to it CAN CACHE THE HASH FUNCTION VALUES, SO QUICKER TO PLACE INTO NEWLY ALLOCATED ARRAY

Question 51

Consequence of Insert?

Answer 51

The worst case time Complexity is O(n), when REHASHING AMORTIZED TIME COMPLEXITY is O(1)

Question 52

What do we need to do with the hash function when doubling array size?

Answer 52

Need to change hash function Usually: -bigHash(key) mod T (bigHash COMPUTES a Big Hashcode ) AFTER DOUBLE SIZE: bigHash(key) mod 2*T

Question 53

What is a Hash Table?

Answer 53

a ADTs with implementation consisting of a array arr, a primary function hash1(key) {maybe hash2(key)}

Question 54

Comparing Hash Table to Trees?

Answer 54

AVL: - Require keys to be comparable and the operations are in O(logn), BEST,AVG & WORST CASE HASH: - Require good Hash Functions, so operations are O(1) AMORTIZED time complexity FOR ALL OPERATIONS

Question 55

Double Hashing Pros over the other 2 Hash Table Methods?

Answer 55

Better Performance advantage: - Clustering in LP is Worse than DH - DC needs to allocate memory which has a large constant cost THIS PROS IS IN MULTIPLIER NOT ENTIRE COMPLEXITY

Question 56

What happens if load factor drops below min threshold?

Answer 56

RARELY Done as it doesn't speed up performance Rehash the into hash table 1/2 size. SAVE MEMORY

Question 57

What happens if the Number of Tombstone values exceed a threshold value?

Answer 57

Rehash without doubling the size - May get a Hash table 1/2 the size - CONSEQUENTLY delete is O(1) Amortized time complexity