简介

LinkedHashMap内部维护了一个双向链表，能保证元素按插入的顺序访问，也能以访问顺序访问，可以用来实现LRU缓存策略。

LinkedHashMap可以看成是 LinkedList + HashMap。

实战另见 LinkedHashMap

二叉树的遍历

我们知道二叉查找树的遍历有前序遍历、中序遍历、后序遍历。

1. 前序遍历，先遍历我，再遍历我的左子节点，最后遍历我的右子节点；
2. 中序遍历，先遍历我的左子节点，再遍历我，最后遍历我的右子节点；
3. 后序遍历，先遍历我的左子节点，再遍历我的右子节点，最后遍历我；

这里的前中后都是以“我”的顺序为准的，我在前就是前序遍历，我在中就是中序遍历，我在后就是后序遍历。

删除元素

删除元素本身比较简单，就是采用二叉树的删除规则。

1. 如果删除的位置有两个叶子节点，则从其右子树中取最小的元素放到删除的位置，然后把删除位置移到替代元素的位置，进入下一步。
2. 如果删除的位置只有一个叶子节点（有可能是经过第一步转换后的删除位置），则把那个叶子节点作为替代元素，放到删除的位置，然后把这个叶子节点删除。
3. 如果删除的位置没有叶子节点，则直接把这个删除位置的元素删除即可。
4. 针对红黑树，如果删除位置是黑色节点，还需要做再平衡。
5. 如果有替代元素，则以替代元素作为当前节点进入再平衡。
6. 如果没有替代元素，则以删除的位置的元素作为当前节点进入再平衡，平衡之后再删除这个节点。

插入元素

插入元素，如果元素在树中存在，则替换value；如果元素不存在，则插入到对应的位置，再平衡树。

简介

TreeMap使用红黑树存储元素，可以保证元素按key值的大小进行遍历。

实战另见 TreeMap

背景

目前OneAlert提供短信、邮件、电话、APP四种通知通道，其中前三种的使用量最高(90%以上的用户)，因此靠谱的第三方推送提供商至关重要。经过对各种三方推送服务的公司调研，目前锁定了阿里大鱼^[1]、容联云^[2]、云片^[3]、云之讯^[4]、SendCloud^[5]，这5家平台提供商。

简介

HashMap采用key/value存储结构，每个key对应唯一的value，查询和修改的速度都很快，能达到O(1)的平均时间复杂度。它是非线程安全的，且不保证元素存储的顺序；

简介

ArrayList是一种以数组实现的List，与数组相比，它具有动态扩展的能力，因此也可称之为动态数组。