HashSets

Intro

Before I can talk about HashSets, I need to talk about Sets overall. A Set is a data structure, like ArrayLists (or Lists in some other languages), but like Stacks, Queues, etc., it is considered an Advanced Data Type in (ADT Java. There is an entire class on these data structures in college, and we go into some detail in HL. HL covers the material found in UW's CSE 145, which is considered to be general overview off data structures. That all aside, let's get into the main part of this.

Dictionaries and Key-Value Pairs

I like to explain what a Set is using the concept of a Dictionary in C# and some other languages. This is not how Parker explains it, but it makes a advanced connection easier to grasp (I don't think it's that hard, but it's considered advanced). A Dictionary is declared liked this in C#:

Dictionary<string, int> dict = new Dictionary<string, int>();

Let's break this down. Notice how the declaration has <>. Just like an ArrayList, you must specify a type. However, there are two values there: string and int (in C# you don't need to use wrapper classes). These are called the "key" and "value". Colllectively they are called a "key-value pair". That is the terms used most languages with structures like this, but Java tends to use slightly different terminology. Since these terms are considered general use, you can use this terms and you won't loose points whatsoever.

Key-Value Pair

Dictionaries work kinda like a table. Each key in the Dictionary, has a value. For example, this Dictionary may have elements like this:

"Raghav", 17
"Ken", 17
"Richard", 16

Each element has a string and an int. The int is associated with the string. In C#, with Lists and Dictionaries you can use [] like with an array (replacing .get()). Here you would put the key in the []. For example:

int ragsAge = dict["Raghav"];
// ragsAge = 17

Benefits

Dictionaries are a very fast. They have O(1) look up, adding, deleting, etc. Very fast.

Dictionaries => Maps and Sets

Maps

In Java, Dictionaries have two equivalents. Maps and Sets. Maps work exactly the same as a Dictionary:

Map<String, Integer> map = new HashMap<>();
/* Code assigning those three elements to this Map
   ...
*/
int ragsAge = map.get("Raghav");

Sets

Sets however are slightly different. These two declarations are the same:

Map<String, Boolean> map = new HashMap<>();
Set<String> set = new HashSet<>();

Sets are fundamentally just Maps, whose values are booleans. The slight difference is that in practice, we only add values that do exist.

Hash vs. Tree

You may have noticed that in my Java code, I create HashMaps and HashSets. Hash means that the elemetns are in a "random" order. It's not necesarrily random, but you think of it as random. You are not expected to know the order that it puts the elements in, put it is similar to the algorithm for a HashTable. Tree means that its sorted in natural order. Natural order for different data types are different. For int: 1, 2, 3. For Strings: a, b, c. You can read more about it on the internet.

MechaDragonX/hashset.md