Yes/No Questions and Answers of Searching and Hashing
1.) Does linear search require the collection to be sorted?
Ans: No, linear search does not require the collection to be sorted.
2.) Can binary search be applied to an unsorted collection?
Ans: No, binary search cannot be applied to an unsorted collection.
3.) Can linear search be used on both sorted and unsorted lists?
Ans: Yes, linear search can be used on both sorted and unsorted lists.
4.) Is linear search more efficient than binary search on a sorted dataset?
Ans: No, linear search is less efficient than binary search on a sorted dataset.
5.) Can a hash function always guarantee unique hash codes for every input?
Ans: No, a hash function cannot guarantee unique hash codes for every input.
6.) Is the mid-square method of hashing suitable for datasets with large key values?
Ans: Yes, the mid-square method of hashing is suitable for datasets with large key values.
7.) Is chaining a collision resolution technique used in hashing?
Ans: Yes, chaining is a collision resolution technique used in hashing.
8.) Does open addressing involve searching for an alternative slot when a collision occurs?
Ans: Yes, open addressing involves searching for an alternative slot when a collision occurs.
9.) Does quadratic probing use a quadratic function to probe for the next available slot?
Ans: Yes, quadratic probing uses a quadratic function to probe for the next available slot.
10.) Can open addressing lead to longer search times compared to separate chaining?
Ans: Yes, open addressing can lead to longer search times compared to separate chaining.
11.) Can quadratic probing lead to better performance than linear probing?
Ans: Yes, quadratic probing can lead to better performance than linear probing.
12.) Does open addressing involve maintaining linked lists?
Ans: No, open addressing does not involve maintaining linked lists.
13.) Can quadratic probing lead to clustering?
Ans: Yes, quadratic probing can lead to clustering of elements in the hash table.
14.) Does Hash Set in Java allow duplicate elements?
Ans: No, Hash Set in Java does not allow duplicate elements.
15.) Is Hash Table in Java synchronized?
Ans: Yes, Hash Table in Java is synchronized.
16.) Can Identity Hash Map in Java have null keys?
Ans: Yes, Identity Hash Map in Java can have null keys.
17.) Does Linked Hash Map in Java maintain the order of elements based on their natural ordering?
Ans: No, it maintains the order of insertion.
18.) Are Java’s utility classes like Hash Map and Hash Set immutable?
Ans: No, they are mutable.
Very Short Questions and Answers of Searching and Hashing
1.) What is searching in data structures?
Ans: Searching is the process of finding specific information from a collection of items stored in computer memory.
2.) Define linear search.
Ans: Linear search is a basic searching algorithm that traverses the entire list sequentially to find the desired element.
3.) Why is binary search more efficient than linear search?
Ans: Binary search is more efficient because it operates on sorted collections and divides the search space in half with each iteration.
4.) What is the time complexity of linear search?
Ans: The time complexity of linear search is O(n), where n is the number of elements in the collection.
5.) How does binary search work?
Ans: Binary search compares the target element with the middle element of the sorted list and recursively searches in the left or right half based on the comparison.
6.) What is the main difference between linear search and binary search?
Ans: Linear search traverses the entire collection sequentially, while binary search operates on sorted collections and divides the search space in half with each iteration.
7.) How does linear search determine if an element is present in the collection?
Ans: Linear search compares each element in the collection with the target element until a match is found or the end of the collection is reached.
8.) What is hashing in data structures?
Ans: Hashing is a technique used to map large chunks of data into smaller tables using a hash function, uniquely identifying specific items from a collection of similar items.
9.) Define a hash function.
Ans: A hash function is a mathematical function that converts input data into a fixed-size value, known as a hash code or hash value, typically used in hashing techniques for data retrieval and storage.
10.) Explain the concept of static hashing.
Ans: Static hashing is a hashing technique where the number of buckets or slots in the hash table remains fixed throughout the operation, typically used when the number of elements to be stored is known in advance and remains relatively stable.
11.) What is the importance of hash functions in DSA?
Ans: Hash functions are essential in DSA for efficient searching, data organization, collision resolution, security applications, and performance optimization.
12.) Describe the collision resolution techniques used in hashing.
Ans: Collision resolution techniques such as chaining and open addressing are employed in hashing to manage scenarios where different keys hash to the same value, ensuring data integrity and maintaining performance.
13.) What is collision resolution?
Ans: Collision resolution is the process of handling collisions that occur when two different keys hash to the same value in a hash table.
14.) What is open addressing?
Ans: Open addressing is a collision resolution technique used in hash tables where the algorithm probes for an alternative location within the hash table when a collision occurs.
15.) Name one variation of open addressing.
Ans: Linear probing.
16.) What is separate chaining?
Ans: Separate chaining is a collision resolution technique where linked lists of values are built in association with each location within the hash table when a collision occurs.
17.) Which Java class uses reference equality instead of object equality for keys?
Ans: Identity Hash Map.
18.) How does Identity Hash Map differ from a regular Hash Map in Java?
Ans: Identity Hash Map uses reference equality rather than object equality when comparing keys. This means it considers two keys equal only if they are the same object.
19.) Why are Java’s utility classes like Hash Map and Hash Set important for implementing algorithms and data structures?
Ans: These utility classes provide efficient implementations of essential data structures, such as hash tables and sets, which are fundamental for building and optimizing algorithms in Java programs.
Short Questions and Answers of Searching and Hashing
1.) How does dynamic hashing differ from static hashing?
Ans: Dynamic hashing allows the hash table to grow or shrink dynamically as records are added or removed, while static hashing maintains a fixed number of buckets throughout the operation.
2.) Explain the mid-square method of hashing.
Ans: The mid-square method involves squaring the key value and extracting the middle digits to obtain the hash value, commonly used in hashing techniques to convert keys into hash indices.
3.) How does the multiplication method of hashing work?
Ans: The multiplication method involves multiplying the key value by a constant ‘A’, extracting the fractional part, multiplying by the size of the hash table, and taking the floor of the result to obtain the hash value.
4.) Describe the extraction method of extracting elements from data structures.
Ans: The extraction method involves identifying the index or location of the desired element in the data structure and accessing it directly, optionally removing it if needed, applicable to arrays, linked lists, stacks, queues, binary trees, and hash tables.
5.) How does linear probing work in open addressing?
Ans: In linear probing, if a collision occurs, the algorithm linearly searches for the next available slot in the hash table, starting from the original hashed index. This can lead to clustering of elements in the hash table.
6.) What is the main drawback of separate chaining?
Ans: The main drawback of separate chaining is that its worst-case time complexity for searching and deletion is O(n), where n is the number of elements in the hash table.
7.) How does double hashing differ from linear and quadratic probing?
Ans: Double hashing uses a secondary hash function to determine the step size for probing after a collision occurs, unlike linear and quadratic probing which use fixed increment values.
8.) What factors determine the performance of separate chaining?
Ans: The performance of separate chaining depends on how evenly the hash function distributes elements across the hash table and the length of the linked lists formed during collisions.
9.) How does Hash Map differ from Hash Table in Java?
Ans: Hash Map allows null keys and values, while Hash Table does not. Additionally, Hash Map is not synchronized, making it preferable for non-thread-safe operations.
10.) What makes Hash Set an efficient data structure for storing unique elements in Java?
Ans: Hash Set uses hashing to store elements in a hash table, allowing for constant-time average-case operations like adding, removing, and checking for containment.
