Histogram :: array based

For any reasonably sized Histogram, you probably want to look at this Histogram class based on a HashMap. However, if your histograms are tiny, say, less than 8 elements occur frequently, this array based histogram is an order of magnitude faster.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.NoSuchElementException;

public class TinyHistogram<T>
{
   private T[]   items;
   private int[] usage;
   private int   size;

   public TinyHistogram()
   {
      this.items = (T[]) new Object[4];
      this.usage = new int[4];
      this.size = 0;
   }

   public int put(T item)
   {
      if (item == null)
         throw new IllegalArgumentException();

      int io = this.indexOfItem(item);

      if (io != -1)
      {
         int result = ++this.usage[io];
         this.swapIncreasedValue(io);
         return result;
      }

      // add item to the end
      if (this.size == this.items.length)
         this.grow();
      this.items[this.size] = item;
      this.usage[this.size] = 1;
      this.size += 1;
      return 1;
   }

   public int get(T item)
   {
      if (item == null)
         throw new IllegalArgumentException();

      int io = this.indexOfItem(item);
      if (io == -1)
         return 0; // not -1, as the object occurred zero times
      return this.usage[io];
   }

   public List<T> topKeys()
   {
      return this.topKeys(Integer.MAX_VALUE);
   }

   public List<T> topKeys(int amount)
   {
      int end = Math.min(this.size, amount);

      // make a copy, the items are already sorted
      List<T> tops = new ArrayList<T>();
      for (int i = 0; i < end; i++)
         tops.add(this.items[i]);
      return tops;
   }

   public List<Pair<T, Integer>> topEntries()
   {
      return this.topEntries(Integer.MAX_VALUE);
   }

   public List<Pair<T, Integer>> topEntries(int amount)
   {
      int end = Math.min(this.size, amount);

      // make a copy, the items are already sorted
      List<Pair<T, Integer>> tops = new ArrayList<Pair<T, Integer>>();
      for (int i = 0; i < end; i++)
         tops.add(new Pair<T, Integer>(this.items[i], Integer.valueOf(this.usage[i])));
      return tops;
   }

   public int remove(T item)
   {
      int io = this.indexOfItem(item);
      if (io == -1)
         throw new NoSuchElementException(String.valueOf(item));

      int result = --this.usage[io];
      if (result == 0)
         return this.removeIndex(io);

      this.swapDecreasedValue(io);
      return result;
   }

   public int reset(T item)
   {
      int io = this.indexOfItem(item);
      if (io == -1)
         throw new NoSuchElementException(String.valueOf(item));
      return this.removeIndex(io);
   }

   //

   private final void swapDecreasedValue(int index)
   {
      while ((index + 1) < size && usage[index + 0] < usage[index + 1])
      {
         int a = index + 0;
         int b = index + 1;

         swapObj(items, a, b);
         swapInt(usage, a, b);

         index++;
      }
   }

   private final void swapIncreasedValue(int index)
   {
      while (index > 0 && usage[index + 0] > usage[index - 1])
      {
         int a = index - 0;
         int b = index - 1;

         swapObj(items, a, b);
         swapInt(usage, a, b);

         index--;
      }
   }

   private static final void swapInt(int[] array, int a, int b)
   {
      int temp = array[a];
      array[a] = array[b];
      array[b] = temp;
   }

   private static final void swapObj(Object[] array, int a, int b)
   {
      Object temp = array[a];
      array[a] = array[b];
      array[b] = temp;
   }

   private void grow()
   {
      this.items = Arrays.copyOf(this.items, this.items.length * 2);
      this.usage = Arrays.copyOf(this.usage, this.usage.length * 2);
   }

   private int removeIndex(int index)
   {
      int count = this.usage[index];
      int shift = --this.size - index;
      System.arraycopy(this.items, index + 1, this.items, index, shift);
      System.arraycopy(this.usage, index + 1, this.usage, index, shift);
      return count;
   }

   private int indexOfItem(T item)
   {
      for (int i = 0; i < this.size; i++)
         if (this.items[i] == item || this.items[i].equals(item))
            return i;
      return -1;
   }
}