Easy to Learn Java: Programming Articles, Examples and Tips

Start with Java in a few days with Java Lessons or Lectures

Home

Code Examples

Java Tools

More Java Tools!

Java Forum

All Java Tips

Books

Submit News
Search the site here...
Search...
 

11: Collections of Objects

Custom Search
11: Collections of Objects

[ Return to Thinking in Java 2, 3rd edition ]

Page: 24/36 



Previous Page Previous Page (23/36) - Next Page (25/36) Next Page

Notice that the comparisons are only interested in the keys, so duplicate values are perfectly acceptable. Feedback

The following example implements a Map using a pair of ArrayLists: Feedback

//: c11:SlowMap.java
// A Map implemented with ArrayLists.
import com.bruceeckel.simpletest.*;
import java.util.*;
import com.bruceeckel.util.*;

public class SlowMap extends AbstractMap {
  private static Test monitor = new Test();
  private List
    keys = new ArrayList(),
    values = new ArrayList();
  public Object put(Object key, Object value) {
    Object result = get(key);
    if(!keys.contains(key)) {
      keys.add(key);
      values.add(value);
    } else
      values.set(keys.indexOf(key), value);
    return result;
  }
  public Object get(Object key) {
    if(!keys.contains(key))
      return null;
    return values.get(keys.indexOf(key));
  }
  public Set entrySet() {
    Set entries = new HashSet();
    Iterator
      ki = keys.iterator(),
      vi = values.iterator();
    while(ki.hasNext())
      entries.add(new MPair(ki.next(), vi.next()));
    return entries;
  }
  public String toString() {
    StringBuffer s = new StringBuffer("{");
    Iterator
      ki = keys.iterator(),
      vi = values.iterator();
    while(ki.hasNext()) {
      s.append(ki.next() + "=" + vi.next());
      if(ki.hasNext()) s.append(", ");
    }
    s.append("}");
    return s.toString();
  }
  public static void main(String[] args) {
    SlowMap m = new SlowMap();
    Collections2.fill(m, Collections2.geography, 15);
    System.out.println(m);
    monitor.expect(new String[] {
      "{ALGERIA=Algiers, ANGOLA=Luanda, BENIN=Porto-Novo,"+
      " BOTSWANA=Gaberone, BURKINA FASO=Ouagadougou, " +
      "BURUNDI=Bujumbura, CAMEROON=Yaounde, " +
      "CAPE VERDE=Praia, CENTRAL AFRICAN REPUBLIC=Bangui,"+
      " CHAD=N'djamena, COMOROS=Moroni, " +
      "CONGO=Brazzaville, DJIBOUTI=Dijibouti, " +
      "EGYPT=Cairo, EQUATORIAL GUINEA=Malabo}"
    });
  }
} ///:~


The put( ) method simply places the keys and values in corresponding ArrayLists. In main( ), a SlowMap is loaded and then printed to show that it works. Feedback

This shows that it’s not that hard to produce a new type of Map. But as the name suggests, a SlowMap isn’t very fast, so you probably wouldn’t use it if you had an alternative available. The problem is in the lookup of the key; there is no order, so a simple linear search is used, which is the slowest way to look something up. Feedback

The whole point of hashing is speed: Hashing allows the lookup to happen quickly. Since the bottleneck is in the speed of the key lookup, one of the solutions to the problem could be to keep the keys sorted and then use Collections.binarySearch( ) to perform the lookup (an exercise at the end of this chapter will walk you through this process). Feedback

Hashing goes further by saying that all you want to do is to store the key somewhere so that it can be quickly found. As you’ve seen in this chapter, the fastest structure in which to store a group of elements is an array, so that will be used for representing the key information (note carefully that I said “key information,” and not the key itself). Also seen in this chapter was the fact that an array, once allocated, cannot be resized, so we have a problem: We want to be able to store any number of values in the Map, but if the number of keys is fixed by the array size, how can this be? Feedback

The answer is that the array will not hold the keys. From the key object, a number will be derived that will index into the array. This number is the hash code, produced by the hashCode( ) method (in computer science parlance, this is the hash function) defined in Object and presumably overridden by your class. To solve the problem of the fixed-size array, more than one key may produce the same index. That is, there may be collisions. Because of this, it doesn’t matter how big the array is; each key object will land somewhere in that array. Feedback

So the process of looking up a value starts by computing the hash code and using it to index into the array. If you could guarantee that there were no collisions (which could be possible if you have a fixed number of values) then you’d have a perfect hashing function, but that’s a special case. In all other cases, collisions are handled by external chaining: The array points not directly to a value, but instead to a list of values. These values are searched in a linear fashion using the equals( ) method. Of course, this aspect of the search is much slower, but if the hash function is good, there will only be a few values in each slot. So instead of searching through the entire list, you quickly jump to a slot where you have to compare a few entries to find the value. This is much faster, which is why the HashMap is so quick. Feedback

Knowing the basics of hashing, it’s possible to implement a simple hashed Map:

//: c11:SimpleHashMap.java
// A demonstration hashed Map.
import java.util.*;
import com.bruceeckel.util.*;

public class SimpleHashMap extends AbstractMap {
  // Choose a prime number for the hash table
  // size, to achieve a uniform distribution:
  private static final int SZ = 997;
  private LinkedList[] bucket = new LinkedList[SZ];
  public Object put(Object key, Object value) {
    Object result = null;
    int index = key.hashCode() % SZ;
    if(index < 0) index = -index;
    if(bucket[index] == null)
      bucket[index] = new LinkedList();
    LinkedList pairs = bucket[index];
    MPair pair = new MPair(key, value);
    ListIterator it = pairs.listIterator();
    boolean found = false;
    while(it.hasNext()) {
      Object iPair = it.next();
      if(iPair.equals(pair)) {
        result = ((MPair)iPair).getValue();
        it.set(pair); // Replace old with new
        found = true;
        break;
      }
    }
    if(!found)
      bucket[index].add(pair);
    return result;
  }
  public Object get(Object key) {
    int index = key.hashCode() % SZ;
    if(index < 0) index = -index;
    if(bucket[index] == null) return null;
    LinkedList pairs = bucket[index];
    MPair match = new MPair(key, null);
    ListIterator it = pairs.listIterator();
    while(it.hasNext()) {
      Object iPair = it.next();
      if(iPair.equals(match))
        return ((MPair)iPair).getValue();
    }
    return null;
  }
  public Set entrySet() {
    Set entries = new HashSet();
    for(int i = 0; i < bucket.length; i++) {
      if(bucket[i] == null) continue;
      Iterator it = bucket[i].iterator();
      while(it.hasNext())
        entries.add(it.next());
    }
    return entries;
  }
  public static void main(String[] args) {
    SimpleHashMap m = new SimpleHashMap();
    Collections2.fill(m, Collections2.geography, 25);
    System.out.println(m);
  }
} ///:~




[ Return to Thinking in Java 2, 3rd edition ]


Top 10 read Java Articles
 Get free "1000 Java Tips eBook"

 Java Calendar and Date: good to know facts and code examples

 Array vs ArrayList vs LinkedList vs Vector: an excellent overview and examples

 How can I convert any Java Object into byte array? And byte array to file object

 The Java Lesson 1: What is Java?

 How do I compare two dates and times, date between dates, time between times and

 Maven vs Ant or Ant vs Maven?

 How to open, read, write, close file(s) in Java? Examples on move, rename and de

 Java Array

 Java: JLabel font and color


[ More in News Section ]
Java Lessons

The Java Lesson 1:
What is Java?
The Java Lesson 2:
Anatomy of a simple Java program
The Java Lesson 3:
Identifiers and primitive data types
The Java Lesson 4:
Variables, constants, and literals
The Java Lesson 5:
Arithmetic operations, conversions, and casts
The Java Lesson 6:
Boolean expressions and operations
The Java Lesson 7:
Bitwise operations
The Java Lesson 8:
Flow control with if and else
The Java Lesson 9:
switch statements
The Java Lesson 10:
for, while, and do-while statements
The Java Lesson 11:
Using break and continue
The Java Lesson 12:
Class methods and how they are called
The Java Lesson 13:
Using the Math class
The Java Lesson 14:
Creating and calling custom class methods
The Java Lesson 15:
Overloading class methods
The Java Lesson 16:
An introduction to objects and object references
The Java Lesson 17:
The String class
The Java Lesson 18:
The StringBuffer class
The Java Lesson 19:
Initializing and processing arrays of primitives
The Java Lesson 20:
Initializing and processing arrays of objects
The Java Lesson 23:
Inheritance and overriding inherited methods
The Java Lesson 24:
abstract classes and polymorphism
The Java Lesson 25:
Interfaces, instanceof, and object conversion and casting
The Java Lesson 26:
Introduction to graphical programming and the java.awt packa
The Java Lesson 27:
The Component class
The Java Lesson 28:
Containers and simple layout managers
The Java Lesson 29:
The Color and Font classes
The Java Lesson 30:
Drawing geometric shapes
The Java Lesson 31:
Choice, List, and Checkbox controls
The Java Lesson 32:
Using the Scrollbar graphical control
The Java Lesson 33:
Menus and submenus
The Java Lesson 34:
An introduction to applets and the Applet class
The Java Lesson 35:
Essential HTML to launch an applet and pass it parameters
The Java Lesson 36:
Mouse event processing
Java Lesson 37:
Menus and submenus
Java Lesson 38:
The WindowListener interface and the WindowAdapter class
Java Lesson 39:
An introduction to GridBagLayout
Java Lesson 40:
An introduction to the Java Collections API
Java Lesson 41:
Exception handling with try, catch, and finally blocks
Java Lesson 42:
Claiming and throwing exceptions
Java Lesson 43:
Multithreading, the Thread class, and the Runnable interface
Java Lesson 44:
An introduction to I/O and the File and FileDialog classes
Java Lesson 45:
Low-level and high-level stream classes
Java Lesson 46:
Using the RandomAccessFile class
Java Lessons by
Joh Huhtala: Update

Latest articles
 Java Profiler JProbe to Resolve Performance Problems Faster

 SSL with GlassFish v2, page 5

 SSL with GlassFish v2, page 4

 SSL with GlassFish v2, page 3

 SSL with GlassFish v2, page 2

 The Java Lesson 2: Anatomy of a simple Java program, page 2

 New site about Java for robots and robotics: both software and hardware.

 Exceptions -III: What's an exception and why do I care?

 Exceptions -II: What's an exception and why do I care?

 Exceptions: What's an exception and why do I care?

 Double your Java code quality in 10 minutes, here is receipt

 Murach's Java Servlets and JSP

 How to get ascii code from a char in Java?

 Can we just try without catch? Yes!

 Make Tomcat page load faster

 Make your Tomcat More secure - limit network address for certain IP addresses

 New Java book online starts now here...

 Implementing RESTful Web Services in Java

 Firefox trimming from 1 GB to 40 Mb with many tabs opened

 SSL with GlassFish v2

 My request to replublish Tech Tips

 Search JavaFAQ.nu site here

 New Advanced Installer for Java 6.0 brings XML updates and imports 3rd party MSI

 EJB programming restrictions

 Maven vs Ant or Ant vs Maven?

 Why Java does not use default value which it should?

 How to unsign signed bytes in Java - your guide is here

 The Java Lesson 3: Identifiers and primitive data types. Page 2

 The Java Lesson 7: Bitwise operations with good examples, click here! Page 4

 The Java Lesson 7: Bitwise operations with good examples, click here! Page 3


[ More in News Section ]


Home Code Examples Java Forum All Java Tips Books Submit News, Code... Search... Offshore Software Tech Doodling

RSS feed Java FAQ RSS feed Java FAQ News     

    RSS feed Java Forums RSS feed Java Forums

All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest 1999-2006 by Java FAQs Daily Tips.

Interactive software released under GNU GPL, Code Credits, Privacy Policy