Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   *  Licensed to the Apache Software Foundation (ASF) under one or more
   *  contributor license agreements.  See the NOTICE file distributed with
   *  this work for additional information regarding copyright ownership.
   *  The ASF licenses this file to You under the Apache License, Version 2.0
   *  (the "License"); you may not use this file except in compliance with
   *  the License.  You may obtain a copy of the License at
   *
   *     http://www.apache.org/licenses/LICENSE-2.0
  *
  *  Unless required by applicable law or agreed to in writing, software
  *  distributed under the License is distributed on an "AS IS" BASIS,
  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  *  See the License for the specific language governing permissions and
  *  limitations under the License.
  */
 
 package org.mapdb;
 
 import java.util.*;

LongHashMap is an implementation of LongMap without concurrency locking. This code is adoption of 'HashMap' from Apache Harmony refactored to support primitive long keys.
 
 public class LongHashMap<V> extends LongMap<V> implements Serializable {
 
     private static final long serialVersionUID = 362340234235222265L;
 
     /*
      * Actual count of entries
      */
     transient int elementCount;
 
     /*
      * The internal data structure to hold Entries
      */
     transient Entry<V>[] elementData;
 
     /*
      * modification count, to keep track of structural modifications between the
      * HashMap and the iterator
      */
     transient int modCount = 0;
 
     /*
      * default size that an HashMap created using the default constructor would
      * have.
      */
     private static final int DEFAULT_SIZE = 16;
 
     /*
      * maximum ratio of (stored elements)/(storage size) which does not lead to
      * rehash
      */
     final float loadFactor;

    
Salt added to keys before hashing, so it is harder to trigger hash collision attack.
 
     protected final long hashSalt = hashSaltValue();
 
     protected long hashSaltValue() {
         return new Random().nextLong();
     }
 
     /*
      * maximum number of elements that can be put in this map before having to
      * rehash
      */
     int threshold;
 
     static class Entry<V>{
         final int origKeyHash;
 
         final long key;
         V value;
         Entry<V> next;
 
 
 
         public Entry(long keyint hash) {
             this. = key;
             this. = hash;
         }
     }
 
     private static class AbstractMapIterator<V>  {
         private int position = 0;
         int expectedModCount;
         Entry<V> futureEntry;
         Entry<V> currentEntry;
         Entry<V> prevEntry;
 
         final LongHashMap<V> associatedMap;
 
         AbstractMapIterator(LongHashMap<V> hm) {
              = hm;
             = hm.modCount;
             = null;
        }
        public boolean hasNext() {
            if ( != null) {
                return true;
            }
            while ( < ..) {
                if (.[] == null) {
                    ++;
                } else {
                    return true;
                }
            }
            return false;
        }
        final void checkConcurrentMod() throws ConcurrentModificationException {
            if ( != .) {
                throw new ConcurrentModificationException();
            }
        }
        final void makeNext() {
            checkConcurrentMod();
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            if ( == null) {
                 = .[++];
                 = .;
                 = null;
            } else {
                if(!=null){
                     = ;
                }
                 = ;
                 = .;
            }
        }
        public final void remove() {
            checkConcurrentMod();
            if (==null) {
                throw new IllegalStateException();
            }
            if(==null){
                int index = . & (.. - 1);
                .[index] = .[index].;
            } else {
                . = .;
            }
             = null;
            ++;
            .++;
            .--;
        }
    }
    private static class EntryIterator <V> extends AbstractMapIterator<V> implements LongMapIterator<V> {
        EntryIterator (LongHashMap<V> map) {
            super(map);
        }
        @Override
        public boolean moveToNext() {
            if(!hasNext()) return false;
            makeNext();
            return true;
        }
        @Override
        public long key() {
            return .;
        }
        @Override
        public V value() {
            return (V) .;
        }
    }
    private static class ValueIterator <V> extends AbstractMapIterator<V> implements Iterator<V> {
        ValueIterator (LongHashMap<V> map) {
            super(map);
        }
        @Override
		public V next() {
            makeNext();
            return .;
        }
    }
    
Create a new element array

Parameters:
s
Returns:
Reference to the element array
    @SuppressWarnings("unchecked")
    Entry<V>[] newElementArray(int s) {
        return new Entry[s];
    }

    
Constructs a new empty HashMap instance.
    public LongHashMap() {
        this();
    }

    
Constructs a new HashMap instance with the specified capacity.

Parameters:
capacity the initial capacity of this hash map.
Throws:
java.lang.IllegalArgumentException when the capacity is less than zero.
    public LongHashMap(int capacity) {
        this(capacity, 0.75f);  // default load factor of 0.75
    }

    
Calculates the capacity of storage required for storing given number of elements

Parameters:
x number of elements
Returns:
storage size
    private static final int calculateCapacity(int x) {
        if(x >= 1 << 30){
            return 1 << 30;
        }
        if(x == 0){
            return 16;
        }
        x = x -1;
        x |= x >> 1;
        x |= x >> 2;
        x |= x >> 4;
        x |= x >> 8;
        x |= x >> 16;
        return x + 1;
    }

    
Constructs a new HashMap instance with the specified capacity and load factor.

Parameters:
capacity the initial capacity of this hash map.
loadFactor the initial load factor.
Throws:
java.lang.IllegalArgumentException when the capacity is less than zero or the load factor is less or equal to zero.
    public LongHashMap(int capacityfloat loadFactor) {
        if (capacity >= 0 && loadFactor > 0) {
            capacity = calculateCapacity(capacity);
             = 0;
             = newElementArray(capacity);
            this. = loadFactor;
            computeThreshold();
        } else {
            throw new IllegalArgumentException();
        }
    }

    
Removes all mappings from this hash map, leaving it empty.

See also:
isEmpty()
size()
    @Override
    public void clear() {
        if ( > 0) {
             = 0;
            Arrays.fill(null);
            ++;
        }
    }


    
Computes the threshold for rehashing
    private void computeThreshold() {
         = (int) (. * );
    }

    
Returns the value of the mapping with the specified key.

Parameters:
key the key.
Returns:
the value of the mapping with the specified key, or null if no mapping for the specified key is found.
    @Override
    public V get(long key) {
        Entry<V> m = getEntry(key);
        if (m != null) {
            return m.value;
        }
        return null;
    }
    final Entry<V> getEntry(long key) {
        int hash = Utils.longHash(key^);
        int index = hash & (. - 1);
        return findNonNullKeyEntry(keyindexhash);
    }
    final Entry<V> findNonNullKeyEntry(long keyint indexint keyHash) {
        Entry<V> m = [index];
        while (m != null
                && (m.origKeyHash != keyHash || key!=m.key)) {
            m = m.next;
        }
        return m;
    }



    
Returns whether this map is empty.

Returns:
true if this map has no elements, false otherwise.
See also:
size()
    @Override
    public boolean isEmpty() {
        return  == 0;
    }

    
Maps the specified key to the specified value.

Parameters:
key the key.
value the value.
Returns:
the value of any previous mapping with the specified key or null if there was no such mapping.
    @Override
    public V put(long key, V value) {
        Entry<V> entry;
        int hash = Utils.longHash(key^);
        int index = hash & (. - 1);
        entry = findNonNullKeyEntry(keyindexhash);
        if (entry == null) {
           ++;
           entry = createHashedEntry(keyindexhash);
           if (++ > ) {
               rehash();
           }
        }
        V result = entry.value;
        entry.value = value;
        return result;
    }
    Entry<V> createHashedEntry(long keyint indexint hash) {
        Entry<V> entry = new Entry<V>(key,hash);
        entry.next = [index];
        [index] = entry;
        return entry;
    }
    void rehash(int capacity) {
        int length = calculateCapacity((capacity == 0 ? 1 : capacity << 1));
        Entry<V>[] newData = newElementArray(length);
        for (int i = 0; i < .i++) {
            Entry<V> entry = [i];
            [i] = null;
            while (entry != null) {
                int index = entry.origKeyHash & (length - 1);
                Entry<V> next = entry.next;
                entry.next = newData[index];
                newData[index] = entry;
                entry = next;
            }
        }
         = newData;
        computeThreshold();
    }
    void rehash() {
        rehash(.);
    }

    
Removes the mapping with the specified key from this map.

Parameters:
key the key of the mapping to remove.
Returns:
the value of the removed mapping or null if no mapping for the specified key was found.
    @Override
    public V remove(long key) {
        Entry<V> entry = removeEntry(key);
        if (entry != null) {
            return entry.value;
        }
        return null;
    }
    final Entry<V> removeEntry(long key) {
        int index = 0;
        Entry<V> entry;
        Entry<V> last = null;
        int hash = Utils.longHash(key^);
        index = hash & (. - 1);
        entry = [index];
        while (entry != null && !(entry.origKeyHash == hash && key == entry.key)) {
             last = entry;
             entry = entry.next;
        }
        if (entry == null) {
            return null;
        }
        if (last == null) {
            [index] = entry.next;
        } else {
            last.next = entry.next;
        }
        ++;
        --;
        return entry;
    }

    
Returns the number of elements in this map.

Returns:
the number of elements in this map.
    @Override
    public int size() {
        return ;
    }
    @Override
    public Iterator<V> valuesIterator() {
        return new ValueIterator<V>(this);
    }
    @Override
    public LongMapIterator<V> longMapIterator() {
        return new EntryIterator<V>(this);
    }
New to GrepCode? Check out our FAQ X