javajavase
Map接口 - 图1

  1. Map:双列数据，存储key-value对的数据   ---类似于高中的函数：y = f(x)
  2. |----HashMap:作为Map的主要实现类；线程不安全的，效率高；存储null的key和value
  3.       |----LinkedHashMap:保证在遍历map元素时，可以照添加的顺序实现遍历。
  4.                原因：在原的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。
  5.                对于频繁的遍历操作，此类执行效率高于HashMap。
  6. |----TreeMap:保证照添加的key-value对进行排序，实现排序遍历。此时考虑key的自然排序或定制排序
  7.                底层使用红黑树
  8. |----Hashtable:作为古老的实现类；线程安全的，效率低；不能存储null的key和value
  9.       |----Properties:常用来处理配置文件。key和value都是String类型
  • Map与Collection并列存在，用于保存具有映射关系的数据：key-value
  • Map接口的常用实现类：HashMap、LinkedHashMap、TreeMap、Properties
  • 其中HashMap是Map接口使用频率最高的实现类

Map结构的理解

  • Map中的key：无序、不可重复的
    • key类似于Set存储—->key所在的类要重写equals()和hashCode() （以HashMap为例）
  • Map中的value：无序、可重复的
    • value类似于Collection存储—->value所在的类要重写equals()
  • 一个键值对：key-value构成了一个Entry对象
    • Map中的entry:无序、不可重复的

Map接口 - 图2

常用方法

  • 添加、修改

**Object put(K key, V value)**第一次存储，直接存储元素返回null；如果已经存在值，就把以前的值替换掉返回以前的值
**void putAll(Map m)**将m中的所有key-value对存放到当前map中

  • 删除

**Object remove(Object key)**移除指定key的key-value对，并返回value
**void clear()**清空当前map中的所有数据

  1. @Test
  2. public void test1() {
  3.     Map map = new HashMap();
  4.     //添加
  5.     map.put("AA",123);
  6.     map.put(45,123);
  7.     map.put("BB",56);
  8.     //修改
  9.     map.put("AA",87);
  10.     System.out.println(map);
  12.     Map map1 = new HashMap();
  13.     map1.put("CC",123);
  14.     map1.put("DD",123);
  15.     map.putAll(map1);
  16.     System.out.println(map);
  18.     //remove(Object key)
  19.     Object value = map.remove("CC");
  20.     System.out.println(value);
  21.     System.out.println(map);
  23.     //clear()
  24.     map.clear();//与map = null操作不同
  25.     System.out.println(map.size());
  26.     System.out.println(map);
  27. }
  • 查询

**Object get(Object key)**获取指定key对应的value
**boolean containsKey(Object key)**是否包含指定的key
**boolean containsValue(Object value)**是否包含指定的value
**int size()**返回map中key-value对的个数
**boolean isEmpty()**判断当前map是否为空
**boolean equals(Object obj)**判断当前map和参数对象obj是否相等

  1. @Test
  2. public void test2() {
  3.     Map map = new HashMap();
  4.     map.put("AA", 123);
  5.     map.put(45, 123);
  6.     map.put("BB", 56);
  8.     // Object get(Object key)
  9.     System.out.println(map.get(45));
  11.     // containsKey(Object key)
  12.     System.out.println(map.containsKey("BB"));
  14.     isExist = map.containsValue(123);
  15.     System.out.println(isExist);
  17.     map.clear();
  18.     System.out.println(map.isEmpty());
  19. }
  • 元视图操作的方法

**Set keySet()**返回所有key构成的Set集合
**Collection values()**返回所有value构成的Collection集合
**Set entrySet()**返回所有key-value对构成的Set集合

  1. @Test
  2. public void test3() {
  3.     Map map = new HashMap();
  4.     map.put("AA",123);
  5.     map.put(45,1234);
  6.     map.put("BB",56);
  8.     // 遍历所有的key集：keySet()
  9.     Set set = map.keySet();
  10.     Iterator iterator = set.iterator();
  11.     while(iterator.hasNext()) {
  12.         System.out.println(iterator.next());
  13.     }
  14.     System.out.println();
  16.     // 遍历所有的value集：values()
  17.     Collection values = map.values();
  18.     for(Object obj : values) {
  19.         System.out.println(obj);
  20.     }
  21.     System.out.println();
  23.     // 遍历所有的key-value
  24.     // 方式一：entrySet()
  25.     Set entrySet = map.entrySet();
  26.     Iterator iterator1 = entrySet.iterator();
  27.     while (iterator1.hasNext()) {
  28.         Object obj = iterator1.next();
  29.         //entrySet集合中的元素都是entry
  30.         Map.Entry entry = (Map.Entry) obj;
  31.         System.out.println(entry.getKey() + "---->" + entry.getValue());
  32.     }
  33.     System.out.println();
  35.     // 方式二：
  36.     Set keySet = map.keySet();
  37.     Iterator iterator2 = keySet.iterator();
  38.     while(iterator2.hasNext()) {
  39.         Object key = iterator2.next();
  40.         Object value = map.get(key);
  41.         System.out.println(key + "=====" + value);
  42.     }
  43. }

HashMap

HashMap是Map接口使用频率最高的实现类

  • 允许使用null键和null值，与HashSet一样，不保证映射的顺序
  • 所有的key构成类似于set：无序、不可重复的。所以key所在的类要重写equals()和hashCode()
  • 所有的value构成类似于Collection：无序、可以重复的。所以，value所在的类要重写equals()
  • 一个key-value构成一个entry
  • 所有的entry构成的集合是Set：无序、不可重复的
  • HashMap判断两个key相等的标准是：两个key通过equals()方法返回true，hashCode值也相等

  • HashMap判断两个value相等的标准是：两个value通过equals()方法返回true.

    1. @Test
    2. public void test1() {
    3.   Map map = new HashMap();
    4.   map.put(null,123);
    5. }

    底层实现原理

  • 存储结构

    • JDK 7.0及以前的版本：HashMap是数组+链表结构（地址链表法）
    • JDK 8.0版本以后：HashMap是数组+链表+红黑树实现
  • 结构图

Map接口 - 图3

Map接口 - 图4

对象创建和添加过程

  1. HashMap map = new HashMap()
  2. // 在实例化以后，底层创建了长度是16的一维数组Entry[] table
  3. map.put(key1, value1); // ...可能已经执行过多次put...
  • 首先，调用key1所在类的hashCode()计算key1哈希值，此哈希值经过某种算法计算后，得到在Entry数组中的存放位置
  • 如果此位置上的数据为空，此时的key1-value1添加成功——情况1

  • 如果此位置上的数据不为空，(意味着此位置上存在一个或多个数据(以链表形式存在))，比较key1和已经存在的一个或多个数据的哈希值：

    • 如果key1的哈希值与已经存在的数据的哈希值都不相同，此时key1-value1添加成功——情况2

    • 如果key1的哈希值和已经存在的某一个数据(key0-value0)的哈希值相同，继续比较：调用key1所在类的equals(key2)方法，比较：

      • 如果equals()返回false:此时key1-value1添加成功——情况3
      • 如果equals()返回true:使用value1替换value0

        补充：关于情况2和情况3，此时key1-value1和原来的数据以链表的方式存储

    • 不断的添加过程中，会涉及到扩容问题，当超出临界值且要存放的位置非空时，扩容。默认的扩容方式：扩容为原来容量的2倍，并将原有的数据复制过来

  • JDK8.0与JDK7.0中HashMap底层的变化

    1. new HashMap()底层没有创建一个长度为16的数组
    2. JDK 8.0底层的数组是：Node[]，而非Entry[]
    3. 首次调用put()方法时，底层创建长度为16的数组
    4. JDK 7.0底层结构只有：数组+链表；JDK 8.0中底层结构：数组+链表+红黑树
      • 形成链表时，七上八下（jdk7：新的元素指向旧的元素。jdk8：旧的元素指向新的元素）
      • 当数组的某一个索引位置上的元素以链表形式存在的数据个数 >= 8且当前数组的长度 >= 64时，此时此索引位置上的所数据改为使用红黑树存储

        HashMap的扩容

        当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，而在HashMap数组扩容之后，原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize

  • HashMap扩容时机

当HashMap中的元素个数超过数组大小（数组总大小length，不是数组中个数） loadFactor时，就会进行数组扩容，loadFactor的默认值(DEFAULTLOAD FACTOR)为0.75。这是一个折中的取值，也就是说，默认情况下，数组大小(DEFAULT INITIAL CAPACITY)为16，那么当 HashMap中元素个数超过16 0.75=12（这个值就是代码中的threshold值，也叫做临界值）的时候，就把数组的大小扩展为2 * 16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能

  • JDK8.0与JDK7.0中HashMap的扩容机制变化
    • 当HashMapl中的其中一个链的对象个数没有达到8个和JDK 7.0以前的扩容方式一样
    • 当HashMapl中的其中一个链的对象个数如果达到了8个，此时如果 capacity没有达到64，那么HashMap会先扩容解决，如果已经达到了64，那么这个链会变成树，结点类型由Node变成 TreeNode类型。当然，如果当映射关系被移除后，下次resize方法时判断树的结点个数低于6个，也会把树再转为链表
  • 底层典型属性的说明
    • DEFAULT_INITIAL_CAPACITY : HashMap的默认容量16
    • DEFAULT_LOAD_FACTOR：HashMap的默认装载因子0.75
    • threshold：扩容的临界值，= 容量填充因子**16 0.75 => 12**
    • TREEIFY_THRESHOLD：Bucket中链表长度大于该默认值8，转化为红黑树——JDK 8.0引入
    • MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量64

      HashMap为何在JDK8中进行如此重大的修改

      为了解决两个隐患
  1. 由于HashMap本身并非线程安全的，所以此隐患并非JDK漏洞。JDK1.7中添加数据达到阈值而触发扩容的时候，创建新数组，原数组某一个桶的若干个数据会被放入新数组的某个桶中，JDK1.7采用的是头插法，假如原数组某个桶中存放链表数据A->B->C->D，其中BC被移往新数组中的一个桶中，单线程下会先放B再放C，此新桶中数据为C—>B，而若此时有两个线程一二都进行扩容可能会使得线程一放为C—>B，而线程二放为B->C，从而BC之间形成循环，再往这个桶中存入新数据会造成死锁，JDK1.8扩容后改为尾插法
  2. 因为多个数据通过hashCode()计算出相同的hash值，黑客很容易创造出大量的相同hash值的数据，进而都放进HashMap内的同一个桶之中，从而使得HashMap查找等操作的时间复杂度从O(1)变为O(n)，进而在如Tomcat服务器中大量用户同时查询这一个桶中的数据，会使得服务器负担极具加重，这就是为何JDK1.8中当链表达到8个后会改为红黑树的原因。而为何是8这个数字，是因为根据泊松分布计算出的结果，一个桶中包含一个数据的概率是0.36，而有8个数据的概率仅剩不足万分之一，设置为8既能防止前面提到的安全漏洞，又能使得触发链表改红黑树这种操作的概率极低
  3. 此外还有延迟开辟数组空间，当放入第一个数据时才开辟

    LinkedHashMap

    LinkedHashMap继承于HashMap

    底层实现原理

  • LinkedHashMap底层使用的结构与HashMap相同
  • 区别就在于：LinkedHashMap内部提供了Entry，替换HashMap中的Node
  • 在HashMap存储结构的基础上，使用了一对双向链表来记录添加元素的顺序

  • 与LinkedHashSet类似，LinkedHashMap可以维护Map的迭代顺序：迭代顺序与Key-value对的插入顺序一致

    1. @Test
    2. public void test() {
    3.   Map map = new LinkedHashMap();
    4.   map.put(123,"AA");
    5.   map.put(345,"BB");
    6.   map.put(12,"CC");
    7.   System.out.println(map);
    8. }

    HashMap中内部类Node源码

    1. static class Node<K,V> implements Map.Entry<K,V> {
    2.   final int hash;
    3.   final K key;
    4.   V value;
    5.   Node<K,V> next;
    6. }

    LinkedHashM中内部类Entry源码

    1. static class Entry<K,V> extends HashMap.Node<K,V> {
    2.   Entry<K,V> before, after;    // 能够记录添加的元素的先后顺序
    3.   Entry(int hash, K key, V value, Node<K,V> next) {
    4.       super(hash, key, value, next);
    5.   }
    6. }

    TreeMap

  • 向TreeMap中添加key-value，要求key必须是由同一个类创建的对象

  • TreeMap存储Key-Value时，需要根据key进行排序，可以保证所有的Key-Value处于有序状态
  • TreeSet底层使用红黑树结构存储数据
  • TreeMap的Key的排序:
    • 自然排序：TreeMap的所有的Key必须实现Comparable接口，而且所有的Key应该是同一个类的对象，否则将会抛出 ClasssCastEXception()
    • 定制排序：创建TreeMap时，传入一个Comparator对象，该对象负责对TreeMap中的所有key进行排序。此时不需要Map的Key实现Comparable接口

  • TreeMap判断两个key相等的标准：两个key通过compareTo()方法或者compare()方法返回0

    1. //自然排序
    2. @Test
    3. public void test1(){
    4.   TreeMap map = new TreeMap();
    5.   User u1 = new User("Tom",23);
    6.   User u2 = new User("Jerry",32);
    7.   User u3 = new User("Jack",20);
    8.   User u4 = new User("Rose",18);
    9.   map.put(u1,98);
    10.   map.put(u2,89);
    11.   map.put(u3,76);
    12.   map.put(u4,100);
    14.   Set entrySet = map.entrySet();
    15.   Iterator iterator1 = entrySet.iterator();
    16.   while (iterator1.hasNext()) {
    17.       Object obj = iterator1.next();
    18.       Map.Entry entry = (Map.Entry) obj;
    19.       System.out.println(entry.getKey() + "---->" + entry.getValue());
    20.   }
    21. }
    22. //定制排序
    23. @Test
    24. public void test2(){
    25.   TreeMap map = new TreeMap(new Comparator() {
    26.       @Override
    27.       public int compare(Object o1, Object o2) {
    28.           if(o1 instanceof User && o2 instanceof User){
    29.               User u1 = (User)o1;
    30.               User u2 = (User)o2;
    31.               return Integer.compare(u1.getAge(),u2.getAge());
    32.           }
    33.           throw new RuntimeException("输入的类型不匹配！");
    34.       }
    35.   });
    37.   User u1 = new User("Tom",23);
    38.   User u2 = new User("Jerry",32);
    39.   User u3 = new User("Jack",20);
    40.   User u4 = new User("Rose",18);
    41.   map.put(u1,98);
    42.   map.put(u2,89);
    43.   map.put(u3,76);
    44.   map.put(u4,100);
    46.   Set entrySet = map.entrySet();
    47.   Iterator iterator1 = entrySet.iterator();
    48.   while (iterator1.hasNext()){
    49.       Object obj = iterator1.next();
    50.       Map.Entry entry = (Map.Entry) obj;
    51.       System.out.println(entry.getKey() + "---->" + entry.getValue());
    53.   }
    54. }

    Hashtable

  • Hashtable是个古老的Map实现类，JDK1.0就提供了。不同于HashMap，Hashtable是线程安全的

  • Hashtable实现原理和HashMap相同，功能相同。底层都使用哈希表结构，查询速度快，很多情况下可以互用
  • 与HashMap不同，Hashtable不允许使用null作为key和value
  • 与HashMap一样，Hashtable也不能保证其中Key-value对的顺序

  • Hashtable判断两个key相等、两个value相等的标准，与HashMap-致

    Properties

  • Properties类是Hashtable的子类，该对象用于处理属性文件

  • 由于属性文件里的key、value都是字符串类型，所以Properties里的key和value都是字符串类型
  • 存取数据时，建议使用

**setProperty(String key,String value)**
**getProperty(String key)**
**load(FileInputStream fis)**

  1. // Properties:常用来处理配置文件。key和value都是String类型
  2. public static void main(String[] args) {
  3.     FileInputStream fis = null;
  4.     try {
  5.         Properties pros = new Properties();
  6.         fis = new FileInputStream("jdbc.properties");
  7.         pros.load(fis);    // 加载流对应的文件
  9.         String name = pros.getProperty("name");
  10.         String password = pros.getProperty("password");
  11.         System.out.println("name = " + name + ", password = " + password);
  12.     } catch (IOException e) {
  13.         e.printStackTrace();
  14.     } finally {
  15.         if(fis != null) {
  16.             try {
  17.                 fis.close();
  18.             } catch (IOException e) {
  19.                 e.printStackTrace();
  20.             }
  21.         }
  22.     }
  23. }

面试题

  1. HashMap的底层实现原理？
  2. HashMap和Hashtable的异同？
  3. ConcurrentHashMap 与 Hashtable的异同？
  4. 负载因子值的大小，对HashMap的影响？
    • 负载因子的大小决定了HashMap的数据密度
    • 负载因子越大密度越大，发生碰撞的几率越高，数组中的链表越容易长，造成査询或插入时的比较次数增多，性能会下降
    • 负载因子越小，就越容易触发扩容，数据密度也越小，意味着发生碰撞的几率越小，数组中的链表也就越短，查询和插入时比较的次数也越小，性能会更高。但是会浪费一定的内存空间。而且经常扩容也会影响性能，建议初始化预设大一点的空间
    • 按照其他语言的参考及研究经验，会考虑将负载因子设置为0.7~0.75，此时平均检索长度接近于常数