Collections Data Structure Java

     * 

     * This implementation creates an empty string buffer, appends a left
     * brace, and iterates over the map's entrySet view, appending
     * the string representation of each map.entry in turn.  After
     * appending each entry except the last, the string ", " is
     * appended.  Finally a right brace is appended.  A string is obtained
     * from the stringbuffer, and returned.
     *
     * @return a String representation of this map.
     */
    public String toString() {
        StringBuffer buf = new StringBuffer();
        buf.append("{");
        for (int i = 0; i < table.length; i++) {
            Entry e = table[i];
            for (; e != null; e = e.next) {
                int key = e.key;
                Object value = e.getValue();
                buf.append(key + "=" + (value == this ? "(this Map)" : value));
            }
        }
        buf.append("}");
        return buf.toString();
    }
    /**
     * Returns the number of key-value mappings in this map.
     *
     * @return the number of key-value mappings in this map.
     */
    public int size() {
        return size;
    }
    /**
     * Returns true if this map contains no key-value mappings.
     *
     * @return true if this map contains no key-value mappings.
     */
    public boolean isEmpty() {
        return size == 0;
    }
    /**
     * Returns the value to which the specified key is mapped in this identity
     * hash map, or null if the map contains no mapping for this key.
     * A return value of null does not necessarily indicate
     * that the map contains no mapping for the key; it is also possible that
     * the map explicitly maps the key to null. The
     * containsKey method may be used to distinguish these two cases.
     *
     * @param key the key whose associated value is to be returned.
     * @return the value to which this map maps the specified key, or
     *         null if the map contains no mapping for this key.
     */
    public Object get(int key) {
        int i = key & (table.length - 1);
        Entry e = table[i];
        while (true) {
            if (e == null) {
                return e;
            }
            if (key == e.key) {
                return e.value;
            }
            e = e.next;
        }
    }
    /**
     * Returns true if this map contains a mapping for the
     * specified key.
     *
     * @param key The key whose presence in this map is to be tested
     * @return true if this map contains a mapping for the specified
     *         key.
     */
    public boolean containsKey(int key) {
        int i = key & (table.length - 1);
        Entry e = table[i];
        while (e != null) {
            if (key == e.key) {
                return true;
            }
            e = e.next;
        }
        return false;
    }
    /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for this key, the old
     * value is replaced.
     *
     * @param key   key with which the specified value is to be associated.
     * @param value value to be associated with the specified key.
     * @return previous value associated with specified key, or null
     *         if there was no mapping for key.  A null return can
     *         also indicate that the IntObjectHashMap previously associated
     *         null with the specified key.
     */
    public Object put(int key, Object value) {
        int i = key & (table.length - 1);
        for (Entry e = table[i]; e != null; e = e.next) {
            if (key == e.key) {
                Object oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }
        addEntry(key, value, i);
        return null;
    }
    /**
     * This method is used instead of put by constructors and
     * pseudoconstructors (clone, readObject).  It does not resize the table,
     * check for comodification, etc.  It calls createEntry rather than
     * addEntry.
     */
    private void putForCreate(int key, Object value) {
        int i = key & (table.length - 1);
        /**
         * Look for preexisting entry for key.  This will never happen for
         * clone or deserialize.  It will only happen for construction if the
         * input Map is a sorted map whose ordering is inconsistent w/ equals.
         */
        for (Entry e = table[i]; e != null; e = e.next) {
            if (key == e.key) {
                e.value = value;
                return;
            }
        }
        createEntry(key, value, i);
    }
    /**
     * Rehashes the contents of this map into a new array with a
     * larger capacity.  This method is called automatically when the
     * number of keys in this map reaches its threshold.
     * 

     * If current capacity is MAXIMUM_CAPACITY, this method does not
     * resize the map, but but sets threshold to Integer.MAX_VALUE.
     * This has the effect of preventing future calls.
     *
     * @param newCapacity the new capacity, MUST be a power of two;
     *                    must be greater than current capacity unless current
     *                    capacity is MAXIMUM_CAPACITY (in which case value
     *                    is irrelevant).
     */
    private void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }
    /**
     * Transfer all entries from current table to newTable.
     */
    private void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry next = e.next;
                    int i = e.key & (newCapacity - 1);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }
    /**
     * Removes the mapping for this key from this map if present.
     *
     * @param key key whose mapping is to be removed from the map.
     * @return previous value associated with specified key, or null
     *         if there was no mapping for key.  A null return can
     *         also indicate that the map previously associated null
     *         with the specified key.
     */
    public Object remove(int key) {
        Entry e = removeEntryForKey(key);
        return e == null ? e : e.value;
    }
    /**
     * Removes and returns the entry associated with the specified key
     * in the IntObjectHashMap.  Returns null if the IntObjectHashMap contains no mapping
     * for this key.
     */
    private Entry removeEntryForKey(int key) {
        int i = key & (table.length - 1);
        Entry prev = table[i];
        Entry e = prev;
        while (e != null) {
            Entry next = e.next;
            if (key == e.key) {
                size--;
                if (prev == e) {
                    table[i] = next;
                } else {
                    prev.next = next;
                }
                return e;
            }
            prev = e;
            e = next;
        }
        return e;
    }
    /**
     * Removes all mappings from this map.
     */
    public void clear() {
        Entry tab[] = table;
        for (int i = 0; i < tab.length; i++) {
            tab[i] = null;
        }
        size = 0;
    }
    /**
     * Returns true if this map maps one or more keys to the
     * specified value.
     *
     * @param value value whose presence in this map is to be tested.
     * @return true if this map maps one or more keys to the
     *         specified value.
     */
    public boolean containsValue(Object value) {
        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;
    }
    private static class Entry {
        final int key;
        Object value;
        Entry next;
        /**
         * Create new entry.
         */
        public Entry(int k, Object v, Entry n) {
            value = v;
            next = n;
            key = k;
        }
        public Object getValue() {
            return value;
        }
        public Object setValue(Object newValue) {
            Object oldValue = value;
            value = newValue;
            return oldValue;
        }
        public boolean equals(Object o) {
            if (!(o instanceof Entry)) {
                return false;
            }
            Entry e = (Entry)o;
            if (key == e.key) {
                if (value == e.value || (value != null && value.equals(e.value))) {
                    return true;
                }
            }
            return false;
        }
        public int hashCode() {
            return key ^ (value == null ? 0 : value.hashCode());
        }
        public String toString() {
            return key + "=" + getValue();
        }
    }
    /**
     * Add a new entry with the specified key, value and hash code to
     * the specified bucket.  It is the responsibility of this
     * method to resize the table if appropriate.
     * 

     * Subclass overrides this to alter the behavior of put method.
     */
    private void addEntry(int key, Object value, int bucketIndex) {
        table[bucketIndex] = new Entry(key, value, table[bucketIndex]);
        if (size++ >= threshold) {
            resize(2 * table.length);
        }
    }
    /**
     * Like addEntry except that this version is used when creating entries
     * as part of Map construction or "pseudo-construction" (cloning,
     * deserialization).  This version needn't worry about resizing the table.
     *