Inserting 14 main hash value is 1 There is already an item in 1 double hash value is 4 1 + 1*4 = 5 So, checking at index 5 % 13 = 5 There is already an item in 5 double hash value is 4 1 + 2*4 = 9 So, checking at index 9 % 13 = 9 There is already an item in 9 double hash value is 4 1 + 3*4 = 13 So, checking at index 13 % 13 = 0 14 is inserted at position 0 14, 79, -, -, 17, 98, -, 59, -, 22, -, 37, - HashTable ----------- 0 - 14 1 - 79 2 - 3 - 4 - 17 5 - 98 6 - 7 - 59 8 - 9 - 22 10 - 11 - 37 12 - Answer: -------- it's placed at index 0
Part 5. Suppose that your hash function resolves collisions using the open addressing method with double...
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))...
11. Dra The size The hash function used is: the contents of the 13 hash tables below. Show your work for partial r hash table is HOk)-k mod 7 13, 17, 6, 24, 3 a) Resolve collisions with chaining b) Double hashing, where W20)-7-0mod 5) 0 1 1 2 2 3 3 4 4 5 5 6 6 c) What is the load factor for the table a? d) What is the load factor for the table b? f) Is...
Let 'M' denote the hash table size. Consider the following four different hash table implementations: a. Implementation (I) uses chaining, and the hash function is hash(x)x mod M. Assume that this implementation maintains a sorted list of the elements (from biggest to smallest) for each chain. b. Implementation (II) uses open addressing by Linear probing, and the hash function is ht(x) - (hash(x) + f(i)) mod M, where hash(x)x mod M, and f(i)- c. Implementation (III) uses open addressing by...
10. Submission In this question you will work with a hash table that uses double hashing. The hash table is size 11, the primary hash function is h(K)-K mod 11, and the secondary hash function is hp(K)-(K mod9) +1 Take an empty hash table. Take your student number and split it into 4 2-digit integers. Insert each of these 2-digit numbers in the order in which they appear in your student number into the empty heap. Then insert the values...
3. (20 points) In open addressing with double hashing, we have h(k,i) hi(k)+ih2(k) mod m, where hi(k) and h2(k) is an auxiliary functions. In class we saw that h2(k) and m should not have any common divisors (other than 1). Explain what can go wrong if h2(k) and m have a common divisor. In particular, consider following scenario: m- 16, h(k) k mod (m/8) and h2(k)-m/2 and the keys are ranged from 0 to 15. Using this hash function, can...
1. Using closed hashing with double hashing to resolve collisions insert the following keys into a table with 11 slots, numbered 0 through 10. The hash functions to be used are H1(k)k(mod11) and H2(k)- Rev(k + 1) (mod11) The function REV reverses the decimal digits like Rev(376) 673. Show the hash table after all nine keys have been inserted. Be sure to indicate how H1 and H2 are used. Keys: 4, 3, 2, 8, 33, 17, 24, 35, 46
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...
4. Hashing and Hash Tables. You need to use the ASCII table in the last page for this question. Study the following hash functions for ASCII C strings that are at least 3-char long unsigned hash1(const char, unsigned unsigned vto]+01997 return (v % m); unsigned hash2Cconst char unsigned) unsigned v-o]k(2] 877 return 1 + (v % ( -1)); (a) Given that m-, 7, compute the hash values and fill the following table (3%) String k hash1k, ) hash2(k, 7) aph...
Exercise 3 (5 points). Suppose we have a hash table of m = 9 slots, and we resolve collisions by chaining. Demonstrate what happens when we insert the keys 5, 28, 19, 15, 20, 33, 12, 17, 10. Use the division-method hash function h (k) = k mod 9.
in C++ Code should work for all cases In this assignment you are requested to implement insert, search, and delete operations for an open-addressing hash table with double hashing. Create an empty hash table of size m= 13. Each integer of the input will be a key that you should insert into the hash table. Use the double hashing function h{k, i) = (hı(k) + ih2(k)) mod 13 where hi(k)= k mod 13 and h2(k) = 1+(k mod 11). The...