Differences between java.util.HashMap vs java.util.Hashtable vs java.util.LinkedHashMap vs java.util.TreeMap 

Differences between java.util.HashMap vs java.util.Hashtable vs java.util.LinkedHashMap vs java.util.TreeMap
Property
HashMap
Hashtable
LinkedHashMap
TreeMap
1
Insertion order
HashMap does not maintains insertion order in java.
Hashtable does not maintains insertion order in java.
LinkedHashMap  maintains insertion order in java.
TreeMap is sorted by natural order of keys in java.
2
Performance
HashMap is not synchronized, hence its operations are faster as compared to Hashtable.
Hashtable is synchronized, hence its operations are slower as compared HashMap.
If we are working not working in multithreading environment jdk recommends us to use HashMap.
LinkedHashMap must be used only when we want to maintain insertion order. Time and space overhead is there because for maintaining order it internally uses Doubly Linked list.
TreeMap must be used only when we want sorting based on natural order. Otherwise sorting operations cost performance. (Comparator is called for sorting purpose)
3
Null keys and values
HashMap allows to store one null key and many null values i.e. many keys can have null value in java.
Hashtable does not allow to store null key or null value.
Any attempt to store null key or value throws runtimeException (NullPointerException) in java.
LinkedHashMap allows to store one null key and many null values i.e. any key can have null value in java.
TreeMap does not allow to store null key but allow many null values.
Any attempt to store null key throws runtimeException (NullPointerException) in java.
4
Implements which interface
HashMap implements java.util.Map
Hashtable implements java.util.Map
LinkedHashMap implements java.util.Map
TreeMap implements
java.util.Map
java.util.SortedMap
java.util.NavigableMap
5
Implementation uses?
HashMap use buckets
Hashtable use buckets
LinkedHashMap uses doubly linked lists
TreeMap uses Red black tree
6
Complexity of put, get and remove methods
O(1)
O(1)
O(1)
overhead of updating Doubly Linked list for maintaining order it internally uses.
O(log(n))
7
Extends java.util.Dictionary (Abstract class, which is obsolete)
HashMap doesn’t extends Dictionary.
Hashtable extends Dictionary (which maps non-null keys to values. In a given Dictionary we can look up value corresponding to key)
LinkedHashMap doesn’t extends Dictionary.
TreeMap doesn’t extends Dictionary.
8
Introduced in which java version?
HashMap was introduced in second version of java i.e. JDK 2.0
Hashtable was introduced in first version of java i.e. JDK 1.0
But it was refactored in java 2 i.e. JDK 1.2 to implement the Map interface, hence making it a member of member of the Java Collections Framework.
LinkedHashMap was introduced in fourth version of java i.e. JDK 4.0
TreeMap was introduced in second version of java i.e. JDK 2.0
FacebookTwitterGoogle+Share

Rehashing

The size of the hash table is not determinate at the very beginning. If the total size of keys is too large (e.g. size >= capacity / 10), we should double the size of the hash table and rehash every keys. Say you have a hash table looks like below:

size=3, capacity=4

<code>[null, 21, 14, null]
       ↓    ↓
       9   null
       ↓
      null
</code>

The hash function is:

<code>int hashcode(int key, int capacity) {
    return key % capacity;
}
</code>

here we have three numbers, 9, 14 and 21, where 21 and 9 share the same position as they all have the same hashcode 1 (21 % 4 = 9 % 4 = 1). We store them in the hash table by linked list.

rehashing this hash table, double the capacity, you will get:

size=3, capacity=8

<code>index:   0    1    2    3     4    5    6   7
hash : [null, 9, null, null, null, 21, 14, null]
</code>

Given the original hash table, return the new hash table after rehashing .

Example

Given [null, 21->9->null, 14->null, null],

return [null, 9->null, null, null, null, 21->null, 14->null, null]

Note

For negative integer in hash table, the position can be calculated as follow:

  • C++/Java: if you directly calculate -4 % 3 you will get -1. You can use function: a % b = (a % b + b) % b to make it is a non negative integer.
  • Python: you can directly use -1 % 3, you will get 2 automatically.

Solution:

Note: For negative integer in hash table, the position can be calculated as follow:
if you directly calculate -4 % 3 you will get -1.
You can use function: a % b = (a % b + b) % b to make it is a non negative integer.

public ListNode[] rehashing(ListNode[] hashTable) {
    if (hashTable == null) {
        return null;
    }
    ListNode[] newHash = new ListNode[hashTable.length * 2];
    int capacity = newHash.length;
    for (int i = 0; i < hashTable.length; i++) {
        ListNode node = hashTable[i];
        while (node != null) {
            int index = mod(node.val, capacity);
            ListNode next = node.next; //need to remove the next pointer
            node.next = null;
            //if it is the first one
            if (newHash[index] == null) {
                newHash[index] = node;
            } else {
                ListNode runner = newHash[index];
                while (runner.next != null) {
                    runner = runner.next;
                }
                runner.next = node;
            }
            hashTable[i] = next; //set to its next node
            node = next;
        }
    }
    return newHash;
}

//For negative integer in hash table, the position can be calculated as follow:
//if you directly calculate -4 % 3 you will get -1.
//You can use function: a % b = (a % b + b) % b to make it is a non negative integer.
public int mod(int A, int module) {
    return (A % module + module) % module;
}

Leetcode: Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

 

public int[] twoSum(int[] numbers, int target) {
        //use hashmap to store <val,index> pairs of all the numbers
        //in this algorithm, we assume all the numbers are different
        //and we need to add one to the index as the final output as requried by this question
        int[] output = new int[2];
        HashMap<Integer, Integer> map = new HashMap<Integer,Integer>();
        for(int i=0;i<numbers.length;i++){
            map.put(numbers[i],i);
        }
        for(int i=0;i<numbers.length;i++){
            int val = target-numbers[i];
            if(map.containsKey(val)){
                int index = map.get(val);
                if(index!=i){
                    if(i<index){
                        output[0] = i+1;
                        output[1] = index+1;
                    }else{
                        output[0] = index+1;
                        output[1] = i+1;
                    }
                    return output;
                }
            }
        }
        return output;
    }

The time complexity is O(N). Since we only need constant time for each HashMap search operation.

Leetcode: Anagrams

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

 

public ArrayList<String> anagrams(String[] strs) {
        // Start typing your Java solution below
        // DO NOT write main() function
        HashMap<String,ArrayList<String>> records = new HashMap<String, ArrayList<String>>();
        ArrayList<String> output = new ArrayList<String>();
        for(int i = 0; i<strs.length;i++){
            char[] charArr = strs[i].toCharArray();
            Arrays.sort(charArr);
            String sorted = new String(charArr);
            if(records.containsKey(sorted)){
                records.get(sorted).add(strs[i]);
            }else{
                ArrayList<String> strings = new ArrayList<String>();
                strings.add(strs[i]);
                records.put(sorted, strings);
            }
        }
        
        for(ArrayList<String> currArr : records.values()){
            if(currArr.size()>1){
                output.addAll(currArr);
            }    
        }    
        return output;
    }