Linear probing is a scheme in computer programming for resolving hash collisions of values of hash functions by sequentially searching the hash table for a free location.
Write a program to implement linear probing hash tables
Algorithm Explanation
![]() | Create the hash table and insert the key, values pair into the hash table. |
![]() | The new location calculated using newLocation = (startingValue + stepSize) % arraySize formula. |
![]() | The linear probing used in open addressed hash table which improve the memory caching. the performance of linear probing is more sensitive to input distribution when compare to double hashing. |
![]() | The insert and remove operations uses hash function and resize the table. |
Source Code
package com.dsacode.DataStructre.hashtable; public class LinearProbingHashTable { private int currentSize, maxSize; private String[] keys; private String[] vals; public LinearProbingHashTable(int capacity) { currentSize = 0; maxSize = capacity; keys = new String[maxSize]; vals = new String[maxSize]; } public void makeEmpty(){ currentSize = 0; keys = new String[maxSize]; vals = new String[maxSize]; } public int getSize() { return currentSize; } public boolean isFull() { return currentSize == maxSize; } public boolean isEmpty() { return getSize() == 0; } public boolean contains(String key) { return get(key) != null; } private int hash(String key) { return key.hashCode() % maxSize; } public void insert(String key, String val) { int tmp = hash(key); int i = tmp; do { if (keys[i] == null) { keys[i] = key; vals[i] = val; currentSize++; return; } if (keys[i].equals(key)) { vals[i] = val; return; } i = (i + 1) % maxSize; } while (i != tmp); } public String get(String key) { int i = hash(key); while (keys[i] != null) { if (keys[i].equals(key)) return vals[i]; i = (i + 1) % maxSize; } return null; } public void remove(String key) { if (!contains(key)) return; int i = hash(key); while (!key.equals(keys[i])) i = (i + 1) % maxSize; keys[i] = vals[i] = null; for (i = (i + 1) % maxSize; keys[i] != null; i = (i + 1) % maxSize) { String tmp1 = keys[i], tmp2 = vals[i]; keys[i] = vals[i] = null; currentSize--; insert(tmp1, tmp2); } currentSize--; } public void printHashTable() { for (int i = 0; i < maxSize; i++) if (keys[i] != null) System.out.println(keys[i] +" "+ vals[i]); System.out.println(); } public static void main(String[] args) { LinearProbingHashTable lpht = new LinearProbingHashTable(5 ); System.out.println("Insert values into Hashtable.\n"); lpht.insert("a", "1111"); lpht.insert("b", "2222"); lpht.insert("c", "3333"); System.out.println("Print values from Hashtable"); lpht.printHashTable(); System.out.println("Print values from Hashtable after remove the 'b'"); lpht.remove("b"); lpht.printHashTable(); System.out.println("Get the value of 'c': "+ lpht.get( "c" )); System.out.println("\nClear the Hashtable.\n"); lpht.makeEmpty(); System.out.println("Size of the Hash table after clear: "+ lpht.getSize() ); } }
Output
Insert values into Hash table. Print values from Hash table a 1111 b 2222 c 3333 Print values from Hash table after remove the 'b' a 1111 c 3333 Get the value of 'c': 3333 Clear the Hash table. Size of the Hash table after clear: 0