JAVA HashMap详细介绍和示例

    // 指定“容量大小”的构造函数
    public hashmap(int initialcapacity) {
        this(initialcapacity, default_load_factor);
    }
    // 默认构造函数。
    public hashmap() {
        // 设置“加载因子”
        this.loadfactor = default_load_factor;
        // 设置“hashmap阈值”，当hashmap中存储数据的数量达到threshold时，就需要将hashmap的容量加倍。
        threshold = (int)(default_initial_capacity * default_load_factor);
        // 创建entry数组，用来保存数据
        table = new entry[default_initial_capacity];
        init();
    }
    // 包含“子map”的构造函数
    public hashmap(map<? extends k, ? extends v> m) {
        this(math.max((int) (m.size() / default_load_factor) + 1,
                      default_initial_capacity), default_load_factor);
        // 将m中的全部元素逐个添加到hashmap中
        putallforcreate(m);
    }
    static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
    // 返回索引值
    // h & (length-1)保证返回值的小于length
    static int indexfor(int h, int length) {
        return h & (length-1);
    }
    public int size() {
        return size;
    }
    public boolean isempty() {
        return size == 0;
    }
    // 获取key对应的value
    public v get(object key) {
        if (key == null)
            return getfornullkey();
        // 获取key的hash值
        int hash = hash(key.hashcode());
        // 在“该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.equals(k)))
                return e.value;
        }
        return null;
    }
    // 获取“key为null”的元素的值
    // hashmap将“key为null”的元素存储在table[0]位置！
    private v getfornullkey() {
        for (entry<k,v> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }
    // hashmap是否包含key
    public boolean containskey(object key) {
        return getentry(key) != null;
    }
    // 返回“键为key”的键值对
    final entry<k,v> getentry(object key) {
        // 获取哈希值
        // hashmap将“key为null”的元素存储在table[0]位置，“key不为null”的则调用hash()计算哈希值
        int hash = (key == null) ? 0 : hash(key.hashcode());
        // 在“该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;
    }
    // 将“key-value”添加到hashmap中
    public v put(k key, v value) {
        // 若“key为null”，则将该键值对添加到table[0]中。
        if (key == null)
            return putfornullkey(value);
        // 若“key不为null”，则计算该key的哈希值，然后将其添加到该哈希值对应的链表中。
        int hash = hash(key.hashcode());
        int i = indexfor(hash, table.length);
        for (entry<k,v> e = table[i]; e != null; e = e.next) {
            object k;
            // 若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出！
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                v oldvalue = e.value;
                e.value = value;
                e.recordaccess(this);
                return oldvalue;
            }
        }
        // 若“该key”对应的键值对不存在，则将“key-value”添加到table中
        modcount++;
        addentry(hash, key, value, i);
        return null;
    }
    // putfornullkey()的作用是将“key为null”键值对添加到table[0]位置
    private v putfornullkey(v value) {
        for (entry<k,v> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                v oldvalue = e.value;
                e.value = value;
                e.recordaccess(this);
                return oldvalue;
            }
        }
        // 这里的完全不会被执行到!
        modcount++;
        addentry(0, null, value, 0);
        return null;
    }
    // 创建hashmap对应的“添加方法”，
    // 它和put()不同。putforcreate()是内部方法，它被构造函数等调用，用来创建hashmap
    // 而put()是对外提供的往hashmap中添加元素的方法。
    private void putforcreate(k key, v value) {
        int hash = (key == null) ? 0 : hash(key.hashcode());
        int i = indexfor(hash, table.length);
        // 若该hashmap表中存在“键值等于key”的元素，则替换该元素的value值
        for (entry<k,v> e = table[i]; e != null; e = e.next) {
            object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                e.value = value;
                return;
            }
        }
        // 若该hashmap表中不存在“键值等于key”的元素，则将该key-value添加到hashmap中
        createentry(hash, key, value, i);
    }
    // 将“m”中的全部元素都添加到hashmap中。
    // 该方法被内部的构造hashmap的方法所调用。
    private void putallforcreate(map<? extends k, ? extends v> m) {
        // 利用迭代器将元素逐个添加到hashmap中
        for (iterator<? extends map.entry<? extends k, ? extends v>> i = m.entryset().iterator(); i.hasnext(); ) {
            map.entry<? extends k, ? extends v> e = i.next();
            putforcreate(e.getkey(), e.getvalue());
        }
    }
    // 重新调整hashmap的大小，newcapacity是调整后的单位
    void resize(int newcapacity) {
        entry[] oldtable = table;
        int oldcapacity = oldtable.length;
        if (oldcapacity == maximum_capacity) {
            threshold = integer.max_value;
            return;
        }
        // 新建一个hashmap，将“旧hashmap”的全部元素添加到“新hashmap”中，
        // 然后，将“新hashmap”赋值给“旧hashmap”。
        entry[] newtable = new entry[newcapacity];
        transfer(newtable);
        table = newtable;
        threshold = (int)(newcapacity * loadfactor);
    }
    // 将hashmap中的全部元素都添加到newtable中
    void transfer(entry[] newtable) {
        entry[] src = table;
        int newcapacity = newtable.length;
        for (int j = 0; j < src.length; j++) {
            entry<k,v> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    entry<k,v> next = e.next;
                    int i = indexfor(e.hash, newcapacity);
                    e.next = newtable[i];
                    newtable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }
    // 将"m"的全部元素都添加到hashmap中
    public void putall(map<? extends k, ? extends v> m) {
        // 有效性判断
        int numkeystobeadded = m.size();
        if (numkeystobeadded == 0)
            return;
        // 计算容量是否足够，
        // 若“当前实际容量 < 需要的容量”，则将容量x2。
        if (numkeystobeadded > threshold) {
            int targetcapacity = (int)(numkeystobeadded / loadfactor + 1);
            if (targetcapacity > maximum_capacity)
                targetcapacity = maximum_capacity;
            int newcapacity = table.length;
            while (newcapacity < targetcapacity)
                newcapacity <<= 1;
            if (newcapacity > table.length)
                resize(newcapacity);
        }
        // 通过迭代器，将“m”中的元素逐个添加到hashmap中。
        for (iterator<? extends map.entry<? extends k, ? extends v>> i = m.entryset().iterator(); i.hasnext(); ) {
            map.entry<? extends k, ? extends v> e = i.next();
            put(e.getkey(), e.getvalue());
        }
    }
    // 删除“键为key”元素
    public v remove(object key) {
        entry<k,v> e = removeentryforkey(key);
        return (e == null ? null : e.value);
    }
    // 删除“键为key”的元素
    final entry<k,v> removeentryforkey(object key) {
        // 获取哈希值。若key为null，则哈希值为0；否则调用hash()进行计算
        int hash = (key == null) ? 0 : hash(key.hashcode());
        int i = indexfor(hash, table.length);
        entry<k,v> prev = table[i];
        entry<k,v> e = prev;
        // 删除链表中“键为key”的元素
        // 本质是“删除单向链表中的节点”
        while (e != null) {
            entry<k,v> next = e.next;
            object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modcount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordremoval(this);
                return e;
            }
            prev = e;
            e = next;
        }
        return e;
    }
    // 删除“键值对”
    final entry<k,v> removemapping(object o) {
        if (!(o instanceof map.entry))
            return null;
        map.entry<k,v> entry = (map.entry<k,v>) o;
        object key = entry.getkey();
        int hash = (key == null) ? 0 : hash(key.hashcode());
        int i = indexfor(hash, table.length);
        entry<k,v> prev = table[i];
        entry<k,v> e = prev;
        // 删除链表中的“键值对e”
        // 本质是“删除单向链表中的节点”
        while (e != null) {
            entry<k,v> next = e.next;
            if (e.hash == hash && e.equals(entry)) {
                modcount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordremoval(this);
                return e;
            }
            prev = e;
            e = next;
        }
        return e;
    }
    // 清空hashmap，将所有的元素设为null
    public void clear() {
        modcount++;
        entry[] tab = table;
        for (int i = 0; i < tab.length; i++)
            tab[i] = null;
        size = 0;
    }
    // 是否包含“值为value”的元素
    public boolean containsvalue(object value) {
    // 若“value为null”，则调用containsnullvalue()查找
    if (value == null)
            return containsnullvalue();
    // 若“value不为null”，则查找hashmap中是否有值为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;
    }
    // 是否包含null值
    private boolean containsnullvalue() {
    entry[] tab = table;
        for (int i = 0; i < tab.length ; i++)
            for (entry e = tab[i] ; e != null ; e = e.next)
                if (e.value == null)
                    return true;
    return false;
    }
    // 克隆一个hashmap，并返回object对象
    public object clone() {
        hashmap<k,v> result = null;
        try {
            result = (hashmap<k,v>)super.clone();
        } catch (clonenotsupportedexception e) {
            // assert false;
        }
        result.table = new entry[table.length];
        result.entryset = null;
        result.modcount = 0;
        result.size = 0;
        result.init();
        // 调用putallforcreate()将全部元素添加到hashmap中
        result.putallforcreate(this);
        return result;
    }
    // entry是单向链表。
    // 它是 “hashmap链式存储法”对应的链表。
    // 它实现了map.entry 接口，即实现getkey(), getvalue(), setvalue(v value), equals(object o), hashcode()这些函数
    static class entry<k,v> implements map.entry<k,v> {
        final k key;
        v value;
        // 指向下一个节点
        entry<k,v> next;
        final int hash;
        // 构造函数。
        // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)"
        entry(int h, k k, v v, entry<k,v> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
        public final k getkey() {
            return key;
        }
        public final v getvalue() {
            return value;
        }
        public final v setvalue(v newvalue) {
            v oldvalue = value;
            value = newvalue;
            return oldvalue;
        }
        // 判断两个entry是否相等
        // 若两个entry的“key”和“value”都相等，则返回true。
        // 否则，返回false
        public final boolean equals(object o) {
            if (!(o instanceof map.entry))
                return false;
            map.entry e = (map.entry)o;
            object k1 = getkey();
            object k2 = e.getkey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                object v1 = getvalue();
                object v2 = e.getvalue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }
        // 实现hashcode()
        public final int hashcode() {
            return (key==null   ? 0 : key.hashcode()) ^
                   (value==null ? 0 : value.hashcode());
        }
        public final string tostring() {
            return getkey() + "=" + getvalue();
        }
        // 当向hashmap中添加元素时，绘调用recordaccess()。
        // 这里不做任何处理
        void recordaccess(hashmap<k,v> m) {
        }
        // 当从hashmap中删除元素时，绘调用recordremoval()。
        // 这里不做任何处理
        void recordremoval(hashmap<k,v> m) {
        }
    }
    // 新增entry。将“key-value”插入指定位置，bucketindex是位置索引。
    void addentry(int hash, k key, v value, int bucketindex) {
        // 保存“bucketindex”位置的值到“e”中
        entry<k,v> e = table[bucketindex];
        // 设置“bucketindex”位置的元素为“新entry”，
        // 设置“e”为“新entry的下一个节点”
        table[bucketindex] = new entry<k,v>(hash, key, value, e);
        // 若hashmap的实际大小 不小于 “阈值”，则调整hashmap的大小
        if (size++ >= threshold)
            resize(2 * table.length);
    }
    // 创建entry。将“key-value”插入指定位置，bucketindex是位置索引。
    // 它和addentry的区别是：
    // (01) addentry()一般用在 新增entry可能导致“hashmap的实际容量”超过“阈值”的情况下。
    //   例如，我们新建一个hashmap，然后不断通过put()向hashmap中添加元素；
    // put()是通过addentry()新增entry的。
    //   在这种情况下，我们不知道何时“hashmap的实际容量”会超过“阈值”；
    //   因此，需要调用addentry()
    // (02) createentry() 一般用在 新增entry不会导致“hashmap的实际容量”超过“阈值”的情况下。
    //   例如，我们调用hashmap“带有map”的构造函数，它绘将map的全部元素添加到hashmap中；
    // 但在添加之前，我们已经计算好“hashmap的容量和阈值”。也就是，可以确定“即使将map中
    // 的全部元素添加到hashmap中，都不会超过hashmap的阈值”。
    //   此时，调用createentry()即可。
    void createentry(int hash, k key, v value, int bucketindex) {
        // 保存“bucketindex”位置的值到“e”中
        entry<k,v> e = table[bucketindex];
        // 设置“bucketindex”位置的元素为“新entry”，
        // 设置“e”为“新entry的下一个节点”
        table[bucketindex] = new entry<k,v>(hash, key, value, e);
        size++;
    }
    // hashiterator是hashmap迭代器的抽象出来的父类，实现了公共了函数。
    // 它包含“key迭代器(keyiterator)”、“value迭代器(valueiterator)”和“entry迭代器(entryiterator)”3个子类。
    private abstract class hashiterator<e> implements iterator<e> {
        // 下一个元素
        entry<k,v> next;
        // expectedmodcount用于实现fast-fail机制。
        int expectedmodcount;
        // 当前索引
        int index;
        // 当前元素
        entry<k,v> current;
        hashiterator() {
            expectedmodcount = modcount;
            if (size > 0) { // advance to first entry
                entry[] t = table;
                // 将next指向table中第一个不为null的元素。
                // 这里利用了index的初始值为0，从0开始依次向后遍历，直到找到不为null的元素就退出循环。
                while (index < t.length && (next = t[index++]) == null)

            }
        }
        public final boolean hasnext() {
            return next != null;
        }
        // 获取下一个元素
        final entry<k,v> nextentry() {
            if (modcount != expectedmodcount)
                throw new concurrentmodificationexception();
            entry<k,v> e = next;
            if (e == null)
                throw new nosuchelementexception();
            // 注意！！！
            // 一个entry就是一个单向链表
            // 若该entry的下一个节点不为空，就将next指向下一个节点;
            // 否则，将next指向下一个链表(也是下一个entry)的不为null的节点。
            if ((next = e.next) == null) {
                entry[] t = table;
                while (index < t.length && (next = t[index++]) == null)

            }
            current = e;
            return e;
        }
        // 删除当前元素
        public void remove() {
            if (current == null)
                throw new illegalstateexception();
            if (modcount != expectedmodcount)
                throw new concurrentmodificationexception();
            object k = current.key;
            current = null;
            hashmap.this.removeentryforkey(k);
            expectedmodcount = modcount;
        }
    }
    // value的迭代器
    private final class valueiterator extends hashiterator<v> {
        public v next() {
            return nextentry().value;
        }
    }
    // key的迭代器
    private final class keyiterator extends hashiterator<k> {
        public k next() {
            return nextentry().getkey();
        }
    }
    // entry的迭代器
    private final class entryiterator extends hashiterator<map.entry<k,v>> {
        public map.entry<k,v> next() {
            return nextentry();
        }
    }
    // 返回一个“key迭代器”
    iterator<k> newkeyiterator()   {
        return new keyiterator();
    }
    // 返回一个“value迭代器”
    iterator<v> newvalueiterator()   {
        return new valueiterator();
    }
    // 返回一个“entry迭代器”
    iterator<map.entry<k,v>> newentryiterator()   {
        return new entryiterator();
    }
    // hashmap的entry对应的集合
    private transient set<map.entry<k,v>> entryset = null;
    // 返回“key的集合”，实际上返回一个“keyset对象”
    public set<k> keyset() {
        set<k> ks = keyset;
        return (ks != null ? ks : (keyset = new keyset()));
    }
    // key对应的集合
    // keyset继承于abstractset，说明该集合中没有重复的key。
    private final class keyset extends abstractset<k> {
        public iterator<k> iterator() {
            return newkeyiterator();
        }
        public int size() {
            return size;
        }
        public boolean contains(object o) {
            return containskey(o);
        }
        public boolean remove(object o) {
            return hashmap.this.removeentryforkey(o) != null;
        }
        public void clear() {
            hashmap.this.clear();
        }
    }
    // 返回“value集合”，实际上返回的是一个values对象
    public collection<v> values() {
        collection<v> vs = values;
        return (vs != null ? vs : (values = new values()));
    }
    // “value集合”
    // values继承于abstractcollection，不同于“keyset继承于abstractset”，
    // values中的元素能够重复。因为不同的key可以指向相同的value。
    private final class values extends abstractcollection<v> {
        public iterator<v> iterator() {
            return newvalueiterator();
        }
        public int size() {
            return size;
        }
        public boolean contains(object o) {
            return containsvalue(o);
        }
        public void clear() {
            hashmap.this.clear();
        }
    }
    // 返回“hashmap的entry集合”
    public set<map.entry<k,v>> entryset() {
        return entryset0();
    }
    // 返回“hashmap的entry集合”，它实际是返回一个entryset对象
    private set<map.entry<k,v>> entryset0() {
        set<map.entry<k,v>> es = entryset;
        return es != null ? es : (entryset = new entryset());
    }
    // entryset对应的集合
    // entryset继承于abstractset，说明该集合中没有重复的entryset。
    private final class entryset extends abstractset<map.entry<k,v>> {
        public iterator<map.entry<k,v>> iterator() {
            return newentryiterator();
        }
        public boolean contains(object o) {
            if (!(o instanceof map.entry))
                return false;
            map.entry<k,v> e = (map.entry<k,v>) o;
            entry<k,v> candidate = getentry(e.getkey());
            return candidate != null && candidate.equals(e);
        }
        public boolean remove(object o) {
            return removemapping(o) != null;
        }
        public int size() {
            return size;
        }
        public void clear() {
            hashmap.this.clear();
        }
    }
    // java.io.serializable的写入函数
    // 将hashmap的“总的容量，实际容量，所有的entry”都写入到输出流中
    private void writeobject(java.io.objectoutputstream s)
        throws ioexception
    {
        iterator<map.entry<k,v>> i =
            (size > 0) ? entryset0().iterator() : null;
        // write out the threshold, loadfactor, and any hidden stuff
        s.defaultwriteobject();
        // write out number of buckets
        s.writeint(table.length);
        // write out size (number of mappings)
        s.writeint(size);
        // write out keys and values (alternating)
        if (i != null) {
            while (i.hasnext()) {
            map.entry<k,v> e = i.next();
            s.writeobject(e.getkey());
            s.writeobject(e.getvalue());
            }
        }
    }

    private static final long serialversionuid = 362498820763181265l;
    // java.io.serializable的读取函数：根据写入方式读出
    // 将hashmap的“总的容量，实际容量，所有的entry”依次读出
    private void readobject(java.io.objectinputstream s)
         throws ioexception, classnotfoundexception
    {
        // read in the threshold, loadfactor, and any hidden stuff
        s.defaultreadobject();
        // read in number of buckets and allocate the bucket array;
        int numbuckets = s.readint();
        table = new entry[numbuckets];
        init();  // give subclass a chance to do its thing.
        // read in size (number of mappings)
        int size = s.readint();
        // read the keys and values, and put the mappings in the hashmap
        for (int i=0; i<size; i++) {
            k key = (k) s.readobject();
            v value = (v) s.readobject();
            putforcreate(key, value);
        }
    }
    // 返回“hashmap总的容量”
    int   capacity()     { return table.length; }
    // 返回“hashmap的加载因子”
    float loadfactor()   { return loadfactor;   }
}

// 删除“键为key”的元素
final entry<k,v> removeentryforkey(object key) {
    // 获取哈希值。若key为null，则哈希值为0；否则调用hash()进行计算
    int hash = (key == null) ? 0 : hash(key.hashcode());
    int i = indexfor(hash, table.length);
    entry<k,v> prev = table[i];
    entry<k,v> e = prev;
    // 删除链表中“键为key”的元素
    // 本质是“删除单向链表中的节点”
    while (e != null) {
        entry<k,v> next = e.next;
        object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            modcount++;
            size--;
            if (prev == e)
                table[i] = next;
            else
                prev.next = next;
            e.recordremoval(this);
            return e;
        }
        prev = e;
        e = next;
    }
    return e;
}