Collection ： 不提供直接子类继承，只提供继承的子接口（List和Set）
List : 有序的Collection，控制元素的插入位置，和通过索引访问List数据，允许相同的Key。
LinkedList( 也继承自 Deque)
Set ： 不保存重复数据
[TOC]
做好微信机器人，在微信公众平台界面发送8将返回一个二维码，扫码登陆后即可开启机器人。
机器人功能： //TODO
* 集成聊天机器人功能。
* 备份聊天记录。
* 爬取所有用户，并分析用户联系人的男女比例，整合头像。
* 爬取公众号文章。
* 撤回消息备份
* 关键词监听
* 消息搜索
* 信息分析
* 查看/删除文件[文件名] e.g. 查看文件[123345234.mp3]
* 撤回附件列表 (查看都有哪些保存在电脑中的已撤回附件)
* 清空附件列表 (清空已经保存在电脑中的附件)
* 添加关键词[关键词] e.g. 设置关键词[在不在]
* 删除关键词[关键词] e.g. 删除关键词[在不在]
* 清空关键词 清空已经设置的所有关键词
* 查看关键词 查看目前设置的关键词
* 添加签到口令#公众号:签到口令# e.g. 添加签到口令#招商银行信用卡:签到#
* 删除签到口令#公众号# e.g. 删除签到口令#招商银行信用卡#
* 查看签到口令 查看已经存在的公众和和对应的签到口令
* 清空签到口令 清空所有签到口令
* 截图 截取当前屏幕发送到文件助手
* 添加自动回复#针对的关键词:回复内容# e.g.添加自动回复#在不在:我现在有事情，待会儿回复你#
* 删除自动回复#针对的关键词# e.g.删除自动回复#在不在#
* 清空自动回复 清空所有的自定义回复规则
* 关闭自动回复
* 打开自动回复
* 退出程序
* 发送 “开启**回复” 即可回复 ** 信息
后台将配置记录到sql中，并缓存到redis中。
HashMap实现了Map接口，继承自AbstactMap。其中Map接口定义了键映射到值的规则。
public class HashMap
extends AbstractMap
implements Map
注意
* HashMap: 它根据键的hashCode值存储数据，大多数情况下可以直接定位到他的值，因此有很乖的访问速度，但是遍历的顺序是不确定的，HashMap最多只允许一条记录为null，允许多条记录的值为null，HashMap不是线程安全的，即任意时刻有多线程同时写HashMap可能会导致数据不一致问题。
* HashTable: HashTable是遗留类，很多映射的功能和HashMap类似，但是他是继承自Dictionary类，并且是线程安全的，任何时间只有一个线程能写hashTable。
* ConcurrentHashMap：
* LinkedHashMap: 是HashMap的一个自雷，保存了插入顺序，在用iterator遍历LinkedHashMap时，先得到的肯定是新插入的，也可以在构造式带参数，按照访问次数进行排序。
* TreeMap: TreeMap实现了SortMap接口，能够把保存的记录根据键排序，默认是按照键值升序排序，也可以指定排序的比较器，在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出ClassCastExeption。
initialCapacity = MAXIMUM_CAPACITY;
初始容量：代表哈希表中通的数量，
加载因子： 代表哈希表在自动增加之前可以达到的尺度。
列表散列：
数组+链表+红黑树(jdk8中增加红黑树)
HashMap的底层实现还是数组，只不过数组的每一项都是一条链，其中initialCapacity参数代表了该数组额长度。1
2
3
4
5
6
7
8
9
10
11
12 /**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
这一段表示将初始容量变成向下靠近2的幂次方的数。
1 | static class Node<K,V> implements Map.Entry<K,V> { |
Node是HashMap的一个内部类，实现了Map.Entry接口，本质是一个映射（键值对）。
HashMap就是使用哈希表来存储的，哈希表为解决冲突，可以采用开放地址法和链地址法等来解决问题，java中HashMap采用了链地址法，简单来说就是数组加链表的结合。在每个数组元素都是一个链表结构，当数据被hash后，得到数组下标，把数据放在对应下标元素的链表上，例如：
map.put("name","earyant")
系统将”name”这个key的HashCode()方法得到其hashCode值，然后再通过Hash算法的后两步运算（高位运算和取模运算）来定位该键值对应的存储位置，有时候两个key会定位到相同的位置，表示发生了Hash碰撞，当然hash算法计算结果越分散均匀，Hash碰撞的概率就越小，map存取效率就会更高。
如果哈希桶数很大，即使较差的hash算法也会比较分散，如果哈希桶数组很小，就很容易发生碰撞。
在理解Hash和扩容流程之前，我们得先了解下HashMap的几个字段。从HashMap的默认构造函数源码可知，构造函数就是对下面几个字段进行初始化，源码如下：1
2
3
4int threshold; // 所能容纳的key-value对极限
final float loadFactor; // 负载因子
int modCount;
int size;
首先，Node[] table的初始化长度length为默认16，loadFactor为负载因子，默认为0.75.threshold是HashMap所能容纳的最大数据量的Node（键值对）个数。threshold=length*loadFactor，也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。
在HashMap中，哈希桶数组table的长度length大小必须为2的n次方(一定是合数)，这是一种非常规的设计，常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数，具体证明可以参考http://blog.csdn.net/liuqiyao_01/article/details/14475159，Hashtable初始化桶大小为11，就是桶大小设计为素数的应用（Hashtable扩容后不能保证还是素数）。HashMap采用这种非常规设计，主要是为了在取模和扩容时做优化，同时为了减少冲突，HashMap定位哈希桶索引位置时，也加入了高位参与运算的过程。
这里存在一个问题，即使负载因子和Hash算法设计的再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响HashMap的性能。于是，在JDK1.8版本中，对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。本文不再对红黑树展开讨论，想了解更多红黑树数据结构的工作原理可以参考。
http://blog.csdn.net/v_july_v/article/details/6105630。
确定哈希桶数组索引位置。
不管增加、删除、查找键值对，定位到哈希桶数组的位置都是很关键的第一步，
1 | // 方法一： |
但是，模运算的消耗还是比较大的，在HashMap中是这样做的：调用方法二来计算该对象应该保存在table数组的哪个索引处。
这个方法非常巧妙，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。
1 | 1 public V put(K key, V value) { |
1 | 1 void resize(int newCapacity) { //传入新的容量 |
这里就是使用一个容量更大的数组来代替已有的容量小的数组，transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。
1 | 1 void transfer(Entry[] newTable) { |
mark，有很多地方还是需要学习的。
跟随大神学习SpringCloud的时候，在使用docker部署时，遇到了提供者注册不到eureka上去，教程地址在此
之后我搜了下docker进程间通信找到了一个解决办法：
我弄了一整天也是一直注册不进去，后来又搜了搜docker进程间通信，发现一个方法，
eureka-server部署的时候给一个名字： docker run —name eureka-server -p 8761:8761
server-hi中部署使用link参数 docker run —link eureka-server（server部署时赋予的名字）:eureka-server(配置中写的地址) ……
注册不进去的可以试试。
挨个查找，不用多说，时间复杂度为O(n);
说明元素必须是有序的，如果是无序的则要先进行排序操作。
基本思想：也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。
1 | //二分查找（折半查找），版本1 |
1 |
|
基本思想：二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。
二叉查找树（BinarySearch Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree）或者是一棵空树，或者是具有下列性质的二叉树：
1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3）任意节点的左、右子树也分别为二叉查找树。
二叉查找树性质：对二叉查找树进行中序遍历，即可得到有序的数列。
不同形态的二叉查找树如下图所示：
基于二叉查找树进行优化，进而可以得到其他的树表查找算法，如平衡树、红黑树等高效算法。
2-3查找树定义：和二叉树不一样，2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node)，他保存1个key和左右两个自己点。对应3节点(3-node)，保存两个Key，2-3查找树的定义如下：
1）要么为空，要么：
2）对于2节点，该节点保存一个key及对应value，以及两个指向左右节点的节点，左节点也是一个2-3节点，所有的值都比key要小，右节点也是一个2-3节点，所有的值比key要大。
3）对于3节点，该节点保存两个key及对应value，以及三个指向左中右的节点。左节点也是一个2-3节点，所有的值均比两个key中的最小的key还要小；中间节点也是一个2-3节点，中间节点的key值在两个跟节点key值之间；右节点也是一个2-3节点，节点的所有key值比两个key中的最大的key还要大。
2-3查找树的性质：
1）如果中序遍历2-3查找树，就可以得到排好序的序列；
2）在一个完全平衡的2-3查找树中，根节点到每一个为空节点的距离都相同。（这也是平衡树中“平衡”一词的概念，根节点到叶节点的最长距离对应于查找算法的最坏情况，而平衡树中根节点到叶节点的距离都一样，最坏情况也具有对数复杂度。）
2-3树的查找效率与树的高度是息息相关的。
在最坏的情况下，也就是所有的节点都是2-node节点，查找效率为lgN
在最好的情况下，所有的节点都是3-node节点，查找效率为log3N约等于0.631lgN
距离来说，对于1百万个节点的2-3树，树的高度为12-20之间，对于10亿个节点的2-3树，树的高度为18-30之间。
2-3查找树能保证在插入元素之后能保持树的平衡状态，最坏情况下即所有的子节点都是2-node，树的高度为lgn，从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂，于是就有了一种简单实现2-3树的数据结构，即红黑树（Red-Black Tree）。
基本思想：红黑树的思想就是对2-3查找树进行编码，尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型，红色链接，他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的，使用红色链接的两个2-nodes来表示一个3-nodes节点，并且向左倾斜，即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修改，和普通的二叉查找树相同。
