# 概述
对 `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