# 概述
对 `JAVA` 的集合框架中的 `Map` 下的一些子类相关的原理以及应用进行复盘。
# 目录
[TOC]
# 主要内容
## 0x01：概述
Map: 双列数据，存储 `key-value` 对的数据
- HashMap：作为 `Map` 的主要实现类；线程不安全的，效率高；存储 ` null` 的 `key` 和 `value`
- `LinkedHashMap`：
保证在遍历map元素时，可以按照添加的顺序实现遍历。
原因：在原有的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。
对于频繁的遍历操作，此类执行效率高于HashMap。
- TreeMap：保证按照添加的 `key-value` 对进行排序，实现排序遍历。此时考虑 `key` 的自然排序或定制排序
- Hashtable：作为古老的实现类；线程安全的，效率低；不能存储 `null` 的 `key` 和 `value`
- Properties：常用来处理配置文件。`key` 和 `value` 都是 `String` 类型
HashMap 的底层结构：
- `jdk7` 及之前：数组+链表
- `jdk8`：数组+链表+红黑树
Map的基础树如下图
## 0x02：对Map中的结构理解
- Map中的 `key` 是无序的，不可重复的，使用 `Set` 储存所有的key
- 在实际开发中，key的值可能是我们自定义的一个类型，所以要求 key 所在的类需要重写 `equals()` 和 `hashCode()` 方法
> 以HashMap为例
- Map中的 `value` 是无序的，可重复的，使用Collection储存所有的value
- value所在类需要重写 `equals()`
- Map中的 `entry`：无序的、不可重复的，使用Set储存所有的 `entry` 对象
> 一个键值对：key-value构成了一个Entry对象
如下图所示
## 0x03：浅谈HashMap底层原理
我们先以 `jdk7` 为例
```java
HashMap map = new HashMap()
```
在实例化以后，底层创建了长度为 `16` 的以为数组 `Entry[] table` 如下代码
```java
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
```
向 map 存入数据
```java
map.put("key1","value1")
```
存入数据的过程如下：
1、在向map存入数据时，首先会调用 `key1` 所在类的 `hashCode()` 计算key1哈希值，此哈希值经过某种算法计算以后，得到在 `Entry` 数组中的存放位置，如下
```java
public V put(K key, V value) {
//省略....
int hash = hash(key);
//通过hash计算得到一个数组的索引坐标
int i = indexFor(hash, table.length);
//省略...
}
```
> 上述代码摘自 JDK7 中的 HashMap源码
2、如果此位置上的数据为空，此时的 `key1-value1` 添加成功。（情况1）
3、如果此位置上的数据不为空 (意味着此位置上存在一个或多个数据 (以链表形式存在) , 则开始比较 `key1` 和已经存在的一个或多个数据的哈希值
- 如果 `key1` 的哈希值与已经存在的数据的哈希值都不相同，此时 `key1-value1` 添加成功 （情况2）
- 如果key1的哈希值和已经存在的某一个数据 (key2-value2) 的哈希值相同，继续比较：调用 `key1` 所在类的`equals(key2)` 方法，比较：
- 如果 `equals()` 返回 `false`: 此时 `key1-value1` 添加成功。（情况3）
- 如果 `equals()` 返回 `true`: 使用 `value1` 替换 `value2`。
源码如下
```java
//摘自JDK7中的HashMap源码中的部分代码实现
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key);
//通过hash计算得到一个数组的索引坐标
int i = indexFor(hash, table.length);
//如果计算得出的位置不为空，呈现为链表的结构，开始遍历
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//情况2、3
if (e.hash == hash && ((k = e.key) == key || key.equals(k))){
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//如果此位置上的数据为空，直接添加 （情况1）
addEntry(hash, key, value, i);
return null;
}
```
补充：关于 “情况2” 和 “情况3”：此时 `key1-value1 ` 和原来的数据以链表（单向）的方式存储。
```java
/**
* Like addEntry except that this version is used when creating entries
* as part of Map construction or "pseudo-construction" (cloning,
* deserialization). This version needn't worry about resizing the table.
*
* Subclass overrides this to alter the behavior of HashMap(Map),
* clone, and readObject.
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
//将当前的数据作的内存地址储存到自身的next中，实现单向链表的方式储存
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
```
在不断的添加过程中，会涉及到扩容问题，当超出临界值 (且要存放的位置非空) 时，扩容。
- 默认的扩容方式：扩容为原来容量的 `2` 倍，并将原有的数据复制过来。部分源码如下
```java
/**
* Adds a new entry with the specified key, value and hash code to
* the specified bucket. It is the responsibility of this
* method to resize the table if appropriate.
*
* Subclass overrides this to alter the behavior of put method.
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
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);
}
```
**而 “jdk8” 相较于 “jdk7” 在底层实现方面的不同，以下列出常见的**
- new HashMap(): 底层没有马上创建一个长度为 `16` 的数组，而是在首次调用 `put()` 方法时，底层创建长度为16的数组
`HashMap` 空参的构造方法，相较于 `JDK7` 中的实现
```java
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
```
而 JDK8 中，在调用 put 时，会先调用 putVa() 方法，再由 putVal 内部进行一些逻辑判断，发现当前为首次调用，则再进行调用 resize() 对数组进行初始化，长度为 `16`。
- `jdk8` 底层的数组是：Node[]，而非Entry[]
- `jdk7 `底层结构只有：数组+链表。而 `jdk8` 中底层结构：数组+链表+红黑树。
- 形成链表时，”七上八下“（ jdk7: 新的元素指向旧的元素。jdk8：旧的元素指向新的元素）
- 当数组的某一个索引位置上的元素以链表形式存在的数据个数 `> 8` 且当前数组的长度 `> 64` 时，此时此索引位置上的所数据改为使用 "红黑树" 存储。
### HashMap源码中的重要常量
- `DEFAULT_INITIAL_CAPACITY` : HashMap的默认容量，16
- `DEFAULT_LOAD_FACTOR`：HashMap的默认加载因子：0.75
- 为什么是 0.75 ？
提前扩容的原因：在数组中预留一些空的索引位置，可以使链表和树形结构出现的数量更少，并且还要兼顾数组索引位置的利用率，所以 “加载因子” 定为 `0.75` 可以使得到一个恰好的扩容临界值，同时兼顾上述的两者。
- `threshold`：扩容的临界值， `容量 * 填充因子` ：`16 * 0.75 => 12`
- `TREEIFY_THRESHOLD`：Bucket 中链表长度大于该默认值，转化为红黑树: `8`
- `MIN_TREEIFY_CAPACITY`：桶中的 `Node` 被树化时最小的 `hash` 表容量: `64`
### 拓展
看到这里，我们在回到 `HashSet` 的源码实现中去看，向 `HashSet` 存入数时将写入的值存到了 HashMap 中的 key 的位置
而 `Value` 的位置则使用一个常量进行填充，常量的值为一个空的 `Object` 对象常量，并且是静态的（只会被创建一次，所有的value都指向同一个），如下代码
所以由此可知，HashSet 实际的底层是使用 HashMap 来进行储存实际上底层是使用 `HashMap` 去储存的。
## 0x04：浅谈LinkedHashMap的底层原理
LinkedHashMap 是 `HashMap` 的子类
在 `HashMap` 存储结构的基础上，使用了一对双向链表来记录添加元素的顺序，并重写了 `HashMap` 中的 `newNode` 方法，如下代码
```java
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
```
在 LinkedHashMap 新增了一个类 `Entry` ，并继承了 `HashMap.Node` ，增加了双向链表的特性，如下代码
```java
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
```
与 `LinkedHashSet` 类似， LinkedHashMap 可以维护 Map 的迭代顺序：迭代顺序 与 `Key-Value` 对的插入顺序一致
## 0x05：Map接口常用的方法
添加、删除、修改操作：
- `Object put(Object key,Object value)`：
将指定key-value添加到(或修改)当前map对象中
- `void putAll(Map m)` :
将m中的所有key-value对存放到当前map中
- `Object remove(Object key)`：
移除指定key的key-value对，并返回value
- `void clear()`：
清空当前map中的所有数据
测试代码
```java
@Test
public void test3(){
Map map = new HashMap();
//添加
map.put("AA",123);
map.put(45,123);
map.put("BB",56);
//修改
map.put("AA",87);
System.out.println(map);
Map map1 = new HashMap();
map1.put("CC",123);
map1.put("DD",123);
map.putAll(map1);
System.out.println(map);
//remove(Object key)
Object value = map.remove("CC");
System.out.println(value);
System.out.println(map);
//clear()
map.clear();//与map = null操作不同
System.out.println(map.size());
System.out.println(map);
}
```
输出结果
```java
{AA=87, BB=56, 45=123}
{AA=87, BB=56, CC=123, DD=123, 45=123}
123
{AA=87, BB=56, DD=123, 45=123}
0
{}
Process finished with exit code 0
```
元素查询的操作：
- `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是否相等
测试代码
```java
@Test
public void test4(){
Map map = new HashMap();
map.put("AA",123);
map.put(45,123);
map.put("BB",56);
// Object get(Object key)
System.out.println(map.get(45));
//containsKey(Object key)
boolean isExist = map.containsKey("BB");
System.out.println(isExist);
isExist = map.containsValue(123);
System.out.println(isExist);
map.clear();
System.out.println(map.isEmpty());
}
```
输出结果
```java
123
true
true
true
Process finished with exit code 0
```
元视图操作的方法：
- `Set keySet()`：
返回所有key构成的Set集合
- `Collection values()`：
返回所有value构成的Collection集合
- `Set entrySet()`：
返回所有key-value对构成的Set集合
```java
@Test
public void test5(){
Map map = new HashMap();
map.put("AA",123);
map.put(45,1234);
map.put("BB",56);
//遍历所有的key集：keySet()
Set set = map.keySet();
Iterator iterator = set.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
System.out.println();
//遍历所有的value集：values()
Collection values = map.values();
for(Object obj : values){
System.out.println(obj);
}
System.out.println();
//遍历所有的key-value
//方式一：entrySet()
Set entrySet = map.entrySet();
Iterator iterator1 = entrySet.iterator();
while (iterator1.hasNext()){
Object obj = iterator1.next();
//entrySet集合中的元素都是entry
Map.Entry entry = (Map.Entry) obj;
System.out.println(entry.getKey() + "---->" + entry.getValue());
}
System.out.println();
//方式二：
Set keySet = map.keySet();
Iterator iterator2 = keySet.iterator();
while(iterator2.hasNext()){
Object key = iterator2.next();
Object value = map.get(key);
System.out.println(key + "=====" + value);
}
}
```
输出结果
```java
AA
BB
45
123
56
1234
AA---->123
BB---->56
45---->1234
AA=====123
BB=====56
45=====1234
Process finished with exit code 0
```
## 0x06：TreeMap
`TreeMap` 存储 `Key-Value` 对时， 需要根据 `key-value` 对进行排序。TreeMap 可以保证所有的 `Key-Value` 对处于有序状态。
并且 `TreeMap` 底层使用红黑树结构存储数据
TreeMap 的 Key 的排序：
- 自然排序： `TreeMap` 的所有的 Key 必须实现 `Comparable` 接口，而且所有的 Key 应该是同一个类的对象，否则将会抛出`ClasssCastException`
- 定制排序：创建 `TreeMap` 时，传入一个 `Comparator` 对象，该对象负责对`TreeMap` 中的所有 key 进行排序。此时不需要 Map 的 Key 实现`Comparable` 接口
TreeMap自然排序
```java
//自然排序
@Test
public void test1(){
TreeMap map = new TreeMap();
User u1 = new User("Tom",23);
User u2 = new User("Jerry",32);
User u3 = new User("Jack",20);
User u4 = new User("Rose",18);
map.put(u1,98);
map.put(u2,89);
map.put(u3,76);
map.put(u4,100);
Set entrySet = map.entrySet();
Iterator iterator1 = entrySet.iterator();
while (iterator1.hasNext()){
Object obj = iterator1.next();
Map.Entry entry = (Map.Entry) obj;
System.out.println(entry.getKey() + "---->" + entry.getValue());
}
}
```
输出结果
```
User{name='Tom', age=23}---->98
User{name='Rose', age=18}---->100
User{name='Jerry', age=32}---->89
User{name='Jack', age=20}---->76
Process finished with exit code 0
```
TreeMap定制排序
```java
//定制排序
@Test
public void test2(){
TreeMap map = new TreeMap(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
if(o1 instanceof User && o2 instanceof User){
User u1 = (User)o1;
User u2 = (User)o2;
return Integer.compare(u1.getAge(),u2.getAge());
}
throw new RuntimeException("输入的类型不匹配！");
}
});
User u1 = new User("Tom",23);
User u2 = new User("Jerry",32);
User u3 = new User("Jack",20);
User u4 = new User("Rose",18);
map.put(u1,98);
map.put(u2,89);
map.put(u3,76);
map.put(u4,100);
Set entrySet = map.entrySet();
Iterator iterator1 = entrySet.iterator();
while (iterator1.hasNext()){
Object obj = iterator1.next();
Map.Entry entry = (Map.Entry) obj;
System.out.println(entry.getKey() + "---->" + entry.getValue());
}
}
```
输出结果
```java
User{name='Rose', age=18}---->100
User{name='Jack', age=20}---->76
User{name='Tom', age=23}---->98
User{name='Jerry', age=32}---->89
Process finished with exit code 0
```
`TreeMap` 判断两个key相等的标准：两个 `key` 通过compareTo()方法或者compare()方法返回0。
## 0x07：Hashtable
`Hashtable` 是个古老的 Map 实现类， `JDK1.0` 就提供了。不同于HashMap，`Hashtable` 是线程安全的。
`Hashtable` 实现原理和 `HashMap` 相同，功能相同。底层都使用哈希表结构，查询速度快，很多情况下可以互用。
- 与 `HashMap` 不同， Hashtable 不允许使用 `null` 作为 `key` 和 `value`
- 与 `HashMap` 一样， `Hashtable` 也不能保证其中 Key-Value 对的顺序
Hashtable 判断两个 `key` 相等、两个 `value` 相等的标准， 与HashMap一致。
由于目前实际开发中 `Hashtable` 用得较少，所以这里就不进行详细的探究。
## 0x08：Properties处理配置文件
Properties 类是 `Hashtable` 的子类，该对象用于处理属性文件
由于属性文件里的 `key`、 `value` 都是字符串类型，所以 `Properties` 里的 `key`和 `value` 都是字符串类型
存取数据时，建议使用 `setProperty(String key,String value)`方法和 `getProperty(String key)` 方法，如下举例
新建一个 `jdbc.properties` 文件，写入下面的内容
```
username=lcyee
password=abc123
```
编写测试代码
```java
//Properties:常用来处理配置文件。key和value都是String类型
public static void main(String[] args) {
FileInputStream fis = null;
try {
Properties pros = new Properties();
fis = new FileInputStream("jdbc.properties");
pros.load(fis);//加载流对应的文件
String name = pros.getProperty("username");
String password = pros.getProperty("password");
System.out.println("username = " + name + ", password = " + password);
} catch (IOException e) {
e.printStackTrace();
} finally {
if(fis != null){
try {
fis.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
}
```
输出结果
```java
username = lcyee, password = abc123
Process finished with exit code 0
```
## 0x09：Collections工具类
- `reverse(List)`：
反转 List 中元素的顺序
- `shuffle(List)`：
对 List 集合元素进行随机排序
- `sort(List)`：
根据元素的自然顺序对指定 List 集合元素按升序排序
- `sort(List，Comparator)`：
根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
- `swap(List，int， int)`：
将指定 list 集合中的 i 处元素和 j 处元素进行交换
- `Object max(Collection)`：
- 根据元素的自然顺序，返回给定集合中的最大元素
- `Object max(Collection，Comparator)`：
根据 Comparator 指定的顺序，返回给定集合中的最大元素
- `Object min(Collection)`
- `Object min(Collection，Comparator)`
- `int frequency(Collection，Object)`：
返回指定集合中指定元素的出现次数
- `void copy(List dest,List src)`：
将src中的内容复制到dest中
- `boolean replaceAll(List list，Object oldVal，Object newVal)`：
使用新值替换 List 对象的所有旧值
这里我们重点举例 `copy` 方法
```java
@Test
public void test2(){
List list = new ArrayList();
list.add(123);
list.add(43);
list.add(765);
list.add(-97);
list.add(0);
//报异常：IndexOutOfBoundsException("Source does not fit in dest")
// List dest = new ArrayList();
// Collections.copy(dest,list);
//正确的：
List dest = Arrays.asList(new Object[list.size()]);
System.out.println(dest.size());//list.size();
Collections.copy(dest,list);
System.out.println(dest);
}
```
从上述代码可以看出，如果我们需要使用 `Collections.copy()` 方法对 `List` 进行从 A 向 B 的复制操作，需要 A 和 B 都持有对等的大小， 通过 `Arrays.asList(new Object[list.size()]);` 的方式，向 `B` 中创建于 `A` 对等数量的空对象，然后再进行复制操作。
### 同步控制
Collections 类中提供了多个 `synchronizedXxx()` 方法，该方法可使将指定集合包装成线程同步的集合，从而可以解决多线程并发访问集合时的线程安全问题。
```java
//返回的list1即为线程安全的List
List list1 = Collections.synchronizedList(list);
```
我们从 `Collections` 的源码中可以看到大量的使用了 `synchronized` 关键字
## 0xFF：拓展
**CurrentHashMap 与 Hashtable 的异同**
为了在高并发的常见下操作Map获得更高的执行效率，所以引入了 `CurrentHashMap` ，其实现了分段锁的技术。
# 总结
- 巩固了 `HashMap` 的部分实现原理以及其扩容方案的实现。
- 并且了解了 `HashMap` 与其他的实现类例如 `TreeMap`、`Hashtable`的一些区别。
【JAVA高级&集合框架】浅谈Map
