Hashing

Open Addressing - a collision handling method in Hash Tables

In this article, we have explored Open Addressing which is a collision handling method in Hash Tables. We have explored the 3 different types of Open Addressing as well.

Algorithms

Geometric Hashing

Geometric hashing is a computer vision technique used to detect geometric features in images and matching them to a database with such features. What makes geometric hashing stand out is that it can detect overlapping objects.

Hashing

Fibonacci Hashing

In this article, an underlooked kind of hash function is to be discussed, the Fibonacci Hashing. It is another form of multiplicative hashing function that is related to the golden ratio.

Algorithms

First K maximum occurring words

In this article, we will understand the different approaches to return the first k maximum occurring words from a given array. It includes core Data Structures and Algorithm topics such as Arrays, HashMap, Sorting, Priority Queue and Heap, Trie, and Bucket sort.

Algorithms

Hashing: Complete Guide

In hashing, we convert key to another value. It is a searching technique. In linear search the time complexity is O(n),in binary search it is O(log(n)) but in hashing it will be constant. We make use of a hash function and a hash table.

Algorithms

Double Hashing

In this article, we will discuss about Double Hashing, a technique to resolve hash collisions in hash tables along with Time Complexity analysis of Double Hashing.

Algorithms

Quadratic Probing

In this article, we will discuss about quadratic probing, a solution for hash collisions in hash tables.

Algorithms

Examples of Hash Functions

In this article, we have listed several examples of good Hash Functions which you are used conveniently. This can be used to hash any data (numeric and string). Some examples are PJW hash, Division Hash, BUZ hash and much more.

Algorithms

Linear Probing in Hashing

In this article, we have explored the algorithmic technique of Linear Probing in Hashing which is used to handle collisions in hashing. We have explained the idea with a detailed example and time and space complexity analysis.

Algorithms

Jump Consistent Hash: A Fast, Minimal Memory, Consistent Hash Algorithm

In this article, we discuss the jump consistent hashing algorithm which offers improvements compared to previous approaches to consistent hashing for distributed data storage applications.

Algorithms

Number of distinct substrings of length K

We have explained the approach to find the Number of distinct substrings of length K using Rolling hash technique, hash table and brute force approach.

Algorithms

Different collision resolution techniques in Hashing

In this article, we have explored the idea of collision in hashing and explored different collision resolution techniques such as open hashing, closed hashing, linear probing, quadratic probing and double hashing.

Algorithms

Number of distinct elements in a given range

This is a problem in which we have an integer array which contains some elements and our job is to find out number of distinct elements in a given range. We have solved this using three methods with the most efficient approach being a hashing technique with linear time complexity O(N).

Data Structures

Bloom Filter: Better than Hash Map

Bloom Filter is a probabilistic Data Structure that is used to determine whether an element is present in a given list of elements. It is quite fast in element searching.

Algorithms

2 Sum Problem: Number of pairs with a given sum

We will find out how we can count the number of pairs in an array whose sum is equal to a certain number. Brute force approaches will take O(N^2) time but we can solve this in O(N) time using a Hash Map.

Algorithms

Finding number of pairs with a certain XOR value

In this article, we are going to find the number of pairs in an unsorted array, whose XOR values matches with our target value (say K). Using our efficient approach (with Hash map), we can solve this in O(N) time complexity while the brute force approach takes O(N^2) time complexity

Problems on Binary Tree

Copy a binary tree where each node has a random pointer

We explored an algorithm to copy a binary tree with an additional pointer which points to any random node in the tree. We explored two techniques Naive solution using 2 traversals and Efficient solution using hashing.

Data Structures

Hash Map / Hash table

Hash map (hash table, unordered map, dictionary, hash set) is a widely used efficient data structure that used to store data which can be searched in constant time O(1). This data structure is implemented over an array that maps keys to values that is it is a set of key value pairs.

Algorithms

String hashing

Hashing is an important technique which converts any object into an integer of a given range. Hashing is the key idea behind Hash Maps which provides searching in any dataset in O(1) time complexity. An efficient algorithm to hash a string is used to compare strings in O(1) time complexity

Software Engineering

HashMap in Java

In Java, HashMap is a Map based collection class that is used for storing Key and value pairs which is denoted as HashMap. It does not maintain order of elements, allows one null key, multiple null values, is not thread safe, default size is 16, default load factor is 0.75 JDK1.7, JDK1.8

game theory

Zobrist Hashing

Algorithm Complexity Implementations Applications Questions Reading time: 15 minutes | Coding time: 5 minutes Zobrist hashing (additionally alluded to as Zobrist keys or Zobrist marks ) is a hash function development utilized as a part