Skip to content

Instantly share code, notes, and snippets.

@Theartbug

Theartbug/java-collections.md

Last active July 25, 2019 16:22
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Theartbug/1a91a68f8a04393ed88212fce34b5db6 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Theartbug/1a91a68f8a04393ed88212fce34b5db6 to your computer and use it in GitHub Desktop.
Download ZIP
Java fundamentals collections
Raw
java-collections.md

Collection Operations

  • operations available on the Collections class
  • Algorithms, factories, utilities

Algorithms

  • public static void Collections.rotate(List<?> l, int distance): takes the last element of the list, moves to beginning, and shuffles all others down. Distance is the number of times to do this
  • public static void Collections.shuffle(List<?> l, Random rndm): random rearrangment of list items. Can accept a Random class object to determine the randomization
  • public static void Collections.sort(List<T> l, Comparator<? super T> c): accepts a comparator to organize the list by
    • in Java 8, the sort method is on the List interface itself list.sort(Comparator c)

Collection Factories

  • static methods on the Collections class that will create a new collection with specific properties
  • Singleton: immutable single value of collection
    • use when you want to pass a single value to a method that takes a collection
    • Example: Singletons
    Set<Integer> set = Collections.singleton(1);
List<String> list = Collections.singletonList("one");
Map<Integer, String> map = Collections.singletonMap(1, "one");
  • Empty: immutable empty collection
    • use when you want to pass no values to a method that requires a collection
    • Example: empties
    Set<Integer> set = Collections.emptySet();
List<String> list = Collections.emptyList();
Map<Integer, String> map = Collections.emptyMap();
  • Singleton and Empty often have performance advantages to creating an ArrayList or HashMap with no values
  • unmodifiable: creates a collection that has an immutable view, but mutable collectino
    • will throw an UnsupportedOperationException if attempts to mutate the view (add / remove from a view)
    • Example: attempted mutation
    UnmodifiableList list = new UnmodifiableList();
// the list itself is still mutable
list.add(Product.door);
// will throw an error, view not mutable
list.getProducts().add(Product.window);

Utilities

  • Collections.addAll(Collection<? extends T> c, T i, T i, ...): lets you add multiple objects to a collection at once
  • Collections.min/max(Collection<? extends T> c, Comparator<? super T> comp): optionally takes a comparator

Collections of Pairs: Maps

why map?

  • does not extend or implement the Collection interface
  • methods:
    • V put(K key, V value): single value
    • void putAll(Map<? extends K, ? extends V> values): another map
    • null keys and values are implementation specific
    • V get(Object key)
    • boolean containsKey(Object key)
    • boolean constainsValue(Objecet value)
    • V remove(Object key)
    • void clear()
    • int size()
    • boolean isEmpty()
  • Example: MapProductLookupTable
public class MapProductLookupTable implements ProductLookupTable {
  private final Map<Integer, Product> idToProduct = new HashMap()<>;
  
  @Override
  public void addProduct(final Product productToAdd) {
    final int id = productToAdd.getId();
    if (idToProduct.containsKey(id) throw new IllegalArgumentException("Unable to add product, duplicate id for " + productToAdd);
    
    idToProduct.put(id, productToAdd);
  }
  
  @Override 
  public Product lookupById(final int id) {
    // will return null if not found
    return idToProduct.get(id);
  }
  
  public void clear() {
    idToProduct.clear();
  }
}

views over maps

  • can create a segemented view of a map depending on the key or the value
  • methods:
    • Collection<Object O> keySet(): returns a set of the keys
      • if you manipulate the keys in this set, the original map will also be manipulated (removal)
      • cannot add directly to the Set, will throw an error
    • Collection<Object O> keyValues(): returns a set of the values
      • can do a remove as well, but no add
    • Set<Map.Entry<Object, Object>> entrySet(): useful for iteration
  • Example: entrySet iteration
final Set<Map.Entry<Integer, Product>> entries = idToProduct.entrySet();

for (Map.Entry<Integer, Product> entry : entries) {
  ...
  // .setValue() method is useful during this time to update multiple fields
}

Sorted and Navigable map

  • traversal in key ascending order
  • SortedMap is superseded by NavigableMap
  • SortedMap methods:
    • K firstKey()
    • K lastKey()
    • SortedMap<K, V> tailMap(E fromKey): inclusive
    • SortedMap<K, V> headMap(E toKey): exclusive
    • SortedMap<K, V> subMap(E fromKey, K toKey)
  • in order to have sorting, must have a key that is comparable or have a specific comparator
  • NavigableMap methods:
    • Map.Entry<K, V> firstEntry()
    • Map.Entry<K, V> lastEntry()
    • Map.Entry<K, V> pollFirstEntry(): removal
    • Map.Entry<K, V> polllastEntry(): removal
    • Map.Entry<K, V> lowerEntry(K key): greatest element that is strictly less than the key
    • Map.Entry<K, V> higherEntry(K key): lowest element that is structly greater than the key
    • K lowerKey(K key)
    • K higherKey(K key)
    • Map.Entry<K, V> floorEntry(K key): next in order
    • Map.Entry<K, V> ceilingEntry(K key): next in order
    • K floorKey(K key)
    • K ceilingKey(K key)
    • NavigableMap<K, V> descendingMap(): reverse order
    • NavigableSet<K> descendingKeySet(): reverse order
    • NavigableSet<K> navigableKeySet()
    • NavigableMap<K, V> tailMap(E fromKey, boolean incl)
    • NavigableMap<K, V> headMap(E toKey, boolean incl)
    • NavigableMap<K, V> subMap(K fromKey, boolean frominclusive, K toKey, boolean toInclusive)

Java 8 enhancements

  • methods:
    • replace(key, value): if key does not exist, will do nothing
    • replaceAll(BiFunction<K, V, V>): replaces all in map based upon the function
    • remove(key, value)
    • getOrDefault(K, Default): has option for default if does not exist
    • putIfAbsent(K, V): add if does not exist
    • compute(K, Func): takes a key and a function, then computes a new value based on the function
      • computeIfAbsent / computeIfPresent
    • merge(K, V, V, BiFunction<K, V, V>): merges a given key, oldvalue, newvalue with a given function
    • forEach: callback based iteration
  • Example: bifunction
idToProduct.replaceAll((id, oldProduct) -> 
  new Product(id, oldProduct.getName(), oldProduct.getWeight() + 10));

implementations

  • HashMap
    • good general purpose implementation
    • use .hashCode() method just like HashSet
    • maintains an array of buckets
      • hash % bucket_count
    • buckets are linked lists to accomodate collisions
      • if two different keys are associated with the same bucket, will be a LinkedList under the hood
    • buckets can be trees
    • number of buckets increases with more elements
      • if you have too many collisions, will turn into a Tree under the hood, performance improvement
  • TreeMap
    • implemented using red-black tree (balanced binary)
    • navigable and sorted
      • uses comparable / comparator to define the order
    • will regularly rebalance to become efficient when searching
    • maximum depth is bound log2(N)
  • LinkedHashMap
    • based on HashMap
    • maintains an order based on either insertion, or access
    • protected boolean removeEldestEntry(Map.Entry<K, V> eldest)
      • good for implementing caches
  • WeakHashMap
    • weak references key
    • can be removed when unreachable
    • used as a cache
  • EnumMap
    • for when keys are enums, faster than other maps
    • implementation based upon bitsets (stored as a singel long for <= 64 elements
Map put get/containsKey next
HashMap O(N), Omega(1) O(log N), Omega(1) O(Capacity/N)
LinkedHashMap O(N), Omega(1) O(log N), Omega(1) O(Capacity/N)
IdentityHashMap O(N), Omega(1) O(N), Omega(1) O(Capacity/N)
TreeMap O(log N) O(log N) O(log N)
EnumMap O(1) O(1) O(1)

Mutable HashMap keys

  • do not allow mutability of hash keys, will create a different hashcode
  • will break the map

Collections and Modification Order: Queues, Deques, Stacks

Queues

  • first in, first out
    • elements leave in the order they went in
  • methods:
    • boolean offer(E e): returns false if the queue is full
    • boolean add(E e): returns exceptions if the quese is full
      • returns false if element already exists
    • E remove(): throws exception if empty
    • E poll(): returns null if empty
    • E element(): throws exception if empty
    • E peek(): returns null if empty
    • probably want to use offer and poll more often than add and remove
  • Example: HelpDesk
public class CategorisedHelpDesk {

  private final Queue<Enquiry> queue = new ArrayDeque<>();
  
  public void enquire(final Custom customer, final Category category) {
    queue.offer(new Enquiry(customer, category));
  }
  
  // general processing
  public void processAllEnquiries() {
    Enquiry enquiry;
    while ((enquiry = enquiries.poll()) != null) {
    // using the remove() method, will throw errors
    // while (!enquiries.isEmpty()) {
      final Enquiry = enquiry = enquiries.remove();
      enquiry.getCustom().reply("Have you tried turning it off and on again?");
    }
  }
  
  public void processEnquiry(predicate, message) {
    // will look into the queue to see if we should handle, if not, leave it alone on the queue
    final Enquiry enquiry = enquiries.peek();
    if (enquiry != null && predicate.test(enquiry)) {
      enquiry.remove()
      enquiry.getCustom().reply(message);
    } else {
      System.out.println("No work here, get snacks!");
    }
  }
  
  public void processPrinterEnquiry() {
    // in Java 8, can use predicate
    Predicate<Enquiry> predicate = enquiry -> enquiry.getCategory() == PRINTER;
    final String message = "Have you tried turning it off and on again?";
    processEnquiry(predicate, message);
  }
  
  public void processGeneralEnquiry() {
    // in Java 8, can use predicate
    Predicate<Enquiry> predicate = enquiry -> enquiry.getCategory() != PRINTER;
    final String message = "Is it out of paper?";
    processEnquiry(predicate, message);
  }
  
  public static void main(String[] args) {
    HelpDesk helpDesk = new HelpDesk(0;
    
    helpDesk.enquire(Customer.JACK, Category.PHONE);
    helpDesk.enquire(Custom.JILL, Category.PRINTER);
    
    helpDesk.processPrinterEnquiry();
    helpDesk.processGeneralEnquiry();
  }
}

Priority Queues

  • highest priority out
    • just defines ordering
  • Example: PriorityHelpDesk
public class PriorityHelpDesk {

  private static final Comparator<Enquiry> BY_CATEGORY = new Comparator<Enquiry>() {
    public int compare(final Enquiry o1, final Enquiry o2) {
      // Enums have a compareTo method built in from their ordering
      return o1.getCategory().compareTo(o2.getCategory());
    }
  }
  
  // PriorityQueue requires a comparator to be passed in
  private final Queue<Enquiry> queue = new PriorityQueue<>(BY_CATEGORY);
  
  public void enquire(final Custom customer, final Category category) {
    enquiries.offer(new Enquiry(customer, category));
  }
  
  // general processing
  public void processAllEnquiries() {
    Enquiry enquiry;
    while ((enquiry = enquiries.poll()) != null) {
      final Enquiry = enquiry = enquiries.remove();
      enquiry.getCustom().reply("Have you tried turning it off and on again?");
    }
  }
  
  public static void main(String[] args) {
    HelpDesk helpDesk = new HelpDesk(0);
    
    helpDesk.enquire(Customer.JACK, Category.PHONE);
    helpDesk.enquire(Custom.JILL, Category.PRINTER);
    helpDesk.enquire(Customer.MARY, Category.COMPUTER);
    
    helpDesk.processPrinterEnquiry();
    helpDesk.processGeneralEnquiry();
  }
}

Stacks and Deques

  • Stacks: last in, first out
    • depricated with java.utils, DO NOT USE
  • Deque: double ended que, better stack, use instead
    • add or remove from both ends! Use as a Queue or a Stack
  • methods:
    • boolean offerFirst(E e) / boolean offerLast(E e)
      • returns false if queue is full
    • void addFirst(E e) / void addLast(E e)
      • throws exception if full
    • E removeFirst() / E removeLast()
      • throws exception if empty
    • E pollFirst() / E pollLast()
      • returns null if empty
    • E getFirst() / E getLast()
      • throws exception when empty
    • E peekFirst() / E peekLast()
      • returns null
    • void push(E e)
    • E pop()
  • Example: Calculator
public class Calculator {

  public int evaluate(final String input) { 
  
  final Deque<String> stack = new ArrayDeque<>();
  final String[] tokens = input.split(" ");
  for (String token : tokens) {
    stack.add(token);
  }
  
  while (stack.size() > 1) {
    int left = parseInt(stack.pop());
    String operator = stack.pop();
    int right = parseInt(stack.pop());
    
    int result = 0;
    switch (operator) {
      case "+":
        result = left + right;
        break;
      case "-"
        result = left - right;
        break;
    }
    // convert back into a string
    stack.push(String.valueOf(result));
  }
  
  // return as an integer
  return parseInt(stack.pop()); }
}

implementations

  • there are multiple concurrent implementations of Queue
  • ArrayDeque
    • RingBuffer based implementation
    • constant time addition / removal
    • less memory, faster
    • no random access
  • LinkedList
    • previously discussed in Lists
    • very seldom used as a Queue
      • slower, uses more memory
    • has random access, but O(N)
    • allows null elements
      • can cause bugs

Collection Uniqueness: Sets

  • collection of distinct elements
  • no additional methods
  • Example: Catalogue
public class ProductCatalogue implements Iterable<Product> {

  // compares each Product's BY_NAME
  private final Set<Product> products = new TreeSet<>(BY_NAME);

  public void isSuppliedBy(Supplier supplier) {
    products.addAll(supplier.products());
  }
  
  public Iterator<Product> iterator() { return products.iterator(); }
}

  • TreeSet will throw an error if it is not given a recipe for how to order the elements given

    • if no recipe is added, will assume all Objects given are comparable (will have a natural built-in sort order)

  • Example: Product

public class Product {
  // comparator for the TreeSet
  public static final Comparator<Product> BY_NAME = Comparator.comparing(Product::getName);
  
  ...
}

SortedSet and NavigableSet

  • a collection with distinct elements that also have order

  • SortedSet defines an order

    • no index associated, but subset views possible
    • methods
      • E first();
      • E last();
    • methods for creating views
      • SortedSet<E> tailSet(E fromElement); (inclusive)
      • SortedSet<E> headSet(E toElement); (exclusive)
      • SortedSet<E> subSet(E fromElement, E toElement); (inclusive, exclusive)
    • if you remove an element from a view, it will be removed from the original collection (does not create a new collection)

  • NavigableSet extends SortedSet

    • provides ways to move through order, implemented by TreeSet
    • methods
      • E lower();: proceeded
      • E higher();: next
      • E floor();
      • E ceiling();
      • E pollFirst();
      • E pollLast();

  • Example: Catalogue

public class Product {
  // comparator for the TreeSet
  public static final Comparator<Product> BY_NAME = Comparator.comparing(Product::getName);
  
  public static final Comparator<Product> BY_WEIGHT = Comparator.comparing(Product::getWeight);
  
  public void isSuppliedBy(Supplier supplier) { products.addAll(supplier.products())); }
  
  public Iterator<Product> iterator() { return products.iterator(); }
  
  public Set<Product> lightVanProducts() {
    Product heaviestLightVanProduct = findHeaviestLightVanProduct();
    // does not include
    return products.headSet(heaviestLightVanProduct);
  }
  
  public Set<Product> heavyVanProducts() {
    Product heaviestLightVanProduct = findHeaviestLightVanProduct();
    // includes
    return products.tailSet(heaviestLightVanProduct);
  }
  
  private Product findHeaviestLightVanProduct() {
    for (Product product:products) {
      if (product.getWeight() > 20) return product;
    }
    // return the last element if none are greater than 20
    return products.last();
  }
}

Set Implementations

  • HashSet: based upon HashMap, calles hashCode() on element and looks up location
    • must implement the hashCode() method for lookups
      • will return a number than can be used to lookup the desired Object
    • good general purpose implementation
      • resizes when runs out of space
    • must follow the hashCode equals contract
      • object.equals(other) ==> object.hashCode() == other.hasCode()
      • hashcodes must match
    • to properly hashcode, you should combine information from each field
      • call hashCode() on each field, add it to a total for the Object, then multiply by some non-prime number
      • call `Arrays.hashCode() for arrays
      • (int) (l ^ (l >> 32)) for longs (give me the first 32 bits of information from the long to convert into an int)
      • Float.floatToIntBits(f) for floats
      • most IDE have refactor methods to do this automatically
      • can use Object.hashCode()
      • always use the same fields as the equals() method
  • TreeSet: based upon TreeMap, uses Binary Tree with a requied sort order
    • keep elements in given order (SortedSet, NavigableSet)
  • EnumSet: specialized implementation for enums
    • uses a bitset based upon the ordinal of the enum
set add contains next
HashSet O(N),Omega(1) O(N),Omega(1) O(Capacity/N)
TreeSet O(logN) O(logN) O(logN)
EnumSet O(1) O(1) O(1)
  • Example: HashCode and equals methods
public class Product {
  ...
  
  // intelliJ generates
  public boolean equals(final Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    
    final Product product = (Product) o;
    
    if (weight != product.weight) return false;
    // return !(name != null ? !name.equals(product.name) : product.name != null);
    // OR from Java 8
    return Objects.equals(name, product.name);
  }
  
  // intelliJ generates
  // public int hashCode() {
    // int result = name != null ? name.hashCode() : 0;
    // result = 31 * result + weight;
    // return result;
  // }
  
  // OR from Java 8
  public int hashCode() {
    return Objects.hash(name, weight);
  }
}

Collection Iteration: Lists

Key features

  • collection with iteration order
    • has an index int representing position
  • modification methods include index
    • void add(int index, E e)
    • E get(int index)
    • E remove(int index): all elements after the removed element shift down in index
    • E set(int index, E element)
    • boolean addAll(int index, Collection<? extends E> c)
    • int indexOf(Object o): will return -1 if not found, will only return fist found
    • Int lastIndexOf(Object o): will return -1 if not found, will only return last found
    • List<E> subList(int fromIndex, int toIndex): from is inclusive, to is exclusive
  • Example: shipments class
public class Shipment implements Iterable<Product> {
  private static final int LIGHT_VAN_MAX_WEIGHT = 20;
  
  private final List<Product> products = new ArrayList<>();
  private List<Product> lightVanProducts;
  private List<Product> heavyVanProducts;
  
  public void add(Product product) {
    products.add(product);
  }
  
  public void replace(Product oldProduct, Product newProduct) {
    final int oldProductIndex = products.indexOf(oldProduct);
    if (oldProductIndex > -1) products.set(oldProductIndex, newProduct);
  }
  
  public void prepare() {
    
    // sort list of products by weight
    // Collections.sort(products, Product.BY_WEIGHT
    // can use method in Java 8+
    products.sort(Product.BY_WEIGHT);
    
    // find the product index that needs heavy van
    int splitpoint = findSplitPoint();
    
    // assign view of product list for heavy and light vans
    lightVanProducts = products.subList(0, splitPoint);
    // since subList is exclusive on the end, can use size to include the last element
    heavyVanProducts = products.subList(splitPoint, products.size());
    
  }
  
  private int findSplitPoint() {
    for ( int i = 0; i < products.size(); i++) {
      Product product = products.get(i);
      if (product.getWeight() > LIGHT_VAN_MAX_WEIGHT) return i; 
    }
    return 0;
  }
  
  public List<Product> getHeavyVanProducts() { return heavyVanProducts; }
  
  public List<Product> getLightVanProducts() { return lightVanProducts; }
  
  // implementation of Iterable
  public Iterator<Product> iterator() { return products.iterate(); }
}
  • example: comparing method
// method in Java 8
public static final Comparator<Product> BY_WEIGHT = comparing(Product::getWeight);

implementations

  • you can implement your own if you want
  • Java ships with ArrayList and LinkedList
  • ArrayList
    • contains a backing Array and has a certain size
    • when end of ArrayList is reached, will need to resize the backing Array, which is expensive
      • will automatically double in size
    • good general purpose, use as default
    • CPU cache sympathetic
  • LinkedList
    • double-linked (reference to previous and next)
    • good for repeatedly adding and removing elements (from the start)
    • slow to iterate over, worst performance
    • use when manipulating elements at the start, bad for manipulation deep within
Collection get add contains next remove
ArrayList O(1) O(N), Omega(1) O(N) O(1) O(N)
LinkedList O(N) O(1) O(N) O(1) O(1)

Defining and Iterating Collections

  • all collections extend the java class Collection and have common features
  • children Interfaces (implementations) include:
    • List (ArrayList, LinkedList)
    • Set (HashSet) -> SortedSet (TreeSet): combine sorting abilities of a List with uniqueness of a Set, cannot index into
    • Queue (PriorityQueue): first in first out ordering -> Deque (LinkedList, ArrayDeque): first in first out, last in first out ordering
    • Map (HashMap) : key value pairs -> SortedMap (TreeMap): sort order allows for iteration

Collection of Collections

  • segregation between interface and implementation is cornerstone to Collections API
  • Interfaces:
    • multiple data structures
    • functional characteristics
      • random access to memory, sortable
    • prefer as variable type
    • often has a popular implementation
  • Implementation:
    • can have multiple implementations of a given interface
    • specific data structure
      • both ArrayList and LinkedList
    • performance characteristics
      • tradeoffs between different implementations
    • concrete and instantiable

how to pick a collection?

  • are elements keyed?
    • YES -> order important?
      • NO -> Map
      • YES -> SortedMap
    • NO -> are elements unique?
      • NO -> first in, first out?
        • YES -> Queue or Deque
        • NO -> last in, first out?
          • NO -> List
          • YES -> Deque
      • YES -> order important?
        • NO -> Set
        • YES -> SortedSet

Collection Behaviors

  • Collection extends Iterable which means we can pull an Iterator out of it, and move through the collection one at a time
  • methods that all share:
method functionality
size() number of elements in Collection
isEmpty() true if size() == 0
add(element) add to beginning, returns true if was added
addAll(collection) add elements of argument collection to this collection
remove(element) remove element from collection
removeAll(collection) remove all elements of argument collection to this collection
retainAll(collection) remove all elements of this collection not in argument collection
contains(element) true if element is in collection
containsAll(collection) true if all elements of argument collection are in this collection
clear() remove all elements from collection
  • declaring Collections
// must give a Generic type to the collection to tell what will be inside it
// can use an empty <> on righthand side as the type is inferred from the left
Collection<Product> products = new ArrayList<>(); 
products.add(door);
products.add(floorPanel);
products.add(window);

// instantiate the iterator
final Iterator<Product> productIterator = products.iterator();
while(productIterator.hasNext()) {
  Product product = productIterator.next();
  if (product.getWeight() > 20) {
    System.out.println(product);
  } else {
    productIterator.remove();
  }
}

// instead, can use a method that works just like the iterator
for (Product product: products) { ... }

// for loop will not allow modification of the collection while looping 
// cannot remove, clear
// will throw ConcurrentModificationException

why collections?

  • using arrays is not debugger friendly
    • must use System.out.println(Arrays.toString(array));
  • arrays do not resize after initial creation
    • lacks methods for adding, removing, finding index, etc.
    • would have to implement own code version for adding / removing / finding index
  • arrays allow duplicates
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment