gt: 		int hash = getHash(key);
context: /*
   * Copyright 2002-2014 the original author or authors.
   *
   * Licensed 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.springframework.util;
  
  import java.lang.ref.ReferenceQueue;
  import java.lang.ref.SoftReference;
  import java.lang.ref.WeakReference;
  import java.lang.reflect.Array;
  import java.util.AbstractMap;
  import java.util.AbstractSet;
  import java.util.Collections;
  import java.util.EnumSet;
  import java.util.HashSet;
  import java.util.Iterator;
  import java.util.Map;
  import java.util.NoSuchElementException;
  import java.util.Set;
  import java.util.concurrent.ConcurrentHashMap;
  import java.util.concurrent.ConcurrentMap;
  import java.util.concurrent.locks.ReentrantLock;
  
  /**
   * A {@link ConcurrentHashMap} that uses {@link ReferenceType#SOFT soft} or
   * {@linkplain ReferenceType#WEAK weak} references for both {@code keys} and {@code values}.
   *
   * <p>This class can be used as an alternative to
   * {@code Collections.synchronizedMap(new WeakHashMap<K, Reference<V>>())} in order to
   * support better performance when accessed concurrently. This implementation follows the
   * same design constraints as {@link ConcurrentHashMap} with the exception that
   * {@code null} values and {@code null} keys are supported.
   *
   * <p><b>NOTE:</b> The use of references means that there is no guarantee that items
   * placed into the map will be subsequently available. The garbage collector may discard
   * references at any time, so it may appear that an unknown thread is silently removing
   * entries.
   *
   * <p>If not explicitly specified, this implementation will use
   * {@linkplain SoftReference soft entry references}.
   *
   * @param <K> The key type
   * @param <V> The value type
   * @author Phillip Webb
   * @since 3.2
   */
  public class ConcurrentReferenceHashMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V> {
  
  	private static final int DEFAULT_INITIAL_CAPACITY = 16;
  
  	private static final float DEFAULT_LOAD_FACTOR = 0.75f;
  
  	private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
  
  	private static final ReferenceType DEFAULT_REFERENCE_TYPE = ReferenceType.SOFT;
  
  	private static final int MAXIMUM_CONCURRENCY_LEVEL = 1 << 16;
  
  	private static final int MAXIMUM_SEGMENT_SIZE = 1 << 30;
  
  
  	/**
  	 * Array of segments indexed using the high order bits from the hash.
  	 */
  	private final Segment[] segments;
  
  	/**
  	 * When the average number of references per table exceeds this value resize will be attempted.
  	 */
  	private final float loadFactor;
  
  	/**
  	 * The reference type: SOFT or WEAK.
  	 */
  	private final ReferenceType referenceType;
  
  	/**
  	 * The shift value used to calculate the size of the segments array and an index from the hash.
  	 */
  	private final int shift;
  
  	/**
  	 * Late binding entry set.
  	 */
  	private Set<Map.Entry<K, V>> entrySet;
  
  
  	/**
  	 * Create a new {@code ConcurrentReferenceHashMap} instance.
  	 */
  	public ConcurrentReferenceHashMap() {
  		this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL, DEFAULT_REFERENCE_TYPE);
  	}
  
  	/**
  	 * Create a new {@code ConcurrentReferenceHashMap} instance.
  	 * @param initialCapacity the initial capacity of the map
  	 */
  	public ConcurrentReferenceHashMap(int initialCapacity) {
  		this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL, DEFAULT_REFERENCE_TYPE);
  	}
  
  	/**
  	 * Create a new {@code ConcurrentReferenceHashMap} instance.
  	 * @param initialCapacity the initial capacity of the map
  	 * @param loadFactor the load factor. When the average number of references per table
  	 * exceeds this value resize will be attempted
  	 */
  	public ConcurrentReferenceHashMap(int initialCapacity, float loadFactor) {
  		this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL, DEFAULT_REFERENCE_TYPE);
  	}
  
  	/**
  	 * Create a new {@code ConcurrentReferenceHashMap} instance.
  	 * @param initialCapacity the initial capacity of the map
  	 * @param concurrencyLevel the expected number of threads that will concurrently
  	 * write to the map
  	 */
  	public ConcurrentReferenceHashMap(int initialCapacity, int concurrencyLevel) {
  		this(initialCapacity, DEFAULT_LOAD_FACTOR, concurrencyLevel, DEFAULT_REFERENCE_TYPE);
  	}
  
  	/**
  	 * Create a new {@code ConcurrentReferenceHashMap} instance.
  	 * @param initialCapacity the initial capacity of the map
  	 * @param referenceType the reference type used for entries (soft or weak)
  	 */
  	public ConcurrentReferenceHashMap(int initialCapacity, ReferenceType referenceType) {
  		this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL, referenceType);
  	}
  
  	/**
  	 * Create a new {@code ConcurrentReferenceHashMap} instance.
  	 * @param initialCapacity the initial capacity of the map
  	 * @param loadFactor the load factor. When the average number of references per
  	 * table exceeds this value, resize will be attempted.
  	 * @param concurrencyLevel the expected number of threads that will concurrently
  	 * write to the map
  	 */
  	public ConcurrentReferenceHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
  		this(initialCapacity, loadFactor, concurrencyLevel, DEFAULT_REFERENCE_TYPE);
  	}
  
  	/**
  	 * Create a new {@code ConcurrentReferenceHashMap} instance.
  	 * @param initialCapacity the initial capacity of the map
  	 * @param loadFactor the load factor. When the average number of references per
  	 * table exceeds this value, resize will be attempted.
  	 * @param concurrencyLevel the expected number of threads that will concurrently
  	 * write to the map
  	 * @param referenceType the reference type used for entries (soft or weak)
  	 */
  	@SuppressWarnings("unchecked")
  	public ConcurrentReferenceHashMap(int initialCapacity, float loadFactor, int concurrencyLevel,
  			ReferenceType referenceType) {
  
  		Assert.isTrue(initialCapacity >= 0, "Initial capacity must not be negative");
  		Assert.isTrue(loadFactor > 0f, "Load factor must be positive");
  		Assert.isTrue(concurrencyLevel > 0, "Concurrency level must be positive");
  		Assert.notNull(referenceType, "Reference type must not be null");
  		this.loadFactor = loadFactor;
  		this.shift = calculateShift(concurrencyLevel, MAXIMUM_CONCURRENCY_LEVEL);
  		int size = 1 << this.shift;
  		this.referenceType = referenceType;
  		int roundedUpSegmentCapacity = (int) ((initialCapacity + size - 1L) / size);
  		this.segments = (Segment[]) Array.newInstance(Segment.class, size);
  		for (int i = 0; i < this.segments.length; i++) {
  			this.segments[i] = new Segment(roundedUpSegmentCapacity);
  		}
  	}
  
  
  	protected final float getLoadFactor() {
  		return this.loadFactor;
  	}
  
  	protected final int getSegmentsSize() {
  		return this.segments.length;
  	}
  
  	protected final Segment getSegment(int index) {
  		return this.segments[index];
  	}
  
  	/**
  	 * Factory method that returns the {@link ReferenceManager}.
  	 * This method will be called once for each {@link Segment}.
  	 * @return a new reference manager
  	 */
  	protected ReferenceManager createReferenceManager() {
  		return new ReferenceManager();
  	}
  
  	/**
  	 * Get the hash for a given object, apply an additional hash function to reduce
  	 * collisions. This implementation uses the same Wang/Jenkins algorithm as
  	 * {@link ConcurrentHashMap}. Subclasses can override to provide alternative hashing.
  	 * @param o the object to hash (may be null)
  	 * @return the resulting hash code
  	 */
  	protected int getHash(Object o) {
  		int hash = o == null ? 0 : o.hashCode();
  		hash += (hash << 15) ^ 0xffffcd7d;
  		hash ^= (hash >>> 10);
  		hash += (hash << 3);
  		hash ^= (hash >>> 6);
  		hash += (hash << 2) + (hash << 14);
  		hash ^= (hash >>> 16);
  		return hash;
  	}
  
  	@Override
  	public V get(Object key) {
  		Reference<K, V> reference = getReference(key, Restructure.WHEN_NECESSARY);
  		Entry<K, V> entry = (reference != null ? reference.get() : null);
  		return (entry != null ? entry.getValue() : null);
  	}
  
  	@Override
  	public boolean containsKey(Object key) {
  		Reference<K, V> reference = getReference(key, Restructure.WHEN_NECESSARY);
  		Entry<K, V> entry = (reference != null ? reference.get() : null);
  		return (entry != null && ObjectUtils.nullSafeEquals(entry.getKey(), key));
  	}
  
  	/**
  	 * Return a {@link Reference} to the {@link Entry} for the specified {@code key},
  	 * or {@code null} if not found.
  	 * @param key the key (can be {@code null})
  	 * @param restructure types of restructure allowed during this call
  	 * @return the reference, or {@code null} if not found
  	 */
  	protected final Reference<K, V> getReference(Object key, Restructure restructure) {
  		int hash = getHash(key);
  		return getSegmentForHash(hash).getReference(key, hash, restructure);
  	}
  
  	@Override
  	public V put(K key, V value) {
  		return put(key, value, true);
  	}
  
  	public V putIfAbsent(K key, V value) {
  		return put(key, value, false);
  	}
  
  	private V put(final K key, final V value, final boolean overwriteExisting) {
  		return doTask(key, new Task<V>(TaskOption.RESTRUCTURE_BEFORE, TaskOption.RESIZE) {
  			@Override
  			protected V execute(Reference<K, V> reference, Entry<K, V> entry, Entries entries) {
  				if (entry != null) {
  					V previousValue = entry.getValue();
  					if (overwriteExisting) {
  						entry.setValue(value);
  					}
  					return previousValue;
  				}
  				entries.add(value);
  				return null;
  			}
  		});
  	}
  
  	@Override
  	public V remove(Object key) {
  		return doTask(key, new Task<V>(TaskOption.RESTRUCTURE_AFTER, TaskOption.SKIP_IF_EMPTY) {
  			@Override
  			protected V execute(Reference<K, V> reference, Entry<K, V> entry) {
  				if (entry != null) {
  					reference.release();
  					return entry.value;
  				}
  				return null;
  			}
  		});
  	}
  
  	public boolean remove(Object key, final Object value) {
  		return doTask(key, new Task<Boolean>(TaskOption.RESTRUCTURE_AFTER, TaskOption.SKIP_IF_EMPTY) {
  			@Override
  			protected Boolean execute(Reference<K, V> reference, Entry<K, V> entry) {
  				if (entry != null && ObjectUtils.nullSafeEquals(entry.getValue(), value)) {
  					reference.release();
  					return true;
  				}
  				return false;
  			}
  		});
  	}
  
  	public boolean replace(K key, final V oldValue, final V newValue) {
  		return doTask(key, new Task<Boolean>(TaskOption.RESTRUCTURE_BEFORE, TaskOption.SKIP_IF_EMPTY) {
  			@Override
  			protected Boolean execute(Reference<K, V> reference, Entry<K, V> entry) {
  				if (entry != null && ObjectUtils.nullSafeEquals(entry.getValue(), oldValue)) {
  					entry.setValue(newValue);
  					return true;
  				}
  				return false;
  			}
  		});
  	}
  
  	public V replace(K key, final V value) {
  		return doTask(key, new Task<V>(TaskOption.RESTRUCTURE_BEFORE, TaskOption.SKIP_IF_EMPTY) {
  			@Override
  			protected V execute(Reference<K, V> reference, Entry<K, V> entry) {
  				if (entry != null) {
  					V previousValue = entry.getValue();
  					entry.setValue(value);
  					return previousValue;
  				}
  				return null;
  			}
  		});
  	}
  
  	@Override
  	public void clear() {
  		for (Segment segment : this.segments) {
  			segment.clear();
  		}
  	}
  
  	/**
  	 * Remove any entries that have been garbage collected and are no longer referenced.
  	 * Under normal circumstances garbage collected entries are automatically purged as
  	 * items are added or removed from the Map. This method can be used to force a purge,
  	 * and is useful when the Map is read frequently but updated less often.
  	 */
  	public void purgeUnreferencedEntries() {
  		for (Segment segment : this.segments) {
  			segment.restructureIfNecessary(false);
  		}
  	}
  
  
  	@Override
  	public int size() {
  		int size = 0;
  		for (Segment segment : this.segments) {
  			size += segment.getCount();
  		}
  		return size;
  	}
  
  	@Override
  	public Set<java.util.Map.Entry<K, V>> entrySet() {
  		if (this.entrySet == null) {
  			this.entrySet = new EntrySet();
  		}
  		return this.entrySet;
  	}
  
  	private <T> T doTask(Object key, Task<T> task) {
  