Unordered Collections

Introduction

Collections used so far are ordered.  There is a predecessor or successor or parent

• Arrays
• Linked Lists
• Trees, general or binary

Sometimes these structures are used for unordered data items.

This chapter is concerned with collections that do not have order as part of the structure. 

Sets

This is conceptually the same as the mathematical set.

The expected operations would be

A = {a, b, e, f, h} and B = {a, c, f, k}

• A.size() returns _______
• A.add("m")
• A.remove("f")
• A.contains("c")
• A.union(B)
• A.intersection(B)
• A.difference(B)
• A.difference(B).isEmpty()

Maps

A map is a collection of key-value pairs.  The collection is sometimes called a Dictionary.

• You store a key along with a value.  
• The key must be unique.
• Keys are not in any particular order.
• You can retrieve the value given a key
• Keys and values are separate objects; not an object with key and value components

This has the characteristic of the mathematical function.  The keys are the domain and values are the range.

Operations

• boolean isEmpty()
• int size()
• boolean add(Object key, Object value)
• Object retrieve(Object key) //gets value
• boolean containsKey(Object key)
• boolean containsValue(Object value)
• iterate through keys
• iterate through values

Bags

A bag is a set that allow duplicate items.  If an item has two occurrences, then it can be removed twice as well.

There would be an internal counter maintaining a frequency count.

The operations are the same as a set except no union, intersection or difference operations.

• boolean isEmpty()
• int size()
• boolean add(Object)
• boolean remove(Object)
• boolean contains(Object)

Implementation

These unordered collections need a way to quickly store an object and quickly determine whether it exists in the collection or not and retrieve it.  In the case of the map, retrieve the value.

An array or linked list forces the processing to a sequential nature --> O(n).

• Sorting, O(n log n) and then using a binary search O(log n) is not acceptable
• Linked lists are not fully an answer either.
• A binary search tree gives O(log n) performance on the store and retrieve operation, but only if the tree is balanced

We need fast storage and fast retrieval.  Ideally we want O(1) performance.

With hashing, we can approach this level of performance.