Containers

Details
Category: Java
Hits: 443
  • The core collection interfaces are the foundation of the Java Collections Framework. 
  • The Java Collections Framework hierarchy consists of two distinct interface trees: Collection and Map.
  • The first tree starts with the Collection interface, which provides for the basic functionality used by all collections, such as add and remove methods. Its subinterfaces — Set, List, and Queue — provide for more specialized collections. 
  • The Set interface does not allow duplicate elements. This can be useful for storing collections such as a deck of cards or student records. The Set interface has a subinterface, SortedSet, that provides for ordering of elements in the set. 
  • The List interface provides for an ordered collection, for situations in which you need precise control over where each element is inserted. You can retrieve elements from a List by their exact position. 
  • The Queue interface enables additional insertion, extraction, and inspection operations. Elements in a Queue are typically ordered in on a FIFO basis. 
  • The second tree starts with the Map interface, which maps keys and values similar to a Hashtable. 
  • Map's subinterface, SortedMap, maintains its key-value pairs in ascending order or in an order specified by a Comparator. 
  • These interfaces allow collections to be manipulated independently of the details of their representation. 

Collections:

 

Set        deck of cards

List        precise control, insert anywhere

Queue  FIFO

Deque  FIFO both end 

 

Characteristics:

 

Hash               no defined order

Tree                in order but need comparator

Linked List     defined order and no comparator

 
Java implementation of hashCode:
    public native int hashCode();
 
Java implementation of Hash Map:
 

    Hash table starts out with 8 buckets implemented as array. Key has value is MOD by 8 to form index.

    Each bucket contains a list of linked Entry class. The class contains the key and value and the "next" pointer.

    If table gets too large, double number of buckets, double MOD by from 8 to 16, rehash and rebucket.

 

Difference between array and vector:

    Conceptually vector can grow and array cannot. As implemented array is not synchronized while vector is. Vector is base class for stack.

 

 

Comparing Java container implementation vs C++

 

HashMap

 

Map<Object,Object> m = new HashMap<Object,Object>();

Object v_put = m.put("Key", "Value");

Object v_get = m.get("Key");

Object v_removed = m.remove("Key");

 

boolean does_contain_key = m.containsKey("Key");

boolean does_contain_value = m.containsValue("Value");

 

int size = m.size();

boolean is_empty = m.isEmpty();

 

C++

 

map<string, SATELLITE*> m;// allocated on the stack

m["Key"] = &data;

SATELLITE *data = m["Key"];

 

// without using [] operator

m.insert(pair<string, SATELLITE*> ("Key", &data));

SATELLITE *data = m.find("Key")->second;

 

unsigned int i = m.erase("Key");

 

int size = m.size();

bool b = m.empty();

 

 

HashSet

 

Collection<Object> c = new HashSet<Object>(collection);

c.add("Random String");

c.remove("Random String");

 

boolean does_cotain = c.contains("Random String");

 

int size = c.size();

boolean is_empty = c.isEmpty();

 

C++

 

set<string> s;

s.insert("string 1");

s.erase("string 1");

 

SET_OF_STRINGS::iterator itr = s.find("string 2");

 

int size = s.size();

bool is_empty = s.empty();

 

 

ArrayList

 

Collection<Object> c = new ArrayList<Object>(collection);

// rest same as HashSet

 

C++

 

ARRAY_OF_STRINGS a(5);

a[0] = "string at index 0";

a[1] = "string at index 1";

 

 

Stack

 

Stack<Object> c = new Stack<Object>();

c.push("string");

// pop returns top value

Object obj = c.pop();

 

C++

 

stack<string> s;
s.push("string");
string str = s.top();

// pop returns void
s.pop();