Please explain this question

#1

If ‘h’ is the hashing function and is used to hash n keys into a table of size s, where n<=s, the expected number of collision involving a particular key X is

less than n/2

less than s

less than n

less than 1

#2

Please explain this:Give the space complexity for removing the specified characters in a string which are given in another string using the concept of Hashing (Consider the length of both strings to be n) O(n) O(logN) O(1)

#3

Consider a hash table of size m = 10000, and the hash function h(K) = floor (m(KA mod 1)) for A = ( √(5) – 1)/2. The key 123456 is mapped to location . 45 41 43 48

#4

Using Hashing finding a pair in the array (of length n) having a given sum has time complexity of: O(1) O(N) O(N^2) O(logN)

#5

Okay I will look into these all and explain it in a single response

#6

For the first question, the answer is less than 1 as n <= s so all keys have space to go without collision
For the second the answer is O(N) as we just need to iterate over the string once and characters can be searched from hash table in O(1) time
For the third answer is 41 as
h(123456) = floor(10000 * (123456 * (√5 − 1) / 2) mod 1)
= floor(10000 * (76300.004115 mod 1)
= floor(10000 * (.004115))
= 41.15
= 41
for the final also the answer is O(N) as we have to search all elements in the worst case