Give an example of a set H of hash functions such that h(x) is equally likely...

Question

Question

Give an example of a set H of hash functions such that h(x) is equally likely to be any element of {0, ..., M − 1} but H is not 2-universal.

Answer 1

Answer #1

Consider set H consists of M hash functions h0, h1, ..., h_M-1

Such h_i( x) = i for any input x.

Now if hash function is selected uniformly at random, then

since any one among {0,1,...,M-1} can be selected with uniform probability.

However since each of the hash function h_i is a constant function.

Hence for any i in {0,1,..,M-1}

Hence this hash function does not belong to 2-universal hash function where for any h_i in set H.

Hence this example is appropriate .

Please comment for any clarification .

Answer 2

Similar Homework Help Questions

i need help with 2b please is a set of input values, Y- 2. In this question, we reuse the notation of lecture 37: X-{xi, ,x , m-1) is a set of hash values, and H is an [X → Y)-valued random variab...

i need help with 2b please is a set of input values, Y- 2. In this question, we reuse the notation of lecture 37: X-{xi, ,x , m-1) is a set of hash values, and H is an [X → Y)-valued random variable {0.1, In lecture, we showed that for any hash value y e Y, the expected number of input values that hash to y is k/m, where k XI and m Yl. However, in determining the time it...
1. Let h be a hash function mapping U to indexes (0...m -1]. Assume that |U|...

1. Let h be a hash function mapping U to indexes (0...m -1]. Assume that |U| m2 Could an adversary could pick a set K of m/2 keys from U which are all mapped into the same cell? What is the value of ΣzyEKFh(x,y) in this case ? Fh(x,y) is the function defined in the slides on the section discussing Universal Families of Hash functions.
A hash table is a data structure that supports the storage of subset of keys from...

A hash table is a data structure that supports the storage of subset of keys from a very large set S. To add a key x to a hash table, we use the hash function h: we compute h(x) and store x at location h(x). If two values x and y hash to the same location, we say we have a collision. For the hash table to work efficiently, we want to minimize the probability of collisions. The hash function...

Insertthe following numbres into a initially empty hash table of size 10. The functions h(x) =...

Insertthe following numbres into a initially empty hash table of size 10. The functions h(x) = x % 10. Use linear probing when collision happens. Draw the hash tables and show the intermediate steps. 8,15,6,25,77,39
Topic: Discrete Mathematics and its Applications" Chapter 9:Equivalence Relations and Partial Orderings. 9. hash function H...

Topic: Discrete Mathematics and its Applications" Chapter 9:Equivalence Relations and Partial Orderings. 9. hash function H : {0,1)" → {0,1)" maps a bit string of length n to a bit string of length k. Hash functions are used to give a short label to a long string. The set of all "collisions" with a given string s defines an equivalence class for a given hash function H, that is: (a) What is the average cardinality of the equivalence classes [s]H...
give me a example Develop a set of functions that will allow you to encrypt a...

give me a example Develop a set of functions that will allow you to encrypt a string using a Caesar cipher. Develop a set of functions that will allow you to decrypt a string using a Caesar cipher. Develop a set of functions that will help you to solve (break) a Caesar cipher. Encrypt, Decrypt, Solve in BASIC 1 Encrypt, Decrypt, Solve in Scala (in a procedural manner)

SU 2020 Example Using Chaining 0 1 A hash table which is initially empty. Every element...

SU 2020 Example Using Chaining 0 1 A hash table which is initially empty. Every element is a LinkedList object. Only the start pointer of the LinkedList object is shown, which is set to NULL 2 3 4 5 The hash function is: 6 h(k)=k%7 CS 2121 Deliverables • Insert Following Numbers in order of 31, 9, 36, 42, 46, 20, 2, 24 After Insertion, how how you find Number 9 and 2 Scan your completed work as FirstLastHw07.pdf to...
Double hashing is scheme for resolving collisions that uses two hash functions HCk, m) and hCk,m)....

Double hashing is scheme for resolving collisions that uses two hash functions HCk, m) and hCk,m). It is similar to linear hashing except that instead of changing the index by 1, the value of the second hash function is used From the view of the general scheme, the Io(k, mHCk, m) Hi(k, m) -(H(k, m)+ h(k,m)) mod m H2 (k, m) = (H(k, m)+ 2 h(k,m)) mod m hash functions are. Hi (k, m) (H(k , m)+ h(k , m))...
give me a example Develop a set of functions that will allow you to encrypt a...

give me a example Develop a set of functions that will allow you to encrypt a string using a Caesar cipher. Develop a set of functions that will allow you to decrypt a string using a Caesar cipher. Develop a set of functions that will help you to solve (break) a Caesar cipher. Encrypt, Decrypt, Solve in COBOL Encrypt, Decrypt, Solve in Fortran

5. Hashing (a) Consider a hash table with separate chaining of size M = 5 and...

5. Hashing (a) Consider a hash table with separate chaining of size M = 5 and the hash function h(x) = x mod 5. i. (1) Pick 8 random numbers in the range of 10 to 99 and write the numbers in the picked sequence. Marks will only be given for proper random numbers (e.g., 11, 12, 13, 14 ... or 10, 20, 30, 40, .. are not acceptable random sequences). ii. (2) Draw a sketch of the hash table...