Computer Science Test - 15

The correct option is Hashing

CONCEPT:

In linear search, every element of a given list is compared one by one with the given key without skipping any element.

It is useful when we need to search for an item in a small unsorted list, but the time is taken to search the list increases as the size of the list increases.

 

In binary search, the key to be searched is compared with the middle element of a sorted list, 

i) If the element at the middle position matches the key the search is successful

ii) If the element at the middle position is greater than the key then the key element may be present in the left part of the list

iii) If the element at the middle position is smaller than the key, then the key element may be present in the right part of the list

This process continues till the element is found or the list is traversed completely.

 

Hash-based searching requires only one key comparison to find the position of a key, provided every element is present at its designated position decided by a hash function. 

It uses a list as a storage medium and uses the hash technique/formula to generate the index which an element is to be inserted or is to be located from.

If two elements map to the same slot in the hash table, it is called collision, and the process of identifying a slot for the second and further items in the hash table in the event of a collision is called collision resolution. 

For example, consider a list of length 5 and the hash function: h(element)= element%5

to store the collection of numbers 4, 12, 5, 3, and 9 in a hash table.

Key	Hash	List index
4	4%5=1	1
12	12%5=2	2
5	5%5=0	0
3	3%5=3	3
9	9%5=4	4

The resulting list will have elements in the following order = [ 5, 4, 12,  3, 9 ] 

If we want to search for key = 12, requires only one key comparison to find the position of key 12 as h(12) = 12 % 5 = 2 

The key element 12 is present at index 2 of the list. 

The correct option is Collision

CONCEPT:

Hash Table is a data structure that stores data in an associative way which has a key-value pair. In a hash table, data is stored in a list format, where each data value has its own unique index value.

It uses a list as a storage medium and uses the hash technique/formula to generate the index which an element is to be inserted or is to be located from.

If two elements map to the same slot in the hash table, it is called collision, and the process of identifying a slot for the second and further items in the hash table in the event of a collision is called collision resolution.

Ways to handle collisions: 

• Chaining
• Open Addressing

The correct option is Dictionary

CONCEPT:

Hash Table is a data structure that stores data in an associative way that has a key-value pair and in which the address or the index value of the data element is generated from a hash function.

So Hash-based searching and insertion require only one key comparison to find the position of a key, provided every element is present at its designated position decided by a hash function as the key values themselves become the index of the list which stores the data.

In Python, the Dictionary data type is an unordered collection of data values, used to store data values like a map representing the implementation of hash tables.

Keys of the dictionary are generated by hashing function which generates unique results for each unique value supplied to the hash function.

Example

dict = {'Name': 'Testbook', 'Course':'Hashing', 'Language': 'Python'}

We can use keys() mthod to get all the keys of dictionary "dict" as shown

dict.keys()
dict_keys(['Name', 'Course', 'Language'])

The Correct option is 5, 4, 2, 3 

CONCEPT:

A hash function takes elements of a list one by one and generates an index value for every element. 

This will generate a new list called the hash table.

It uses a list as a storage medium and uses the hash technique/formula to generate the index which an element is to be inserted or is to be located from.

If two elements map to the same slot in the hash table, it is called collision, and the process of identifying a slot for the second and further items in the hash table in the event of a collision is called collision resolution. 

For example, consider a list of length 5 and the hash function: h(element)= element%6

to store the collection of numbers 12, 2, 4, 15, 19, and 59 in a hash table.

Key	Hash value	List index
12	12%6=0	0
2	2%6=2	2
4	4%6=0	4
15	15%6=3	3
19	19%6=1	1
59	59%6=5	5

The resulting list will have elements in the following order = [ 12, 19, 2,  15, 4, 59 ] 

Key element 59 is present at index 5 of the list. 

Key element 4 is present at index 4 of the list. 

Key element 2 is present at index 2 of the list. 

Key element 15 is present at index 3 of the list. 

The correct option is Search by Hashing.

CONCEPT:

In linear search, every element of a given list is compared one by one with the given key without skipping any element.

It is useful when we need to search for an item in a small unsorted list, but the time taken to search the list increases as the size of the list increases.

For example, consider a list of length 5 and the key element is present at the end of this list. Number of comparisons required to search the key element = size of list i.e 5

If we increase the size of the same list (say 15) and the key element is present at the end of this list. Number of comparisons required to search the key element = size of list i.e 15

 

In binary search, the key to be searched is compared with the middle element of a sorted list, If the element at the middle position:

i)  Matches the key the search is successful

ii) Is greater than the key then the key element may be present in the left part of the list

iii) Is smaller than the key, then the key element may be present in the right part of the list

This process continues till the element is found or the list is traversed completely.

Thus the time taken to search the list increases as the size of the list increases. But it will not be as large as the time required by linear search

 

Hash-based searching requires only one key comparison to find the position of a key, provided every element is present at its designated position decided by a hash function. 

For example, consider a list of length 5 and the hash function: h(element) = element % size(list)

A hashing function is a mathematical function that generates unique results for each unique value supplied to the hash function in constant time.

For example: Consider a list of length 5 and if we want to search for key = 12, the index returned by the hash function is h(12) = 12 % 5  = 2  and requires only one key comparison to find the key at that index

Similarly increasing the size of the list (say 15) and if we want to search for key = 12, the index returned by the hash function is h(12) = 12 % 5  = 12  and requires only one key comparison to find the key at that index

Thus it is independent of the length of the list.

Hashing is a method to store data in an array so that sorting, searching, inserting and deleting data is fast. For this, every record needs a unique key.

The basic idea is not to search for the correct position of a record with comparisons but to compute the position within the array. The function that returns the position is called the 'hash function' and the array is called a 'hash table'.

Collision occurs when two items hash to the same slot. Ideally, a perfect hash function is the one in which no collision occurs. But this is not possible in real world applications. Hence when an attempt is made to insert a record at a slot which is full or at a primary bucket which is full, collision occurs.

Key Points

Concept:

Division Method:

This is the easiest method to create a hash function. The hash function can be described as

 h(k) = k mod n

Here, h(k) is the hash value obtained by dividing the key-value k by the size of hash table n using the remainder. It is best that n is a prime number as that makes sure the keys are distributed with more uniformity. So here mod operation gives a reminder of k and m.

Explanation:

57 × 1 = 57

57 × 2 = 114

57 × 3 = 171

So both are close to 171,

171 + 6 = 177

171 + 26 = 197

 h(177) = 177 mod 57 = 6

 h(197) = 197 mod 57 = 26

positions are 6, 26 of 177 and 197 respectivly.

Hence the correct answer is 6, 26.

The correct answer is: 12 and 2

Concept:

A problematic situation, where two or more elements try to be stored in the same position in the list. This situation is called collision in hashing.

Explanation:

• In the given hash function the 10 is the size of the list, and the function is based on the remainder method. 
• The expression 12%10 results in index value 2 and the expression 2%10 results in index value 2. 
• Now both the index values are the same so the collision will take place.
• A mechanism for placing the other items with the same hash value in the hash table. This process is called collision resolution. 

Additional Information

• The 15%10 becomes 5 and 14%10 becomes 4, so both remainders are different, and no collision is possible.
• The 1%10 becomes 1 and 10%10 becomes 0, so both remainders are different, and no collision is possible.
• The 11%10 becomes 1 and 22%10 becomes 2, so both remainders are different, and no collision is possible.

The correct answer is: perfect hash table.

Concept: 

When two or more elements try to share the same position in the list. This situation is called collision in hashing.

Explanation:

• The hash function is a function that takes elements of a list one by one and generates an index value for every element.
• If the hash function is based on the remainder method and the for two values it will results in the same remainder which is considered as the index value then the situation is getting problematic. 

 

 

The hash table which kept each element at different index and does not show any common index value for any two entries from the list then the table is called perfect hast table.