Transcript IAT265-Lec-Jul07-JavaCollections.pptx

IAT 265
Java Collections
Jul 7, 2015
IAT 265
1
Data Structures
 With
a collection of data, we often want to
do many things
– Organize
– Iterate
– Add new
– Delete old
– Search
Jul 7, 2015
IAT 265
2
Data Structures
 Some
are built to enable fast searching
 Some enable fast insertion/deletion
–
–
–
–
–
–
What
Store
Iterate
Add
Delete
Search
Jul 7, 2015
LnkList
Light
simple
O(1)
O(1)
O(n)
Tree
Less light
moderate
O( lgN )
O( lgN + )
O(lgN)
IAT 265
HashTable
Medium
difficult
O(1)
O(1)
O(1)
3
Hash Table

An array in which items are not
stored consecutively - their place of
storage is calculated using the key
and a hash function
Key


hash
function
array
index
key
entry
4
10
Hashed key: the result of applying a
hash function to a key
Keys and entries are scattered
throughout the array
Jul 7, 2015
IAT 265
123
4
Hashing
insert: compute location,
insert TableNode; O(1)
 find: compute location,
retrieve entry; O(1)
 remove: compute location,
set it to null; O(1)

key
entry
4
10
123
Jul 7, 2015
IAT 265
5
Hashing example

10 stock details, 10 table positions

Stock numbers between 0 and 1000

Use hash function: stock no. / 100



What if we now insert stock no. 350?
– Position 3 is occupied: there is a collision
Collision resolution strategy: insert in the next
free position (linear probing)
Given a stock number, we find stock by
using the hash function again, and use
the collision resolution strategy if
necessary
Jul 7, 2015
IAT 265
0
1
2
3
4
5
6
7
8
9
key
85
entry
85, apples
323
462
350
323, guava
462, pears
350, oranges
912
912, papaya
6
Hashing performance

The hash function
– Ideally, it should distribute keys and entries evenly throughout the table
– It should minimize collisions, where the position given by the hash
function is already occupied


The collision resolution strategy
– Separate chaining: chain together several keys/entries in each position
– Open addressing: store the key/entry in a different position
The size of the table
– Too big will waste memory; too small will increase collisions and may
eventually force rehashing (copying into a larger table)
– Should be appropriate for the hash function used – and a prime number is
best
Jul 7, 2015
IAT 265
7
Applications of Hashing




Compilers use hash tables to keep track of declared
variables
A hash table can be used for on-line spelling
checkers — if misspelling detection (rather than
correction) is important, an entire dictionary can be
hashed and words checked in constant time
Hash functions can be used to quickly check for
inequality — if two elements hash to different values
they must be different
Storing sparse data
Jul 7, 2015
IAT 265
8
When to use hashing?

Good if:
– Need many searches in a reasonably stable table

Not So Good if
–
–
–
–
Many insertions and deletions,
If table traversals are needed
Need things in sorted order
More data than available memory
• Use a tree and store leaves on disk
Jul 7, 2015
IAT 265
9
Java Collections
Java Collection class is a class that
stores and organizes data
A
– Uses one of the algorithms mentioned in
previous lectures
Jul 7, 2015
IAT 265
10
Java Collections Framework
A
unified architecture for representing and
manipulating collections:
– Interfaces: The means by which you access a
collection class
• Independent of implementation details
– Implementations: The machinery behind the
interface that does the work
• Concrete implementations
– Algorithms: Algorithms that run on collection
classes: Searching and sorting
• Reusable Functionality
Jul 7, 2015
IAT 265
11
Java Collections Framework
 Why?
 Reduces
programming effort
 Increases program speed and quality
 Interoperable: You and I can pass data in
collections between our code
Jul 7, 2015
IAT 265
12
Interfaces
 Collection
– A group of objects (elements)
– This is a generic idea, there are more
detailed Collection types that you actually use
 Set
– A collection with no duplicate elements
 SortedSet
– A Set in ascending order
– (Typically alphabetical or numeric order)
Jul 7, 2015
IAT 265
13
Interfaces
 List
– An ordered collection
– May contain duplicates
– Can access by index (like ArrayList)
 Queue
– A collection that holds items in some order
– Typically FIFO (First in/First Out)
Jul 7, 2015
IAT 265
14
Interfaces
 Map
– An collection that maps keys to values
• Think phone book
– May contain duplicates
– Can access by index (like ArrayList)
 SortedMap
– A Map in sorted order of keys
Jul 7, 2015
IAT 265
15
Using a List
Declare:
ArrayList aList = new ArrayList(6);
 Methods
you use:
SomeClass item, newItem, existingItem ;
item = (SomeClass)aList.get( i );
aList.add( newItem );
aList.remove( existingItem );
Jul 7, 2015
IAT 265
16
Using a HashMap
HashMap<String,String> hm = new HashMap<String,String> ();
hm.put( "Ava", "555-8976" );
hm.put( "Mary", "555-1238" );
hm.put( "Joe", "555-2121" );
String phone = hm.get( "Mary" );
Iterator I = hm.entrySet().iterator();
while( I.hasNext() ) {
Map.Entry me = (Map.Entry)I.next();
print( me.getKey() + " is " );
println( me.getValue() );
}
Jul 7, 2015
IAT 265
17
Using a TreeMap
TreeMap<String,String> tm = new TreeMap<String,String>();
tm.put( "Ava", "555-8976" );
tm.put( "Mary", "555-1238" );
tm.put( "Joe", "555-2121" );
String phone = tm.get( "Mary" );
Iterator I = tm.entrySet().iterator();
while( I.hasNext() ) {
Map.Entry me = (Map.Entry)I.next();
print( me.getKey() + " is " );
println( me.getValue() );
}
Jul 7, 2015
IAT 265
18
Jul 7, 2015
IAT 265
19