HashMap / HashSet

From CS315

HashSet and HashMap perform insertion, deletion, and find operations in a constant time by distributing the values through out the hash table.

Contents 1 Hashing and HashTable 2 HashSet 3 HashMap 4 Applications 5 References

Hashing and HashTable

Hashing function maps large numbers into smaller, more manageable numbers by internally managing an array and storing the object using an index which is calculated from the hashcode of the object [1]. This hashcode has no real significance beyond its usefulness in storing an retrieving a particular data record, and these "hashed" numbers are stored into a dictionary like contained called hash table [2]. Hash tables are rather complex to program, but the computer science students study about the HashSet and HashMap from the sophomore level class called “Algorithm and Data Structures” being taught by Dr. Glenn Downing from the University of Texas at Austin.

HashSet

Definition

HashSet is one of implementations in Set collection frameworks. HashSet stores its elements in a hash table while other Set collection called TreeSet stores its element in a tree.

Operations

HashSet uses the HashMap as the container in its class. The method call add(), for instance, calls for the put() function that is default on Map.

The primary operations in the HashSet are shown below.

  /**
    Insert the value into HashSet and return true if the value was added.
    O(1) in time
    @return  true if the value was added
  **/
  public boolean add (K k) { ... }


  /**
    Clear the Set.
    O(N) in time
  **/
  public void clear () { ... }


  /**
    Check if the Set contains the key 
    O(1) in time
    @return true if the Set contains the key
  **/
  public boolean contains (Object k) { ... }


  /**
    Remove the value corresponding to the key
    O(1) in time
    @return true if the object was removed successfully
  */
  public boolean remove (Object k) { ... }


  /**
    Returns the size of the elements in the Set
    O(1) in time
    @return the size of current set
  */
    public int size () { ... }

Note that the clear() method takes a linear time.

HashMap

Definition

HashMap is one of implementations in Maps collection frameworks.

Difference from HashSet

The HashMap is different from HashSet primarily because:

• HashMap is unsynchoronized, meaning that multiple threads can modify a HashMap concurrently.
• HashMap allows null keys and null values.

Basic Operations

Invoking a HashMap is similar to using a dictionary. In a dictionary, you can look up a word you want to know, then the definition will be below the word you looked up. Similarly, you search for key in Hash table to get the value(s) corresponding to the key. There are many operations in the Hash function, but the primary operations revolve around utilizing the key or the value.

The primary operations in the HashMap are shown below:

  /**
    Gets the key value of the HashMap
    O(1) in time
    @return  key
  **/
  public K getKey () { ... }


  /**
    Gets the value of the HashMap
    O(1) in time
    @return  value
  **/
  public V getValue () { ... }
  

  /**
    Adds the value to the HashMap
    O(1) in time
    @return value added to the HashMap
  **/
  public V setValue (V v) { ... } 


  /**
    Remove a value from the HashMap
    O(1) in time
  **/
   public void remove () { ... }

Extended Operations

The additional operations can be performed on the HashMap by implementing the Iterator method. Some examples of the operations are shown below.

  /**
    Gets the next key in the HashMap
    O(1) in time
    @return key
  **/
  public K next () { ... }


  /**
    Gets the next value in the HashMap
    O(1) in time
    @return value
  **/
  public V next () { ... }


  /**
    Clears all the value in the HashMap
    O(N) in time
  **/
  public void clear () { ... }


  /**
    Checks if the value is contained in the HashMap
    O(1) in time
    @return in true if the object is already in the Map
  **/
  public boolean contains (Object o) { ... }


  /**
    Returns the current size of HashMap
    O(1) in time
    @return the size of current Map
  **/
  public int size () { ... }

Note that the clear() method takes a linear time.

Applications

Here are few example of applications where the HashMap or the HashSet are actually being used.

• Database: The popular database systems like MySQL, Oracle, DB2, and MSServer has the key for every data value it needs to operate on. Thus, the hash function provides the good option to implement a database system since it offers the various key and the value pair operations.
• Cryptography: The cryptography is the practice and the study of hiding information [3]. And hash functions helps to do message integrity checks and digital signatures in various information security applications.

References

1. Deitel, Harvey. Java How to Program 6th Edition 14 August, 2004.

2. Weiss, Mark A. Data Structures and Problem Solving Using Java (3rd Edition) 24 February, 2005

3. Cryptography hash function

Written by Ji Son