Searching for a specific element efficiently is a common challenge in computer programming. When working with large datasets or searching for elements frequently, it becomes crucial to adopt efficient searching techniques to optimize the search process. In this article, we will explore two efficient searching techniques: hashing and binary search trees, and discuss their implementation in Java.

Hashing is a technique that allows for constant-time average search complexity. It is based on the hash function, which maps a given input value to a specific index in a hash table.

- A hash function takes an input value and calculates its hash code.
- The hash code is then mapped to an index within the hash table, which is an array of fixed size.
- Upon collision (when two different input values generate the same hash code), a collision resolution technique is employed to handle the situation.

In Java, the `HashMap`

class provides an implementation of hashing. It allows storing key-value pairs, where each value can be accessed through its associated key.

Consider the following example:

```
import java.util.HashMap;
public class HashingExample {
public static void main(String[] args) {
// Create a HashMap
HashMap<Integer, String> hashMap = new HashMap<>();
// Insert elements
hashMap.put(1, "John");
hashMap.put(2, "Alice");
hashMap.put(3, "Bob");
// Access elements
System.out.println(hashMap.get(2)); // Output: Alice
}
}
```

Here, we create a `HashMap`

and insert key-value pairs. The `put`

method is used to add elements, and the `get`

method is used to access a value using its key.

By utilizing hashing, searching for an element in a `HashMap`

has an average time complexity of O(1).

Binary Search Trees (BSTs) are hierarchical data structures that allow for efficient searching, insertion, and deletion operations. A BST is a binary tree where each node has at most two child nodes: a left child and a right child.

- All nodes in the left subtree of a node have values smaller than the current node.
- All nodes in the right subtree of a node have values greater than the current node.
- The left and right subtrees are recursively defined as Binary Search Trees.

In Java, we can implement a binary search tree using a custom class. Each node of the tree contains a key-value pair.

Let's take a look at an example:

```
class Node {
int key;
String value;
Node left, right;
public Node(int key, String value) {
this.key = key;
this.value = value;
left = right = null;
}
}
public class BSTExample {
Node root;
public BSTExample() {
root = null;
}
// Insert a node
void insert(int key, String value) {
root = insertNode(root, key, value);
}
// Recursive method to insert a node
Node insertNode(Node root, int key, String value) {
// Base case: if the tree is empty
if (root == null) {
root = new Node(key, value);
return root;
}
// Recurse down the tree
if (key < root.key)
root.left = insertNode(root.left, key, value);
else if (key > root.key)
root.right = insertNode(root.right, key, value);
return root;
}
// Search for a node
Node search(int key) {
return searchNode(root, key);
}
// Recursive method to search for a node
Node searchNode(Node root, int key) {
// Base case: if the tree is empty or the key is present at the root
if (root == null || root.key == key)
return root;
// Recurse down the tree
if (key < root.key)
return searchNode(root.left, key);
else
return searchNode(root.right, key);
}
public static void main(String[] args) {
BSTExample tree = new BSTExample();
tree.insert(1, "John");
tree.insert(2, "Alice");
tree.insert(3, "Bob");
Node result = tree.search(2);
System.out.println(result.value); // Output: Alice
}
}
```

In this Java example, we create a binary search tree using the `BSTExample`

class. We implement methods to insert a node (`insert`

) and search for a node (`search`

). The `Node`

class represents each node in the tree, containing a key-value pair.

By utilizing BSTs, searching for an element has an average time complexity of O(log n) in a balanced binary search tree.

Efficient searching techniques such as hashing and binary search trees are crucial when dealing with large datasets or frequently searching for elements. In this article, we explored the concepts behind hashing and binary search trees and implemented them in Java. These techniques can significantly boost the performance of the search process, ultimately enhancing the overall efficiency of your programs.

© NoobToMaster - A 10xcoder company