Java Map 集合学习笔记

Map 概述

Map 和 Collection 没有继承关系。
Map 以键值对的方式存储数据，key 和 value 都是存储对象的内存地址。
key 起到主导作用，value 是 key 的一个附属品，所有的 key 是一个 Set 集合。

Map 接口常用方法

• void clear()
• boolean containsKey(Object key)
• boolean containsValue(Object value)
• boolean isEmpty()
• V get(Object key)通过 key 获取 value
• Set<K> keySet()获取 Map 集合所有的 key
• V put(K key, V value)向 Map 集合中添加键值对
• V remove(Object key)通过 key 删除键值对
• int size()获取集合中键值对个数
• Collection<V> values()获取 Map 集合中所有 value，返回一个 Collection
• Set<Map.Entry<K,V>> entrySet()将 Map 集合转换成 Set 集合。转换后 key 和 value 对应起来，形成 key = 对应 value 的形式。
  Entry 是 Map 的静态内部类。

Map<Integer,String>map=newHashMap<>();Set<Map.Entry<Integer,String>>set=map.entrySet();// set 元素类型就是 Map.Entry<K,V>

遍历 Map 集合

第一种方式

1. 通过keySet()方法获取所有的 key，所有的 key 是一个 Set 集合。
2. 遍历 key（可以使用迭代器或者 foreach），通过 key 获取 value（通过get方法）。

第二种方式

1. 通过entrySet()方法将 Map 全部转换成 Set。
2. 通过迭代器或者 foreach 遍历 Set 集合。

Set<Map.Entry<Integer,String>>set=map.entrySet();Iterator<Map.Entry<Integer,String>>it=set.iterator();while(it.hasNext()){Map.Entry<Integer,String>node=it.next();Integerkey=node.getKey();Stringvalue=node.getValue();}for(Map.Entry<Integer,String>node:set){Integerkey=node.getKey();Stringvalue=node.getValue();}

HashMap 集合

底层数据结构

1. HashMap 集合底层是哈希表的数据结构。
2. 哈希表是数组和单向链表的结合体（一维数组，数组中每一个元素是一个单链表），能充分发挥数组和单向链表的优点。

底层源码

publicclassHashMap{Node<K,V>table;staticclassNode{finalinthash;// 哈希值（是 key 的 hashCode() 方法的执行结果，通过哈希算法计算出数组下标）finalKkey;finalVvalue;Node<K,V>next;// 下一个节点的存储地址}}

深入 put(k,v) 方法

实现原理：

1. 先将 k，v 封装到 Node 对象中。
2. 底层调用hashCode()方法得出 hash 值，通过哈希算法将 hash 值转换成数组下标。
   • 下标位置没有元素的话，将 Node 添加到这个位置。
   • 如果对应下标有链表，就拿着 k 和链表中每一个 k 进行equals比较，如果都返回 false 则添加到链表末尾；如果有返回 true 的，那么这个节点的 value 被覆盖。

深入 get(k) 方法

原理类似 put(k,v)：
调用 key 的hashCode()方法得出 hash 值，然后通过哈希算法得出数组下标。

• 如果该下标下没有元素则返回 null。
• 否则拿着 k 和该下标的链表进行equals比较，有返回 true 的就返回 value，没有的话就返回 null。

重写 hashCode() 和 equals()

HashMap 集合中的hashCode()和equals()方法会被调用，所以需要对这两个方法进行重写。
由于放在 HashMap 中的 key 部分就是放在 HashSet 集合中了，所以 HashSet 集合也需要重写hashCode()和equals()。

hashCode使用不当会导致 HashMap 无法发挥性能：

• 如果hashCode的返回值都不一样，HashMap 就会被用成一维数组。
• 如果返回值都一样，就会被用成单向链表。
  要想充分发挥 HashMap 的性能，这些元素最好散列分布均匀。

放在 HashMap 和 HashSet 中的元素都需要重写hashCode和equals方法。

扩容与红黑树优化

• HashMap 中的所用容量占总容量 0.75 的时候就会开始扩容。
• 在 JDK 8 之后，如果 HashMap 中单向链表的元素超过 8 个，单向链表的数据结构就会变成红黑树；而元素个数低于 6 时会将红黑树再改回单向链表。这样做可以提高检索效率。

HashMap 和 Hashtable 的区别

• HashMap 允许 key 和 value 部分为 null，但只能有一个 key 为 null。
• Hashtable 不允许 key 部分和 value 部分为空，会报空指针异常。
  由于 Hashtable 是线程安全的，其下方法都带synchronized关键字，效率低，所以不常用。

Properties 属性类

Properties 是一个 Map 集合，继承 Hashtable，Properties 的 key 和 value 都是 String 类型。
Properties 被称为属性类对象，是线程安全的。

• 存：setProperty
• 取：getProperty

Propertiespro=newProperties();pro.setProperty("111","abandon");pro.getProperty("111");

HashSet 集合

• 无序不可重复。

Sets1=newHashSet();

TreeSet 集合

底层实现

TreeSet 集合底层实际是一个 TreeMap，TreeMap 集合底层是一个二叉树。
放到 TreeSet 集合中的元素，等同于放到 TreeMap 集合 key 部分了。
TreeMap 集合中的元素无序不可重复，但会自动排序。
但是对于自定义类型的元素来说，TreeSet 不能排序，因为没有指定比较规则，会抛出异常。

自平衡二叉树

• 左小右大的方式存放。
• 遍历二叉树的方式：
  • 前序遍历：根左右
  • 中序遍历：左根右
  • 后序遍历：左右根
• TreeSet 和 TreeMap 采用中序遍历，Iterator 也是中序遍历。

元素排序的两种方式

放到 TreeSet 或者 TreeMap 集合 key 部分的元素要想做到排序有两种方式：

1. 实现Comparable接口
2. 在构造集合的时候传递一个比较器Comparator

第一种方式：实现 Comparable 接口

要进行比较就要让自定义类型实现Comparable接口，同时实现接口中的compareTo方法。
TreeSet 中的equals可以不重写，需要在这个方法中写出比较的规则。

compareTo源代码：

publicintcompareTo(To){return0;}

例如，有一个 Stu 类，需要根据年龄大小进行排序放到 TreeSet：

classStuimplementsComparable<Stu>{intage;publicStu(){}publicStu(intage){this.age=age;}publicintcompareTo(Stus){// 调用的时候就是 s1.compareTo(s)，也就是 this(已放置的) 和 s(需要放置的) 比较returns.age-this.age;// 需要放置的 s 大返回正数，s 小返回负数，相等返回 0，然后调用者再根据返回值进行排序}}

第二种方式：使用比较器 Comparator

实现比较器接口：

classStu{intage;publicStu(){}publicStu(intage){this.age=age;}}classStuComparatorimplementsComparator<Stu>{publicintcompare(Stus1,Stus2){returns1.age-s2.age;}}// TreeSet<Stu> stus = new TreeSet<>(); 这个时候不能这么构造了TreeSet<Stu>stus=newTreeSet<>(newStuComparator());// 需要传递比较器进去

或者使用匿名内部类，直接 new 接口：

TreeSet<Stu>stus=newTreeSet<>(newComparator<Stu>(){publicintcompare(Stus1,Stus2){returns1.age-s2.age;}});

两种方式的选择

• 当比较规则单一的时候，建议使用 Comparable 接口。
• 如果有多个规则并需要频繁切换，建议使用 Comparator 接口。

集合工具类 Collections

java.util.Collections是集合工具类，注意与java.util.Collection（集合接口）区分。

Listl1=newArrayList();// 变成线程安全的Collections.synchronizedList(l1);// 此时 l1 就是线程安全的了l1.add(100);l1.add(200);// 排序Collections.sort(l1);// 对自定义类型的元素排序，例如 StuList<Stu>l2=newArrayList<>();// 两种方式：// 1. 实现 Comparable 接口// 2. 用比较器对象// Set 集合如何排序？可以将 Set 转换为 ListSet<Stu>set=newHashSet<>();List<Stu>list=newArrayList<>(set);Collections.sort(list);// 或者用比较器对象：Collections.sort(比较器对象)