Topic: Hashing

Questions Successfully Completed: 2

1) Sort array using number hashing	Easy
2) Sort string using character hashing	Easy

Sort array using number hashing

Time Complexity : O(n)

Space Complexity: O(k)

package hashing;
import java.util.Arrays;
public class numberHashing {
    public static int findmax(int[] arr,int n){
        int s=arr[0];
        for(int i=0;i<n;i++){
            if(arr[i]>s){
                s=arr[i];
            }
        }
        return s;
    }
    public static void numHash(int[] arr,int n){

        int max = findmax(arr,n);
        int[] hashh = new int[max+1];
        for(int i=0;i<n;i++){
            hashh[arr[i]]++;
        }
      System.out.println(Arrays.toString(hashh));
        // Output [0, 2, 1, 2, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]
        // hashing to sort the array
        int i =0;
        for(int j=0;j<=max;j++) {
            while (hashh[j] > 0) {
                arr[i++] = j;
                hashh[j]--;
            }
        }
        System.out.println(Arrays.toString(arr));
        // Output [1, 1, 2, 3, 3, 4, 5, 12, 15]
}
public static void main(String[] args){
        int[] arr = {2,3,1,4,3,1,5,15,12};
        numHash(arr,arr.length);
    }}

Sort string using character hashing

Time Complexity : O(n)

Space Complexity: O(k)

package hashing;
import java.util.Arrays;
public class characterHashing {
    public static void charHash(String str,int n){
        char c[]= str.toCharArray();
        int[] hassh = new int[26];
        for(int i=0;i<n;i++){
            hassh[c[i]-97]++;
        }
      System.out.println(Arrays.toString(hassh));
        // OUTPUT - [2, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
        // sort the character array
        String new_str="";
        for (int i =0; i<hassh.length;i++){
            while(hassh[i]>0){
                char ik = (char) (i+97);
                new_str = new_str + ik;
                hassh[i]--;
            }
        }
        System.out.println(new_str);
        // OUTPUT - aabbcd
    }
    public static void main(String[] args){
        String str ="abacbd";
        charHash(str,str.length());
    }}

Thank you for Reading :)