Robert Bosch Hash Tables Quiz 3

Explanation: The time complexity of inserting an element into a hash table is typically O(1) on average. This is because the hash function allows for direct access to the slot where the element should be stored.

Explanation: To convert a key into an index. A hash function takes a key as input and maps it to an index in the hash table's underlying array. The goal of a good hash function is to distribute the keys evenly across the array, minimizing collisions.

Explanation: By chaining the new key-value pair to the existing one using a linked list. When a collision occurs, the hash table uses a technique called chaining to handle it. Each bucket in the array contains a linked list, and new key-value pairs with the same hash value are added to the list.

Explanation: By hashing the key and directly accessing the corresponding bucket. To retrieve the value associated with a key in a hash table, the key is hashed to determine the index in the array where the value is stored. This allows for efficient and direct access to the desired value without searching the entire hash table.

Explanation: The correct answer is c) A hash table handles collisions by storing both elements in the same array index. This is typically done using techniques such as chaining (storing elements in a linked list) or open addressing (finding an alternative empty slot in the array).

Explanation: The correct answer is c) A good hash function does not need to produce unique hash values for all inputs. Collisions are inevitable in hash tables, and a good hash function should aim to distribute hash values uniformly across the array to minimize collisions.

Explanation:
Quadratic probing is a collision resolution technique used in hash tables. When a collision occurs (i.e., the hash function produces the same index for multiple keys), quadratic probing increments the probe sequence by a quadratic function of the attempt number (i.e., i^2). This means that the probing sequence follows the pattern: 0, 1, 4, 9, 16, and so on.

The concept of linear probing is that collisions are resolved by sequentially scanning the array until an empty location is found.
In this case we need to store at Location 2 , so we can go to that location only if we receive locations to be 7,8,9,10,1 ( these locations are already filled so it will scan for an empty location i.e. 2 ) and location 2 of course.
So probability would be = favorable locations/total locations
=6/10
=0.6

 

The sequence (A) doesn’t create the hash table as the element 52 appears before 23 in this sequence.

The sequence (B) doesn’t create the hash table as the element 33 appears before 46 in this sequence.

The sequence (C) creates the hash table as 42, 23 and 34 appear before 52 and 33, and 46 appears before 33.

The sequence (D) doesn’t create the hash table as the element 33 appears before 23 in this sequence.

For each entry probability of collision is 1/20 {as possible total spaces =20, and an entry will go into only 1 place}
Say after inserting x values probability becomes ½
(1/20).x = ½
X=10