Calculate all keys of maximum times occurring value from HashTable in JAVA

Calculate all keys of maximum times occurring value from HashTable in JAVA 
-------------------------------------------------------------------------------
Recently one of my friend had come across one problem, where he had a hashtable (or just consider its just a key/value map), and in our case it was of type Hashtable(String, ArrayList(Long)) and now the arraylist size may vary, it can have duplicate long type values. and he needed to get the maximum times occurring long number's all keys from values ArrayLists (i.e. for which all keys its present in values ArrayList)


So we did it this way -
Its just my try,  as it was a interesting programming challenge, so posting for others who need this kind of data mining in java (logic remains same for other programming languages too)


FileName - LogicProHashTB.java

//FileName - LogicProHashTB.java
package logic.others;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Random;

/** 
 * Problem Name - Calculate all keys of maximum times occurring value from HashTable
 * Purpose - To solve Problem of data-mining in HashTable data. 
 * @author Pramod Khare
 * 
 * Problem Description - There is a HashTable with random data (HashTable of type <String, ArrayList<Long>>)
 * Length of ArrayList of each String-key in above HashTable may vary, its not constant.
 * 
 * Need to calculate maximum times occurring value's (Long) all keys(String) from HashTable
 * 
 * e.g. Consider following HashTable
 *  Key(String) - "values5" ---> Values(ArrayList<Long>) - [9, 4, 2, 8, 1, 4, 6]
 Key(String) - "Values1" ---> Values(ArrayList<Long>) - [6, 4, 6, 4, 4, 8]
 Key(String) - "values4" ---> Values(ArrayList<Long>) - [2, 9, 9, 2, 8, 4, 8, 5, 10, 9]
 Key(String) - "values3" ---> Values(ArrayList<Long>) - [8, 7, 6, 2, 5, 9, 4, 8]
 Key(String) - "values2" ---> Values(ArrayList<Long>) - [9, 2, 3, 6, 5, 9, 3, 5, 7]
 Key(String) - "values8" ---> Values(ArrayList<Long>) - [6, 4, 10]
 Key(String) - "values7" ---> Values(ArrayList<Long>) - [7, 1, 9, 9, 9, 7, 8, 2, 4, 5, 6, 6]
 Key(String) - "values6" ---> Values(ArrayList<Long>) - [2, 9, 2, 3, 9]
 
 So we need answer as - 
 
 Maximum Times Occurred Number - 9, and it has Occurred - 12 times
 
 All Keys of maximum times occurred value - [values5, values4, values3, values2, values7, values6]
 */

public class LogicProHashTB {
 
 public LogicProHashTB() {
  //Default Constructor
 }
 
 /**
  * This is just a dummy method to generate HashTable with random data
  * ....Solely for testing purpose of final method
  * @return HashTable<String, ArrayList<Long>>
  */
 public Hashtable<String, ArrayList<Long>> generateRandomHashTableWithData(){
  Hashtable <String, ArrayList<Long>> exeg = new Hashtable <String, ArrayList<Long>>(); 
  Random rd = new Random();
  //Values ArrayList containing long values
  ArrayList<Long> values1 = new ArrayList<Long>(6); 
  for (int i = 0; i < 6 /*values1.size()*/; i++) {
   values1.add(new Long(rd.nextInt(10)+1));
  }
    
  ArrayList<Long> values2 = new ArrayList<Long>(9);
  for (int i = 0; i < 9/*values2.size()*/; i++) {
   values2.add(new Long(rd.nextInt(10)+1));
  }
  
  ArrayList<Long> values3 = new ArrayList<Long>(8);
  for (int i = 0; i < 8 /*values3.size()*/; i++) {
   values3.add(new Long(rd.nextInt(10)+1));
  }
  
  ArrayList<Long> values4 = new ArrayList<Long>(10);
  for (int i = 0; i < 10/*values4.size()*/; i++) {
   values4.add(new Long(rd.nextInt(10)+1));
  }
  
  ArrayList<Long> values5 = new ArrayList<Long>(7);
  for (int i = 0; i < 7/*values5.size()*/; i++) {
   values5.add(new Long(rd.nextInt(10)+1));
  }
  
  ArrayList<Long> values6 = new ArrayList<Long>(5);
  for (int i = 0; i < 5 /*values6.size()*/; i++) {
   values6.add(new Long(rd.nextInt(10)+1));
  }
  
  ArrayList<Long> values7 = new ArrayList<Long>(12);
  for (int i = 0; i < 12 /*values7.size()*/; i++) {
   values7.add(new Long(rd.nextInt(10)+1));
  }
  
  ArrayList<Long> values8 = new ArrayList<Long>(3);
  for (int i = 0; i < 3/*values8.size()*/; i++) {
   values8.add(new Long(rd.nextInt(10)+1));
  }
  
  //Adding Values To HashTable
  exeg.put("Values1", values1); 
  exeg.put("values2", values2); 
  exeg.put("values3", values3); 
  exeg.put("values4", values4); 
  exeg.put("values5", values5); 
  exeg.put("values6", values6); 
  exeg.put("values7", values7); 
  exeg.put("values8", values8); 
  
  //Print All Keys with their Values -
  Enumeration<String> eString = exeg.keys();
  while(eString.hasMoreElements()){
   String temp = (String)eString.nextElement();
   System.out.println("Key - "+temp+" --- Values - "+exeg.get(temp).toString());
  }
  System.out.println("********************************************************************");
  return exeg;
 }
 
 
 /**
  * main method
  * @param args
  */
 
 public static void main(String[] args) {
  try{
   LogicProHashTB E = new LogicProHashTB();
   
   Hashtable <String, ArrayList<Long>> exeg = E.generateRandomHashTableWithData();
   
   E.getAllKeysForMaxOccurringValue(exeg);
   
  }catch(Exception e){
   e.printStackTrace();
  }
 }
 
 /**Improved Version
  * Actual Method doing all computations
  * Strategy - 1) First Get All unique values, out of all values for all keys.
  *     (As a value (i.e. here a ArrayList<Long>) for a key might have duplicate values (i.e.Here Long values in ArrayList<Long>))
  *      2) Find for each of above unique value, how many times it has occurred in total in HashTable
  *      3) Find Out the maximum times occurred Value (i.e. here a Long Value)
  *            4) Get All the keys(i.e. Here String[]) for which this max-occurred-value (above (3)) is in its values  
  * @param exeg
  * @return String[] of All found Keys
  */
 public String[] getAllKeysForMaxOccurringValue(Hashtable <String, ArrayList<Long>> exeg){
  
  //Get all Values (i.e. Collection of All ArrayList<Long> of exeg HashTable) into a collection object
  Collection<ArrayList<Long>> eValues = exeg.values();
  //to iterate over this collection of ArrayList<Long>
  Iterator <ArrayList<Long>> itr = eValues.iterator();
  
  //Stores unique Value and its Total Occurrences in given exeg HashTable
  Hashtable<Long, Integer> finalTable = new Hashtable<Long, Integer>();
  
  while(itr.hasNext()){
   ArrayList<Long> temp1 = itr.next();
   //System.out.println("Values - "+temp1.toString());
   //For Each value(i.e. Long value) in current ArrayList<Long>
   for (Long long1 : temp1) {
    //if its already stored in finalTable HashTable, 
    //then just increment the number of times this Value(Long value) has occurred.
    if(finalTable.containsKey(long1)){
     Integer occurances = finalTable.get(long1);
     occurances +=1; //Increment total occurrances by 1
     finalTable.remove(long1);
     finalTable.put(long1, occurances);
     //System.out.println("Value - "+long1+", --- Total Count - "+finalTable.get(long1));
    }else{
    //If its not yet stored in finalTable HashTable then store it with occurrence no as 1.
     finalTable.put(long1, 1);
    }
   }
  }
  
  //Using Java inbuilt Collection Framework, get maximum occurrence number.
  Integer MaxOccurances = Collections.max(finalTable.values());
  
  //Another Approach can be using Arrays
  //Arrays.sort(finalTable.values().toArray(new Long[0]));
  
  //Long maxOccuringNumber = 0l;
  ArrayList<Long> maxOccuringNumber = new ArrayList<Long>();
  
  //Now to get Maximum occurring number (i.e. Long Value), iterate over finalTable HashTable
  Enumeration<Long> keys = finalTable.keys();
  while(keys.hasMoreElements()){
   Long temp = keys.nextElement();
   //System.out.println("Value - "+temp+", Count - "+finalTable.get(temp));
   if(finalTable.get(temp) == MaxOccurances){ //this comparision condition may change for other datatypes
    //Once We know the number (i.e. value which occurred max no of times in exeg HashTable)
    //Break the loop to improve efficiency, no need to search more.
    
    //Here One condition can occur, if two different values occur max no of times, 
    //then dont break the loop, get all those max occurring values and show correct results
    
    maxOccuringNumber.add(temp);
    //maxOccuringNumber = temp;
    System.out.println("Maximum Times Occured Number - "+temp+", Occured - "+MaxOccurances+" times");
    //break;
   }
  }
  
  //This is to get All Keys of the max no of times occurring value(s)
  ArrayList<String> finalKeys = new ArrayList<String>(); 
  
  //If more than one different values from exeg hashtable values have occurred max no of times
  //Consider scenario where 2 different values occurred max times like 
  //Maximum Times Occurred Number - 9, and it has Occurred - 12 times
  //Maximum Times Occurred Number - 10, and it has Occurred - 12 times
  //So output should contain both value's keys
  
  for (Long value : maxOccuringNumber) {
   //Getting exeg's Keys where this maxOccuringNumber is(are) present in its values array
   Enumeration<String> exegKeys = exeg.keys();
   while(exegKeys.hasMoreElements()){
    String temp = exegKeys.nextElement();
    if(exeg.get(temp).contains(value))
     finalKeys.add(temp);
   }
  }
  
  //It may happen like this - 
  /**
   *  Key - values5 --- Values - [7, 4, 10, 6, 2, 2, 7]
   Key - Values1 --- Values - [8, 8, 7, 10, 10, 4]
   Key - values4 --- Values - [8, 4, 7, 10, 9, 3, 10, 8, 10, 8]
   Key - values3 --- Values - [1, 2, 4, 3, 1, 8, 2, 4]
   Key - values2 --- Values - [7, 8, 1, 5, 9, 9, 4, 3, 3]
   Key - values8 --- Values - [6, 9, 7]
   Key - values7 --- Values - [3, 7, 1, 4, 2, 10, 6, 4, 5, 9, 10, 8]
   Key - values6 --- Values - [4, 7, 9, 9, 8]
   ********************************************************************
   Maximum Times Occured Number - 8, Occured - 9 times
   Maximum Times Occured Number - 4, Occured - 9 times
   final Keys - [Values1, values4, values3, values2, values7, values6, values5, Values1, values4, values3, values2, values7, values6] 
  
  //But We should have unique finalKeys Array ...so...
  **/
  ArrayList<String> finalList = new ArrayList<String>();
  
  for (String key : finalKeys) {
   if(!finalList.contains(key)){
    finalList.add(key);
   }
  }
  //So output should be like this one -
  /**
   *  Key - values5 --- Values - [4, 5, 9, 7, 8, 2, 6]
   Key - Values1 --- Values - [8, 2, 3, 1, 2, 10]
   Key - values4 --- Values - [10, 5, 6, 4, 5, 2, 6, 9, 8, 2]
   Key - values3 --- Values - [7, 5, 10, 1, 6, 4, 5, 1]
   Key - values2 --- Values - [2, 3, 3, 4, 1, 8, 5, 10, 7]
   Key - values8 --- Values - [7, 9, 8]
   Key - values7 --- Values - [6, 7, 5, 5, 9, 8, 2, 9, 6, 1, 1, 1]
   Key - values6 --- Values - [7, 4, 3, 2, 1]
   ********************************************************************
   Maximum Times Occured Number - 5, Occured - 8 times
   Maximum Times Occured Number - 2, Occured - 8 times
   Maximum Times Occured Number - 1, Occured - 8 times
   final Keys - [values5, values4, values3, values2, values7, Values1, values6]
   */
  System.out.println("final Keys - "+finalList.toString());
  return finalList.toArray(new String[0]);
 }
 
 /**Older Version
  * Actual Method doing all computations
  * Strategy - 1) First Get All unique values, out of all values for all keys.
  *     (As a value (i.e. here a ArrayList<Long>) for a key might have duplicate values (i.e.Here Long values in ArrayList<Long>))
  *      2) Find for each of above unique value, how many times it has occurred in total in HashTable
  *      3) Find Out the maximum times occurred Value (i.e. here a Long Value)
  *            4) Get All the keys(i.e. Here String[]) for which this max-occurred-value (above (3)) is in its values  
  * @param exeg
  * @return String[] of All found Keys
  *//*
 public String[] getAllKeysForMaxOccurringValue(Hashtable <String, ArrayList<Long>> exeg){
  //GetValues
  Collection<ArrayList<Long>> eValues = exeg.values();
  Iterator <ArrayList<Long>> itr = eValues.iterator();
  
  //ArrayList<Long> uniqueValues = new ArrayList<Long>();
  //Stores unique Value and its Total Occurrances
  Hashtable<Long, Integer> finalTable = new Hashtable<Long, Integer>();
  
  while(itr.hasNext()){
   ArrayList<Long> temp1 = itr.next();
   System.out.println("Values - "+temp1.toString());
   for (Long long1 : temp1) {
    if(finalTable.containsKey(long1)){
     Integer occurances = finalTable.get(long1);
     occurances +=1; //Increment total occurrances by 1
     finalTable.remove(long1);
     finalTable.put(long1, occurances);
     //System.out.println("Value - "+long1+", --- Total Count - "+finalTable.get(long1));
    }else{
     finalTable.put(long1, 1);
    }
   }
  }
  Integer MaxOccurances = Collections.max(finalTable.values());
  //Arrays.sort(finalTable.values().toArray(new Long[0]));
  Long maxOccuringNumber = 0l;
  
  Enumeration<Long> keys = finalTable.keys();
  while(keys.hasMoreElements()){
   Long temp = keys.nextElement();
   //System.out.println("Value - "+temp+", Count - "+finalTable.get(temp));
   if(finalTable.get(temp) == MaxOccurances){
    maxOccuringNumber = temp;
    System.out.println("Maximum Times Occured Number - "+temp+", Occured - "+MaxOccurances+" times");
    break;
   }
  }
  
  ArrayList<String> finalKeys = new ArrayList<String>(); 
  //Getting exeg's Keys where this maxOccuringNumber is present in its values array
  Enumeration<String> exegKeys = exeg.keys();
  while(exegKeys.hasMoreElements()){
   String temp = exegKeys.nextElement();
   if(exeg.get(temp).contains(maxOccuringNumber))
    finalKeys.add(temp);
  }
  
  System.out.println("final Keys - "+finalKeys.toString());
  return finalKeys.toArray(new String[0]);
 }
 */
}

Copy the code and paste it in any text-editor, save file with .java extension and Auto-format the code (e.g. in Eclipse IDE with CTRL+SHIFT+F key-combination) to view code and comments written properly. Enjoy...:-)


Above function can be achieved using only array too,..specifically for non-java or light-weight languages where we don't have Collections equivalent.


Array implementation code - 

/**
 * FileName - LogicProProblem1.java
 * Author - Pramod Khare
 * Using Solving most-occuring-values-key-array problem using Primitive Datatype array
 */
package logic.others;

import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Random;

public class LogicProProblem1 {

 public LogicProProblem1() {
  // TODO Auto-generated constructor stub
 }

 /**
  * This is just a dummy method to generate HashTable with random data
  * ....Solely for testing purpose of final method
  * @return HashTable<String, ArrayList<Long>>
  */
 public long [][] generateRandomLong2DArrayWithData(){
  //8 x N - Array
  long [][] exeg = new long [8][]; 
  Random rd = new Random();
  //Values ArrayList containing long values
  exeg[0] = new long[6]; 
  for (int i = 0; i < 6; i++) {
   exeg[0][i] = new Long(rd.nextInt(10)+1);
  }
  exeg[1] = new long[9]; 
  for (int i = 0; i < 9; i++) {
   exeg[1][i] = new Long(rd.nextInt(10)+1);
  }
  exeg[2] = new long[8]; 
  for (int i = 0; i < 8 ; i++) {
   exeg[2][i] = new Long(rd.nextInt(10)+1);
  }
  exeg[3] = new long[10]; 
  for (int i = 0; i < 10; i++) {
   exeg[3][i] = new Long(rd.nextInt(10)+1);
  }
  exeg[4] = new long[7]; 
  for (int i = 0; i < 7; i++) {
   exeg[4][i] = new Long(rd.nextInt(10)+1);
  }
  exeg[5] = new long[5]; 
  for (int i = 0; i < 5; i++) {
   exeg[5][i] = new Long(rd.nextInt(10)+1);
  }
  exeg[6] = new long[12]; 
  for (int i = 0; i < 12 ; i++) {
   exeg[6][i] = new Long(rd.nextInt(10)+1);
  }
  exeg[7] = new long[3]; 
  for (int i = 0; i < 3; i++) {
   exeg[7][i] = new Long(rd.nextInt(10)+1);
  }
   
  for (int i = 0; i<8;i++) {
   System.out.print("\n"+i+"th Row - ");
   long [] temp = exeg[i];
   for (int j=0;j<temp.length;j++) {
    System.out.print("\t"+temp[j]);
   }
  }
  System.out.println("\n********************************************************************");
  return exeg;
 }
  
 
 public static void main(String[] args) {
  long[] keysArray = new LogicProProblem1().findMaxOccuringValuesPositions(new LogicProProblem1().generateRandomLong2DArrayWithData());
 }
 
 /**Primitive Datatype Method Version
  * Method Name - findMaxOccuringValuesPositions
  * 
  * e.g. For Getting All Keys i.e. in which this max occurring value is present ...
  In here its 1-Dimensional indexes where this value occurs in this 2-Dimensional Array
  e.g. [[7, 5, 4, 3, 8, 2, 8],
    [1, 6, 4, 10, 9],
    [2, 5, 3, 12, 11, 9, 21, 6, 8],
    [8, 9, 3, 8, 7, 8],
    [10, 9, 7, 4, 2, 7, 8]]
  Then 8 is max occurring value and its keys will be - [0,1,2,3]
  
  because 8 never comes in second 1-D array of this 2-D Array
  * Strategy - 1) First Get All unique values, out of all values for all keys.
  *      2) Find for each of above unique value, how many times it has occurred in total in long Array
  *      3) Find Out the maximum times occurred Value (i.e. here a long Value)
  *            4) Get All the keys(i.e. Here long[]) for which this max-occurred-value is in its values  
  * @param finalKeys
  * @return long[] of All found Keys
  */
 public long[] findMaxOccuringValuesPositions(long[][] inputArr) {
  int maxCount = 0;
  for(int i=0;i<inputArr.length;i++){
   maxCount +=inputArr[i].length;
  }
  
  //Worst Case Scenario - All Values are unique, 
  //So array of unique values and array of there no of their resp occurrences
  long[][] uniqueValues = new long[maxCount][2];
  int actualUniqueCount = 0;
  for(int i = 0; i<inputArr.length;i++){
   for(int j= 0; j<inputArr[i].length;j++){
    //Check if Current inpurArr[i][j] value is present in unique Array, 
    //if yes increment count and continue otherwise 
    //Add it to uniqueValues Array with count =1
    if(actualUniqueCount == 0){
     uniqueValues[0][0] = inputArr[i][j];
     uniqueValues[0][1] = 1l;
     actualUniqueCount+=1;
    }else{
     int x=0;
     for(x=0;x<actualUniqueCount;x++){
      if(inputArr[i][j] == uniqueValues[x][0]){
       //increment the Count
       uniqueValues[x][1]+=1;
       break;
      }
     }
     if(x==actualUniqueCount){
      uniqueValues[x][0] = inputArr[i][j];
      uniqueValues[x][1] = 1l;
      actualUniqueCount+=1;
     }
    }
   }
  }
  
  //now we have unique values and their corresponding occurrences
  //Getting the Final Array From Crude Array
  //This finalArray also can be removed in order to improve efficiency -- its just for better understanding
  long [][] finalSortedUnique = new long[actualUniqueCount][2];
  for(int y=0;y<actualUniqueCount;y++){
   finalSortedUnique[y] = uniqueValues[y];
  }
  
  //Sorting in Ascending order based on number of occurrences, and not value
  //Selection Sort
  for(int i=0;i<finalSortedUnique.length;i++){
   for(int j = i; j<finalSortedUnique.length;j++){
    if(finalSortedUnique[i][1]<finalSortedUnique[j][1]){
     long [] temp = finalSortedUnique[j];
     finalSortedUnique[j] = finalSortedUnique[i];
     finalSortedUnique[i] = temp;
    }
   }
  }
  
  //Now We have our sorted Array 
  //Following for-loop is Not required...its just for printing sorted values.
  for(int i= 0; i<finalSortedUnique.length;i++){
   System.out.println("\nUnique "+(i+1)+" - "+finalSortedUnique[i][0]+" - "+finalSortedUnique[i][1]);
  }
  
  //For Getting All Keys i.e. in which this max occurring value is present ...
  //In here its 1-Dimensional indexes where this value occurs in this 2-Dimensional Array
  //e.g. [[7, 5, 4, 3, 8, 2, 8],
  //  [1, 6, 4, 10, 9],
  //  [2, 5, 3, 12, 11, 9, 21, 6, 8],
  //  [8, 9, 3, 8, 7, 8],
  //  [10, 9, 7, 4, 2, 7, 8]]
  //Then 8 is max occurring value and its keys will be - [0,1,2,3]
  //because 8 never comes in second 1-D array of this 2-D Array
  
  int x=0;
  long [] keysArray = new long[inputArr.length]; //this is a worst case scenario
  for(int i = 0; i<inputArr.length;i++){
   for(int j =0; j<inputArr[i].length;j++){
    if(finalSortedUnique[0][0] == inputArr[i][j]){
     keysArray[x++] = i;
     break;
    }
   }
  }
  
  long [] finalKeys = new long [x];
  for(int i=0;i<x;i++){
   finalKeys[i] = keysArray[i];
  }
  
  System.out.println("\nTotal Keys - "+x+"\n");
  //For Printing All Keys
  for(int j =0; j<finalKeys.length;j++){
   System.out.print("\t"+finalKeys[j]);
  }
  
  return finalKeys;
 }
}