各种集合类的总结：
GO
ArrayList
addAll一次性会增加多个）+原数组长度”的较大值。new ArrayList()，数组默认长度为10，但是创建ArrayList时不会立即创建数组，而是在第一次添加元素时创建，只有在第一次添加小于等于10个元素时，第一次初始化的数组长度才为10。new ArrayList(n)可以指定初始大小，创建时会立即分配。所以在可预知数组大小或大概大小时，可以指定此值，避免空间浪费和频繁扩充数组。ListIterator listIterator()相比传统Iterator iterator()多了添加，删除的方法，可以在遍历中途进行增删。在遍历过程中不能进行增删（调用ListIterator的API除外），否则此Iterator对象再执行next()时，会抛出ConcurrentModificationException，for (X i : list) 用于集合时其实也是调用的Iterator。subList()返回一个SubList对象，该对象的各种增删查方法都会被代理到原List中去，会相互影响，注意。当然有时用SubList时会有好处，相当于返回一个视图，操作视图会比对着原对象操作有时会直观一些。LinkedList
CopyOnWriteArrayList
ReentrantLock给包裹iterator()效率非常高，因为next()方法都不会做各种确认列表未做修改的检查。Iterator不感知，还是遍历修改之前的数组，不会抛出ConcurrentModificationException，因为适用于大量读很少写的情况Vector
ArrayList几乎相同，只不过是把几乎所有方法都加上synchronized，类似Collections.synchronizedList()Stack
Vector的子类，仅仅加了几个栈的方法例如push()、pop()、peek()HashMap
null键和null值（因为支持null值的特性，需要注意containsKey(K)和get(K) != null可能结果会不一样
结构是：散列桶数组Node[] table，数组引用的可能情况：
null，没有数据落入此桶Node，单向链表，应用于当此桶的数据比较少时TreeNode，红黑树（后面简称RBT）的根节点，应用于当此桶的数据比较多时（get时能够比较快的搜索到，比如，此桶有1024个元素，如果是链表结构，最坏的情况是目标元素在链表尾部，需要寻找差不多1024次，而用RBT则最多差不多只需要找lg 1024 = 10次）hash值，不是简单的hashCode()，而是通过原hashCode()的高位经过处理扩展到低位，使hash值的低位变得更加杂乱和随机。毕竟桶的数量一般不是太多，所以hash值的低位才决定了入哪个桶。
插入逻辑：首先根据对象的hash值对桶个数取模（由于HashMap中桶的数量保持在2的指数，可以可以用取模达到求余的效果，而Hashtable的桶数量默认是11，所以只能用%求余），然后根据该桶的情况将数据放进去
null：包裹成Node直接赋值，作为链表头。树化：如果散列桶大小小于64，则进行散列桶扩充，但是此桶不会改成红黑树，因为很有可能在散列桶扩充后，此桶的一些元素会挪到其他桶去。如果散列桶大小已经达到64，则将所有元素重新组织成RBT。
扩充：将散列桶长度翻倍，然后重新组织（假如原来有16个桶，则hash值为17和33的元素都在第二个桶，扩充到32个桶后。hash为17的就直接挪到第18个桶了）。触发扩充的条件：当总元素个数达到原桶个数乘以增长因子时（默认初始桶大小是16个，增长因子是0.75，所以到达第12个时就进行扩充）；树化时也可能会进行扩充（例如初始桶个数16个小于64，插入了落到同一个桶8个数据，会触发树化扩充，所以并不一定非得达到增长因子时才会扩充）。
扩充逻辑效率很低（新建比较大桶数组，然后需要将每个桶的数据拆分出去，例如上例中第一个桶需要分出去一部分到第17个，如果原RBT将数据分出去后数量小于6时会退化到链表，新桶分到的元素个数达到8时又会变成RBT），所以在构建HashMap时能大概清楚会有多少数据，会不会冲突很多，根据HashMap的行为，选定一个初始散列桶大小。
删除元素：删除链表或RBT的一个节点。在RBT节点数减到6时，会将RBT又退化到链表。
Map的键值是可变对象会是什么情况？在将某个键值对放入Map后，这个对象变了，导致新的hash值变化了，但是HashMap识别不了这种情况，不会重新安插。所以不要将可变对象作为K，或者保证插入后不变。
在桶里面的RBT根据什么去决定Key的顺序？从先到后，如果前者一致的话，试图往下继续比较：
hash值大小Comparable，如果Key实现了此接口的话，如果未实现或比较结果为0，则getClass().getName()，字符串比较，不过大部分情况下插入的Key的所有Class都一样，少数可能会有子类存在System.identityHashCode()，这个每个对象都不一致不会再重复 而对于
TreeMap的话，也是用的RBT，但是TreeMap要求Key实现Comparable接口，如果没有实现，则需要传一个Comparator，所以比较逻辑不会像这么蛋疼。首先根据hash值大小，如果两个hash一致时，如果K类实现了Comparable接口，会根据比较的值做比较，如果还是一样的话，则比较getClass().getName()，还一样的话，则根据System.identityHashCode()做比较，反正得找到东西让这两个对象不一样。而TreeMap的话就强制要求实现Comparable或者传进去一个Comparator。
Map.Key 和Set这些根据hashCode或equals或compareTo方法等各种手段来决定位置，此对象在插入后如果改变的话导致这些方法的返回值变化，导致逻辑上这些元素的位置“不再正确”，很可能出现各种问题，所以尽量使用Integer、String这些不可变对象，即使用了可变对象，在插入后不应该再动这些数据。
LinkedHashMap
HashMap的子类，很多特性一致，同样线程不安全，支持null键和null值iterator、keySet、entrySet这些）时，能按照插入的先后顺序遍历HashMap完全一致但是做了扩充，其在散列桶数组之外又单独维护了一个链表，在使用HashMap的完成散列桶的操作后，再往自己独立的链表尾部插入此节点。遍历时即遍历此链表。Hashtable
Vector那样，简单暴力的将几乎所有方法都加上synchronizednull键，也不允许null值。HashMap基本一致，但是每个桶里面只会是链表，不会出现红黑树，在单个桶里面比较多的时候，查找会比较慢TreeMap
null键，但支持null值，内部使用RBT保持节点有序，是有序的Map，遍历时会根据顺序进行。NavigableMap和SortedMap接口，里面有一些API是跟次序相关的，有些场景就不需要进行遍历，直接用这些API更简单一些。new TreeMap(Comparator)执行Comparator时，Key的类必须要实现Comparator接口；如果没有实现的话，必须要传一个Comparator做RBT节点的比较。如果Key实现了Comparable，并且指定了Comparator，RBT会根据Comparator.compare做比较，忽略Comparable.compareToComparator或Comparable的比较结果而不是根据equals()方法，所以可能会出现equals不一样但compare或compareTo方法返回0的情况，这时，会被理解成一样的Key，如果此时做更新的话，Key不会更新，只有Value更新。ConcurrentHashMap
public static int hammingDistance(int x, int y) {
int res = 0, exc = x ^ y;
System.out.println(x + " in Binary: " + Integer.toBinaryString(x));
System.out.println(y + " in Binary: " + Integer.toBinaryString(y));
System.out.println("The result of " + x + "^" + y + " is :" + Integer.toBinaryString(exc));
boolean flag = (exc == 0) ? false : true;
while (flag) {
++res;
exc &= (exc - 1);
if (exc == 0) {
flag = false;
}
}
return res;
}