aud.HashMap< Key, Value > Class Template Reference

Implementation of an unordered map based on a hash table. More...

Classes
class	Bucket
	entry (key,value) in HashMap with link to next
class	Entries
	provide HashMap iterator over key-value pairs (Entry) More...
class	Entry
	entry (key,value) in HashMap (iterator) More...
class	EntryIterator
	iterator over key-value pairs (Entry) in HashMap

Public Member Functions
	HashMap (int size)
	create empty map More...
	HashMap ()
	create empty map More...
int	getHashtableSize ()
	get current size of hash table (will be prime) More...
int	size ()
	get current number of entries More...
boolean	is_empty ()
	is map empty? More...
double	getLoadFactor ()
	get current load factor More...
void	reserve (int size)
	Reserve buckets for expected size. More...
Entries	entries ()
	get iterable instance for (HashMap<K,T>.Entry entry : map.entries()) { ... } @endiliteral More...
Value	insert (Key key, Value value)
	insert key-value pair More...
Value	remove (Key key)
	remove entry (equivalent to insert(key,null)) More...
Value	find (Key key)
	find value for key @endiliteral More...
boolean	contains (Key key)
	Is key contained in map? More...
String	toString ()

Static Public Member Functions
static void	main (String args[])

Detailed Description

Implementation of an unordered map based on a hash table.

HashMap implements a hash table with separate chaining for collision handling. (For better performance, it implements its own singly linked list made of Bucket instances.) In case a user defined threshold on the load factor (see getLoadFactor, setMaximumLoadFactor is exceeded on insert, a rehashing is triggered. The size of the hash table getHashtableSize is doubled on rehashing and automatically maintained to be prime (see getNextPrime). It may be a good ideap to reserve enough buckets to avoid rehashing if there is a reasonable guess on the expected number of entries.

HashMap provides an iterator that enumerates all key-value-pairs (Entry) in an arbitrary order. In particular, the order may change after an insert operation. Any manipulation of the map (insert or remove) invalidates all iterators in use!

The key-value mapping uses the special convention that null values are never mapped. Inserting a key wit a null value is hence equivalent to removeing the entry! (Use another value instance like "nil" as a placeholder in case you need such semantics.)

Definition at line 31 of file HashMap.java.

Constructor & Destructor Documentation

HashMap() [1/2]

aud.HashMap< Key, Value >.HashMap

(

int

size

)

create empty map

Parameters

size	estimated size (sets initial number of buckets)

Definition at line 135 of file HashMap.java.

                           {
    int n=(int) ((double) size/maxLoad_);
    if (n<size) n=size;
    n=getNextPrime(n);
    table_=new Object[n];
  }

References aud.HashMap< Key, Value >.size().

Here is the call graph for this function:

HashMap() [2/2]

aud.HashMap< Key, Value >.HashMap

(

)

create empty map

Definition at line 143 of file HashMap.java.

                   {
    this(PRIMES[0]);
  }

Member Function Documentation

contains()

boolean aud.HashMap< Key, Value >.contains

(

Key

key

)

Is key contained in map?

Definition at line 295 of file HashMap.java.

                                   {
    return find(key)!=null;
  }

References aud.HashMap< Key, Value >.find().

Here is the call graph for this function:

entries()

Entries aud.HashMap< Key, Value >.entries

(

)

get iterable instance
for (HashMap<K,T>.Entry entry : map.entries()) { ... } @endiliteral


Definition at line 207 of file HashMap.java.

{ return new Entries(this); }

Referenced by aud.HashMap< Key, Value >.main(), and aud.HashMap< Key, Value >.toString().

Here is the caller graph for this function:

find()

Value aud.HashMap< Key, Value >.find

(

Key

key

)

find value for key @endiliteral


Returns

value or null if the key is not contained in map

Definition at line 281 of file HashMap.java.

                             {
    int hash=key.hashCode();
    hash = hash < 0 ? -hash : hash;
    int i=hash % table_.length;
    if (table_[i]!=null) {
      for (Bucket b=(Bucket) table_[i];b!=null;b=b.next) {
        if (b.key.equals(key))
          return b.value;
      }
    }
    return null;
  }

Referenced by aud.HashMap< Key, Value >.contains(), aud.HashMap< Key, Value >.main(), and aud.PriorityQueue< T >.main().

Here is the caller graph for this function:

getHashtableSize()

int aud.HashMap< Key, Value >.getHashtableSize

(

)

get current size of hash table (will be prime)

Definition at line 148 of file HashMap.java.

                                {
    return table_.length;
  }

getLoadFactor()

double aud.HashMap< Key, Value >.getLoadFactor

(

)

get current load factor

Definition at line 159 of file HashMap.java.

                                {
    return (double) size_/(double) table_.length;
  }

insert()

Value aud.HashMap< Key, Value >.insert	(	Key	key,
		Value	value
	)

insert key-value pair

Parameters

key	if map already contains key then its value is changed
value	stored (or new) value. Providing value=null is equivalent to removeing an enty (null values are not stored!}

Returns

old value, i.e., null if the key was not contained in map before

Definition at line 260 of file HashMap.java.

                                           {
    Value v=_set(key,value);
    if (v==null && value!=null) {      // increased size()?
      if (getLoadFactor()>maxLoad_)
        rehash(table_.length*2);       // rehash if maximum load factor exceeded
    }
    return v;
  }

Referenced by aud.HashMap< Key, Value >.main(), and aud.PriorityQueue< T >.main().

Here is the caller graph for this function:

is_empty()

boolean aud.HashMap< Key, Value >.is_empty

(

)

is map empty?

Definition at line 156 of file HashMap.java.

{ return size_==0; }

main()

static void aud.HashMap< Key, Value >.main ( String  args[] )

static

Definition at line 308 of file HashMap.java.

                                         {
    HashMap<String,Integer> map=new HashMap<String,Integer>();
 
    map.insert("a",1);
    map.insert("b",2);
    map.insert("c",3);
    map.insert("d",4);
    map.insert("e",5);
    map.insert("f",6);
    map.insert("g",7);
    map.insert("h",8);
 
    for (HashMap<String,Integer>.Entry entry : map.entries()) {
      System.out.println(entry.key+" => "+entry.value);
    }
    System.out.println(map);
    map.remove("a");
    System.out.println(map);
    System.out.println(map.find("c"));
    System.out.println(map.find("x"));
  }

References aud.HashMap< Key, Value >.entries(), aud.HashMap< Key, Value >.find(), aud.HashMap< Key, Value >.insert(), and aud.HashMap< Key, Value >.remove().

Here is the call graph for this function:

remove()

Value aud.HashMap< Key, Value >.remove

(

Key

key

)

remove entry (equivalent to insert(key,null))

Parameters

key

Returns

value of entry (null if the key was not conatined in map)

Definition at line 273 of file HashMap.java.

                               {
    return _set(key,null);
  }

Referenced by aud.HashMap< Key, Value >.main().

Here is the caller graph for this function:

reserve()

void aud.HashMap< Key, Value >.reserve

(

int

size

)

Reserve buckets for expected size.

May call rehash, will only increase table size.

Parameters

size	expected number of entries

Definition at line 175 of file HashMap.java.

                                {
    if (size>size_)
      rehash((int) ((double) size)/maxLoad_);
  }

References aud.HashMap< Key, Value >.size().

Here is the call graph for this function:

size()

int aud.HashMap< Key, Value >.size

(

)

get current number of entries

Definition at line 153 of file HashMap.java.

{ return size_; }

Referenced by aud.HashMap< Key, Value >.HashMap(), and aud.HashMap< Key, Value >.reserve().

Here is the caller graph for this function:

toString()

String aud.HashMap< Key, Value >.toString

(

)

Definition at line 299 of file HashMap.java.

                                     {
    String s="{ ";
    for (Entry entry : entries())
      s+=(entry.key.toString()+"=>"+entry.value+",");
    s=s.substring(0,s.length()-1);
    return s+=" };";
  }

References aud.HashMap< Key, Value >.entries().

Here is the call graph for this function:

---

The documentation for this class was generated from the following file:

• HashMap.java