跳至主要內容

19、Java 集合:Map 之 Map、AbstractMap、HashMap

安图新大约 6 分钟

19、Java 集合:Map 之 Map、AbstractMap、HashMap

Map 结构图
 

Map

public interface Map

1、 将键映射到值的对象一个映射不能包含重复的键;每个键最多只能映射到一个值;
2、 此接口取代 Dictionary 类,后者完全是一个抽象类,而不是一个接口;
3、 Map 接口提供三种 collection 视图,允许以键集、值集或键-值映射关系集的形式查看某个映射的内容;
4、 键注意其自身 equals 和 hashCode 方法;

嵌套类

interface Entry<K,V> {
    /**
	 * 返回Key
	 */
	K getKey();

    /**
	 * 返回value
	 */
	V getValue();

    /**
	 * 特定值value
     */
	V setValue(V value);

	/**
	 * 比较entry是否相同
     */
	boolean equals(Object o);

	/**
	 * 返回entry的哈希码
	 */
	int hashCode();
}

接口定义方法

 
 

AbstractMap

public abstract class AbstractMap implements Map

1、 提供 Map 接口的主要实现,最大限度减少实现此接口的 Map 所需的工作;

该抽象类为子类提供了 Map 接口的接口方法默认实现,子类可根据需要覆写父类方法,除了两个方法没提供默认实现。
要实现可修改的映射,编程人员必须另外重写此类的 put 方法。

	public V put(K key, V value) {
		throw new UnsupportedOperationException();
    }

HashMap

public class HashMap extends AbstractMap implements Map ,Cloneable, Serializable

1、 基于哈希表的 Map 接口的实现;
2、 允许使用 null 值和 null 键;
3、 HashMap 的实例有两个参数影响其性能:初始容量(默认 16)和加载因子(默认 0.75);
4、 此实现不是同步的,fail-fast;

成员变量

    /**
     * 默认初始容量
     */
    static final int DEFAULT_INITIAL_CAPACITY = 16;

    /**
     * 最大容量
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 默认加载因子
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * key-value组成Entry存入该数组中
     */
    transient Entry[] table;

    /**
     * key-value键值对数
     */
    transient int size;

    /**
     *  当size达到该值时即capacity * load factor,再rehash
     */
    int threshold;

    /**
     * 加载因子
     */
    final float loadFactor;

    /**
     * 被修改次数
     */
    transient volatile int modCount;

    /**
     * 此映射所包含的映射关系的 Set 视图。
     */
    private transient Set<Map.Entry<K,V>> entrySet = null;

构造方法

    /**
     *  构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
        init();
    }

    void init() {
    }

内部类 Entry 成员变量

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;//哈希地址相同的,通过链表链接,即链地址法解决哈希冲突
        final int hash;
    }

常用方法

Vput(K key, V value): 在此映射中关联指定值与指定键。

    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);//null 专门存入到table[0]
        int hash = hash(key.hashCode());//再哈希
        int i = indexFor(hash, table.length);//根据哈希码机及数组长度计算索引
        //循环对应的table[i]的链表,若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.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;//修改次数+1
        addEntry(hash, key, value, i);//存入到指定位置
        return null;
    }

    /**
     * 存入key为null的value
     */
    private V putForNullKey(V value) {
	    //key==null的专门放到table[0]中,但也补排除别的键hash地址一样
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {//找到对应key,替换value
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;//修改次数+1
        addEntry(0, null, value, 0);、、
        return null;
    }

    /**
     * 以hash, key, value创建新entry并放入到table的指定位置
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
		Entry<K,V> e = table[bucketIndex];//获取对应索引entry
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);//table[bucketIndex]存入的是一个链表
        if (size++ >= threshold)
            resize(2 * table.length);//元素已到阀值,再扩容
    }

    /**
     * 两倍扩容,并进行table转化
     */
    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);//更新扩容阀值
    }

    /**
     * 转移当前全部 entries 到 newTable.
     * 转移过程中,每个entry会重新计算在newTable的index,并存入
     */
    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);
            }
        }
    }

    /**
     * 计算并返回哈希码的index
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

Vget(Object key): 返回指定键所映射的值;如果对于该键来说,此映射不包含任何映射关系,则返回 null。

    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());//再哈希
        //循环对应table[indexFor(hash, table.length)]的链表
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            //Entry哈希码相同且key相同,映射关系存在,返回对应value
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

    //从table[0]中找出NullKey的映射关系,并返回对应value
    private V getForNullKey() {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

Vremove(Object key): 从此映射中移除指定键的映射关系(如果存在)。

    public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }

    final Entry<K,V> removeEntryForKey(Object key) {
        int hash = (key == null) ? 0 : hash(key.hashCode());//计算哈希码
        int i = indexFor(hash, table.length);//计算table对应index
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;

        while (e != null) {
            Entry<K,V> next = e.next;
            Object k;
            //Entry哈希码相同,key相同 找到对应的映射关系
            if (e.hash == hash &&
	            ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;//修改次数+1
                size--;//映射关系数-1
                if (prev == e)//table[i]和链表头部是同一个entry
                    table[i] = next;//下一个entry前移
                else
                    prev.next = next;//下一个entry前移
                e.recordRemoval(this);
                return e;
            }
            //没有找到对应映射关系,继续找下一个节点
            prev = e;
            e = next;
        }

        return e;
    }

HashMap 总结:

1、 默认初始容量 16 和默认加载因子 0.75,当 key-value 个数达到初始容量*加载因子时,会现有容量 2 倍扩容,且容量达到 1<<30 时,不再扩容扩容时会 newTable,重新计算每个 Entry 在 newTable 的索引,并存入到对应位置,从而将 oldTable 中全部转移 Entry 到 newTable 中扩容时,在多线程中可能产生条件竞争,从而产生死循环,故避免在多线程中使用 HashMap;
2、 采用数组+链表结构存储元素,链地址法解决哈希冲突;
3、 当 Entry 哈希码和 key 同时相等,才能确定 key 已存在或找到对应 key 的 entry;
4、 entrySet 方法已经返回了 key-value 映射关系,不要用 keySet 方法;
5、 允许使用 null 值和 null 键;

jdk1.8 优化:

1、 采用数组+链表+红黑树结构提高了查找性能当哈希桶中元素达到 TREEIFY_THRESHOLD=8 时,由链表转换为红黑树 TreeNode 少于 8 时,又会转换为链表结构;

上次编辑于:
贡献者: Andy