脑图:

Java 中的 Map 接口 是和 Collection 接口 同一等级的集合根接口,它 表示一个键值对 (key-value) 的映射

没有重复的 key;
每个 key 只能对应一个 value, 多个 key 可以对应一个 value;
key,value 都可以是任何引用类型的数据,包括 null

  • 遍历

    //使用 keySet 遍历:
    Set set = map.keySet();
    for (Object key : set) {
        System.out.println(map.get(key));
    }
    //使用 values 遍历:
    Collection values = map.values();
    Iterator iterator = values.iterator();
    while (iterator.hasNext()){
        System.out.println("value " + iterator.next());
    }
    //使用 Entry 遍历,通过 Map.entrySet() 方法获得的是一组 Entry 的集合,保存在 Set 中
    Set entrySet = map.entrySet();
    for (Object o : entrySet) {
        Map.Entry entry = (Map.Entry) o;
        System.out.println(entry);      //key=value
        System.out.println(entry.getKey() + " / " + entry.getValue());
    }
  • Entry

    Map 接口中的静态内部接口,表示一个键值对的映射

  • Hashtable
    古老,线程安全:Hashtable不允许键或者值是null。

  • HashMap
    容量:数组的数量
    加载因子:决定了 HashMap 中的元素占有多少比例时扩容
    工作原理:当调用put()方法的时候,HashMap会计算key的hash值,然后把键值对存储在集合中合适的索引上
    在插入元素的时候是先算出该对象的hashCode。
    如果hashcode相等话的。那么表明该对象是存储在同一个位置上的。
    如果调用equals()方法,两个key相同,则替换元素
    如果调用equals()方法,两个key不相同,则说明该hashCode仅仅是碰巧相同,此时是散列冲突,将新增的元素放在桶子上
    1. 在获取指定元素前需要经过哈希运算,得到目标元素在哈希表中的位置,然后再进行少量比较即可得到元素
    2. 发生 哈希冲突(碰撞)的时候,HashMap 采用 拉链法(桶) 进行解决
    3. 底层实现是 链表数组,JDK 8 后又加了 红黑树
    4. 实现了 Map 全部的方法
    5. key 用 Set 存放,所以想做到 key 不允许重复,key 对应的类需要重写 hashCode 和 equals 方法
    6. 允许空键和空值(但空键只有一个,且放在第一位)
    7. 元素是无序的,而且顺序会不定时改变
    8. 插入、获取的时间复杂度基本是 O(1)(前提是有适当的哈希函数,让元素分布在均匀的位置)
    9. 遍历整个 Map 需要的时间与 桶(数组) 的长度成正比(因此初始化时 HashMap 的容量不宜太大)

红黑树

1.当 HashMap 中有大量的元素都存放到同一个桶中时,这个桶下有一条长长的链表
这个时候 HashMap 就相当于一个单链表,假如单链表有 n 个元素,遍历的时间复杂度就是 O(n)
2.在添加时,如果一个桶中已经是红黑树结构,就要调用红黑树的添加元素方法 putTreeVal()。
3.删除、扩容时,如果桶中结构为红黑树,并且树中元素个数太少的话,会进行修剪或者直接还原成链表结构;
4.在Java 8 中,如果一个桶中的元素个数超过 TREEIFY_THRESHOLD(默认是 8 ),就使用红黑树来替换链表,从而提高速度
1.HashMap 中往红黑树中添加一个新节点 n 时
2.根节点开始遍历当前红黑树中的元素 p,对比 n 和 p 的哈希值;
3.如果哈希值相等并且键也相等,就判断为已经有这个元素
4.最后得到哈希值比较结果后,如果当前节点 p 还没有左孩子或者右孩子时才能插入,否则就进入下一轮循环;
5.插入元素后还需要进行红黑树例行的平衡调整,还有确保根节点的领先地位。

static class Node<K,V> implements Map.Entry<K,V> {
    //哈希值,就是位置
    final int hash;
    //键
    final K key;
    //值
    V value;
    //指向下一个几点的指针
    Node<K,V> next;
    //...
}
  • TreeMap
    有序的,效率比 HashMap 低

  • LinkedHashMap
    结合 HashMap 和 TreeMap 的有点,有序的同时效率也不错,仅比 HashMap 慢一点

HashMap 和 HashTable 到底哪不同 ?