HashMap/HashTable :- This question arises in most of the interviews. General hashcode and quals contract even fresher will also explain. The main point is why the hash map is faster? why hashmap best time complexity is O(1) without collision?.What is collision what happens when the collision occurs?. what is the internal data structure used in Hash map? and many more questions. Below example will clear all your doubts which has customized hashmap with minimal functionality mimicking actual hashmap/hashtable.
Implementation :-
package com.shift.tcm.util;
/* Operations performed in custom map */
interface ExtendableMap {
public abstract void put(Object key, Object value);
public abstract Object get(Object key);
}
/* MapEntry is the actual data structure used inside array to store the data*/
class MapEntry<K, V> {
final K key;
V value;
/*
* Incase of duplicates we need to maintain it as a linked list when hash
* code collides
*/
MapEntry<K, V> next;
final int hash;
MapEntry(int h, K k, V v, MapEntry<K, V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
// whether two entry objects are equal based on their hashcode and equals
// method
public final boolean equals(Object o) {
if (!(o instanceof MapEntry))
return false;
MapEntry e = (MapEntry) o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {
return key.hashCode();
}
public final String toString() {
return getKey() + "=" + getValue();
}
}
Map impelmentation starts here :-
public class CustomHashMap implements ExtendableMap {
// Using array will provide random access which returns value in constant
// time
Object[] table;
int length;
// Setting up default size 16
public CustomHashMap() {
this.table = new Object[16];
this.length = 16;
}
// User setting custom size
public CustomHashMap(int size) {
this.table = new Object[size];
this.length = size;
}
@Override
public void put(Object key, Object value) {
int hashKey = calculateHash(key.hashCode());
if (hashKey > -1 && hashKey < length) {
MapEntry entry = new MapEntry(key.hashCode(), key, value, null);
if (table[hashKey] == null) {
table[hashKey] = entry;
} else {
// If there are duplicates we need to form an linkedlist of type
// MapEntry
handleDuplicatesOrUpdateExisting(entry, hashKey);
}
}
}
@Override
public Object get(Object key) {
// Determine hashvalue
int hashKey = calculateHash(key.hashCode());
// Now lookup is very fast because array is an index based hash no need
// to loop through the array
if (hashKey > -1 && hashKey < length) {
MapEntry entry = (MapEntry) table[hashKey];
if (entry.next != null) {
return exactMatchInList(entry, key);
}
return entry.getValue();
}
return null;
}
/*
* If hashcodes are matching then we have to loop through linked list and
* find the exact value
*
*/
private Object exactMatchInList(MapEntry entry, Object key) {
while (entry!= null) {
if (entry.hashCode() == key.hashCode() && entry.getKey().equals(key)) {
return entry;
} else {
entry = entry.next;
}
}
return null;
}
/*
* If hashcodes are matching then we have to form a linked list and store
* the value
*
*/
private void handleDuplicatesOrUpdateExisting(MapEntry entry, int hashKey) {
MapEntry prevEntry = (MapEntry) table[hashKey];
if (prevEntry.equals(entry)) {
table[hashKey] = entry;
} else {
prevEntry.next = entry;
table[hashKey] = prevEntry;
}
}
/*
* Base hash function responsible for converting hash key to actual hash
* value Generally many people gets confuse between hashkey and actual hash
* value which is computed to make hashmap respond in constant time to make it work
* in constant time always
*/
private int calculateHash(int key) {
return key % length;
}
}
End usage of the custom hashmap :-
package com.shift.tcm.util;
/*
* Test case for unit testing customhashmap
*
* */
public class HashMapTest {
public static void main(String[] args) {
// Initialize the custom hashmap with default size 16
CustomHashMap customHashMap = new CustomHashMap();
//Put data to map
Employee employee= new Employee(2,"krishna");
customHashMap.put(employee, "Manager");
Employee employee1= new Employee(1,"satish");
customHashMap.put(employee1, "Assistent Manager");
Employee employee4= new Employee(4,"employee");
customHashMap.put(employee4, "Engineer");
//Putting duplicate key data
Employee employee2= new Employee(2,"krishna1");
customHashMap.put(employee2, "Director");
Employee employee3= new Employee(1,"satish1");
customHashMap.put(employee3, "Sr Director");
//Retrieve Data from map;
Employee retrieveEmployee1= new Employee(1,"satish1");
System.out.println(customHashMap.get(retrieveEmployee1));
Employee retrieveEmployee2= new Employee(2,"krishna");
System.out.println(customHashMap.get(retrieveEmployee2));
Employee employee5= new Employee(4,"employee");
System.out.println(customHashMap.get(employee5));
}
}
class Employee {
int id;
String name;
public Employee(int id,String name) {
this.id = id;
this.name=name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
/* If hashcode is equals it is not necessary that both the objects are same.
* In case of duplicate values in hashmap its equals methods is verified to check whether the objects are same are not
*/
@Override
public int hashCode() {
return id;
}
/* If both the objects equals method returns same then its hashcode method should also return same value */
@Override
public boolean equals(Object o) {
if(o instanceof Employee){
Employee employee = (Employee)o;
if(employee.getName()== getName()){
return true;
}else {
return false;
}
}else{
return false;
}
}
public String toString(){
return "Employee ID :- "+id;
}
}
