This post is part of a personal study group activity, summarizing the content after reading through the book "Grokking Algorithms."

Of all the data formats we've covered so far, the array is probably the most effective for handling a large number of values. However, arrays are specialized for storing exactly one value per element. What would happen if you wanted to store two values in a single element? You'd end up representing it as something like $[ [ "A", 1 ], [ "B", 2 ], [ "C", 3 ] ]$.

One downside of arrays is that finding a value quickly requires sorting them first. But once an array's depth gets deep, like an array containing other arrays as shown above, the structure gets complicated and increasingly hard to work with.

What's more, searching for a desired element in an array requires a time complexity of at least $O(\log N)$. What if there were a data structure that could search for a desired value in constant time, like $O(1)$, within a collection of data like an array? Somehow, this chapter seems like the place we'll find the answer.

Java, along with most programming languages, has a concept called Hash Table. Depending on the language, this may be called a hash, a map, a hash map, and so on, but the underlying concept is ultimately the hash table.

JAVA
HashMap<String, String> map = new HashMap<>();
map.put("A", "1");
map.put("B", "2");
map.put("C", "3");
map.put("D", "4");

Java manages this with its HashMap class. Unlike JavaScript, it has the characteristic that only data of a predeclared type can be entered. A single pair of data, like A: 1 or B: 2, is commonly referred to as key-value data. Hash tables are extremely effective at managing this kind of key-value data.

JAVA
HashMap<String, String> map = new HashMap<>();
map.put("A", "1");
map.put("B", "2");
map.put("C", "3");
map.put("D", "4");

System.out.println(map.get("A"));

To access data in a HashMap, you can access it by entering the key of the value you want, as shown above. What's interesting is that for a hash table, the amount of work needed for this kind of search is 1. That is, it has a time complexity of $O(1)$. We've spent so much effort learning all sorts of sorting techniques on arrays just to improve search speed—so what makes this thing capable of achieving that kind of workload?

Have you ever heard of the concept of hashing? Converting data into a unique value is called hashing. As a simple example, let's assume we have a mapping table like this.

Based on the table above, ABC would become 123, and EAD would become 514. It's a very crude example, but this kind of conversion can be considered a form of hashing. An algorithm that converts values like the table above is called a hash function.

Suppose the hash function we want to use converts keys A-Z into the corresponding numbers from the table above, then sums them all together. Converting FAD would proceed in this order.

1. The hash function converts FAD into 614.
2. Each digit is added together: 6 + 1 + 4.
3. We obtain the hash value 11.

This gives us the hash FAD = 11. The following conditions matter for hashing.

• Hashing a given value always returns the same result. (FAD must always return 11)
• Different values must not share the same hash value.

🔒 Hash Functions
Unlike the example above, most real hash functions use an asymmetric encryption method that's effectively impossible to reverse. For security, they also often incorporate a random value called a Salt during hashing to prevent brute-force attacks.
Because of this property, hashing is used to encrypt passwords, personal information, and other data that should be known only to the user, and includes algorithms like MD5, SHA-1, SHA-256, and SHA-512.

However, the hashing function in the example above is just a simplified illustration meant to aid understanding, and doesn't match real hashing. According to the hash function above, FAD, ADF, and DAF all end up with the same value, 11. This directly violates one of hashing's requirements: different values must not share the same hash value.

We'll discuss this issue later.

As described in the book, let's assume we're building a quirky dictionary that, given a certain word, returns the trendiest synonym for it.

The hash is based on the table used in the previous section, and the hashing result is obtained by multiplying together the converted numbers.

This would be a diagram of how the underlying hash table works internally. Given the key-value pair bad: evil, the hash function would convert it as follows.

1. Convert the key of bad: evil, which is bad.
2. Get the converted value 214.
3. Multiply each digit together to get the hash value $2 \times 1 \times 4 = 8$.

As shown above, the value evil is inserted at position 8. Let's also hash cab: taxi. Its hash value is 6. Also, ace: star has a hash value of 15.

The hash table now looks like this. What happens if we want to retrieve a previously stored value?

Let's retrieve the data for one of the keys we used, cab. The hashing algorithm converts it into 6.

Since we've obtained the hash value, we simply access the element at index 6, which is taxi. We've accessed the desired value directly, with no additional searching needed.

This is how hash tables achieve a time complexity of $O(1)$.

There's a hashing requirement mentioned briefly earlier.

• Different values must not share the same hash value.

Let's say we want to add dab: pat to the hash table from the previous section. dab's hash value is 8. All that's left is to insert it into the table—but there's a problem.

Index 8 already holds evil. This phenomenon, where different values end up with the same hash value, is called a collision.

The most traditional and simple approach is, when a value would be assigned to an already-occupied position, to add a nested structure like an array.

In other words, arrange it as shown above. So how does searching proceed in this case? Let's search for the data whose key is dab.

1. Compute dab's hash value, 8.
2. Notice that, due to a collision, index 8 holds an array.
3. Check the key of each element in the array to find a match.

In this case, the search will work correctly, but it now has a time complexity of $O(N)$. A data structure fast enough to have a time complexity of $O(1)$ has instantly become equivalent to an ordinary array. However you look at it, this isn't a good outcome.

In conclusion, hashing should be designed to minimize collisions as much as possible.

The book explains that a hash table's efficiency depends on the following three factors.

• How much data is stored in the hash table
• How many cells are available in the hash table
• Which hash function is used

Based on the mapping table used earlier, let's now assume we use a function that sums the converted digits repeatedly until it reduces to a single digit.

For put, the converted value is 16 + 21 + 20 = 57, and summing 57's digits again gives 5 + 7 = 12, then 1 + 2 = 3, so ultimately put = 3.

Assume we have a hash table like this. There are 16 available slots, but due to the nature of this hash function, the hash value is always somewhere between 1 and 9, so slots 10 through 16 will always be empty.

In other words, a hash table's size should be at least large enough to accommodate the range of expected hash values. If the hash range is 1 to 10 but the hash table's size is 100, collisions would be very unlikely, but that wastes a huge amount of memory.

In other words, collision resolution needs to be done appropriately so that all hash values can be accommodated without wasting too much memory.

According to research, when there are 7 pieces of data, having 10 rows in the table is ideal. This ratio is called the load factor, and a load factor of 70% is considered optimal. Fortunately, the fine details of hash tables are handled at the compiler level, so unless you need fine-grained tuning, this isn't something developers need to worry about.

Thanks to hashing's properties, hash tables are used in countless places for countless purposes, but this book focuses on using hash tables to speed up algorithms.

Chapter 1 covered sets, where no element is duplicated. Building a set algorithm using an array requires search and insertion operations, each with a time complexity of $O(N)$.

The property of a set—having every element be unique and non-duplicated—is extremely useful in many places, but it comes with a linear time complexity of $O(N)$. What if we applied a hash table here, where search has a time complexity of $O(1)$?

As shown above, we could dramatically reduce the workload. We already wrote logic to check for duplicate elements in an array back in Chapter 4. The time complexity of the initial design was $O(N^2)$, but after improvements, we managed to bring it down to $O(N)$.

JAVA
/**
 * 요소의 중복 여부 반환 함수
 *
 * @param array: [int[]] 배열
 *
 * @return [boolean] 중복 여부
 */
private static boolean isDuplicated(int[] array)
{
	for (int i = 0; i < array.length; i++)
	{
		for (int j = 0; j < array.length; j++)
		{
			count++;
			
			// 서로 다른 요소가 동일한 값을 가질 경우
			if (i != j && array[i] == array[j])
			{
				return true;
			}
		}
	}
	
	return false;
}

The source code above is the $O(N^2)$ version of the duplicate-check algorithm from Chapter 4.

JAVA
/**
 * 요소의 중복 여부 반환 함수
 *
 * @param array: [int[]] 배열
 *
 * @return [boolean] 중복 여부
 */
private static boolean isDuplicated(int[] array)
{
	ArrayList<Integer> list = new ArrayList<>();
	
	for (int item : array)
	{
		count++;
		
		// 중복되지 않았을 경우
		if (!list.contains(item))
		{
			list.add(item);
		}
		
		// 중복된 경우
		else
		{
			return true;
		}
	}
	
	return false;
}

The source code above is the $O(N)$ version of the duplicate-check algorithm from Chapter 4. Let's use a hash table to bring this type of algorithm down to a time complexity of $O(1)$.

Following the theme suggested in the book, let's design an electronic voting machine that lets voters pick from a list of candidates or add an arbitrary candidate.

JAVA
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

/**
 * 누구나 자료 구조와 알고리즘 전자 투표 기계 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/07/29/about-algorithm-chapter07/">해시 테이블로 매우 빠른 룩업</a>
 * @since 2021.07.29 Thu 22:15:32
 */
public class Vote
{
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		ArrayList<String> list = new ArrayList<>();
		
		while (true)
		{
			writer.write("후보 이름 입력 (x: 종료) >> ");
			writer.flush();
			
			String name = reader.readLine().trim();
			
			// x가 입력되었을 경우
			if (name.equalsIgnoreCase("x"))
			{
				break;
			}
			
			// 빈 문자가 입력되었을 경우
			else if (name.equals("") || name.isEmpty())
			{
				writer.newLine();
				writer.write("올바른 이름을 입력하세요.");
			}
			
			// 일반적인 이름이 입력되었을 경우
			else
			{
				list.add(name);
			}
		}
		
		writer.write(list.toString());
		writer.flush();
		
		writer.close();
		reader.close();
	}
}

INPUT
Jay
Park
Kim
Park
Kim
Jay
Jay
Jay
Park
Kim
x

OUTPUT
[Jay, Park, Kim, Park, Kim, Jay, Jay, Jay, Park, Kim]

The source code and input/output are as shown above. Since it simply takes input and appends it to the array regardless of duplicates, its time complexity has just one insertion step, so it's $O(1)$.

Fast as it is, once there are many candidates or many voters, this becomes very hard to organize. In the former case, there are too many categories to classify; in the latter, too much data to classify.

What if we used a hash table to map each candidate's name to their vote count and display it simply?

JAVA
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashMap;

/**
 * 누구나 자료 구조와 알고리즘 해시 테이블을 적용한 전자 투표 기계 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/07/29/about-algorithm-chapter07/">해시 테이블로 매우 빠른 룩업</a>
 * @since 2021.07.29 Thu 22:27:23
 */
public class HashVote
{
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		ArrayList<String> list = new ArrayList<>();
		HashMap<String, Integer> map = new HashMap<>();
		
		while (true)
		{
			writer.write("후보 이름 입력 (x: 종료) >> ");
			writer.flush();
			
			String name = reader.readLine().trim();
			
			// x가 입력되었을 경우
			if (name.equalsIgnoreCase("x"))
			{
				break;
			}
			
			// 빈 문자가 입력되었을 경우
			else if (name.equals("") || name.isEmpty())
			{
				writer.newLine();
				writer.write("올바른 이름을 입력하세요.");
			}
			
			// 일반적인 이름이 입력되었을 경우
			else
			{
				list.add(name);
			}
		}
		
		for (String name : list)
		{
			// 이미 등록된 이름일 경우
			if (map.containsKey(name))
			{
				map.put(name, map.get(name) + 1);
			}
			
			// 등록되지 않은 이름일 경우
			else
			{
				map.put(name, 1);
			}
		}
		
		writer.write(map.toString());
		writer.flush();
		
		writer.close();
		reader.close();
	}
}

INPUT
Jay
Park
Kim
Park
Kim
Jay
Jay
Jay
Park
Kim
x

OUTPUT
{Jay=4, Kim=3, Park=3}

The source code and input/output are as shown above. Jay got 4 votes, and everyone else got 3. It works cleanly, but since the vote tallying happens all at once after voting ends, an additional $O(N)$ search operation gets added, bumping the time complexity from constant to linear.

JAVA
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;

/**
 * 누구나 자료 구조와 알고리즘 해시 테이블을 적용한 향상된 전자 투표 기계 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/07/29/about-algorithm-chapter07/">해시 테이블로 매우 빠른 룩업</a>
 * @since 2021.07.29 Thu 22:31:45
 */
public class ImproveHashVote
{
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		HashMap<String, Integer> map = new HashMap<>();
		
		while (true)
		{
			writer.write("후보 이름 입력 (x: 종료) >> ");
			writer.flush();
			
			String name = reader.readLine().trim();
			
			// x가 입력되었을 경우
			if (name.equalsIgnoreCase("x"))
			{
				break;
			}
			
			// 빈 문자가 입력되었을 경우
			else if (name.equals("") || name.isEmpty())
			{
				writer.newLine();
				writer.write("올바른 이름을 입력하세요.");
			}
			
			// 일반적인 이름이 입력되었을 경우
			else
			{
				// 이미 등록된 이름일 경우
				if (map.containsKey(name))
				{
					map.put(name, map.get(name) + 1);
				}
				
				// 등록되지 않은 이름일 경우
				else
				{
					map.put(name, 1);
				}
			}
		}
		
		writer.write(map.toString());
		writer.flush();
		
		writer.close();
		reader.close();
	}
}

INPUT
Jay
Park
Kim
Park
Kim
Jay
Jay
Jay
Park
Kim
x

OUTPUT
{Jay=4, Kim=3, Park=3}

Instead of tallying the vote count at the end, votes are now counted in real time as each vote comes in. The underlying principle and the result are the same, but the speed is different.

Depending on whether the name is already registered, this splits into either search + insert, or just insert alone—but since search itself also has a time complexity of $O(1)$, the overall result can ultimately be expressed as $O(1)$.

The key points from this chapter are as follows.

• A hash table stores values as key-value pairs.
• A hash table manages keys by hashing them through an arbitrary function.
• A hash table's search time complexity is $O(1)$.
• A good hash function should minimize collisions.

The property of storing data as key-value pairs, along with fast search speed, will prove useful across many algorithms. In the next chapter, we'll look at two other very classic data structures: stacks and queues.