1. (4 points) Suppose we have a hash table of size 29 and we want to implement a system for looking up a friend's information given his/her name. Which of the following hash functions is the best? Justify your choice. (Assuming none of the names is empty.) (a) h(x) = x (b) h(x) = n % 13, where n is the number of characters in x (c) h(x) = (ord(x[0])+ ord(x[-1])) % 29, where x[0] is the first character in the name and x[-1] is the last. (d) h(x) = 29 (e) h(x) = 11 Σ ord(x[i]), where n is the number of characters in x, x[i] the ith character in x, i=0 and ord(c) returns the ordinal value of a character. (Instruction on the Σ summation symbol https://www.mathsisfun.com/algebra/sigma-notation.html.)

1. (4 points) Suppose we have a hash table of size 29 and we want to implement a system for looking up a friend's information given his/her name. Which of the following hash functions is the best? Justify your choice. (Assuming none of the names is empty.) (a) h(x) = x (b) h(x) = n % 13, where n is the number of characters in x (c) h(x) = (ord(x[0])+ ord(x[-1])) % 29, where x[0] is the first character in the name and x[-1] is the last. (d) h(x) = 29 (e) h(x) = 11 Σ ord(x[i]), where n is the number of characters in x, x[i] the ith character in x, i=0 and ord(c) returns the ordinal value of a character. (Instruction on the Σ summation symbol https://www.mathsisfun.com/algebra/sigma-notation.html.)

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: a) Why is Hashing preferred over other method of searching? b) Explain the differences between open…

A: Answer the following questions: a) What is the reason for preferring Hashing as a searching method…

Q: 3. Consider an example of hash table of size 30, and the following items are to be stored. Design…

Q: 0 1 11592 2 4786 3 4 5 6 589 7 1794 For this problem the hash function h(k) is equal to the sum of…

A: Linear probing is a collision resolution technique employed in hash tables to address collisions…

Q: Given a hash table of size 9 with hash function x%9. Write the element order of the linear probe…

A: Solution:

Q: The Java hash function for Strings generates a hash code depending on the string's maximum length.…

A: The Java hash function for Strings is designed to generate a hash code based on the characters of…

Q: Explain how hash table works in detail. Taking this as an example, the keyword sequence (54, 46, 7,…

A: GIVEN: The given hash function H (key) = key% 10 has a sequence of keys (54, 46, 7, 78, 12, 94, 25,…

Q: A hash table is an efficient data structure to store and access data via keys. In this problem, you…

A: a) The number of unique subarrays in an array of length n can be calculated as n(n+1)/2. b) To…

Q: what is the correct formula for the load factor?

A: The load factor is the proportion of the array's size to the number of entries in the hash table.…

Q: 1. Given the hash function: h(i) = i % 13 and double hash function: d(i) = 1 + i % 12. Show the…

A: Introduction: Using a collection of inputs of any size, a hash function organizes them into a table…

Q: Suppose you have a hash table of size N = 64, and you are using quadratic probing with c1 = 1 and c2…

A: The objective of the question is to find the first four values in the search sequence for a record…

Q: We have the hashTable H with bucketsize=10 and hash function N%10. If we iterate over all the keys…

A: Given:bucket size =10hash function =N%10 since bucket size is 10,we can store 10 values in the…

Q: b) Consider an empty hash table of size 7. Draw the table that results after inserting, in the given…

A: The answer is as follows:-

Q: Suppose we were supplied a hash function h(k) =k mod 10. Let our hash table T consist of a modest 10…

A: The solution to the given problem is below.

Q: The following should be taken into account while creating a fully working open hash table:

A: Tableau hash When data is hashed, a hash table represents it as an array where each item carries a…

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: Hashing (4’). For the input 30, 20, 56, 75, 31, 25 and hash function h(K) = K mod 12 a. (1’)…

A: Given- For the input 30, 20, 56, 75, 31, 25 and hash function h(K) = K mod 12 we have to - a.…

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: Use the following values to answer the questions bellow 66 47 87 900 126 140 145 500 177 285 393…

Q: Suppose you have a hash table of size N = 64, and you are using quadratic probing. The keys in your…

A: The objective of the question is to evaluate the effectiveness of a given hash function. The hash…

Q: Linear hash index: Consider the Extendible Hashing index shown in figure below. A bucket is split…

A: Extendible hashing is a dynamic hashing method.

Q: 3. Consider an example of hash table of size 30, and the following items are to be stored. Design…

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

Problem 3 (24 points)
1. (4 points) Suppose we have a hash table of size 29 and we want to implement a system for looking
up a friend's information given his/her name. Which of the following hash functions is the best?
Justify your choice. (Assuming none of the names is empty.)
(a) h(x) = x
(b) h(x) = n % 13, where n is the number of characters in x
(c) h(x) = (ord(x[0])+ ord (x[-1])) % 29, where x[0] is the first character in the name and x[-1]
is the last.
(d) h(x) = 29
n
(e) h(x) = ord(x[i]), where n is the number of characters in x, x[i] the ith character in x,
i=0
and ord(c) returns the ordinal value of a character. (Instruction on the Σ summation symbol
https://www.mathsisfun.com/algebra/sigma-notation.html.)

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

Question

VIEW

Answer

VIEW

Trending now

This is a popular solution!

Step by step

Solved in 2 steps

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

A hash-map has been constructed with quadratic-hashing. The hashing function is h(k;) = (3 * k; + 7) mod 17 and the table length is N = 17. How many cells will be probed by the call of insert(2) 1 4 5 6 7 8 10 11 12 13 14 15 16 26 89 11 35 70 59 Note: First row contains the indices and the second row contains the items.
Consider a open bucket hash table and closed bucket hash table in which the keys are student identifiers (strings of 6 digits). Assume the following number of buckets and hash function: m = 100; hash(id) = first two digits of id #. Starting with an empty hash table, show the effect of successively adding the following student identifiers: 000014, 990021, 990019, 970036, 000015, 970012, 970023. Use following function as second hash function hash(id) = last digit of id # Show the effect of deleting 000014 from the hash table. (Java Programming DSA)
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?)
Suppose we were supplied a hash function h(k) = k mod 10. Let our hash table T consist of a modest 10 slots, addressed by index values 0 through 9: and the remaining part is continued in the image
Use python
Assume that linear probing is used for hash-tables. To improve the time complexity of the operations performed on the table, a special AVAILABLE object is used to mark a location when an item is removed from the location. Assuming that all keys are positive integers, the following two techniques were suggested instead of marking the location as AVAILABLE: i) When an entry is removed, instead of marking its location in the table as AVAILABLE, indicate the key in the location as the negative value of the removed key (e.g., if the removed key was 16, indicate the key as -16). Searching for an entry with the removed key would then terminate once a negative value of the key is found (instead of continuing to search if AVAILABLE is used). ii) Instead of using AVAILABLE, find a key in the table that should have been placed in the location of the removed entry, then place that key (the entire entry of course) in that location (instead of setting the location as AVAILABLE). The motive is to…
Implement a commonly used hash table in a program that handles collision using linear probing. Using (K mod 13) as the hash function, store the following elements in the table: {1, 5, 21, 26, 39, 14, 15, 16, 17, 18, 19, 20, 111, 145, 146}.
). 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?
The Big O value of hashing is: O a. O(log N) O b. O(N) Oc O(N*Log N) O d. 0(1)
What is the average-case runtime required for a successful operation in a hash table using chaining where there are m buckets and n items in the hash table? Select one: a. O( n/m ) b. O(n) The answer depends on both n and m c. O( 1) d. O(m)
A linear probing hash table of length 10 uses the hash function h(x) = x mod 10 + 1. mod is the reminder operator. For example the h(42) = 42 mod 10 + 1 = 2 + 1 = 3 so we insert 42 in the position 3 in the array. After inserting 6 integer keys into an initially empty hash table, the array of keys is…