implements ConcurrentMap<K,V>, Serializable {

private static final long serialVersionUID = 7249069246763182397L;

/*

/* ---------------- Constants -------------- */

/**

private static final int MAXIMUM_CAPACITY = 1 << 30;

/**

private static final int DEFAULT_CAPACITY = 16;

/**

static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**

private static final int DEFAULT_CONCURRENCY_LEVEL = 16;

/**

private static final float LOAD_FACTOR = 0.75f;

/**

static final int TREEIFY_THRESHOLD = 8;

/**

static final int UNTREEIFY_THRESHOLD = 6;

/**

static final int MIN_TREEIFY_CAPACITY = 64;

/**

private static final int MIN_TRANSFER_STRIDE = 16;

/**

private static int RESIZE_STAMP_BITS = 16;

/**

private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;

/**

private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;

/*

static final int MOVED = -1; // hash for forwarding nodes

static final int TREEBIN = -2; // hash for roots of trees

static final int RESERVED = -3; // hash for transient reservations

static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash

/** Number of CPUS, to place bounds on some sizings */

static final int NCPU = Runtime.getRuntime().availableProcessors();

/** For serialization compatibility. */

private static final ObjectStreamField[] serialPersistentFields = {

new ObjectStreamField("segments", Segment[].class),

new ObjectStreamField("segmentMask", Integer.TYPE),

new ObjectStreamField("segmentShift", Integer.TYPE)

};

/* ---------------- Nodes -------------- */

/**

static class Node<K,V> implements Map.Entry<K,V> {

final int hash;

final K key;

volatile V val;

volatile Node<K,V> next;

Node(int hash, K key, V val, Node<K,V> next) {

this.hash = hash;

this.key = key;

this.val = val;

this.next = next;

}

public final K getKey() { return key; }

public final V getValue() { return val; }

public final int hashCode() { return key.hashCode() ^ val.hashCode(); }

public final String toString(){ return key + "=" + val; }

public final V setValue(V value) {

throw new UnsupportedOperationException();

}

public final boolean equals(Object o) {

Object k, v, u; Map.Entry<?,?> e;

return ((o instanceof Map.Entry) &&

(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&

(v = e.getValue()) != null &&

(k == key || k.equals(key)) &&

(v == (u = val) || v.equals(u)));

}

/**

Node<K,V> find(int h, Object k) {

Node<K,V> e = this;

if (k != null) {

do {

K ek;

if (e.hash == h &&

((ek = e.key) == k || (ek != null && k.equals(ek))))

return e;

} while ((e = e.next) != null);

}

return null;

}

}

/* ---------------- Static utilities -------------- */

/**

static final int spread(int h) {

return (h ^ (h >>> 16)) & HASH_BITS;

}

/**

private static final int tableSizeFor(int c) {

int n = c - 1;

n |= n >>> 1;

n |= n >>> 2;

n |= n >>> 4;

n |= n >>> 8;

n |= n >>> 16;

return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

}

/**

static Class<?> comparableClassFor(Object x) {

if (x instanceof Comparable) {

Class<?> c; Type[] ts, as; Type t; ParameterizedType p;

if ((c = x.getClass()) == String.class) // bypass checks

return c;

if ((ts = c.getGenericInterfaces()) != null) {

for (int i = 0; i < ts.length; ++i) {

if (((t = ts[i]) instanceof ParameterizedType) &&

((p = (ParameterizedType)t).getRawType() ==

Comparable.class) &&

(as = p.getActualTypeArguments()) != null &&

as.length == 1 && as[0] == c) // type arg is c

return c;

}

}

}

return null;

}

/**

@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable

static int compareComparables(Class<?> kc, Object k, Object x) {

return (x == null || x.getClass() != kc ? 0 :

((Comparable)k).compareTo(x));

}

/* ---------------- Table element access -------------- */

/*

@SuppressWarnings("unchecked")

static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {

return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);

}

static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,

Node<K,V> c, Node<K,V> v) {

return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);

}

static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {

U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);

}

/* ---------------- Fields -------------- */

/**

transient volatile Node<K,V>[] table;

/**

private transient volatile Node<K,V>[] nextTable;

/**

private transient volatile long baseCount;

/**

private transient volatile int sizeCtl;

/**

private transient volatile int transferIndex;

/**

private transient volatile int cellsBusy;

/**

private transient volatile CounterCell[] counterCells;

// views

private transient KeySetView<K,V> keySet;

private transient ValuesView<K,V> values;

private transient EntrySetView<K,V> entrySet;

/* ---------------- Public operations -------------- */

/**

public ConcurrentHashMap() {

}

/**

public ConcurrentHashMap(int initialCapacity) {

if (initialCapacity < 0)

throw new IllegalArgumentException();

int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?

MAXIMUM_CAPACITY :

tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));

this.sizeCtl = cap;

}

/**

public ConcurrentHashMap(Map<? extends K, ? extends V> m) {

this.sizeCtl = DEFAULT_CAPACITY;

putAll(m);

}

/**

public ConcurrentHashMap(int initialCapacity, float loadFactor) {

this(initialCapacity, loadFactor, 1);

}

/**

public ConcurrentHashMap(int initialCapacity,

float loadFactor, int concurrencyLevel) {

if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)

throw new IllegalArgumentException();

if (initialCapacity < concurrencyLevel) // Use at least as many bins

initialCapacity = concurrencyLevel; // as estimated threads

long size = (long)(1.0 + (long)initialCapacity / loadFactor);

int cap = (size >= (long)MAXIMUM_CAPACITY) ?

MAXIMUM_CAPACITY : tableSizeFor((int)size);

this.sizeCtl = cap;

}

// Original (since JDK1.2) Map methods

/**

public int size() {

long n = sumCount();

return ((n < 0L) ? 0 :

(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :

(int)n);

}

/**

public boolean isEmpty() {

return sumCount() <= 0L; // ignore transient negative values

}

/**

public V get(Object key) {

Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;

int h = spread(key.hashCode());

if ((tab = table) != null && (n = tab.length) > 0 &&

(e = tabAt(tab, (n - 1) & h)) != null) {

if ((eh = e.hash) == h) {

if ((ek = e.key) == key || (ek != null && key.equals(ek)))

return e.val;

}

else if (eh < 0)

return (p = e.find(h, key)) != null ? p.val : null;

while ((e = e.next) != null) {

if (e.hash == h &&

((ek = e.key) == key || (ek != null && key.equals(ek))))

return e.val;

}

}

return null;

}

/**

public boolean containsKey(Object key) {

return get(key) != null;

}

/**

public boolean containsValue(Object value) {

if (value == null)

throw new NullPointerException();

Node<K,V>[] t;

if ((t = table) != null) {

Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);

for (Node<K,V> p; (p = it.advance()) != null; ) {

V v;

if ((v = p.val) == value || (v != null && value.equals(v)))

return true;

}

}

return false;

}

/**