Big Data - BitMap

What is BitMap?
Use bit storing data. See links for detailed explanation.
Why BitMap?
Save much space.
Key points
1 bit.
1 byte = 8 bit.
1 kb = 1024 byte.
1 mb = 1024 kb
1 gb = 1024 mb.
In Java:
char = 2 byte, 16 bit
String = n * char
long = 8 byte = 64 bit.
int = 4 byte = 32 bit.
http://www.cnblogs.com/pangxiaodong/archive/2011/08/14/2137748.html
Java BitMap?
https://docs.oracle.com/javase/7/docs/api/java/util/BitSet.html
Example
Given an unsorted array {2, 4, 1, 5}. Find int x is in this set or not.

// Persudo code 
void setBitMap(bit[] bitmap, int k)
{
  bitmap[k] = 1;
}

bit checkBitMap(bit[] bitmap, int k)
{
  return bitmap[k];
}

boolean contains(Iterator<Integer> aVeryBigArray, int target)
{
  // Init bit map
  bit[] map = initBitMap();
  while (aVeryBigArray.hasNext())
  {
    setBitMap(map, aVeryBigArray.next());
  }
  
  return checkBitMap(map, k) == 1;
}

1 byte can represents 8 numbers.
Thus, let's say we have 1G numbers, 
need 1G / 8  / 1024(kb) / 1024(mb) = 125 mb. So cool.

// Using java BitSet

boolean contains(Iterator<Integer> aVeryBigArray, int target)
{
  // By default, it will create a 64bit map, which represents 64 numbers.
  // Thus estimate the largest element, and allocate a good size of bitset.
  BitSet bitmap = new BitSet();
  
  
  while (aVeryBigArray.hasNext())
  {
    bitmap.set(aVeryBigArray.next());
  }
  return bitmap.get(target);
}

Links
http://dongxicheng.org/structure/bitmap/
http://blog.csdn.net/v_july_v/article/details/6685962