I don't see why we put the wildcard on the Map.Entry class.  We only ever use an Entry to iterate over with this.  In that case I think it would be better to instead add wildcard for the key and value entry types instead.  This would make the reuse of the Actions a bit more flexible.

```
   public interface ParallelIterator<K,V>{

      /**
       * Performs the given action for each entry but in parallel.
       *
       * @param parallelismThreshold the (estimated) number of elements
       * needed for this operation to be executed in parallel
       * @param action the action
       */
      public void forEachEntry(long parallelismThreshold,
                               Action<? super K,? super V> action) throws InterruptedException;

      /** Interface describing a void action of one argument */
      public interface Action<A, B> { void apply(Map.Entry<A, B> entry); }
   }
```

Or do we think the Actions will be reused outside of a Map?