Java集合类学习(四) Map集合

1 Map集合类型

1.1 Map

  • 特点:存储的键值对映射关系,根据key可以找到value
  • Map中所有的Key集合可以看做Set集合,无序、唯一
  • Map中所有Value的集合无序、不唯一
  • Set集合的底层就是Map,所以Set和Map的类型一致,也有HashMap、LinkedHashMap、TreeMap三种

1.2 HashMap

• 采用Hashtable哈希表存储结构
• 优点:添加速度快 查询速度快 删除速度快
• 缺点:key无序

1.3 LinkedHashMap

• 采用哈希表存储结构,同时使用链表维护次序
• key有序(添加顺序)

1.4 TreeMap

• 采用二叉树(红黑树)的存储结构
• 优点:key有序 查询速度比List快
• 缺点:查询速度没有HashMap快

2 Map接口方法摘要

返回值 方法描述
void clear() 从此映射中移除所有映射关系(可选操作)。
boolean containsKey(Object key) 如果此映射包含指定键的映射关系,则返回 true。
boolean containsValue(Object value) 如果此映射将一个或多个键映射到指定值,则返回 true。
Set<Map.Entry<K,V>> entrySet() 返回此映射中包含的映射关系的 Set 视图。
boolean equals(Object o) 比较指定的对象与此映射是否相等。
V get(Object key) 返回指定键所映射的值;如果此映射不包含该键的映射关系,则返回 null。
int hashCode() 返回此映射的哈希码值。
boolean isEmpty() 如果此映射未包含键-值映射关系,则返回 true。
Set keySet() 返回此映射中包含的键的 Set 视图。
V put(K key, V value) 将指定的值与此映射中的指定键关联(可选操作)。
void putAll(Map<? extends K,? extends V> m) 从指定映射中将所有映射关系复制到此映射中(可选操作)。
V remove(Object key) 如果存在一个键的映射关系,则将其从此映射中移除(可选操作)。
int size() 返回此映射中的键-值映射关系数。
Collection values() 返回此映射中包含的值的 Collection 视图。

3 HashMap源码分析

  • JDK1.7及其之前,HashMap底层是一个table数组+链表实现的哈希表存储结构 Java集合类学习(四) Map集合
  • 在JDK1.8中有一些变化,当链表的存储数据个数大于等于8的时候,不再采用链表存储,而采用红黑树存储结构。这么做主要是查询的时间复杂度上,链表为O(n),而红黑树一直是O(logn)。如果冲突多,并且超过8,采用红黑树来提高效率
    Java集合类学习(四) Map集合
  • 链表的每个节点就是一个Entry,其中包括:键key、值value、键的哈希码hash、执行下一个节点的引用next四部分
static class Entry<K, V> implements Map.Entry<K, V> {
     final K key; //key
     V value;//value
     Entry<K, V> next; //指向下一个节点的指针
     int hash;//哈希码
}

3.1 HashMap基本属性

//JDK1.7
public class HashMap<K, V> implements Map<K, V> {
    //哈希表主数组的默认长度
    static final int DEFAULT_INITIAL_CAPACITY = 16; 
    //默认的装填因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f; 
    //主数组的引用
    transient Entry<K, V>[] table; 
    int threshold;//界限值  阈值 主数组长度×装填因子
    final float loadFactor;//装填因子
    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }
    public HashMap(int initialCapacity, float loadFactor) {
        this.loadFactor = loadFactor;//0.75
        threshold = (int) Math.min(capacity * loadFactor, 
                 MAXIMUM_CAPACITY + 1);//16*0.75=12
        table = new Entry[capacity];
      ....
    }
 }

3.2 HashMap的put方法

调用put方法添加键值对。哈希表主要通过三个步骤添加数据:

  1. 第一步计算哈希码,注意计算哈希码时不仅调用了key的hashCode(),还进行了更复杂处理,目的是尽量保证不同的key尽量得到不同的哈希码
  2. 第二步根据哈希码计算存储位置,这里使用了位运算提高效率。同时也要求主数组长度必须是2的幂
  3. 第三步添加Entry
    正常情况:添加到链表的第一个位置,而不是链表末尾
    发现了相同的key已经存在的情况:就使用新的value替代旧的value,并且返回旧的value
public class HashMap {
    public V put(K key, V value) {
       //如果key是null,特殊处理
        if (key == null) return putForNullKey(value);
        //1.计算key的哈希码hash 
        int hash = hash(key);
        //2.将哈希码代入函数,计算出存储位置  y= x%16;
        int i = indexFor(hash, table.length);
        //如果已经存在链表,判断是否存在该key,需要用到equals()
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //如找到了,使用新value覆盖旧的value,返回旧value
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
                V oldValue = e.value;// the United States
                e.value = value;//America
                e.recordAccess(this);
                return oldValue;
            }
        }
        //添加一个结点
        addEntry(hash, key, value, i);
        return null;
    }
    final int hash(Object k) {
        int h = 0;
        h ^= k.hashCode();
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
    static int indexFor(int h, int length) {
    //作用就相当于y = x%16,采用了位运算,效率更高
        return h & (length-1);
    }
}

3.3 HashMap的get方法

其实是根据key找Entry,再从Entry中获取value即可

public V get(Object key) {
    //根据key找到Entry(Entry中有key和value)
    Entry<K,V> entry = getEntry(key);
    //如果entry== null,返回null,否则返回value
    return null == entry ? null : entry.getValue();
}

3.4 HashMap的扩容

void addEntry(int hash, K key, V value, int bucketIndex) {
    //如果达到了门槛值,就扩容,容量为原来容量的2位 16---32
    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);
}

4 TreeMap源码分析

Java集合类学习(四) Map集合

TreeMap每个节点的结构

static final class Entry<K,V> implements Map.Entry<K,V> {
   K key;
   V value;
   Entry<K,V> left;
   Entry<K,V> right;
   Entry<K,V> parent;
   boolean color = BLACK;
}

4.1 TreeMap基本属性

public class TreeMap<K, V> implements NavigableMap<K, V> {
    private final Comparator<? super K> comparator;//外部比较器
    private transient Entry<K, V> root = null; //红黑树根节点的引用
    private transient int size = 0;//红黑树中节点的个数
    public TreeMap() {
        comparator = null;//没有指定外部比较器
    }
    public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;//指定外部比较器
    }
}

4.2 TreeMap的put和get方法

添加原理

  • 从根节点开始比较
  • 添加过程就是构造二叉平衡树的过程,会自动平衡
  • 平衡离不开比较:外部比较器优先,然后是内部比较器。如果两个比较器都没有,就抛出异常
  • 查找方法与添加方法的原理基本相同
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;
        return null;
    }
    //如果是添加非第一个节点,就这么处理
    int cmp;
    Entry<K,V> parent; 
    Comparator<? super K> cpr = comparator;
    //如果外部比较器存在,就使用外部比较器
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;//在左子树中查找
           else if (cmp > 0)                
                t = t.right; //在右子树查找
            else
               //找到了对应的key,使用新的value覆盖旧的value                 
                return t.setValue(value);
        } while (t != null);
    }
    else {
        //如果外部比较器没有,就使用内部比较器
       ....
    }
    //找到了要添加的位置,创建一个新的节点,加入到树中
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)  
        parent.left = e;
    else
        parent.right = e;       
    size++;
    return null;
}

public V get(Object key) {
    //根据key(cn)找Entry(cn--China)
    Entry<K,V> p = getEntry(key);
    //如果Entry存在,返回value:China
    return (p==null ? null : p.value);
}

final Entry<K, V> getEntry(Object key) {
    //如果外部比较器存在,就使用外部比较器
    if (comparator != null)
        return getEntryUsingComparator(key);
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
    //如果外部比较器不存在,就使用内部比较器
    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;
        else if (cmp > 0)
            p = p.right;
        else
            //如果找到了,就返回Entry
            return p;
    }
    //如果没有找到,就返回null
    return null;
}


上一篇:java集合浅谈——Map之HashTable


下一篇:JDK1.7HashMap死锁