Unit 9: Sets and Maps
Store unordered, non-duplicate elements using a set
The Set interface extends the Collection interface.
It does not introduce new methods or constants, but it stipulates that an instance of Set contains no duplicate elements.
The concrete classes that implement Set must ensure that no duplicate elements can be added to the set.
The AbstractSet class extends AbstractCollection and implements Set.
The AbstractSet class provides concrete implementations for the equals method and the hashCode method.
The hash code of a set is the sum of the hash code of all the elements in the set. Since the size method and iterator method are not implemented in the AbstractSet class, AbstractSet is an abstract class.
Exploring HashSet, LinkedHashSet, and TreeSet
//HashSet
import java.util.*;
public class TestHashSet {
public static void main(String[] args) {
Set<String> set = new HashSet<>(); // Create a hash set
// Add strings to the set
set.add("London");
set.add("Paris");
set.add("New York");
set.add("San Francisco");
set.add("Beijing");
set.add("New York");
System.out.println(set);
// Display the elements in the hash set
for (String s: set) {
System.out.print(s.toUpperCase() + " ");
}
System.out.println();
// Process the elements using a forEach method
// uses an iterator to traverse the elements in the list
set.forEach(e -> System.out.print(e.toLowerCase() + " "));
}
}
/*
[San Francisco, Beijing, New York, London, Paris]
SAN FRANCISCO BEIJING NEW YORK LONDON PARIS
san francisco beijing new york london paris
//LinkedHashSet
//maintains order of insertion
import java.util.*;
public class TestLinkedHashSet {
public static void main(String[] args) {
Set<String> set = new LinkedHashSet<>(); // Create a hash set
// Add strings to the set
set.add("London");
set.add("Paris");
set.add("New York");
set.add("San Francisco");
set.add("Beijing");
set.add("New York");
System.out.println(set);
// Display the elements in the hash set
for (String element: set) {
System.out.print(element.toUpperCase() + " ");
}
System.out.println();
// Process the elements using a forEach method
// uses an iterator to traverse the elements in the list
set.forEach(e -> System.out.print(e.toLowerCase() + " "));
}
}
/*[London, Paris, New York, San Francisco, Beijing]
LONDON PARIS NEW YORK SAN FRANCISCO BEIJING
london paris new york san francisco beijing
//TreeSet (Red-Black tree)
import java.util.*;
public class TestTreeSet {
public static void main(String[] args) {
TreeSet<String> treeSet = new TreeSet<>(); // Create a tree set
// Add strings to the set
treeSet.add("London"); treeSet.add("Paris"); treeSet.add("New York");
treeSet.add("San Francisco"); treeSet.add("Beijing"); treeSet.add("New York");
System.out.println("Sorted tree set: " + treeSet);
// Use the methods in SortedSet interface
System.out.println("first(): " + treeSet.first());
System.out.println("last(): " + treeSet.last());
System.out.println("headSet(\"New York\"): “
+ treeSet.headSet("New York"));
System.out.println("tailSet(\"New York\"): “
+ treeSet.tailSet("New York"));
// Use the methods in NavigableSet interface
System.out.println("lower(\"P\"): " + treeSet.lower("P"));
System.out.println("higher(\"P\"): " + treeSet.higher("P"));
System.out.println("floor(\"P\"): " + treeSet.floor("P"));
System.out.println("ceiling(\"P\"): " + treeSet.ceiling("P"));
System.out.println("pollFirst(): " + treeSet.pollFirst());
System.out.println("pollLast(): " + treeSet.pollLast());
System.out.println("New tree set: " + treeSet);
}
}
/*[Sorted tree set: [Beijing, London, New York, Paris, San Francisco]
first(): Beijing
last(): San Francisco
headSet("New York"): [Beijing, London]
tailSet("New York"): [New York, Paris, San Francisco]
lower("P"): New York
higher("P"): Paris
floor("P"): New York
ceiling("P"): Paris
pollFirst(): Beijing
pollLast(): San Francisco
New tree set: [London, New York, Paris]
import java.util.*;
/* a program that demonstrates how to sort elements in a tree
set using the Comparator interface. The example creates a tree
set of geometric objects. The geometric objects are sorted using
the compare method in the Comparator interface. */
public class TestTreeSetWithComparator {
public static void main(String[] args) {
// Create a tree set for geometric objects using a comparator
Set<GeometricObject> set = new TreeSet<>(new GeometricObjectComparator());
set.add(new Rectangle(4, 5));
set.add(new Circle(40));
set.add(new Circle(40));
set.add(new Rectangle(4, 1));
// Display geometric objects in the tree set
System.out.println("A sorted set of geometric objects");
for (GeometricObject element: set)
System.out.println("area = " + element.getArea());
}
}
import java.util.Comparator;
public class GeometricObjectComparator implements Comparator<GeometricObject>,
java.io.Serializable {
public int compare(GeometricObject o1, GeometricObject o2) {
double area1 = o1.getArea();
double area2 = o2.getArea();
if (area1 < area2) return -1;
else if (area1 == area2) return 0;
else return 1;
}
}
/*A sorted set of geometric objects
area = 4.0
area = 20.0
area = 5026.548245743669
Maps and the Difference between Collection and Map
Map interface is Not part of the collection hierarchy, but it is part of the java collection as a separate branch.
The Map interface maps keys to the elements. The keys are like indexes
The list indices are integers, in Map, the keys are object
In the Map interface there are HashMap, TreeMap, and LinkedHashMap
Exploring HashMap, TreeMap, and LinkedHashMap
The HashMap and TreeMap classes are two concrete implementations of the Map interface.
- The HashMap class is efficient for locating a value, inserting a mapping, and deleting a mapping.
- The TreeMap class, implementing SortedMap, is efficient for traversing the keys in a sorted order.
- LinkedHashMap extends HashMap with a linked list implementation that supports an ordering of the entries in the map in which they were inserted into the map (known as the insertion order), or the order in which they were last accessed, from least recently accessed to most recently (access order).
The no-arg constructor constructs a LinkedHashMap with the insertion order.
To construct a LinkedHashMap with the access order, use the LinkedHashMap(initialCapacity, loadFactor, true) .
import java.util.*;
public class CountOccurrenceOfWords {
public static void main(String[] args) {
// Set text in a string
String text = "Good morning. Have a good class. " +
"Have a good visit. Have fun!";
// Create a TreeMap to hold words as key and count as value
Map<String, Integer> map = new TreeMap<>();
String[] words = text.split("[\\s+\\p{P}]");
for (int i = 0; i < words.length; i++) {
String key = words[i].toLowerCase();
if (key.length() > 0)
if (!map.containsKey(key))
map.put(key, 1);
else {
int value = map.get(key);
value++;
map.put(key, value);
}
}