V put(K key, V value);

 public V put(K key, V value) {

    if (key == null)

      return putForNullKey(value);

    int hash = hash(key);

    int i = indexFor(hash, table.length);

    for (Entry<K,V> e = table[i]; e != null; e = e.next) {

      Object k;

      if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

        V oldValue = e.value;

        e.value = value;

        e.recordAccess(this);

        return oldValue;

      }

    }

 

    modCount++;

    addEntry(hash, key, value, i);

    return null;

  }

 void addEntry(int hash, K key, V value, int bucketIndex) {

    if ((size >= threshold) && (null != table[bucketIndex])) {

      resize(2 * table.length);

      hash = (null != key) ? hash(key) : 0;

      bucketIndex = indexFor(hash, table.length);

    }

 

    createEntry(hash, key, value, bucketIndex);

  }

 

  void createEntry(int hash, K key, V value, int bucketIndex) {

    Entry<K,V> e = table[bucketIndex];

    table[bucketIndex] = new Entry<>(hash, key, value, e);

    size++;

  }

   Entry(int h, K k, V v, Entry<K,V> n) {

      value = v;

      next = n;

      key = k;

      hash = h;

    }

 public boolean containsKey(Object key) {

    return getEntry(key) != null;

  }

 

  final Entry<K,V> getEntry(Object key) {

    int hash = (key == null) ? 0 : hash(key);

    for (Entry<K,V> e = table[indexFor(hash, table.length)];

       e != null;

       e = e.next) {

      Object k;

      if (e.hash == hash &&

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

        return e;

    }

    return null;

  }

  public boolean containsValue(Object value) {

    if (value == null)

      return containsNullValue();

 

    Entry[] tab = table;

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

      for (Entry e = tab[i] ; e != null ; e = e.next)

        if (value.equals(e.value))

          return true;

    return false;

  }

 public boolean contains(Object o) {

    returnmap.containsKey(o);

  }

  public V put(K key, V value) {

    Entry<K,V> t = root;

    if (t == null) {

      compare(key, key); // type (and possibly null) check

 

      root = new Entry<>(key, value, null);

      size = 1;

      modCount++;

      return null;

    }

    int cmp;

    Entry<K,V> parent;

    // split comparator and comparable paths

    Comparator<? super K> cpr = comparator;

    if (cpr != null) {

      do {

        parent = t;

        cmp = cpr.compare(key, t.key);

        if (cmp < 0)

          t = t.left;

        elseif (cmp > 0)

          t = t.right;

        else

          return t.setValue(value);

      } while (t != null);

    }

    else {

      if (key == null)

        thrownew NullPointerException();

      Comparable<? super K> k = (Comparable<? super K>) key;

      do {

        parent = t;

        cmp = k.compareTo(t.key);

        if (cmp < 0)

          t = t.left;

        elseif (cmp > 0)

          t = t.right;

        else

          return t.setValue(value);

      } while (t != null);

    }

    Entry<K,V> e = new Entry<>(key, value, parent);

    if (cmp < 0)

      parent.left = e;

    else

      parent.right = e;

    fixAfterInsertion(e);

    size++;

    modCount++;

    return null;

  }

 public boolean containsKey(Object key) {

    return getEntry(key) != null;

  }

 

  final Entry<K,V> getEntry(Object key) {

    // Offload comparator-based version for sake of performance

    if (comparator != null)

      return getEntryUsingComparator(key);

    if (key == null)

      thrownew NullPointerException();

    Comparable<? super K> k = (Comparable<? super K>) key;

    Entry<K,V> p = root;

    while (p != null) {

      int cmp = k.compareTo(p.key);

      if (cmp < 0)

        p = p.left;

      elseif (cmp > 0)

        p = p.right;

      else

        return p;

    }

    return null;

  }