Find Longest Chain of Consecutive Integers in Arrays

Find the length of the longest chain of consecutive integers in an unsorted map in linear time
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Solution 1: 
The key factors about a cluster is: lowest, highest, and length.
Map lowest and highest to length.
To merge two neighbor clusters, only need to update it's new lowest and highest, with new length.
For every a[i], checking its neighbor a[i]-1 and a[i]+1 is enough.

public class Find_Longest_Consecutive_Integer_in_Array {
 public int findLonestConsequence(int[] array) {
  HashMap map = new HashMap();
  int max = 1;
  for (int num: array) {
   if (map.containsKey(num)) {
    continue;
   }
   map.put(num, 1);
   
   if (map.containsKey(num - 1)) {
    max = Math.max(max, merge(map, num - 1, num));
   }
   if (map.containsKey(num + 1)) {
    max = Math.max(max, merge(map, num, num + 1));
   }
  }
  return max;
 }
 
 public int merge(HashMap map, int left, int right) {
  int upper = right + map.get(right) - 1;
  int lower = left - (map.get(left) - 1);
  int len = upper - lower + 1;
  map.put(upper, len);
  map.put(lower, len);
  return len;
 }
}

Solution 2: 
We can use a HashSet to add and remove elements. HashSet is implemented by using a hash table. Elements are not ordered.
The add, remove and contains methods have constant time complexity O(1).
Time complexity is O(n*(m1+m2)), m is the average length of all consecutive sequences.

public class Find_Longest_Consecutive_Integer_in_Array {
 public int findLonestConsequence(int[] num) {
  Set set = new HashSet();
  int max = 1;
  for (int n : num) {
   set.add(n);
  }
  for (int n : num) {
   int left = n - 1;
   int right = n + 1;
   int count = 1;
   while (set.contains(left)) {
    count++;
    /* After the element is checked, it should be 
     *  removed from the set
     */
    set.remove(left);
    left--;
   }
   while (set.contains(right)) {
    count++;
    set.remove(right);
    right++;
   }
   max = Math.max(count, max);
  }
  return max;
 }
}