Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  package org.infinispan.commons.util;
  
  
 import java.util.Map;
 import java.util.Set;

A HashMap that is optimized for fast shallow copies.

Null keys are not supported.

Author(s):
Jason T. Greene
Since:
4.0
 
 public class FastCopyHashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, CloneableSerializable {
 
    private static final Log log = LogFactory.getLog(FastCopyHashMap.class);
    private static final boolean trace = .isTraceEnabled();

   
Serialization ID
 
    private static final long serialVersionUID = 10929568968762L;

   
Same default as HashMap, must be a power of 2
 
    private static final int DEFAULT_CAPACITY = 8;

   
MAX_INT - 1
 
    private static final int MAXIMUM_CAPACITY = 1 << 30;

   
67%, just like IdentityHashMap
 
    private static final float DEFAULT_LOAD_FACTOR = 0.67f;

   
The open-addressed table
 
    private transient Entry<K, V>[] table;

   
The current number of key-value pairs
 
    private transient int size;

   
The next resize
 
    private transient int threshold;

   
The user defined load factor which defines when to resize
 
    private final float loadFactor;

   
Counter used to detect changes made outside of an iterator
 
    private transient int modCount;
 
    public FastCopyHashMap(int initialCapacityfloat loadFactor) {
       if (initialCapacity < 0)
          throw new IllegalArgumentException("Can not have a negative size table!");
 
       if (initialCapacity > )
          initialCapacity = ;
 
       if (!(loadFactor > 0F && loadFactor <= 1F))
          throw new IllegalArgumentException("Load factor must be greater than 0 and less than or equal to 1");
 
       this. = loadFactor;
       init(initialCapacityloadFactor);
    }
 
    @SuppressWarnings("unchecked")
    public FastCopyHashMap(Map<? extends K, ? extends V> map) {
       if (map instanceof FastCopyHashMap) {
          FastCopyHashMap<? extends K, ? extends V> fast = (FastCopyHashMap<? extends K, ? extends V>) map;
          this. = (Entry<K, V>[]) fast.table.clone();
          this. = fast.loadFactor;
          this. = fast.size;
          this. = fast.threshold;
       } else {
          this. = ;
          init(map.size(), this.);
         putAll(map);
      }
   }
   @SuppressWarnings("unchecked")
   private void init(int initialCapacityfloat loadFactor) {
      int c = 1;
      for (; c < initialCapacityc <<= 1) ;
      this. = new Entry[c];
       = (int) (c * loadFactor);
   }
   public FastCopyHashMap(int initialCapacity) {
      this(initialCapacity);
   }
   public FastCopyHashMap() {
      this();
   }
   private int nextIndex(int indexint length) {
      index = (index >= length - 1) ? 0 : index + 1;
      return index;
   }
   private static int index(int hashCodeint length) {
      return hashCode & (length - 1);
   }
   public int size() {
      return ;
   }
   public boolean isEmpty() {
      return  == 0;
   }
   public V get(Object key) {
      assertKeyNotNull(key);
      int hash = hash(key);
      int length = .;
      int index = index(hashlength);
      for (; ;) {
         Entry<K, V> e = [index];
         if (e == null)
            return null;
         if (e.hash == hash && eq(keye.key))
            return e.value;
         index = nextIndex(indexlength);
      }
   }
   public boolean containsKey(Object key) {
      assertKeyNotNull(key);
      int hash = hash(key);
      int length = .;
      int index = index(hashlength);
      for (; ;) {
         Entry<K, V> e = [index];
         if (e == null)
            return false;
         if (e.hash == hash && eq(keye.key))
            return true;
         index = nextIndex(indexlength);
      }
   }
   
   
Returns a string representation of this map. The string representation consists of a list of key-value mappings in the order returned by the map's entrySet view's iterator, enclosed in braces ("{}"). Adjacent mappings are separated by the characters ", " (comma and space). Each key-value mapping is rendered as the key followed by an equals sign ("=") followed by the associated value. Keys and values are converted to strings as by java.lang.String.valueOf(java.lang.Object).

Returns:
a string representation of this map
   public String toString() {
     Iterator<java.util.Map.Entry<K, V>> i = entrySet().iterator();
     if (! i.hasNext())
         return "{}";
     StringBuilder sb = new StringBuilder();
     sb.append('{');
     for (;;) {
         java.util.Map.Entry<K, V> e = i.next();
         K key = e.getKey();
         V value = e.getValue();
         sb.append(key   == this ? "(this Map)" : key);
         sb.append('=');
         sb.append(value == this ? "(this Map)" : value);
         if (! i.hasNext())
           return sb.append('}').toString();
         sb.append(", ");
     }
   }
   public boolean containsValue(Object value) {
      for (Entry<K, V> e : )
         if (e != null && eq(valuee.value))
            return true;
      return false;
   }
   public V put(K key, V value) {
      assertKeyNotNull(key);
      Entry<K, V>[] table = this.;
      int hash = hash(key);
      int length = table.length;
      int start = index(hashlength);
      int index = start;
      for (; ;) {
         Entry<K, V> e = table[index];
         if (e == null)
            break;
         if (e.hash == hash && eq(keye.key)) {
            table[index] = new Entry<K, V>(e.keye.hashvalue);
            return e.value;
         }
         index = nextIndex(indexlength);
         if (index == start)
            throw new IllegalStateException("Table is full!");
      }
      ++;
      table[index] = new Entry<K, V>(keyhashvalue);
      if (++ >= )
         resize(length);
      return null;
   }
   @SuppressWarnings("unchecked")
   private void resize(int from) {
      int newLength = from << 1;
      // Can't get any bigger
      if (newLength >  || newLength <= from)
         return;
      Entry<K, V>[] newTable = new Entry[newLength];
      Entry<K, V>[] old = ;
      for (Entry<K, V> e : old) {
         if (e == null)
            continue;
         int index = index(e.hashnewLength);
         while (newTable[index] != null)
            index = nextIndex(indexnewLength);
         newTable[index] = e;
      }
       = (int) ( * newLength);
       = newTable;
   }
   public void putAll(Map<? extends K, ? extends V> map) {
      int size = map.size();
      if (size == 0)
         return;
      if (size > ) {
         if (size > )
            size = ;
         int length = .;
         for (; length < sizelength <<= 1) ;
         resize(length);
      }
      for (Map.Entry<? extends K, ? extends V> e : map.entrySet())
         put(e.getKey(), e.getValue());
   }
   public V remove(Object key) {
      assertKeyNotNull(key);
      Entry<K, V>[] table = this.;
      int length = table.length;
      int hash = hash(key);
      int start = index(hashlength);
      for (int index = start; ;) {
         Entry<K, V> e = table[index];
         if (e == null)
            return null;
         if (e.hash == hash && eq(keye.key)) {
            table[index] = null;
            relocate(index);
            ++;
            --;
            return e.value;
         }
         index = nextIndex(indexlength);
         if (index == start)
            return null;
      }
   }
   private void relocate(int start) {
      Entry<K, V>[] table = this.;
      int length = table.length;
      int current = nextIndex(startlength);
      for (; ;) {
         Entry<K, V> e = table[current];
         if (e == null)
            return;
         // A Doug Lea variant of Knuth's Section 6.4 Algorithm R.
         // This provides a non-recursive method of relocating
         // entries to their optimal positions once a gap is created.
         int prefer = index(e.hashlength);
         if ((current < prefer && (prefer <= start || start <= current))
               || (prefer <= start && start <= current)) {
            table[start] = e;
            table[current] = null;
            start = current;
         }
         current = nextIndex(currentlength);
      }
   }
   public void clear() {
      ++;
      Entry<K, V>[] table = this.;
      for (int i = 0; i < table.lengthi++)
         table[i] = null;
       = 0;
   }
   @SuppressWarnings("unchecked")
   public FastCopyHashMap<K, V> clone() {
      try {
         FastCopyHashMap<K, V> clone = (FastCopyHashMap<K, V>) super.clone();
         clone.table = .clone();
         clone.entrySet = null;
         clone.values = null;
         clone.keySet = null;
         return clone;
      }
      catch (CloneNotSupportedException e) {
         // should never happen
         throw new IllegalStateException(e);
      }
   }
   public void printDebugStats() {
      int optimal = 0;
      int total = 0;
      int totalSkew = 0;
      int maxSkew = 0;
      for (int i = 0; i < .i++) {
         Entry<K, V> e = [i];
         if (e != null) {
            total++;
            int target = index(e.hash.);
            if (i == target)
               optimal++;
            else {
               int skew = Math.abs(i - target);
               if (skew > maxSkewmaxSkew = skew;
               totalSkew += skew;
            }
         }
      }
      ..println(" Size:            " + );
      ..println(" Real Size:       " + total);
      ..println(" Optimal:         " + optimal + " (" + (floatoptimal * 100 / total + "%)");
      ..println(" Average Distnce: " + ((floattotalSkew / (total - optimal)));
      ..println(" Max Distance:    " + maxSkew);
   }
   @SuppressWarnings("unchecked")
      s.defaultReadObject();
      int size = s.readInt();
      init(size);
      for (int i = 0; i < sizei++) {
         K key = (K) s.readObject();
         V value = (V) s.readObject();
         putForCreate(keyvalue);
      }
   }
   @SuppressWarnings("unchecked")
   private void putForCreate(K key, V value) {
      Entry<K, V>[] table = this.;
      int hash = hash(key);
      int length = table.length;
      int index = index(hashlength);
      Entry<K, V> e = table[index];
      while (e != null) {
         index = nextIndex(indexlength);
         e = table[index];
      }
      table[index] = new Entry<K, V>(keyhashvalue);
   }
   private void writeObject(java.io.ObjectOutputStream sthrows IOException {
      s.defaultWriteObject();
      s.writeInt();
      for (Entry<K, V> e : ) {
         if (e != null) {
            s.writeObject(e.key);
            s.writeObject(e.value);
         }
      }
   }
   private abstract class FasyCopyHashMapIterator<E> implements Iterator<E> {
      private int next = 0;
      private int expectedCount = ;
      private int current = -1;
      private boolean hasNext;
      Entry<K, V> table[] = FastCopyHashMap.this.;
      @Override
      public boolean hasNext() {
         if ()
            return true;
         Entry<K, V> table[] = this.;
         for (int i = i < table.lengthi++) {
            if (table[i] != null) {
                = i;
               return  = true;
            }
         }
          = table.length;
         return false;
      }
      protected Entry<K, V> nextEntry() {
         if ( != )
            throw new ConcurrentModificationException();
         if (! && !hasNext())
            throw new NoSuchElementException();
          = ++;
          = false;
         return [];
      }
      @Override
      @SuppressWarnings("unchecked")
      public void remove() {
         if ( != )
            throw new ConcurrentModificationException();
         int current = this.;
         int delete = current;
         if (current == -1)
            throw new IllegalStateException();
         // Invalidate current (prevents multiple remove)
         this. = -1;
         // Start were we relocate
          = delete;
         Entry<K, V>[] table = this.;
         if (table != FastCopyHashMap.this.) {
            FastCopyHashMap.this.remove(table[delete].);
            table[delete] = null;
             = ;
            return;
         }
         int length = table.length;
         int i = delete;
         table[delete] = null;
         --;
         for (; ;) {
            i = nextIndex(ilength);
            Entry<K, V> e = table[i];
            if (e == null)
               break;
            int prefer = index(e.hashlength);
            if ((i < prefer && (prefer <= delete || delete <= i))
                  || (prefer <= delete && delete <= i)) {
               // Snapshot the unseen portion of the table if we have
               // to relocate an entry that was already seen by this iterator
               if (i < current && current <= delete && table == FastCopyHashMap.this.) {
                  int remaining = length - current;
                  Entry<K, V>[] newTable = new Entry[remaining];
                  System.arraycopy(tablecurrentnewTable, 0, remaining);
                  // Replace iterator's table.
                  // Leave table local var pointing to the real table
                  this. = newTable;
                   = 0;
               }
               // Do the swap on the real table
               table[delete] = e;
               table[i] = null;
               delete = i;
            }
         }
      }
   }
   private class KeyIterator extends FasyCopyHashMapIterator<K> {
      @Override
      public K next() {
         return nextEntry().;
      }
   }
   private class ValueIterator extends FasyCopyHashMapIterator<V> {
      @Override
      public V next() {
         return nextEntry().;
      }
   }
   private class EntryIterator extends FasyCopyHashMapIterator<Map.Entry<K, V>> {
      private class WriteThroughEntry extends AbstractMap.SimpleEntry<K, V> {
         WriteThroughEntry(K key, V value) {
            super(keyvalue);
         }
         @Override
         public V setValue(V value) {
            if ( != FastCopyHashMap.this.)
               FastCopyHashMap.this.put(getKey(), value);
            return super.setValue(value);
         }
      }
      @Override
      public Map.Entry<K, V> next() {
         Entry<K, V> e = nextEntry();
         if ()
            .tracef("Next entry: key=%s, value=%s"e.keye.value);
         return new WriteThroughEntry(e.keye.value);
      }
   }
   public Collection<V> values() {
      if ( == null = new Values();
      return ;
   }
   public final class Values extends AbstractCollection<V> {
      @Override
      public Iterator<V> iterator() {
         return new ValueIterator();
      }
      @Override
      public int size() {
         return FastCopyHashMap.this.size();
      }
      @Override
      public boolean contains(Object o) {
         return containsValue(o);
      }
      @Override
      public void clear() {
         FastCopyHashMap.this.clear();
      }
   }
   public Set<K> keySet() {
      if ( == null = new KeySet();
      return ;
   }
   public class KeySet extends AbstractSet<K> {
      @Override
      public Iterator<K> iterator() {
         return new KeyIterator();
      }
      @Override
      public void clear() {
         FastCopyHashMap.this.clear();
      }
      @Override
      public boolean contains(Object o) {
         return containsKey(o);
      }
      @Override
      public boolean remove(Object o) {
         int size = size();
         FastCopyHashMap.this.remove(o);
         return size() < size;
      }
      @Override
      public int size() {
         return FastCopyHashMap.this.size();
      }
   }
   public Set<Map.Entry<K, V>> entrySet() {
      if ( == null = new EntrySet();
      return ;
   }
   public class EntrySet extends AbstractSet<Map.Entry<K, V>> {
      @Override
      public Iterator<Map.Entry<K, V>> iterator() {
         return new EntryIterator();
      }
      @Override
      public boolean contains(Object o) {
         if (!(o instanceof Map.Entry))
            return false;
         Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
         Object value = get(entry.getKey());
         return eq(entry.getValue(), value);
      }
      @Override
      public void clear() {
         FastCopyHashMap.this.clear();
      }
      @Override
      public boolean isEmpty() {
         return FastCopyHashMap.this.isEmpty();
      }
      @Override
      public int size() {
         return FastCopyHashMap.this.size();
      }
   }
   private static final class Entry<K, V> {
      final K key;
      final int hash;
      final V value;
      Entry(K keyint hash, V value) {
         this. = key;
         this. = hash;
         this. = value;
      }
   }
New to GrepCode? Check out our FAQ X