Map
★Map接口和常用方法
public interface Map<K,V>Map接口实现类的特点：Map与Collection并列存在。用于保存具有映射关系的数据：**Key-Value**（双列元素）。Map中的key和value可以是任何引用类型的数据，会封装到HashMap$Node对象中。Map中的key不允许重复，原因和HashSet一样，前面分析过源码。**注意：当
key重复时，后面put的value会替换前面put的value**，例如：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18package com.f.chapter14.map;
import java.util.HashMap;
import java.util.Map;
/**
* @author fzy
* @date 2023/6/21 14:50
*/
public class Map01 {
public static void main(String[] args) {
Map map = new HashMap();
map.put("num1", "java");
map.put("num2", "go");
map.put("num1", "python");
System.out.println(map);
}
}输出结果为：
1
{num1=python, num2=go}
Map中的value可以重复。Map的key可以为null，value也可以为null。注意
key可以为null，但是只能有一个；value可以为null，但是可以多个。经常使用
String类作为Map的key。key和value之间存在单向一对一关系，即通过指定的key总能找到对应的value。如下图是
Map存放数据的key-value示意图，一对key-value最终是放在一个HashMap$Node中的，又因为Node实现了Entry接口：static class Node<K,V> implements Map.Entry<K,V>，所以有些书上也说“一对k-v就是一个Entry”。
另外，
key-value为了方便程序员的遍历，还会创建entrySet集合 ：transient Set<Map.Entry<K,V>> entrySet;，该集合存放的元素的类型为HashMap$Node，该类型实现了Entry接口，而一个Entry对象就有key（指向HashMap$Node中的key）、value（指向HashMap$Node中的value）。当把
HashMap$Node对象存放到entrySet后，就方便了我们的遍历，因为Map.Entry提供了重要的方法：getKey和getValue：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28package com.f.chapter14.map;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
/**
* @author fzy
* @date 2023/6/21 14:50
*/
public class Map01 {
public static void main(String[] args) {
Map map = new HashMap();
map.put("num1", "java");
map.put("num2", "go");
map.put("num1", "python");
map.put("num3", "php");
map.put(1, "hello");
map.put(2, "world");
Set set = map.entrySet();
System.out.println(set.getClass()); //class java.util.HashMap$EntrySet
for (Object obj : set) {
//System.out.println(obj.getClass()); //class java.util.HashMap$Node
Map.Entry entry = (Map.Entry) obj;
System.out.println(entry.getKey() + " " + entry.getValue());
}
}
}最后回到这张图，一对
k-v存储到EntrySet中的流程如下：
如果我们只想得到
key的集合，也可以只使用Set set = map.keySet();如果我们只想得到
value的集合，也可以只使用Collection values = map.values();
Map接口的常用方法：put(K key, V value)：向map中添加一对k-v，如果键key重复，则会对value进行覆盖替换。 -> 增 + 改remove(Object key)：根据键删除映射关系。 -> 删get(Object key)：根据键获取值。 -> 查size()：获取k-v对的个数。isEmpty()：判断map是否为空。clear()：清空map。containsKey(Object key)：查找键是否存在。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43package com.f.chapter14.map;
import java.util.HashMap;
import java.util.Map;
/**
* @author fzy
* @date 2023/6/22 9:39
*/
public class MapMethod01 {
public static void main(String[] args) {
Map map = new HashMap();
//1.`put(K key, V value)`：向 `map` 中添加一对 `k-v` ，如果键 `key` 重复，则会对 `value` 进行覆盖替换。
map.put("num1", "三国演义");
map.put("num2", "石头记");
map.put("num2", "红楼梦"); //“红楼梦”替换了“石头记”
map.put("num3", "水浒传");
map.put("num4", "西游记");
map.put(null, "四大名著");
System.out.println(map); //{null=四大名著, num1=三国演义, num4=西游记, num3=水浒传, num2=红楼梦} -> 注意是无序的
//2.`remove(Object key)`：根据键删除映射关系。
map.remove(null);
System.out.println(map); //{num1=三国演义, num4=西游记, num3=水浒传, num2=红楼梦}
//3.`get(Object key)`：根据键获取值。
System.out.println(map.get("num2")); //红楼梦
//4.`size()`：获取 `k-v` 对的个数。
System.out.println(map.size()); //4
//5.`isEmpty()`：判断 `map` 是否为空。
System.out.println(map.isEmpty()); //false
//6.`clear()`：清空 `map`。
map.clear();
System.out.println(map); //{}
//7.`containsKey(Object key)`：查找键是否存在。
System.out.println(map.containsKey(null)); //false
}
}
Map六大遍历方式
- 分别是
KeySet、values和entrySet的增强 for和iterator遍历。
1 | package com.f.chapter14.map; |
★★★Map.Entry相关说明
对
Map.Entry相关再做一个说明：首先要明确，
Entry是一个接口，而且是Map接口的内部接口。而HashMap的静态内部类Node是实现了Map.Entry接口。**真正存放
k-v的地方是HashMap$Node**，即HashMap的静态内部类Node。EntrySet是用于方便程序员对map中的元素进行遍历，因为Map.Entry有两个抽象方法：getKey和getVal，通过这两个方法我们可以获取map中的k-v的具体的内容。因为
HashMap$Node实现了Map.Entry接口，所以其实现了getKey和getVal方法，按理来说，在进行遍历时（以第五种方式为例），我们可以直接用HashMap.Node node = (HashMap.Node) obj;，然后再使用node.getKey()和node.getVal()来获取k-v值，但实际是不行的。原因在于Node是HashMap的静态内部类，并没有被public关键字修饰，所以无法在包外被使用。所以采用
Map.Entry的方式 （Map.Entry entry = (Map.Entry) obj;）来调用entry.getKey()和entry.getVal()方法，这里是用到了接口的多态（obj实际的运行类型是HashMap$Node）。
★★★HashMap
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
HashMap是Map接口使用频率最高的实现类。HashMap以key-value对的方式来存储数据（HahsMap$Node类型）。key不能重复，但是值可以重复，允许使用null键和null值。- 如果添加相同的
key，则会覆盖原来的key-val，等同于修改。(key不会替换，val会替换) - 与
HashSet一样，不保证存入和取出的顺序一样，因为底层是以hash表的方式来存储的。 HashMap没有实现同步，因此是线程不安全的，方法没有做同步互斥的操作，没有synchronized。
HashMap底层机制
因为
HashSet底层就是HashMap，所以前面介绍的HashSet底层机制本质就是HashMap的底层机制，即HashMap底层是（数组+链表+红黑树）。
扩容机制：和
HashSet的扩容机制是完全一样的，还是再简单总结一遍：HashMap底层维护了Node类型的数组HashMap$Node[] table，默认为null。- 当创建
HashMap对象时，先将加载因子 (loadfactor) 初始化为 0.75，且table初始为 null。 - 当添加
key-val时，通过key的哈希值得到在tablel的索引。然后判断该索引处是否有元素，如果没有元素直接添加。如果该索引处有元素，继续判断该元素的key和准备加入的key是否相等，如果相等，则直接替换val；如果不相等需要判断是树结构还是链表结构，做出相应处理。如果添加时发现容量不够，则需要扩容。 - 第 1 次添加，则需要扩容
table容量为16，临界值 (threshold) 为12。 - 以后再扩容，则需要扩容
table容量为原来的 2 倍，即 32，临界值为原来的 2 倍，即24，依次类推。 - 在 Java8 中，如果一条链表的元素个数超过
TREEIFY THRESHOLD(默认是8)，并且table的大小>=MIN TREEIFY CAPACITY(默认64)，就会进行树化（红黑树）。
Hashtable
public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable
- 存放的元素是键值对：即
K-V。 Hashtable的键和值都不能为null，否则会抛出NullPointerException异常。Hashtable使用方法基本上和HashMap一样。Hashtable是线程安全的(synchronized)，HashMap是线程不安全的。
Hashtable扩容机制
Hashtable底层有数组Hashtable$Entry[]，初始化大小为 11，加载因子为 0.75，初始threshold为 8（11*0.75，丢弃小数部分）。1
2
3public Hashtable() {
this(11, 0.75f);
}1
2
3
4
5
6
7
8
9
10
11
12
13public Hashtable(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor);
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry<?,?>[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}在添加
k-v元素时，put函数会调用addEntry(hash, key, value, index);函数来添加。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
}在
addEntry函数中可以看到，如果(count >= threshold)，就会rehash，即进行扩容。扩容机制为int newCapacity = (oldCapacity << 1) + 1;。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
int newCapacity = (oldCapacity << 1) + 1; //新的容量=(旧的容量*2+1)
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Entry<K,V>)newMap[index];
newMap[index] = e;
}
}
}
Properties
Properties类继承自Hashtable类并且实现了Map接口，也是使用一种键值对的形
式来保存数据。- 它的使用特点和
Hashtable类似。 Properties还可以用于从xxx.properties文件中，加载数据到Properties类对象，
并进行读取和修改。- 说明：工作后
xxx.properties文件通常作为配置文件，这个知识点会在IO流举例。
TreeMap
TreeMap和TreeSet大同小异，因为TreeSet底层就是TreeMap。- 只不过在
TreeSet中，k-v中的v都是同一个对象（作为占位作用）：private static final Object PRESENT = new Object();。 - 在
TreeMap中，k-v中的v可以有不同的值。
- 只不过在
★注意：在
HashMap中，判断key是否相同是通过源码中的1
2if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))来判断的。
而在
TreeMap中，判断key是否相同是通过我们传入的Comparator对象来判断的。1
2
3
4
5
6TreeMap treeMap = new TreeMap(new Comparator() {
public int compare(Object o1, Object o2) {
return ((String)o1).compareTo((String)o2);
}
});
★★★集合选型规则
开发中如何选择集合实现类：
在开发中，选择什么集合实现类，主要取决于业务操作特点，然后根据集合实现类特性进行选择，分析如下：
- 先判断存储的类型（一组对象或一组键值对
k-v）。 - 如果是一组对象：
Collection接口：- 允许重复：
List- 增删多：
LinkedList（底层维护了一个双向链表） - 改查多：
ArrayList（底层维护了Object类型的可变数组）
- 增删多：
- 不允许重复：
Set- 无序：
HashSet（底层是HashMap，维护了一个哈希表，即（**数组+链表+红黑树**）。 - 排序：
TreeSet - 插入和取出顺序一致：
LinkedHashSet（维护数组+双向链表）
- 无序：
- 允许重复：
- 如果是一组键值对：
Map接口：- 键无序：
HashMap（底层是：哈希表。jdk7：数组+链表，**jdk8：数组+链表+红黑树**） - 键排序：
TreeMap - 键插入和取出顺序一致：
LinkedHashMap - 读取文件：
Properties
- 键无序：
- 先判断存储的类型（一组对象或一组键值对
Collections工具类
Collections是一个操作Set、List和Map等集合的工具类。Collections中提供了一系列静态的方法，用以对集合元素进行排序、查询和修改等操作。
排序操作
reverse(List<?> list)：反转List中的元素的顺序。shuffle(List<?> list)：对List集合元素进行随机排序。sort(List<T> list)：根据元素的自然顺序对指定List集合元素按升序排序。sort(List<T> list, Comparator<? super T> c)：通过传入Comparator来指定排序的方式，对List集合元素进行排序。swap(List<?> list, int i, int j)：将List中索引为i和j的集合元素对调位置。
1 | package com.f.chapter14.collections; |
查找操作
max(Collection<? extends T> coll)：根据元素的自然顺序，返回给定集合中的最大元素。max(Collection<? extends T> coll, Comparator<? super T> comp)：根据传入的Comparator指定的顺序，返回给定集合中的最大元素。min(Collection<? extends T> coll)：和1.类似。min(Collection<? extends T> coll, Comparator<? super T> comp)：和2.类似。frequency(Collection<?> c, Object o)：返回指定集合中指定元素的出现次数。
1 | package com.f.chapter14.collections; |
修改操作
copy(List<? super T> dest, List<? extends T> src)：将src中的内容复制到dest中。replaceAll(List<T> list, T oldVal, T newVal)：使用newVal替换List对象的所有oldVal。
1 | package com.f.chapter14.collections; |