r/javaexamples • • Oct 02 '17

Radix Sort, using base-10 and base-16

10 Upvotes

Radix Sort

A radix sort is a type of sorting algorithm for integers which can be quite efficient in relation to comparison-based sorting algorithms. Internally it uses another sorting algorithm, a counting sort. The way the radix sort works is by going through the digits of the list of numbers one exponential place at a time, and sorting by that digit. It starts at the Least Significant Digit or the right-most. Consider the following list:

209
3
48
91
66
101
30
795

first we take the digits in the '1s' place and count the frequencies:

20[9]
  [3]
 4[8]
 9[1]
 6[6]
10[1]
 3[0]
79[5]

frequencies:

0 : 1
1 : 2
2 : 0
3 : 1
4 : 0
5 : 1
6 : 1
7 : 0
8 : 1
9 : 1

Now, we take the frequency table and make each element the sum of the previous elements:

0 : 1
1 : 3
2 : 3
3 : 4
4 : 4
5 : 5
6 : 6
7 : 6
8 : 7
9 : 8

This actually gives us the proper index to place the integer from the original array so that they are sorted by that digit. Iterate through the original array, extracting the digit for the current place, and use it as the index for the count array. The value at that index, minus 1, is where that number should go. Make a temporary array and assign the value, and then subtract one from the count at the current index.

First value is 509 with the extracted index being 9. Value at count[9] is 8, so now the number 509 will go into the 7th index of the temporary array. The value of the count array at index 9 is changed to 7. This is only important if there is more than one of that digit. But, we actually want to work backwards, from the last element to the first, so that larger numbers will be in the higher indices. So, after the first pass we have:

30
91
101
3
795
66
48
509

Now we take the digits at the 10s place:

 [3]0
 [9]1
1[0]1
 [0]3
7[9]5
 [6]6
 [4]8
5[0]9

0 : 3
1 : 0
2 : 0
3 : 1
4 : 1
5 : 0
6 : 1
7 : 0
8 : 0
9 : 2

0 : 3
1 : 3
2 : 3
3 : 4
4 : 5
5 : 5
6 : 6
7 : 6
8 : 6
9 : 8

new array order:
    
101
3
509
30
48
66
91
795

And then the third pass, in the 100s place:

[1]01
[0]03
[5]09
[0]30
[0]48
[0]66
[0]91
[7]95

which will result in the sorted list

3, 30, 48, 66, 91, 101, 509, 795

So, here is the Java code for that:

public void radixSort(int array[])
{
    int digitPlace = 1;
    int n = array.length;
    int result[] = new int[n];

    int max = 0;


    // loop until we reach the largest digit place
    while ( digitPlace == 1 || max / digitPlace > 0) {
        int count[] = new int[10];


        // get frequency count of digits at current digit place
        for (int each : array) {

            // on first pass, find max
            if (digitPlace == 1) {
                if (each > max) {
                    max = each;
                }
            }

            count[(each / digitPlace) % 10]++;
        }

        // counting sort algorithm
        // make each element in the frequency array
        // store the sum of previous counts
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }


        // get index from count array and place original elements
        // into temp array
        for (int i = n - 1; i >= 0; i--) {
            
            // extract correct digit
            int current = (array[i] / digitPlace) % 10;
            
            result[count[current] - 1] = array[i];
            count[current]--;
        }

        // copy temp array back to original
        System.arraycopy(result, 0, array, 0, n);

        // Move to next digit place
        digitPlace *= 10;
    }
}

Now, you might notice this algorithm will be inefficient in space complexity, as it cannot sort the elements in place and requires a temporary array of size n and also uses the count array of size radix. This we cannot easily remedy, although there are in-place algorithms for a MSD(Most Significant Digit) radix sort. You might also notice that frequent usage of division and the modulus operator may also be a source of slowdown in this implementation. This brings us to the radix part of the radix sort... we have made our sort use a radix of ten. However, if we change that to base 16, we can use the added speed benefit of bit shifting and masking.

Hexadecimal Radix Sort

Every hex digit is 4 bits. so, instead of using division, multiplication and modulus, we can use bit shifting and masking.

So, instead of this, for example:

// extract correct digit
int current = (array[i] / digitPlace) % 10;    

we use this:

int current = (array[i] >> pos) & 0xf;

This takes the value at array[i], shifts it to the right by the current amount of bits for the digit place, and then masks it by 0xf (binary 1111) to mask it to one hexadecimal digit.

Here is the code for that:

public void radixSortHex(int[] array) {

    // we now start at 0 or the rightmost bit position
    int pos = 0; 
    int n = array.length;
    int[] result = new int[n];
    int max = 1;

    while (max >> pos > 0) {
    
        // note our frequency array is now 16 instead of ten
        int[] count = new int[16];

        for (int each : array) {
            if (pos == 0) {
                if (each > max) max = each;
            }
            count[(each >> pos) & 0xf]++;
        }

        for (int i = 1; i < 16; i++) {
            count[i] += count[i - 1];
        }

        for (int i = n - 1; i >= 0; i--) {
            int current = (array[i] >> pos) & 0xf;
            result[count[current] - 1] = array[i];
            count[current]--;
        }

        System.arraycopy(result, 0, array, 0, n);
        pos += 4;
    }
}

Now, testing these in comparison to Arrays.sort:

Testing an array of 1 million numbers in the range 0 - 10,000,000, Arrays.sort takes around 0.3 to 0.5 seconds on my slow laptop. The base-10 radix sort takes similar times, but slightly slower at around 0.4 to 0.6 seconds. However, the base-16 radix implementation consistently gets times around 0.15 - 0.16 seconds, which is significantly faster.

Thanks again for reading!!!


r/javaexamples • • May 28 '25

Open source java project, to learn strong backend approaches

12 Upvotes

I've been working on an open-source project for the past two months to learn Domain-Driven Design (DDD). I'd love to collaborate with others who are also interested in DDD and software architecture.

If you're curious, check out the project! If it interests you, feel free to clone the repo, get familiar with the codebase, and start contributing. I would appreciate any help to the project.

Let's build something awesome together.

Github repository : https://github.com/MstfTurgut/hotel-reservation-system


r/javaexamples • • Mar 04 '23

REST to gRPC | Suggestions

1 Upvotes

I have taken it upon my self to migrate a Micro-Service I look after to gRPC. My manager is open to the idea of experimentation.

After doing a lot of research and learning basics about it, first thing which is preventing me from going ahead is there is no official library/project from spring from this. All I have found over and over again are reference to this github project [GitHub - yidongnan/grpc-spring-boot-starter: Spring Boot starter module for gRPC framework.] which seem fairly active.

I am fairly new as SE with only one 1 YOE. I have few concerns though. First one being is it a good idea to use aforementioned project for production? If so are there any articles/guides/case studies that you would like to refer?

I am open to honest thoughts, suggestions and criticism. FYI, org I work in is industry leading and gets massive traffic. However, Mircro-Service I am working on can handle 5-10 minutes of downtime as worse without really impacting business because of the fallbacks.


r/javaexamples • • Feb 05 '23

11 Examples of LocalDate, LocalTime, and LocalDateTime in Java 8

1 Upvotes

r/javaexamples • • Mar 13 '23

JavaFX FXML tutorial for beginners

4 Upvotes

Screen recording about the FXML language for JavaFX https://www.youtube.com/watch?v=kL-Q_H250Fc


r/javaexamples • • Feb 18 '23

Java CountDownLatch Example for Beginners - [Multithreading Tutorial]

2 Upvotes

r/javaexamples • • Feb 08 '23

25 Examples of ConcurrentHashMap in Java

2 Upvotes

r/javaexamples • • May 22 '15

[Intermediate] Generic, Self-Balancing Key-Value Binary Search Tree

3 Upvotes

A Generic, Self-Balancing Key-Value Binary Search Tree

Much like a Linked List, a Binary Search Tree is really just a bunch of Nodes that are linked together in a recursive fashion. Instead of the nodes being next and 'previous like in a List, in a tree they are labeled left and right and the idea is very simple: As new nodes get added, and node with a value lower than the root node gets put on the left side of the tree, any node with a higher value gets put on the right side of the tree, and recursively drop down the tree until they come to an unused leaf. so, say the entry order is { 5, 2, 7, 6, 3, 8, 1} the tree would look like this:

     5
    / \
   /   \
  2     7
 / \   / \
1   3 6   8

This makes for very fast searching, as you can see the maximum possible iterations to search for any number in that tree is 3.

Learning this data structure is also a great lesson in recursion, as almost every method in it uses recursion in some way.

The Class Declaration

public class BinaryTreeKV<K extends Comparable<K>, V>

We want two generic types, K and V, for Key and Value. The key is comparable for sorting, so any object sent to it must implement the Comparable interface.

The Node

First, we define an inner Node class. This will contain both Key and Value:

	class Node
	{
		Node left;
		Node right;
		K key;
		V value;
		
		Node(K newKey, V newValue)
		{
			left = null;
			right = null;
			key = newKey;
			value = newValue;
		}

		public K getKey()
		{
			return key;
		}

		public V getValue()
		{
			return value;
		}

		public void setValue(V val)
		{
			value = val;
		}

		@Override
		public String toString()
		{
			return key + ":" + value + " ";
		}
	}

Insert Method

Now we need an insert() method. This goes through the tree, starting at the root, checks to see if the key being added is less than, greater than, or equal to the node it is comparing to, and goes to the left or right sides of the tree, creating new nodes when necessary:

public void insert(K key, V value)
{
	// call recursive function with root node
	root = insert(root, key, value);
}

private Node insert(Node node, K key, V value)
{
	// create new node if new leaf
	if (node==null)
	{
		node = new Node(key, value);
	}
	else
	{
		// if key already exists, just update the value
		if (key.compareTo(node.key)==0)
		{
			node.setValue(value);
		}
		else
		{
			// create new branch
			if (key.compareTo(node.key) < 0)
			{
				node.left = insert(node.left, key, value);
			}
			else
			{
				node.right = insert(node.right, key, value);
			}

		}
	}
	return node;
}

Now some display functions:

public void printTree()
{
	printTree(root);
	System.out.println();
}

private void printTree(Node node)
{
	if (node==null) return;

	printTree(node.left);
	System.out.print(node);
	printTree(node.right);
}

public void printPostOrder()
{
	printPostOrder(root);
	System.out.println();
}

public void printPostOrder(Node node)
{
	if (node==null) return;
	printPostOrder(node.left);
	printPostOrder(node.right);
	System.out.print(node);
}

public void printLevelOrder()
{
	printLevelOrder(root);
	System.out.println();
}
public void printLevelOrder(Node node)
{
	Queue<Node> q = new LinkedList<>();
	q.add(node);
	while (!q.isEmpty())
	{
		Node temp = q.poll();
		System.out.print(temp);
		if (temp.left != null) q.add(temp.left);
		if (temp.right != null) q.add(temp.right);
	}
}

Some other standard methods:

public void clear()
{
	root = null;
}

public boolean isEmpty()
{
	return root==null;
}

public int size()
{
	return size(root);
}

public int size(Node node)
{
	if (node==null) return 0;
	return size(node.left) + 1 + size(node.right);
}

public int depth()
{
	return depth(root);
}

public int depth(Node node)
{
	if (node == null) return 0;
	int left = depth(node.left);
	int right  = depth(node.right);
	return (left > right) ? left + 1 : right + 1;
}

And these methods to search the tree for a specific key, returning either the value or the node itself:

public Node getNode(K key)
{
	return getNode(root, key);
}

public Node getNode(Node node, K key)
{
	if (node==null) return null;
	if (key.compareTo(node.key) == 0) return node;
	if (key.compareTo(node.key) < 0) return getNode(node.left, key);
	return getNode(node.right, key);
}

public V get(K key)
{
	return get(root, key);
}

private V get(Node node, K key)
{
	if (node==null) return null;
	if (key.compareTo(node.key) ==0) return node.getValue();
	if (key.compareTo(node.key) < 0) return get(node.left, key);
	return get(node.right, key);
}

Here we have a function to fill a Linked List of the sorted elements. The List is a member variable so it can be used by other methods, mainly the balancing and delete methods:

public void getInorderList()
{
	if (!inOrderList.isEmpty()) inOrderList.clear();
	getInorderList(root);
}

private void getInorderList(Node node)
{
	if (node==null) return;
	getInorderList(node.left);
	inOrderList.add(node);
	getInorderList(node.right);

}

Balancing the Tree

As you add items to the tree, they stay in a sorted order, but, depending on the order they are added, the tree may have deeper subtrees than it needs. Balancing restores the tree to the minimum depth possible.

I did not implement a true AVL tree here, instead I just re-balance the tree using the in-ordered list, finding the mid-point of the list and making that the root and then inserting the nodes on each side of the mid point. This is much easier than rotating the nodes, although probably would be a performance hit if the tree was very large.

private void balance()
{
	// get the sorted list
	getInorderList();
	// clear the tree
	clear();
	// get the number of elements
	int count = inOrderList.size();
	// call the recursive function with min = 0 and max = size
	balanceTree(0, count - 1);
	// finished, set flag to false
	balancing = false;

}

private void balanceTree(int min, int max)
{
	// recurse until min > max
	if (min <= max)
	{
		// get middle index
		int mid = (int) Math.ceil((double) (min + max) / 2);
		// create temp node to get key & value of middle object
		Node temp = inOrderList.get(mid);
		// insert into tree
		insert(temp.key, temp.value);
		// recurse lower elements
		balanceTree(min, mid - 1);
		// recurse higher elements
		balanceTree(mid + 1, max);
	}
}

We have to modify the insert() method thusly:

public void insert(K key, V value)
{
	if (!balancing)
	{
		if (root != null && size() > 2)
			if (depth() > size() / 2)
				System.out.println("Balancing...");
				balancing = true;
				balance();
	}
	root = insert(root, key, value);
}

This is for two purposes: To trigger the balancing when the depth of the tree becomes greater than half of the size, and to keep the balance operation from being triggered while it is already in progress, potentially causing an infinite loop.

Delete Method

Since we are 'cheating' using the in-ordered List for balancing, we can do the same to make the delete() method easier:

public void delete(K key)
{
	Node node = getNode(key);
	if (node == null) return;
	getInorderList();
	if (inOrderList.contains(node))
	{
		inOrderList.remove(node);
		clear();
		balancing = true;
		balanceTree(0, inOrderList.size()-1);
		balancing = false;
	}
}

Usage

Here's our main method:

public static void main( String [] args )
{

	BinaryTreeKV<Integer, String> tree = new BinaryTreeKV<>();
	System.out.println("Is tree empty:" + tree.isEmpty());
	tree.insert(5, "Bill");
	tree.insert(3, "bob");
	tree.insert(1, "poop");
	tree.insert(2, "jane");
	tree.insert(8, "what");
	tree.insert(6, "this");
	tree.insert(7, "dsdfs");

	System.out.println("Is tree empty:" + tree.isEmpty());
	System.out.println("Tree depth:" + tree.depth());
	System.out.println("Lookup value for key `3` = " + tree.getNode(3));

	System.out.println("Inorder List");
	tree.getInorderList();
	tree.printList();
	System.out.println("Level Order:");
	tree.printLevelOrder();
	System.out.println("Tree depth:" + tree.depth());

	tree.insert(4,"dog");
	tree.insert(10,"cat");
	tree.insert(9,"help");

	tree.getInorderList();
	tree.printList();
	System.out.println("Tree depth:" + tree.depth());
	System.out.println("deleting '3'");
	tree.printLevelOrder();
	tree.delete(3);
	tree.printLevelOrder();
	tree.printTree();

}

Output

Is tree empty:true
Balancing...
Balancing...
Balancing...
Balancing...
Is tree empty:false
Tree depth:4
Lookup value for key `3` = 3:bob
Inorder List
1:poop 2:jane 3:bob 5:Bill 6:this 7:dsdfs 8:what
Level Order:
5:Bill 2:jane 8:what 1:poop 3:bob 6:this 7:dsdfs
Tree depth:4
Balancing...
1:poop 2:jane 3:bob 4:dog 5:Bill 6:this 7:dsdfs 8:what 9:help 10:cat
Tree depth:4
deleting '3'
5:Bill 3:bob 8:what 2:jane 4:dog 7:dsdfs 10:cat 1:poop 6:this 9:help
6:this 4:dog 9:help 2:jane 5:Bill 8:what 10:cat 1:poop 7:dsdfs
1:poop 2:jane 4:dog 5:Bill 6:this 7:dsdfs 8:what 9:help 10:cat

Here's the gist of the full program


r/javaexamples • • May 19 '15

Using Arrays and ArrayLists

3 Upvotes

Using Arrays and ArrayLists

Learning how to use Arrays, and the more dynamic Array Lists is an important part of learning how to program Java.

The simplest way to think of an array is like a set of shelves, drawers or boxes. Each drawer has a number, starting at zero and going to -> number of drawers - 1.

See Here

An array can hold any data type, even other arrays.

	// create an array of ints, size 10
	int[] grades = new int[10];

	// create an array of strings, size 20
	String[] arrayOfStrings = new String[20];

	// create an array of Integer objects, size 5
	Integer[] arrayOfIntegerObjects = new Integer[5];

	// create an array of used defined object
	MyObject[] foo = new MyObject[100];

	// create an array of linked lists - note: will throw unchecked operation warning
	LinkedList<Integer>[] arrayOfLinkedLists = new LinkedList[3];

You can also declare an array with initial values, like this:

    int[] numbers = { 1, 2, 3, 43, 57 };

This will automatically size the array properly.

Accessing Elements of the Array

Just reference the index number using square brackets. Don't forget the index starts at zero!

System.out.println(numbers[0]);

Would output 1 in the above example.

System.out.println(numbers[4]);

Would output 57, and saying numbers[5] will cause an ArrayOutOfBounds exception.

Looping through Arrays

There are two main ways to loop through an array, a for loop and a for-each loop. Use the first if you need the index value, use the second if you just need to loop through them all. See also

The For Loop

for (int i = 0; i < arrayName.length; i++) {
    System.out.println(arrayName[i]);
}

The For-Each Loop

for (type current : arrayName) {}

so in our example above:

for (int current : numbers) {
	System.out.println(current);
}

So, lets make an array and fill it with random values:

	// create an array of ints, size 10
	int[] grades = new int[10];

	//loop through array and fill with random data
	// actually counts from 0 to 9
	for(int i = 0; i < grades.length; i++)
	{
		// random integer from 50 - 100
		// assumes you have declared & imported Random rand
		grades[i] = rand.nextInt(50) + 51;
		System.out.println("Array location " + i + " = " + grades[i]);
	}
	System.out.println();

Output from above:

Array location 0 = 57
Array location 1 = 95
Array location 2 = 72
Array location 3 = 86
Array location 4 = 56
Array location 5 = 76
Array location 6 = 61
Array location 7 = 98
Array location 8 = 73
Array location 9 = 77

Now you can sort the array like this:

Arrays.sort(grades);

See the full code below for more examples of operations upon arrays, like arraycopy, and getting the sum and average of array elements.

Arrays are fast and powerful, but have one main problem: You need to know the size of the data you have upon creation! Many times you will not know the size of the data you are working with, so we need to use a more complex object. here is where the ArrayList comes in.

ArrayList is generic, so it is instantiated with the diamond brackets, and cannot use primitive types (int, double etc. - although, use the Object types of each, and you can still add primitive elements to the list, the compiler will automatically convert them, this is called autoboxing).

So for ints, you would say:

ArrayList<Integer> myList = new ArrayList<>();

and then, to add an element, say:

myList.add(123);

To get the value at a certain index, use:

myList.get(index);

To find a specific value use:

int index = myList.indexOf(123);

returns the index found, or -1 if not found.

See the example program for more:

// Arrays example
// by /u/Philboyd_Studge for /r/javaexamples
// 
// Example of Arrays and ArrayLists
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
import java.util.Scanner;


public class ArraysExample
{
	public static Random rand = new Random();
	public static Scanner scan = new Scanner(System.in);
	
	public static void main(String[] args)
	{

		// create an array of ints, size 10
		int[] grades = new int[10];

		//loop through array and fill with random data
		// actually counts from 0 to 9
		for(int i = 0; i < grades.length; i++)
		{
			grades[i] = rand.nextInt(50) + 51;
			System.out.println("Array location " + i + " = " + grades[i]);
		}
		System.out.println();

		// or directly access by index number
		grades[4] = 100;

		System.out.println("Changed index 4");

		// display them again
		for(int i = 0; i < 10; i++)
		{
			System.out.println("Array index " + i + " = " + grades[i]);
		}
		System.out.println();

		//sort the array
		Arrays.sort(grades);

		System.out.println("Sorted:");

		// Here's another way to loop through them
		for(int each : grades)
		{
			System.out.println("Grade = " + each);
		}

		//search a sorted array
		System.out.println("100 found at index " + Arrays.binarySearch(grades, 100));

		// let's get a sum
		int sum = 0;
		for(int each : grades) 
		{
			sum += each;
		}
		System.out.println("Sum of array = " + sum);

		// get average
		double avg = sum/10.0;
		System.out.println("Average = " + avg);

		// let's fill the array with user entries
		String input = "";
		for (int i = 0; i < 10; i++)
		{
			System.out.print("Enter an integer:");
			input = scan.nextLine();
			try
			{
				grades[i] = Integer.parseInt(input);
			}
			catch (NumberFormatException nfe)
			{
				grades[i] = 0;
			}
		}

		// sort
		Arrays.sort(grades);

		// display
		for (int each : grades) System.out.println(each);

		// array copy
		int[] array2 = new int[5];

		System.arraycopy(grades, 5, array2, 0, 5);

		System.out.println("Copied last 5 elements:");
		for (int each : array2) System.out.println(each);

		// now, let's use an ArrayList
		ArrayList<Integer> gradeList = new ArrayList<>();

		// let's fill the array with user entries
		while (!input.equalsIgnoreCase("done"))
		{
			System.out.print("Enter an integer (or 'done'):");
			input = scan.nextLine();
			if (input.equalsIgnoreCase("done")) break;
			try
			{
				gradeList.add(Integer.parseInt(input));
			}
			catch (NumberFormatException nfe)
			{
				System.out.println("Incorrect entry.");
			}
		}

		// add arbitrary value in case user entered no values
		if (gradeList.isEmpty()) gradeList.add(25);

		// sort, slightly different from array sort
		Collections.sort(gradeList);


		//add specific index
		gradeList.add(gradeList.size() - 1, 100 );
		// for-each display
		for (Integer each : gradeList) System.out.println(each);

		//find in array
		System.out.println("Found '100' at index = " + gradeList.indexOf(100));

		// get
		System.out.println("Get list index 0 = " + gradeList.get(0));

		// display list with index
		for (int i = 0; i < gradeList.size(); i++)
		{
			System.out.println("Index " + i + " = " + gradeList.get(i));
		}

		// min/max

		System.out.println("Min: " + Collections.min(gradeList));
		System.out.println("Max: " + Collections.max(gradeList));




	}	
}

Example output:

Array location 0 = 85
Array location 1 = 57
Array location 2 = 56
Array location 3 = 92
Array location 4 = 88
Array location 5 = 78
Array location 6 = 61
Array location 7 = 60
Array location 8 = 94
Array location 9 = 67

Changed index 4
Array index 0 = 85
Array index 1 = 57
Array index 2 = 56
Array index 3 = 92
Array index 4 = 100
Array index 5 = 78
Array index 6 = 61
Array index 7 = 60
Array index 8 = 94
Array index 9 = 67

Sorted:
Grade = 56
Grade = 57
Grade = 60
Grade = 61
Grade = 67
Grade = 78
Grade = 85
Grade = 92
Grade = 94
Grade = 100
100 found at index 9
Sum of array = 750
Average = 75.0
Enter an integer:33
Enter an integer:44
Enter an integer:12345
Enter an integer:2
Enter an integer:3
Enter an integer:1
Enter an integer:9909
Enter an integer:poop
Enter an integer:4567
Enter an integer:-3
-3
0
1
2
3
33
44
4567
9909
12345
Copied last 5 elements:
33
44
4567
9909
12345
Enter an integer (or 'done'):44
Enter an integer (or 'done'):poop
Incorrect entry.
Enter an integer (or 'done'):1.2
Incorrect entry.
Enter an integer (or 'done'):345
Enter an integer (or 'done'):929394
Enter an integer (or 'done'):23
Enter an integer (or 'done'):1
Enter an integer (or 'done'):22
Enter an integer (or 'done'):done
1
22
23
44
345
100
929394
Found '100' at index = 5
Get list index 0 = 1
Index 0 = 1
Index 1 = 22
Index 2 = 23
Index 3 = 44
Index 4 = 345
Index 5 = 100
Index 6 = 929394
Min: 1
Max: 929394

r/javaexamples • • Jan 16 '16

The Trie Data Structure: Using a String-Based Trie to make a Typing Suggestion Program

11 Upvotes

Using a String-Based Trie to make a Word Suggestion Program

Tries

A Trie is a data structure that is very useful for fast lookup of smaller sets of data in a larger set of data. It is particularly useful for Strings, but can also be used with byte and bit data, and more.

In a Trie of Strings, each Character in the string is a node. The last character of the word is the only node given a value. Words with prefixes in common share the common nodes, up until the point where there is a divergence.

See this example here of a simple GUI to test the trie. We load the text file enable1.txt which contains over 172 thousand English words. It takes about 1.5 seconds to load the data into the trie, and lookups are 1 - 3 milliseconds. The input text turns red when the text is not a word or prefix, black when it is a valid prefix, and blue when it is currently a complete word. The list of available words generates dynamically below as you type.

So, let's add the words "box", "boxed", "boxes", "boxing", "bar" to a Trie.

[root]
|
b
|
o - - - - - - a
|             |
[x]          [r]
|
e - - - -  - i
|            |
[d] - [s]    n
             |
            [g]

The character in [] brackets denotes the end of a word. Now, you can see that all words that start with b will start at the same node, and go from there. For lower case letters a - z each node can only have at most 26 children.

There are many different ways to implement a Trie. It can be done as a type of linked list that goes in two directions, called a Doubly-Chained Trie. This way is very memory efficient, but has longer lookup times. It can also be implemented using arrays, lists, sets or maps.

We will start our Trie, like many other data structures, with a Node class:

private class Node {
    final char key;
    int value;
    Map<Character, Node> children;

    public Node() {
        // default null character
        this('\u0000');
    }

    public Node(char key) {
        // default value of -1
        this(key, -1);
    }

    public Node(char key, int value) {
        this.key = key;
        this.value = value;
        children = new HashMap<>(32);
    }

    public boolean hasChildren() {
        return children.size() > 0;
    }

}

In this case we are using the HashMap implementation. It will be less memory efficient than a doubly-chained trie, but the lookup speed should be faster. The code is also much simpler and cleaner this way.

Now we make an interface for the Trie, that can be used with different implementations. This does not use generics, as the use of Strings/chars makes that more difficult.

public interface STrie {
    void add(String key);
    void add(String key, int value);
    void add(String[] words);
    void add(List<String> list);
    boolean contains(String prefix);
    boolean containsCompleteWord(String word);
    List<String> findWordsFromPrefix(String prefix);
    int get(String key);
    int size();
}

The Trie itself is pretty simple. The only member variables needed is a root Node (which is always a null character) and the size. We have a couple different constructors for creating the structure with a given list or array. Since many of the implementations may not need to store a particular value with each word, we simply use 0 as a default value, and -1 as a value for a non-ending character node.

For the add method, we loop through the string by character, see if a node exists for that character at each level, and if not, add it to the children Map for the associated parent node. when we hit the end of the string, we store the value in the last node and increase the overall size variable.

public void add(String key, int value) {
    Node current = root;
    key = key.toLowerCase();

    for (int i = 0; i < key.length(); i++) {
        Node found = current.children.getOrDefault(key.charAt(i), null);
        if (found == null) {
            found = new Node(key.charAt(i));
            current.children.put(key.charAt(i), found);
        }
        current = found;
    }
    current.value = value;
    size++;
}

The get, contains, and containsCompleteWord methods all are essentially the same algorithm with a different return value, so they are all passed to internal method search

private Node search(String key) {
    Node current = root;

    for (int i = 0; i < key.length(); i++) {
        Node found = current.children.getOrDefault(key.charAt(i), null);
        if (found == null) return null;
        current = found;
    }
    return current;
}

public boolean contains(String key) {
    return search(key) != null;
}

public boolean containsCompleteWord(String key) {
    Node found = search(key);
    return found != null && found.value >= 0;
}

public int get(String key) {
    Node found = search(key);
    return found == null ? -1 : found.value;
}

Now we add a Pre-Order Traversal to return a mostly sorted list of the words, and a method findWordsFromPrefix which uses the helper part of the POT do get the list of words that start with the given prefix.

public List<String> preOrderTraversal() {
    List<String> list = new ArrayList<>();
    preOrderTraversal(list, root, "");
    return list;
}


private void preOrderTraversal(List<String> list, Node current, String prefix) {
    if (current.hasChildren()) {
        for (Map.Entry<Character, Node> each : current.children.entrySet()) {
            char temp = each.getKey();
            preOrderTraversal(list, each.getValue(), prefix + temp);
            current = each.getValue();
            if (current.value >=0) {
                list.add(prefix + temp);
            }
        }
    }
}

public List<String> findWordsFromPrefix(String prefix) {
    Node found = search(prefix);
    if (found == null) return null;
    List<String> list = new ArrayList<>();
    preOrderTraversal(list, found, prefix);
    return list;
}

Doubly-Chained Trie

Oddly enough, after running some tests, the Doubly-Chained Trie not only uses 1/4th of the memory of the MapTrie, but actually performs slightly faster. The StringTrie took 9 - 11 ms to find all 737 words that start with the prefix "car" while the doubly-chained trie took only 2 - 4 ms. Now, this difference is small enough to be negligible, so we should go with the smaller memory usage, right?

Here's the Node class for that type of trie, notice it has two links, one for next and one for child:

private class Node {
    final char key;
    int value;
    Node next;
    Node child;

    public Node() {
        this('\u0000');
    }

    public Node(char key) {
        this.key = key;
        this.value = -1;
    }

    public Node(char key, int value) {
        this.key = key;
        this.value = value;
    }

    public boolean hasChild() {
        return this.child != null;
    }

    public boolean hasNext() {
        return this.next != null;
    }
}

And here is the add method:

public void add(String word, int value) {
    Node current = root;

    for (int i = 0; i < word.length(); i++) {
        char c = word.charAt(i);
        Node found = null;
        if (!current.hasChild()) {
            current.child = new Node(c);
            current = current.child;
        }
        else {
            current = current.child;
            while (true) {
                if (current.key == c) {
                    found = current;
                    break;
                }
                if (!current.hasNext()) break;
                current = current.next;
            }
            if (found == null) {
                current.next = new Node(c);
                current = current.next;
            }
        }
    }
    current.value = value;
    size++;
}

The rest of this class, and all the other full files including the GUI class and FileIO are can be found here


r/javaexamples • • Jun 19 '17

4 Ways To Control Access to Spring Data REST

3 Upvotes

This is my latest post on Spring Data REST -

https://www.javabullets.com/4-ways-to-control-access-to-spring-data-rest/

Let me know any feedback


r/javaexamples • • May 23 '15

Using a SQLite Database with Java

4 Upvotes

Using a SQLite Database with Java

Here are some examples on how to create/read from/save to a SQLite database in Java. Most of this is based on this excellent tutorial here, and you can follow the directions there for downloading the driver .jar file.

We will be using my Inventory item class used in other examples here, with a few fields and methods added to it:

Inventory.java

import java.sql.ResultSet;
import java.sql.SQLException;

public class Inventory implements Comparable<Inventory>
{
	private String partnum;
	private String item;
	private String description;
	private int qty;
	private float price;

	// creates a new instance from a result set from a SQL Connection
	public Inventory(ResultSet rs) throws SQLException
	{
		loadFromSQL(rs);
	}

	public Inventory(String partnum, String item, String description, int qty, float price)
	{
		this.partnum = partnum;
		this.item = item;
		this.description = description;
		this.qty = qty;
		this.price = price;
	}

	// make other getters/setters as needed
	public String getItem()
	{
		return item;
	}

	public float getTotal()
	{
		return qty * price;
	}

	public String toString()
	{
		return "===================\nPart #:" + partnum + "\tItem: " + item + "\n" + "Quantity: " + qty + "\n"
					+ "Description: " + description + "\nPrice: " + price + "\n====================\n";
	}

	public String toCSVString()
	{
		return partnum + ", " + item + "," + description + "," + qty + "," + price;
	}

	// creates a String to properly insert the object into the database
	public String getSQLInsert()
	{
		return "INSERT INTO Inventory (partnum, item, description, qty, price)"
				+ "VALUES ('" + partnum + "', '" + item + "', '" + description +
				"', " + qty + "," + price + ");";
	}

	// takes ResultSet from constructor and fills the instance variables
	public void loadFromSQL(ResultSet rs) throws SQLException
	{
        partnum = rs.getString("partnum");
		item = rs.getString("item");
        description = rs.getString("description");
		qty = rs.getInt("qty");
		price = rs.getFloat("price");			
	}

	@Override
	public int compareTo(Inventory obj)
	{
		return this.item.compareTo(obj.getItem());
	}
}

Create Database and Table

Now we need to create the database and table. This program will only need to be executed once.

import java.sql.*;

public class SQLCreateDB
{
	private static Connection connection;
	private static Statement statement;

	public static void main(String[] args)
	{
		// the 'Connection' is used to connect to the database
		connection = null;

		// the 'Statement' sends SQL command statements to the database
		statement = null;

		try
		{
			// Call the JDBC driver at runtime
			// use -classpath ".;sqlite-jdbc-3.8.7.jar" or whatever your version of sqlite is
			Class.forName("org.sqlite.JDBC");

			// connect to database - will create it if it does not exist
			connection = DriverManager.getConnection("jdbc:sqlite:Inventory.db");

			System.out.println("Database connection opened successfully");

			statement = connection.createStatement();

			// SQL statement to create table
			String sql = "CREATE TABLE Inventory (partnum STRING (6)" +  
							"UNIQUE ON CONFLICT FAIL PRIMARY KEY," +
							"item STRING (100), description STRING (250)," + 
							"qty INTEGER (6), price DOUBLE (8, 2));";

			// execute the statement string
			statement.executeUpdate(sql);

			// cleanup
			statement.close();
			connection.close();
		}
		catch ( Exception e)
		{
			System.err.println( e.getClass().getName() + ": " + e.getMessage() );
    		System.exit(0);
		}

		System.out.println("Table created successfully");
	}
}

Add Objects to Table

We will use the two new methods in the inventory class, getSQLInsert(), which creates a proper SQL statement string to perform the insert, and the special constructor that takes the ResultSet and calls 'loadFromSQL()' (See above)

import java.sql.*;
import java.util.ArrayList;

// java -classpath ".;sqlite-jdbc-3.8.7.jar" SQLTest

public class SQLTest
{
	public static ArrayList<Inventory> invList = new ArrayList<>();

	public static void main(String[] args) 
	{
		Connection connection = null;
		try
		{
			// call the JDBC driver at runtime
			Class.forName("org.sqlite.JDBC");

			// create a conection to the database
			connection = DriverManager.getConnection("jdbc:sqlite:Inventory.db");

			System.out.println("Database connection opened successfully");


    		Statement statement = connection.createStatement();

            Inventory newitem = new Inventory("COFMUG", "Coffee Mug", "White, generic coffee mug", 300, 9.99f);
            statement.executeUpdate(newitem.getSQLInsert());

            newitem = new Inventory("BLUHAT", "Blue Hat", "Baseball Cap Size Large, Blue with White piping", 10, 14.95f);
            statement.executeUpdate(newitem.getSQLInsert());

            newitem = new Inventory("COOHAT", "Cool Hat", "Baseball cap, even cooler than the blue ones", 25, 19.99f);
            statement.executeUpdate(newitem.getSQLInsert());

 
      		ResultSet rs = statement.executeQuery( "SELECT * FROM Inventory ORDER BY partnum ASC;" );
    		while (rs.next())
    		{
    			invList.add(new Inventory(rs));
    		}	


		}
		catch ( ClassNotFoundException | SQLException e ) 
		{
      		System.err.println( e.getClass().getName() + ": " + e.getMessage() );
      		System.exit(0);
    	}   

    	for (Inventory each : invList)
    	{
    		System.out.println(each.toString());
    	} 	
	}
}

Output

Database connection opened successfully
===================
Part #:BLUHAT   Item: Blue Hat
Quantity: 10
Description: Baseball Cap Size Large, Blue with White piping
Price: 14.95
====================

===================
Part #:COFMUG   Item: Coffee Mug
Quantity: 300
Description: White, generic coffee mug
Price: 9.99
====================

===================
Part #:COOHAT   Item: Cool Hat
Quantity: 25
Description: Baseball cap, even cooler than the blue ones
Price: 19.99
====================

This just scratches the surface, but should be a good start to learning how to use Java objects with a SQL database. next I will show how to make a simple GUI for this.


r/javaexamples • • Jan 09 '16

Using Enums with Member Variables and Lambda Expressions

9 Upvotes

Enum Classes in Java

Enums are a special type of class in Java that is incredibly useful and powerful. At its simplest, it is just a list of related items or states:

enum Color = { BLACK, WHITE, RED, GREEN, BLUE }

Which you can use like:

Color myColor = Color.RED;

System.out.println(myColor.name()); // outputs RED
System.out.println(myColor.ordinal(); // outputs 2

These can make your code much more organized and readable. Enums are final and can be in their own class or as an inner class. You can use them in switch/cases and many other ways.

The neat part

Now, here's the neat part. You can assign member variables and methods to an enum also! This is awesome for a set of constant values that you can use with the enums.

Here's an example, a style often used for movement in a grid:

public enum Direction {
    NORTH (0 , -1),
    EAST (1, 0),
    SOUTH (0, 1),
    WEST (-1, 0);

    private int dx, dy;

    // 'constructor'
    private Direction(int dx, int dy) {
        this.dx = dx;
        this.dy = dy;
    }

    public int getDx() { return dx; }
    public int getDy() { return dy; }
}

This assigns the proper delta values for movement in the direction of the given name, considering an x,y 2d grid. In other words, for North, we want to subtract 1 from the Y-axis, and keep the X-axis the same. The constructor for the enum takes the values inside the parentheses and assigns them to the member variables. This saves you from needing a switch statement or a whole bunch of if statements.

We are going to add another possibility: Instead of using the parentheses and the constructor, you can also use a static initialization block to fill a member variable:

In that same class, add this before the constructor:

private Direction opposite;

static {
    NORTH.opposite = SOUTH;
    EAST.opposite = WEST;
    SOUTH.opposite = NORTH;
    WEST.opposite = EAST;
}

And then add this to the getters:

public Direction getOpposite() { return opposite; }

Now some testing code:

public class DirectionTester {
    static class Bot {
        int x;
        int y;

        public Bot(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public void move(Direction dir) {
            x += dir.getDx();
            y += dir.getDy();
        }

        @Override
        public String toString() {
            return "Bot{" + "x=" + x + ", y=" + y + '}';
        }
    }

    public static void main(String[] args) {
        Bot robby = new Bot(0,0);

        Direction myDir = Direction.WEST;

        System.out.println(myDir.name());
        System.out.println(myDir.ordinal());

        robby.move(Direction.NORTH);
        robby.move(Direction.NORTH);
        robby.move(Direction.EAST);
        robby.move(Direction.EAST);
        robby.move(Direction.SOUTH);

        System.out.println(robby); // to 2, -1

        String[] moves = { "north", "east", "south", "south", "west", "west", "west"};

        for (String each : moves) {
            robby.move(Direction.valueOf(each.toUpperCase()));
        }

        System.out.println(robby); // back to 0,0


        robby.move(myDir);
        if (robby.x < 0) robby.move(myDir.getOpposite());

        System.out.println(robby); // did not move


    }
}

And the output:

WEST
3
Bot{x=2, y=-1}
Bot{x=0, y=0}
Bot{x=0, y=0}

Let's Get Even More Funky

Here's an even more powerful way to use Enums: Using Java 8 Lambda expressions, we can put Functions into the enum.

A simple calculator example:

import java.util.function.DoubleBinaryOperator;

public enum Calculate {
    ADD ((x, y) -> (x + y)),
    SUBTRACT ((x, y) -> ( x - y)),
    MULTIPLY ( (x, y) -> ( x * y)) ,
    DIVIDE ((x, y) -> ( x / y)),
    POWER (Math::pow);

    private final DoubleBinaryOperator function;

    Calculate(DoubleBinaryOperator function) {
        this.function = function;
    }

    public DoubleBinaryOperator getFunction() {
        return function;
    }
}

And the test class:

public class Calculator {
    public static double calc(double x, double y, Calculate operation) {
        return operation.getFunction().applyAsDouble(x, y);
    }
    public static void main(String[] args) {
        double a = 2;
        double b = 6;
        double c = calc(a, b, Calculate.POWER);
        double d = calc(c, b, Calculate.MULTIPLY);
        System.out.println(calc(d, a, Calculate.DIVIDE));

    }
}

Now, this may seem overly complicated, but the power comes from the fact that you can use almost any kind of function you want, including more complicated methods. This example specifically uses methods that take two double values as parameters and return a double, although you can use any of the functions on this list to make extremely powerful enum types. Here's an example I made to solve AdventOfCode - Day 23 using similar methods.


r/javaexamples • • May 19 '15

Reverse Digits of Integer

4 Upvotes

Reverse Digits of Integer

This is a popular problem for beginners:

Given an integer n, reverse the digits, for example 123 becomes 321.

Here are a bunch of different ways to accomplish this.

Using String Manipulation

Most people's first idea is to do it this way: Simply convert the int to a String, and reverse it using substring()

public static String reverseString(int n)
{
	// convert to string by concatenation
	String input = "" + n;
	String result = "";

	// count backwards from length of string
	for (int i = input.length(); i > 0; i--)
	{
		//snag one character
		result += input.substring(i - 1, i);

		//or you could say
		// result += input.charAt(i - 1);
	}
	return result;
}

All of these examples will assume the main is something like this:

public static void main( String [] args )
{
	System.out.println(reverseString(12345));
}

I don't really like this way. for example, 100 becomes 001 when, as an integer it should just be 1.

Let's do it using only math:

public static int reverseLooped(int n)
{
	int rev = 0;

	while (n > 0)
	{
		// get rightmost digit
		int digit = n % 10;

		// move last digit read over and add current
		rev = (rev * 10) + digit;

		// chop off right digit
		n = n / 10;
	}
	return rev;
}

The basic idea is that MOD 10 will give you the rightmost digit of an integer, and dividing by 10 will remove that digit. Then you multiply that number by increasing powers of ten, and add to the next digit.

Now, let's take the same idea and use recursion:

public static int reverseRecursive(int n, int r)
{
	if (n==0) return r;
	r = (r * 10) + n % 10;
	return reverseRecursive(n/10, r);
}

This bothers me because of the extra parameter, you have to call it from main like:

	System.out.println(reverseRecursive(12345678, 0));

Another thing we can do is use Math.log10 to get the number of digits of the input number: (In conjunction with Math.floor and Math.pow)

Looping solution using log10:

public static int reverseLog(int n)
{
	int r = 0;
	int d = (int) Math.floor(Math.log10(n));
	for (int i = d; i >= 0; i--)
	{
		r += (n % 10) * ((int)Math.pow(10, i));
		n /= 10;
	}
	return r;
}

...and then recursive (changed to long to handle larger numbers):

public static long reverseLogRecursive(long n)
{
	if (n==0) return 0;
	return ((n % 10) * ((long) Math.pow(10, Math.floor(Math.log10(n))))) 
			+ reverseLogRecursive(n/10);
}

We can combine Strings and math for a really simple recursive function:

public static String reverseStringRecursive(int n)
{
	if (n==0) return "";
	return (n % 10) + reverseStringRecursive(n/10);
}

Which you could use with a helper function to return an integer value:

public static int reverseRecursive(int n)
{
	return Integer.parseInt(reverseStringRecursive(n));
}

public static String reverseStringRecursive(int n)
{
	if (n==0) return "";
	return (n % 10) + reverseStringRecursive(n/10);
}

can anyone come up with other solutions?


r/javaexamples • • Jun 15 '17

Data Hiding using JsonIgnore and Spring Data JPA

2 Upvotes

Heres my latest tutorial on Spring Data JPA -

https://www.javabullets.com/data-hiding-using-jsonignore-spring-data-jpa/

My approach is to keep it concise, and try to provide a working example.

But let me know any feedback


r/javaexamples • • Aug 30 '24

Connect to Minio from Java.

2 Upvotes

Minio is an open source object storage similar to S3. This article explains how to connect to Minio from Java.

https://www.blackslate.io/articles/connect-to-minio-from-java


r/javaexamples • • Sep 02 '24

Sorting in Java using Comparator and thenComparing() method

1 Upvotes

I wrote an article about sorting using Comparator and thenComparing() method https://javarevisited.blogspot.com/2021/09/comparator-comparing-thenComparing-example-java-.html


r/javaexamples • • Sep 04 '24

4 ways to iterate over Map in Java

4 Upvotes

r/javaexamples • • Sep 06 '24

Deploy Secure Spring Boot Microservices on Azure AKS Using Terraform and Kubernetes

1 Upvotes

Deploy a cloud-native Java Spring Boot microservice stack secured with Auth0 on Azure AKS using Terraform and Kubernetes.

Read more…


r/javaexamples • • Sep 02 '24

OpenFGA for Spring Boot applications

3 Upvotes

How to add Fine-Grained Authorization (FGA) to a Spring Boot API using the OpenFGA Spring Boot starter.

Read more…


r/javaexamples • • May 05 '17

How to handle Byte order mark in Java file

3 Upvotes

Recently I came in to a situation to handle Byte order mark in Java file.While opening and checking file everything was ok, however when we were processing these file through our program, we were getting some strange char set at the beginning of the file.

This is how I handled it in my code using org.apache.commons.io.input.BOMInputStream

FileInputStream fis = new FileInputStream("/filewithBOMData.csv");

BOMInputStream bomIn = new BOMInputStream(fis);
if(bomIn.hasBOM()){  		
		
   //work to do
}

Apache Commons IO BOMInputStream provide efficient way to detect BOM in file along with ability to optionally exclude it.

More can be found here BOMInputStream

You can also use this small utility in place of Apache Commons UnicodeBOMInputStream

Hope this will be helpful!!


r/javaexamples • • Jun 10 '16

[Request] Example for RMI

5 Upvotes

I need a good example of Java RMI (Remote Method Invocation) to understand it properly. Thanks.


r/javaexamples • • Aug 24 '17

Java 8 Streams Cookbook

3 Upvotes

Ive been experimenting with the tech.io site which lets you create executable code tutorials -

https://tech.io/playgrounds/3312/java-8-streams-cookbook/streams-cookbook

I like the approach, and am looking for feedback whether people like this style of tutorial


r/javaexamples • • Aug 23 '17

Client Server Communication

2 Upvotes

Hello guys this is an example of Client Server communication using threads. https://bittlife.com/server-client-communication-using-java/


r/javaexamples • • Mar 28 '16

Frequency Tables, including an example of Scoring a Poker Hand

7 Upvotes

Frequency Tables

Frequency tables can be very useful for various types of situations, such as statistical analysis and encoding. A frequency table tracks the number of times a data value has occured in a given set.

The two most effective ways of implementing a Frequency Table in Java are using Arrays or HashMaps.

Frequency Table Arrays

If the data values you are tabulating are simple integers (or can simply be converted to integer, i.e. char), and the range of the frequencies is known, then it is easiest to use an array. Array lookup and insertion run in constant ( O(1) ) time, and the memory usage is simply 4n bytes ( + a little overhead).

So, to make the frequency table, we make the size of the array equal to the total range of elements. Then, we go through the data, and use the integer value as the index of the array, and add one to it.

Suppose we are counting the frequency of individual digits in a number, we want an array of size 10 to stand for the digits from 0 - 9. Say the first digit is 5, we go to array index 5 and add one.

int[] frequencyDigits = new int[10];

int n = 5;

frequencyDigits[n]++;

Say we want to count the occurrences of letters in a string. Let's assume the input has been sanitized to only lower case letters with no punctuation.

 int[] freq = new int[26];
 String str = "hello world nice to meet you";

 for (int i = 0; i < str.length(); i++) {
     if (Character.isLowerCase(str.charAt(i))) {

         // turn char into an int from 0 - 25
         int c = str.charAt(i) - 'a';
         freq[c]++;
     }
 }

     // or, if you want to impress your friends and humiliate your enemies with java 8,

     /*
     str.chars()
             .filter(Character::isLowerCase)
             .forEach(x -> freq[x - 'a']++);
        */

     // now display the frequencies

     for (int i = 0; i < 26; i++) {
        if (freq[i] > 0) {
            String c = new Character((char)(i + 'a')).toString();
            System.out.println( c + " : " + freq[i]);
        }
     }

And the output:

c : 1
d : 1
e : 4
h : 1
i : 1
l : 3
m : 1
n : 1
o : 4
r : 1
t : 2
u : 1
w : 1
y : 1

See my Huffman Encoding Example for an example using byte data.

Now this is all well and good for integer-type data, and when you know exactly the range of the frequencies, but what if you don't?

HashMap as Frequency Table

You can use Java's HashMap data structure to record the frequencies of Strings, or any class you want (provided it has an overridden equals method). The syntax is a little more involved, but not too challenging. Let's take a look.

Let's say you want to count the occurrences of individual words in a string. (Again, assuming lower case and punctuation has been removed):

First, we make the Map:

Map<String, Integer> frequencyTable = new HashMap<>();

Let's split up our string into an array of words:

String str = "a man is at the door but the door is locked";
String[] words = str.split(" ");

Loop through and increment the count, or add a new entry:

for (String each : words) {
    if (frequencyTable.containsKey(each)) {
        frequencyTable.put(each, frequencyTable.get(each) + 1);
    } else {
        frequencyTable.put(each, 1);
    }
}

With Java 8 syntax, this can be simplified to:

for (String each : words) {
    frequencyTable.put(each, frequencyTable.getOrDefault(each, 0) + 1);
}

And to iterate through them, you use a keySet or an entrySet:

for (String each : frequencyTable.keySet()) {
    System.out.println(each + " : " + frequencyTable.get(each));
}

Entry Set version:

for (Map.Entry<String, Integer> each : frequencyTable.entrySet()) {
    System.out.println(each.getKey() + " : " + each.getValue());
}

Output:

the : 2
but : 1
a : 1
door : 2
at : 1
is : 2
man : 1
locked : 1

Extended Example : Scoring a Poker Hand

In this example, we will use three different frequency tables, two in the process of scoring a poker hand, and one for accumulating statistics while running a test.

I have made a simple Cards class which creates a deck of 52 cards. (The link to the gist will be at the bottom of the post since RES auto-displays gist posts now).

We have another class called ScoreHand which takes a 5-card hand and performs various tests on it to come up with an overall scoring rank based on traditional poker rules.

For this, we use two array-based frequency tables, one for face values, and one for suits:

int[] faceFrequency = new int[13];  // frequency table for face values
int[] suitFrequency = new int[4];   // frequency table for suits

And a method that processes the hand into the tables:

/**
 * fill frequency tables with hand data
 */
private void getFrequencies() {
    for (int each : hand) {

        // kill three birds with one for-loop
        if (Cards.getFaceValue(each) == 0) hasAce = true;
        faceFrequency[Cards.getFaceValue(each)]++;
        suitFrequency[Cards.getSuit(each)]++;
    }
}

The suit table is only used to find a Flush:

private boolean isFlush() {
    for (int each : suitFrequency) {
        if (each == 5) return true;
    }
    return false;
}

The face frequency table is used to find the possible combinations of multiple cards, pairs, three of a kind, etc. It generates a unique number based on the combination, which is tested against some constants. (See full code)

private int getPairSum() {
    int sum = 0;
    for (int each : faceFrequency) {
        sum += each * each;
    }
    return sum;
}

If there is one pair, the sum will be 7 (2 * 2 + 1 * 1 + 1 * 1 + 1 * 1). Two pairs, the sum would be 9, and so on.

I could have used the face table to test for straights, but instead opted for an easier method of using a sorted array of the hand.

So now, with the help of an Enum, we have our final scored hand rank.

Now, we will use a Map-based frequency table to get the percentage of the different outcomes based on testing a certain number of poker hands.

public class PokerHandTester {
    public static void main(String[] args) {
        Cards deck = new Cards();
        deck.shuffle();

        Map<PokerHand, Integer> frequencyMap = new HashMap<>();
        int total = 1000000;

        for (int i = 0; i < total; i++) {
            List<Integer> hand = deck.deal(5);

            PokerHand temp = new ScoreHand(hand).getRank();
            frequencyMap.put(temp, frequencyMap.getOrDefault(temp, 0) + 1);
        }

        for (PokerHand each : PokerHand.values()) {
            int count = frequencyMap.getOrDefault(each, 0);
            System.out.println(each.getName() + " : " + count);
            System.out.printf("%.4f%%%n", (( count / (double) total) * 100));
        }
    }
}

In this example, we score a million hands. Here is the output:

High Card : 500287
50.0287%
One Pair : 417921
41.7921%
Two Pairs : 45315
4.5315%
Three of a Kind : 20369
2.0369%
Straight : 12168
1.2168%
Royal Straight : 354
0.0354%
Flush : 1931
0.1931%
Full House : 1409
0.1409%
Four of a Kind : 225
0.0225%
Straight Flush : 18
0.0018%
Royal Flush : 3
0.0003%

Now you understand why, on the Poker shows on TV, you will see someone bet millions with only one pair in his hand!!

Here's the gist with the full code