**Transcription for Educational Website:**A frequently used hash family is the matrix multiplication hash family that we have introduced in class.Suppose we have \( n \) buckets \(\{1, 2, \ldots, n\}\), we will use a binary string of length \( b = \log_2 n \) to index each bucket. (For example, if we have 4 buckets, they will be indexed as 00, 01, 10, 11.)Now, we would like to hash a \( u \)-bit binary string \( x \) into the hash table. (For example, \( x \) could be an 8-bit string 10100110.) To hash this \( u \)-bit string \( x \) into a bucket, we use the hash function \( h_A(x) = (Ax) \mod 2 \), where \( A \) is a \( b \times u \) dimensional binary matrix, and \( x \) is a \( u \times 1 \) dimensional column vector. As a result, \( h_A(x) \) will be a \( b \times 1 \) dimensional vector which shows the bucket index that \( x \) will be hashed to. (For example, \( x \) is an 8-bit string \([10100110]^T\), and \( A \) is a \( 2 \times 8 \) dimensional matrix \[\begin{bmatrix} 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \end{bmatrix}\]then \( h_A(x) = (Ax) \mod 2 = [1, 0]^T \), which means that \( x \) will be hashed to bucket 2.)Prove that the above hash function \( h_A(x) = (Ax) \mod 2 \) is a universal hash family. [Hint: Consider hashing two arbitrary keys \( x \) and \( y \) into the hash table, both \( x \) and \( y \) are \( u \)-bit binary strings.]

Answered: Image /qna-images/answer/4467c222-fa6a-4c3d-802f-0ff19eba5a1f.jpg

A frequently used hash family is the matrix multiplication hash family that we have introduced in class. Suppose we have n buckets {1, 2, ..., n}, we will use a binary string of length b = log₂ n to index each bucket. (For example, if we have 4 buckets, they will be indexed as 00, 01, 10, 11.) Now, we would like to hash a u-bit binary string x into the hash table (For example, x could be an 8-bit string 10100110). To hash this u-bit string x into a bucket, we use the hash function hд(x) = (Ax)mod 2, where A is a b x u dimensional binary matrix, and x is a u x 1 dimensional column vector. As a result, h(x) will be a b × 1 dimensional vector which shows the bucket index that x will be hashed to. (For example, x is an 8-bit string [10100110]™, and A is a [1 0 1 1 0 0 0 then h₁(x) ) = (Ax)mod 2 = 2 x 8 dimensional matrix [ 0 1 1 0 1 0 1 [1, 0]T, which means that x will be hashed to bucket 2.) Prove that the above hash function h₁(x) = (Ax)mod 2 is a universal hash family. [Hint: Consider hashing two arbitrary keys x and y into the hash table, both x and y are u-bit binary strings.]

A frequently used hash family is the matrix multiplication hash family that we have introduced in class. Suppose we have n buckets {1, 2, ..., n}, we will use a binary string of length b = log₂ n to index each bucket. (For example, if we have 4 buckets, they will be indexed as 00, 01, 10, 11.) Now, we would like to hash a u-bit binary string x into the hash table (For example, x could be an 8-bit string 10100110). To hash this u-bit string x into a bucket, we use the hash function hд(x) = (Ax)mod 2, where A is a b x u dimensional binary matrix, and x is a u x 1 dimensional column vector. As a result, h(x) will be a b × 1 dimensional vector which shows the bucket index that x will be hashed to. (For example, x is an 8-bit string [10100110]™, and A is a [1 0 1 1 0 0 0 then h₁(x) ) = (Ax)mod 2 = 2 x 8 dimensional matrix [ 0 1 1 0 1 0 1 [1, 0]T, which means that x will be hashed to bucket 2.) Prove that the above hash function h₁(x) = (Ax)mod 2 is a universal hash family. [Hint: Consider hashing two arbitrary keys x and y into the hash table, both x and y are u-bit binary strings.]

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Q: With a given binary search tree, you are asked to save the key of all the nodes into a file, then…

A: My program would: • Read integer data from the ﬁle designated by the user. Every line of the ﬁle…

Q: Given the series of inputs [45, 7, 46, 90, 34, 6, 7, 71, 23, 24], insert each of these integers into…

Q: Write a program to compute the number of collisions required in a long random sequence of insertions…

A: Here is the explanation regarding the program to compute number of collisions required in a long…

Q: a hash function: h(k) = ((A*k mod 2^w)) >> (w-r), where you are given a value of k and w. How do you…

A: It is defined as a mathematical function that converts a numerical input value into another…

Q: ou are given an array of integers nums and an integer target. Return the indices of two numbers in…

A: The approach used for solving the Two Sum problem using a hash map is as follows: Create an empty…

Q: Write a program to compute the number of collisions required in a long random sequence of insertions…

A: /** * Java Program to implement Linear Probing Hash Table **/ import java.util.Scanner; /**…

Q: We discussed the concept of utilising just 64 bits of the hash in 12.2 Lamport's Hash. Each step…

A: Introduction: A Lam-port signature sometimes referred to as a one-time signature scheme, is a…

Q: What is the worst-case runtime of a successful search operation in a hash table using chaining where…

A: ⦁ Big o of n

Q: Given the following hash map array of size 10 (horrible array size!!) and a hashing function of…

A: Answer 1: Explanation: Given hash function is num%arraysize In the question, num=73 and…

Q: 12. Suppose there are eight students with IDs 907354877, 193318608, 132489986, 134052069, 316500320,…

A: Given That Eight student's ID :907354877, 193318608, 132489986, 134052069, 316500320, 106500319,…

Q: Show the result when we insert the keys 5; 28; 19; 15; 20; 33; 12; 17; 10 into a hash table with…

A: Separate chaining refers to the implementation of the array as a chain, which is a linked list. One…

Q: Let us consider a hash table with an underlying array of length 5. It is initially empty, and we…

A: Given that, Let us consider a hash table with an underlying array of length 5. It is initially…

Concept explainers

Hash Table

A hash table also called a hash map, is a data structure that maps key-value pairs. The hash table can be used in complex systems to provide fast access and compact storage. A hash table is a structure that stores data in an abstract data type kind of associative array. It keeps data in an array format, with a distinct index value for every data value. If the index of the required data is known, then the data can be accessed very easily.

Question

**Transcription for Educational Website:**

A frequently used hash family is the matrix multiplication hash family that we have introduced in class.

Suppose we have \( n \) buckets \(\{1, 2, \ldots, n\}\), we will use a binary string of length \( b = \log_2 n \) to index each bucket. (For example, if we have 4 buckets, they will be indexed as 00, 01, 10, 11.)

Now, we would like to hash a \( u \)-bit binary string \( x \) into the hash table. (For example, \( x \) could be an 8-bit string 10100110.) To hash this \( u \)-bit string \( x \) into a bucket, we use the hash function \( h_A(x) = (Ax) \mod 2 \), where \( A \) is a \( b \times u \) dimensional binary matrix, and \( x \) is a \( u \times 1 \) dimensional column vector. As a result, \( h_A(x) \) will be a \( b \times 1 \) dimensional vector which shows the bucket index that \( x \) will be hashed to. (For example, \( x \) is an 8-bit string \([10100110]^T\), and \( A \) is a \( 2 \times 8 \) dimensional matrix
\[
\begin{bmatrix}
1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 1 & 0 & 1
\end{bmatrix}
\]
then \( h_A(x) = (Ax) \mod 2 = [1, 0]^T \), which means that \( x \) will be hashed to bucket 2.)

Prove that the above hash function \( h_A(x) = (Ax) \mod 2 \) is a universal hash family. [Hint: Consider hashing two arbitrary keys \( x \) and \( y \) into the hash table, both \( x \) and \( y \) are \( u \)-bit binary strings.]

Expert Solution

This question has been solved!

Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.

This is a popular solution!

SEE SOLUTION Check out a sample Q&A here

Step 1

VIEW

Step 2

VIEW

Trending now

This is a popular solution!

Step by step

Solved in 2 steps with 1 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions

You are given an array of integers nums and an integer target. Return the indices of two numbers in the array such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. Implement a function in Java to solve this problem using a hash map, and explain the time and space complexity of your solution.
The Java hash function for Strings computes a hash code based on a fixed maximum number of characters of the string. Given that Strings have no meaningful upper bound in length, describe how an effective, constant-time hashing algorithm can be constructed. (Hint: If you were to pick, say, eight characters to represent a string of length l, which would you choose?)
Double Hashing Given input {19, 29, 7, 116, 44, 8, 45}, a hash function h(x) = x mod 11 and the double hash h2(key) = 7 - (key mod 7). Show the resulting hash table using double hashing. copyAndPaste the table into the textBox for your nice answer. Please consider showing work for the h(x). [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
I am trying to implement a hash table of key-value pairs, where the key determines the location of the pair in the hash table, the key is what the hash function is used on. The hash table that I am trying to implement will use separate chaining (with unordered linked lists) for collision resolution. I need help changing the code where: 1. The "search" method of the code returns the node that was found or "None" 2. The "Node" implementation has a "key" and "value" member This is what I have so far class Node: def __init__(self,initdata): self.data = initdata self.next = None def getData(self): return self.data def getNext(self): return self.next def setData(self,newdata): self.data = newdata def setNext(self,newnext): self.next = newnext class UnorderedList: def __init__(self): self.head = None def isEmpty(self): return self.head == None def add(self,item): temp = Node(item) temp.setNext(self.head)…
ANSWER ALL QUESTIONS
A hash-map has been constructed with double-hashing by applying h;(k;) = [h(k;) + jd(k;)] mod N. The primary hashing function is given as h(k;) hashing function as d;(k;) = k;divN where div is integer division. The maximum number of cells probed is N = 13. How many cells will be probed by the call of findElement(38) = k;modN and the secondary Note: The first row contains the indices and the second row contains the elements. 1 2 4 5 6. 7 8 10 11 12 27 14 available 6. 35 25 51
). This problem is about the chaining method we discussed in the class. Problem 3 (, Consider a hash table of size N = 11. Suppose that you insert the following sequence of keys to an initially empty hash table. Show, step by step, the content of the hash table. Sequence of keys to be inserted:
Suppose you have a hash table of size N = 64, and you are using pseudo-random probing. The keys in your hash are 4-digit integers (0000 through 9999) and your hash function is h(k) = (the sum of the digits in k). Assume that the first 4 slots of your pseudo-random probing array contain: 5, 10, 60, 30 What are the first 4 values in the probe sequence (starting with the home position) for a record with key k=1948?
Suppose you have a hash table with seven entries (indexed 0 through 6). This table uses open addressing with the hash function that maps each letter to its alphabet code (a = A = 0, etc.) modulo 7. Rehashing is accomplished using linear-probing with a jump of 1. Describe the state of the table after each of the letters D, a, d, H, a, and h are added to the table.
What is the worst-case performance of a lookup operation in a hashmap and why? Group of answer choices A- O(1), hashmap always has a constant time lookup, and that is why we like using this associative data structure. B- O(lg(n)) hashmap has a log(n) lookup because we are able to perform a binary search on the keys because our hashmap always maintains a sorted order of entries added. C- O(n) because we can have a bad hash function that puts all of our items in the same bucket, thus we would have to iterate through all n items.
Suppose we use a hash function h to hash n distinct keys into an array T oflength m. Assuming simple uniform hashing, what is the expected number ofcollisions? More precisely, what is the expected cardinality of ffk; lg W k ¤ l andh.k/ D h.l/g?
In this task, two hash tables should should be implemented. You can follow the followinginstructions:- In class HashTable implement a hash table and consider the following:(i) Keys are integers (therefore also negative!) and should be stored in the tableint[] data.(ii) As a hash function take h(x) = (x · 701) mod 2000. The size of the table istherefore 2000. Be careful when computing the index of a negative key. Forexample, the index of the key x = −10 ish(−10) = (−7010) mod 2000 = (2000(−4) + 990) mod 2000 = 990.Hence, indices should be non-negative integers between 0 and 1999!(iii) Implement insert, which takes an integer and inserts it into a table. Themethod returns true, if the insertion is successful. If an element is already inthe table, the function insert should return false.(iv) Implement search, which takes an integer and finds it in the table. The methodreturns true, if the search is successful and false otherwise.(v) Implement delete, which takes an integer and deletes it…