Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  package org.infinispan.commons.equivalence;
  
  import java.util.Iterator;
  import java.util.Map;
 import java.util.Set;
 
Custom hash-based map which accepts no null keys nor null values, where equality and hash code calculations are done based on passed Equivalence function implementations for keys and values, as opposed to relying on their own equals/hashCode/toString implementations. This is handy when using key/values whose mentioned methods cannot be overriden, i.e. arrays, and in situations where users want to avoid using wrapper objects. This hash map implementation is optimised for store/retrieval rather than iteration. Internal node entries are not linked, so responsibility to link them falls on the iterators.

Author(s):
Galder ZamarreƱo
Since:
5.3
See also:
java.util.HashMap
 
 public class EquivalentHashMap<K, V> extends AbstractMap<K, V> {
 
    private static final int DEFAULT_INITIAL_CAPACITY = 16;
 
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
 
    private static final int MAXIMUM_CAPACITY = 1 << 30;
 
    private Node<K, V>[] table;
 
    int size;
 
    private int threshold;
 
    private final float loadFactor;
 
    int modCount;
 
    private final Equivalence<K> keyEq;
 
    private final Equivalence<V> valueEq;
 
    @SuppressWarnings("unchecked")
    public EquivalentHashMap(
          Equivalence<K> keyEqEquivalence<V> valueEq) {
       this(keyEqvalueEq);
    }
 
    @SuppressWarnings("unchecked")
    public EquivalentHashMap(
          int initialCapacityEquivalence<K> keyEqEquivalence<V> valueEq) {
       this(initialCapacitykeyEqvalueEq);
    }
 
    @SuppressWarnings("unchecked")
    public EquivalentHashMap(
          int initialCapacityfloat loadFactor,
          Equivalence<K> keyEqEquivalence<V> valueEq) {
       int capacity = 1;
       while (capacity < initialCapacity)
          capacity <<= 1;
 
       this. = loadFactor;
        = (int)(capacity * loadFactor);
        = new Node[capacity];
       this. = keyEq;
       this. = valueEq;
    }
 
    @SuppressWarnings("unchecked")
    public EquivalentHashMap(
          Map<? extends K, ? extends V> mapEquivalence<K> keyEqEquivalence<V> valueEq) {
       if (map instanceof EquivalentHashMap) {
          EquivalentHashMap<? extends K, ? extends V> equivalentMap =
                (EquivalentHashMap<? extends K, ? extends V>) map;
          this. = (Node<K, V>[]) equivalentMap.table.clone();
          this. = equivalentMap.loadFactor;
          this. = equivalentMap.size;
          this. = equivalentMap.threshold;
       } else {
          this. = ;
          init(map.size(), this.);
          putAll(map);
       }
       this. = keyEq;
       this. = valueEq;
    }
 
    @SuppressWarnings("unchecked")
   private void init(int initialCapacityfloat loadFactor) {
      int c = 1;
      for (; c < initialCapacityc <<= 1) ;
      this. = new Node[c];
       = (int) (c * loadFactor);
   }
   public int size() {
      return ;
   }
   public boolean isEmpty() {
      return  == 0;
   }
   public boolean containsKey(Object key) {
      assertKeyNotNull(key);
      int hash = spread(.hashCode(key));
      int length = .;
      int index = index(hashlength);
      for (; ;) {
         Node<K, V> e = [index];
         if (e == null)
            return false;
         if (e.hash == hash && .equals(e.keykey))
            return true;
         index = nextIndex(indexlength);
      }
   }
   public boolean containsValue(Object value) {
      for (Node<K, V> e : )
         if (e != null && .equals(e.valuevalue))
            return true;
      return false;
   }
   public V get(Object key) {
      Node<K, V> n = getNode(key);
      return n == null ? null : n.value;
   }
   @SuppressWarnings("unchecked")
   <T> T getNode(Object key) {
      assertKeyNotNull(key);
      int hash = spread(.hashCode(key));
      int length = .;
      int index = index(hashlength);
      for (; ;) {
         Node<K, V> e = [index];
         if (e == null)
            return null;
         if (e.hash == hash && .equals(e.keykey))
            return (T) e;
         index = nextIndex(indexlength);
      }
   }
   public V put(K key, V value) {
      assertKeyNotNull(key);
      Node<K, V>[] table = this.;
      int hash = spread(.hashCode(key));
      int length = table.length;
      int start = index(hashlength);
      int index = start;
      for (; ;) {
         Node<K, V> e = table[index];
         if (e == null)
            break;
         if (e.hash == hash && .equals(e.keykey)) {
            table[index] = createNode(e.keyvaluee.hash);
            return e.value;
         }
         index = nextIndex(indexlength);
         if (index == start)
            throw new IllegalStateException("Table is full!");
      }
      ++;
      table[index] = createNode(keyvaluehash);
      if (++ >= )
         resize(length);
      return null;
   }
   <T> T createNode(K key, V valueint hash) {
      return (T) new Node<K, V>(keyhashvalue);
   }
   @SuppressWarnings("unchecked")
   private void resize(int from) {
      int newLength = from << 1;
      // Can't get any bigger
      if (newLength >  || newLength <= from)
         return;
      Node<K, V>[] newTable = new Node[newLength];
      Node<K, V>[] old = ;
      for (Node<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 V remove(Object key) {
      Node<K, V> prevNode = removeNode(key);
      return prevNode == null ? null : prevNode.value;
   }
   <T> T removeNode(Object key) {
      assertKeyNotNull(key);
      Node<K, V>[] table = this.;
      int length = table.length;
      int hash = spread(.hashCode(key));
      int start = index(hashlength);
      for (int index = start; ;) {
         Node<K, V> e = table[index];
         if (e == null)
            return null;
         if (e.hash == hash && .equals(e.keykey)) {
            table[index] = null;
            relocate(index);
            ++;
            --;
            return (T) e;
         }
         index = nextIndex(indexlength);
         if (index == start)
            return null;
      }
   }
   private void relocate(int start) {
      Node<K, V>[] table = this.;
      int length = table.length;
      int current = nextIndex(startlength);
      for (; ;) {
         Node<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 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 void clear() {
      ++;
      Node<K, V>[] table = this.;
      for (int i = 0; i < table.lengthi++)
         table[i] = null;
       = 0;
   }
   @SuppressWarnings("unchecked")
   public boolean equals(Object o) {
      if (o == this)
         return true;
      if (!(o instanceof Map))
         return false;
      Map<K, V> m = (Map<K, V>) o;
      if (m.size() != size())
         return false;
      try {
         for (Entry<K, V> e : entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            if (value == null) {
               if (!(m.get(key) == null && m.containsKey(key)))
                  return false;
            } else {
               if (!.equals(valuem.get(key)))
                  return false;
            }
         }
      } catch (ClassCastException unused) {
         return false;
      } catch (NullPointerException unused) {
         return false;
      }
      return true;
   }
   public Equivalence<K> getKeyEquivalence() {
      return ;
   }
   public Equivalence<V> getValueEquivalence() {
      return ;
   }
   /* ---------------- Iterating methods and support classes -------------- */

   
Exported Entry for iterators
   static class MapEntry<K,V> implements Map.Entry<K,V> {
      final K key// non-null
      V val;       // non-null
      final EquivalentHashMap<K, V> map;
      MapEntry(K key, V valEquivalentHashMap<K,V> map) {
         this. = key;
         this. = val;
         this. = map;
      }
      @Override public K getKey() { return ; }
      @Override public V getValue() { return ; }
      @Override public V setValue(V value) {
         if (value == nullthrow new NullPointerException();
         V v = ;
          = value;
         .put(value);
         return v;
      }
      @Override public final int hashCode() {
         return ..hashCode()
               ^ ..hashCode();
      }
      @Override public final String toString() {
         return ..toString() + "="
               + ..toString();
      }
      @Override public final boolean equals(Object o) {
         Object kvEntry<?,?> e;
         return ((o instanceof Entry) &&
            (k = (e = (Entry<?,?>)o).getKey()) != null &&
            (v = e.getValue()) != null &&
            (k ==  || ..equals(k)) &&
            (v ==  || ..equals(v)));
      }
   }
   public Set<K> keySet() {
      if ( == null = new KeySet();
      return ;
   }
   Iterator<K> newKeyIterator()   {
      return new KeyIterator();
   }
   Iterator<V> newValueIterator()   {
      return new ValueIterator();
   }
   Iterator<Map.Entry<K,V>> newEntryIterator()   {
      return new EntryIterator();
   }
   private final class KeySet extends AbstractSet<K> {
      @Override public Iterator<K> iterator() {
         return newKeyIterator();
      }
      @Override public int size() {
         return ;
      }
      @Override public boolean contains(Object o) {
         return containsKey(o);
      }
      @Override public boolean remove(Object o) {
         int size = size();
         EquivalentHashMap.this.remove(o);
         return size() < size;
      }
      @Override public void clear() {
         EquivalentHashMap.this.clear();
      }
   }
   private final class KeyIterator extends EquivalentHashMapIterator<K> {
      @Override public K next() {
         return nextEntry().getKey();
      }
   }
   private abstract class EquivalentHashMapIterator<E> implements Iterator<E> {
      private int next = 0;
      private int expectedCount = ;
      private int current = -1;
      private boolean hasNext;
      Node<K, V> table[] = EquivalentHashMap.this.;
      public final boolean hasNext() {
         if ()
            return true;
         Node<K, V> table[] = this.;
         for (int i = i < table.lengthi++) {
            if (table[i] != null) {
                = i;
               return  = true;
            }
         }
          = table.length;
         return false;
      }
      final Entry<K,V> nextEntry() {
         if ( != )
            throw new ConcurrentModificationException();
         if (! && !hasNext())
            throw new NoSuchElementException();
          = ++;
          = false;
         Node<K, V> node = [this.];
         return new MapEntry<K, V>(
               node.keynode.valueEquivalentHashMap.this);
      }
      public void remove() {
         if ( != )
            throw new ConcurrentModificationException();
         int current = this.;
         if (current == -1)
            throw new IllegalStateException();
         // Invalidate current (prevents multiple remove)
         this. = -1;
         // Start were we relocate
          = current;
         EquivalentHashMap.this.remove([current].);
          = ;
      }
   }
   public Collection<V> values() {
      if ( == null = new Values();
      return ;
   }
   public final class Values extends AbstractCollection<V> {
      @Override public Iterator<V> iterator() {
         return newValueIterator();
      }
      @Override public int size() {
         return EquivalentHashMap.this.size();
      }
      @Override public boolean contains(Object o) {
         return containsValue(o);
      }
      @Override public void clear() {
         EquivalentHashMap.this.clear();
      }
      @Override public boolean remove(Object o) {
         if (o != null) {
            Iterator<V> it = iterator();
            while (it.hasNext()) {
               if (EquivalentHashMap.this..equals(it.next(), o)) {
                  it.remove();
                  return true;
               }
            }
         }
         return false;
      }
   }
   private class ValueIterator extends EquivalentHashMapIterator<V> {
      @Override public V next() {
         return nextEntry().getValue();
      }
   }
   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 newEntryIterator();
      }
      @Override public boolean contains(Object o) {
         if (!(o instanceof Map.Entry))
            return false;
         Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
         V value = get(entry.getKey());
         return .equals(valueentry.getValue());
      }
      @Override public void clear() {
         EquivalentHashMap.this.clear();
      }
      @Override public boolean isEmpty() {
         return EquivalentHashMap.this.isEmpty();
      }
      @Override public int size() {
         return EquivalentHashMap.this.size();
      }
   }
   private final class EntryIterator extends EquivalentHashMapIterator<Map.Entry<K,V>> {
      @Override
      public Map.Entry<K, V> next() {
         return nextEntry();
      }
   }
   private static int spread(int hashCode) {
      hashCode ^= (hashCode >>> 20) ^ (hashCode >>> 12);
      return hashCode ^ (hashCode >>> 7) ^ (hashCode >>> 4);
   }
   private static int index(int hashCodeint length) {
      return hashCode & (length - 1);
   }
   private static int nextIndex(int indexint length) {
      index = (index >= length - 1) ? 0 : index + 1;
      return index;
   }
   protected static class Node<K, V> {
      final K key;
      final int hash;
      final V value;
      protected Node(K keyint hash, V value) {
         this. = key;
         this. = hash;
         this. = value;
      }
   }
New to GrepCode? Check out our FAQ X