balabala List 和 Map

简单聊下 List 和 Map

前言

本文涉及到以下内容：

1. 简单介绍下数组和链表

   • 数组
   • 链表
   • 哈希表

2. 简单介绍下 ArrayList 和 LinkedList

   • ArrayList
   • LinkedList

3. 简单介绍下 Map

   • HashMap 的一些特点
   • HashMap put() 数据时的步骤
   • HashMap get() 数据时的步骤
   • LinkedHashMap 与 HashMap 的不同
   • ConcurrentHashMap 与 HashMap 的不同

作为开发最为常用的两个数据集合，List 和 Map ，怎么有特征的识别他们呢？

下面，简简单单的聊一下 List 是什么，Map 是什么。

开发常见到的 List 有：

1. ArrayList
2. LinkedList

开发常见到的 Map 有：

1. HashMap
2. LinkedHashMap
3. ConCurrentHashMap

在 Java 中，常见的数据结构有两种：数组和链表， 下面先介绍下这两种数据结构。

1. 简单介绍：数组、链表、哈希表

1.1 数组

首先数组在内存中是一段连续的存储单元，每个数据依次放在每个单元中。

它有已下特性：

1. 数组的大小是固定的，无法动态调整其大小；
2. 数组的 get 获取第 index 操作，nums[index] 时间复杂度为 O(1), 可以根据地址直接找到它；
3. 数组的 set 操作同 get 操作
4. 数组的查询需要遍历，时间复杂度为 O(n)

注：因为数组在内存上的存储是连续的，所以会造成内存碎片化严重。

1.2 链表

链表与数组的连续性不同，它在内存中不是连续的，当前的数据元素里面包含下一个数据元素的内存地址。

有关链表的一些特性：

1. 链表大小不是固定的，可动态调整；
2. 链表的 get(index) 是比较复杂的，只能从第一个元素起，找到第 index 数据；
3. 链表新增比较方便，只需要改变上一个元素的 next 和要插入数据的 next 即可；
4. 链表的查询需要遍历，时间复杂度为 O(n)

1.3 哈希表

上面数组和链表的介绍中，都提到了一点， 查询比较慢。
为了解决这个问题，我们可以使用哈希表

简单来说，哈希表是通过一个关键字来获取真正的值的数据结构。
也就是我们熟悉的 key-value 形式。

Map 就是基于 key-value 的数据结构。

目前我们使用的哈希表，一般都是由 数组 + 链表 设计实现的:

• 数组用来存储数据
• 链表用来解决哈希碰撞

一图表示哈希表:

哈希表

图来自网络

从图中可以得到：

1. 根据 hash(key) 快速定位到在数组中数据的存储位置，如果该位置不只一个数据，则该位置的所有数据根据先后顺序组成一个链表；
2. 一个数据，怎么才能唯一的定位它呢？需要根据 hash(key) 和 key 同时作用下，才能准确定位到它。

一个设计比较好的哈希表，会同时具备数组和链表的优点，且会大大减少查询需要的时间。

下面我们将要提到的各种数据集合，本质上都是利用上述三种数据结构实现的「可能在加上红黑树，这里暂不讨论。」

2. 简单介绍下 ArrayList 和 LinkedList

2.1 ArrayList

ArrayList 是利用数组实现的。
ArrayList 是可动态调整大小的，而数组是大小固定的～
那么必然存在着一个数组扩容的操作。

// 第一种方式， 未指定大小
val list1 = ArrayList<Int>()
// 第二种方式，指定大小
val list2 = ArrayList<Int>(20)

上述代码中 list1 的大小为默认值，list1 在未添加数据时，是空的，当添加数据时，才会使得 ArrayList 的大小变为默认的 10;
第二种方式手动指定了 ArrayList 的大小。

ArrayList 最为重要的是它的扩容机制,
简单总结为下面：

1. 默认会创建一个空数组 Object[] elementData, 它是数据真正存储的地方

2. 当第一次 add数据时，会在 grow() 方法中，对 elementData 扩容
   扩容的方式是通过：elementData = Arrays.copyOf(elementData, newCapacity) 拷贝旧的数据到新的里面，并指定新的大小 newCapacity

3. 每次新增数据时 add 都会调用 ensureCapacityInternal 确保 elementData 数组的容量是可以容纳这一次新增数据

4. 真正的扩容操作在 grow(int minCapacity) 里面， 并且每次扩容的的大小不太一样，具体逻辑在这里：

   // 旧的容量
   int oldCapacity = elementData.length;
   // 新的容量默认是 oldCapacity 的 1.5 倍
       int newCapacity = oldCapacity + (oldCapacity >> 1);
   // 如果 1.5 * oldCapacity < minCapacity ; 1.5 倍后仍然不满足最小容量，
   //则会使用 minCapacity作为新的数组容量
       if (newCapacity - minCapacity < 0)
             newCapacity = minCapacity;
       if (newCapacity - MAX_ARRAY_SIZE > 0)
             newCapacity = hugeCapacity(minCapacity);
       elementData = Arrays.copyOf(elementData, newCapacity);
   

5. 获取到的 ArrayList.size() 并不是存储的数组 elementData.length, size <= elementData.length

ArrayList 是基于数组实现的，对于增 add , 删 remove，都涉及到对数组的拷贝

//add(E e) 时的 ,如果数组大小不满足，则会扩容；
elementData = Arrays.copyOf(elementData, newCapacity);
// remove() 时
System.arraycopy(elementData, index+1, elementData, index, numMoved);
// add(int index, e) ，在中间添加数据时， 一定会涉及到数据的一定，需要移动 index 后面的数据
System.arraycopy(elementData, index, elementData, index + 1, size - index);

所以 ArrayList 在涉及到大量的增删时，性能并不是很好。

ArrayList 的一些特性：

1. 基于数组， 可动态调整大小；
2. 对于数据的 add remove 增删操作涉及到数组的拷贝，比较耗时；
3. 对于数据的 get(index) 较快；
4. ArrayList 是可以重复添加一个数据的, 因此可能会存在一个 List 中存在多个相同对象。

2.2 LinkedList

而 LinkedList解决了 ArrayList 的增删较慢的问题。
为什么呢？
因为 LinkedList 是基于 链表 实现的， 而链表的增删，相对比较简单，不需要拷贝移动数据。

LinkedList 里面的链表是双向链表， 它实现了 Deque 接口，实现队列的功能。

所以， LinkedList 的删除和增加数据，都比较方便，只需要改变链表中元素的 prev 和 next 就行。

一些 LinkedList 的特性：

1. 是个双向链表，里面包含一个头节点 Node<E> first和尾节点 Node<E> last
   表明它可以从头遍历，也可从尾部遍历。
2. LinkedList 对数据的增加 add 和删除 remove，要优于 ArrayList, 因为不涉及到数据的拷贝；
3. LinkedList 对数据的查询 get 操作，要比 ArrayList 慢，因为涉及到链表的遍历
4. LinkedList 拥有队列的功能，可以利用它实现 FIFO 的队列，也可以使用它实现 LRUCache

3. 简单介绍下 HashMap

3.1 HashMap 的一些特点

HashMap 的数据结构为哈希表，在上面，我们说过，一般哈希表是由 数组 + 链表 实现的。

HashMap 应该是我们最为常用的 Map 集合了。
关于它的分析由太多的文章，这里只简单说一下。

想要了解详细的，可参考：https://www.jianshu.com/p/f16bfeeeea88

有关 HashMap 的一些特点：

1. 采用 数组 + 链表 实现，当链表长度大于 8 时，会把链表树化，用于提高查询的效率：
   树化为红黑树， 红黑树的基础是二叉查找树，查询的效率从链表的 O(n) 下降为 O(lgn)

2. HashMap 中的数据是无序的，存入数据的顺序和取出数据的顺序可能会不同；

3. HashMap 中允许空的 key 和 value, 但最多只能有一个 key 为空；

4. HashMap 是线程不安全的， ConcurrentHashMap HashTable 是线程安全的

3.2 HashMap put 数据时的步骤

当往 HashMap 里 put 一个数据时，会经历以下步骤：

1. hashMap.put(key, value) -> putVal(hash(key), key, value, false, true)
   调用 putVal(xxx)；
   其中 hash(key) 为 HashMap hash 后等到的数据。

2. 根据 hash(key) 的值，找到数组中的该位置：table[hash % (length -1 )]

3. 如果该位置的数据为空， 则表明，这个位置尚未放入其他的数据，则直接把 (key, value) 该位置该位置， 然后走步骤 9；否则走步骤 4

4. 如果该位置的数据不为空，表明这个位置已经有了数据， 则进入下一步骤, 该位置的存放数据为 p ；

5. 判断 p 是否和当前要插入的 (key, value) 是否相同， 相同走步骤 9， 不同走步骤 6：

   先判断 p.hash == hash(key) , 再判断 p.key == key, 如果满足，则表明是 同一个 key 对应的存放位置，则覆盖原有的数据，写入新数据；
   代码如下：

   if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))) {
       // 比较 hash 值和 key 是否相同， 如果相同，则表明，就是在次数插入数据，覆盖原有的数据；
       e = p; 
   }
   

6. 如果不相同，表明此时发生了 哈希碰撞，则判断当前节点 p 是否为树节点，如果是，则走步骤 7, 否的话，跳到第 8 步；

7. 将该数据插入到树中， 然后走步骤 9;

8. 表明此时链表尚未树化，此时需要 for 循环遍历链表：

   如果在 for 循环中，遇到某个节点的 if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) 则表明该数据已经插入过 HashMap 中，遇到了和步骤 5 的相同情况，此时需要覆盖旧数据；然后到步骤 9；

   如果没有遇到上述情况，则会遍历完该链表，并在链表的末尾添加该数据：
   p.next = newNode(hash, key, value, null)， 插入后再次判断当前链表的长度是否 > 需要树化的值, 如果是，则去树化 treeifyBin(tab, hash); 如果否，则不做处理, break, 到步骤 9。

9. 经过上述步骤，已经找到插入了数据，距离结束很近了。此时需要判断 size > 需要扩容的某个值, 如果是的话，则 resize() 对 HashMap 进行扩容处理；走步骤 10

10. 结束；

上述简单的概括了在存储数据时的一些逻辑，具体实现可以去看源码的实现。

3.3 HashMap get() 数据时的步骤

上面讨论了往 hashMap 中 put 数据时的步骤，查询时的步骤
当往 HashMap 里 get 一个数据时，会经过以下步骤：

1. get(Object key) 会调用 getNode(int hash, Object key)
2. 查询 table[(table.length - 1) & hash] 是否 != null , 如果 != null 为 true, 则走步骤 3, 否则说明 HashMap 中不存在该 key 对应的值，返回 return null；
3. 先判断当前节点 first 的 key 值是否和要查询的 key 相同，是的话，则找到该值，返回 return first
4. 如果不是，则判断该节点是否为树节点 TreeNode, 如果是，则去 ((TreeNode<K,V>)first).getTreeNode(hash, key), 返回它的返回结果；
5. 如果为链表的节点，则 do 循环去链表中找是否有要找的 key, 有则返回 return e，无返回 return null

上述简单的总结了去 HashMap 里 get 一个数据时的代码运行逻辑。

3.4 简单介绍下 LinkedHashMap 与 HashMap 的不同

LinkedHashMap 是 HashMap 的子类，它具备 HashMap 的一些特性。

它与 HashMap 最大的不同是，它内部维护了一个双向链表， 保证了遍历 LinkedHashMap 数据时的顺序和插入的顺序相同。

我们在上面也提到了，HashMap 是无序的，而 LinkedHashMap 是有序的。

LinkedHashMap 的一些增删查改逻辑都是和 HashMap 相似的，这里不在分析。

3.5 ConcurrentHashMap 与 HashMap 的不同

ConcurrentHashMap 是 Java 并发库里面的，它是线程安全的 。

HashMap 是非线程安全的

HashTable是线程安全的，但目前不推荐使用

如果要实现线程安全的 Map ，就用 ConcurrentHashMap 吧。

ConcurrentHashMap 实现线程安全的方式：使用 synchronized 和 CAS 「CompareAndSwap」 实现并发的操作，并且做了很多锁优化，可以把它看作一个优化过且线程安全的 HashMap 。

4 总结

简单的总结了一下常用的 List 和 Map 的一些特性。

有很多内容点没有详细展开，网络上已经有很多资料，
这篇文章更像是一个简单的自我总结。

如有错误，还请指出～

2020.6.13 by chendroid

参考链接：

1. https://www.jianshu.com/p/407afb4a267a 系列，写得很好，很仔细。