List是一个接口，List的两个重要接口，ArrayList和linkedList都是实现了List接口的类：
ArrayList的继承实现关系图：
linkedList的继承实现关系图：
Map
Map集合概述和特点
概述：
Map集合是将键映射到值的对象，一个映射不能包含重复的键，每个键最多只能映射到一个值
Map接口和Collection接口的不同：
| Map | Collection | |
| 存储结构 | 双列 | 单列 |
| 键 | 唯一 | 子体系Set是唯一的 |
| 数据结构 | 对键有效，跟值无关 | 针对元素有效 |
Map集合的常用功能：
| 功能 | 语句 | 描述 |
| 添加 | V put(K key,V value) | 添加元素,这个其实还有另一个功能?替换 如果键是第一次存储，就直接存储元素，返回null 如果键不是第一次存在，就用值把以前的值替换掉，返回以前的值 |
| 删除 | void clear() | 移除所有的键值对元素 |
| V remove(Object key) | 根据键删除键值对元素，并把值返回 | |
| c:判断功能 | boolean containsKey(Object key) | 判断集合是否包含指定的键 |
| boolean containsValue(Object value) | 判断集合是否包含指定的值 | |
| boolean isEmpty() | 判断集合是否为空 | |
| 获取 | Set | 返回一个键值对的Set集合 |
| V get(Object key) | 根据键获取值 | |
| Set keySet() | 获取集合中所有键的集合 | |
| Collection values() | 获取集合中所有值的集合 | |
| e:长度功能 | int size() | 返回集合中的键值对的对数 |
通常来说，Map是一个由键值对组成的数据结构，且在集合中每个键是唯一的。下面就以K和V来代表键和值，来说明一下java中关于Map的九大问题。
1、将Map转换为List类型
在java中Map接口提供了三种集合获取方式：Key set，value set，key-value set.。它们都可以通过构造方法或者addAll()方法来转换为List类型。代码如下：
ArrayList： // key list List keyList = new ArrayList(map.keySet()); // value list List valueList = new ArrayList(map.valueSet()); // key-value list List entryList = new ArrayList(map.entrySet());
1、通过Entry 遍历Map
java中这种以键值对存在的方式被称为Map.Entry。Map.entrySet()返回的是一个key-value 集合，这是一种非常高效的遍历方式。
for(Entry entry: map.entrySet()) {
// get key
K key = entry.getKey();
// get value
V value = entry.getValue();
}
Iterator 我们也经常用到，尤其是在JDK1.5以前
Iterator itr = map.entrySet().iterator();
while(itr.hasNext()) {
Entry entry = itr.next();
// get key
K key = entry.getKey();
// get value
V value = entry.getValue();
}
2、按key来对Map排序
排序需要对Map的key进行频繁的操作，一种方式就是通过比较器(comparator )来实现：
List list = new ArrayList(map.entrySet());
Collections.sort(list, new Comparator() {
@Override
public int compare(Entry e1, Entry e2) {
return e1.getKey().compareTo(e2.getKey());
}
});
另外一种方法就是通过SortedMap，但必须要实现Comparable接口。
SortedMap sortedMap = new TreeMap(new Comparator() {
@Override
public int compare(K k1, K k2) {
return k1.compareTo(k2);
}
});
sortedMap.putAll(map);
3、按value对Map进行排序
这与上一点有些类似，代码如下：
List list = new ArrayList(map.entrySet());
Collections.sort(list, new Comparator() {
@Override
public int compare(Entry e1, Entry e2) {
return e1.getValue().compareTo(e2.getValue());
}
});
4、初始化一个static 的常量Map
创建一个全局静态Map有以下两种方式，而且都是线程安全的。
下面代码，声明了map是静态的，但是在初始化时，我们依然可以改变它的值，比如Test1.map.put(3,"three");
public class Test1 {
private static final Map map;
static {
map = new HashMap();
map.put(1, "one");
map.put(2, "two");
}
}
在Test2中，我们通过一个内部类，将其设置为不可修改，那么当我们运行Test2.map.put(3,"three")的时候，它就会抛出一个UnsupportedOperationException 异常来禁止你修改。
public class Test2 {
private static final Map map;
static {
Map aMap = new HashMap();
aMap.put(1, "one");
aMap.put(2, "two");
map = Collections.unmodifiableMap(aMap);
}
}
6、Map中的反向查询
我们在Map添加一个键值对后，意味着这在Map中键和值是一一对应的，一个键就是对应一个值。但是有时候我们需要反向查询，比如通过某一个值来查找它的键，这种数据结构被称为bidirectional map，遗憾的是JDK并没有对其支持。
Apache和Guava 共同提供了这种bidirectional map实现，它在实现中它规定了键和值都是必须是1:1的关系。
7、对Map的复制
java中提供了很多方法都可以实现对一个Map的复制，但是那些方法不见得会时时同步。简单说，就是一个Map发生的变化，而复制的那个依然保持原样。下面是一个比较高效的实现方法：
Map copiedMap = Collections.synchronizedMap(map);
当然还有另外一个方法，那就是克隆。但是我们的java鼻祖Josh Bloch却不推荐这种方式，他曾经在一次访谈中说过关于Map克隆的问题：在很多类中都提供了克隆的方法，因为人们确实需要。但是克隆非常有局限性，而且在很多时候造成了不必要的影响。
8、创建一个空的Map
如果这个map被置为不可用，可以通过以下实现
map = Collections.emptyMap();
相反，我们会用到的时候，就可以直接。
Map接口几个重要的实现类：hashMap、TreeMap、Hashtable、linkedHashMap
1、什么是 HashMap，什么时候选择 HashMap？说到容器我们会想到 Java中对象存储容器还有ArrayList，linkedList，HashSet等，HashMap 相对这些容器来说，可以理解为多了一层指向关系，可以用指定Key找到指定Value。
比如现在有一个Java Bean 用于存储职员的信息，字段包括（职员姓名，职员年龄，职员身高，职员体重，职员教育程度 ... 等等），我是一名人力资源管理，我需要将员工信息整理好发给老板。这个时候出现了两个人名字一样的问题，查到的到底是谁的信息呢？前者信息会被覆盖吗？带着问题来学习一下HashMap数据结构及其工作原理。
2、HashMap 数据结构及其工作原理？2.1 数据结构
HashMap 数据结构为 数组+链表，其中：链表的节点存储的是一个 Entry 对象，每个Entry 对象存储四个属性（hash，key，value，next）
整体是一个数组；
数组每个位置是一个链表；
链表每个节点中的Value即我们存储的Object；
2.2 工作原理
首先，初始化 HashMap，提供了有参构造和无参构造，无参构造中，容器默认的数组大小 initialCapacity 为 16，加载因子loadFactor 为0.75。容器的阈(yu)值为 initialCapacity * loadFactor，默认情况下阈值为 16 * 0.75 = 12; 后面会讲到阈值有啥用。
然后，这里我们拿 PUT 方法来做研究：
第一步：通过 HashMap 自己提供的hash 算法算出当前 key 的hash 值
第二步：通过计算出的hash 值去调用 indexFor 方法计算当前对象应该存储在数组的几号位置
第三步：判断size 是否已经达到了当前阈值，如果没有，继续；如果已经达到阈值，则先进行数组扩容，将数组长度扩容为原来的2倍。
注意size 是当前容器中已有 Entry 的数量，不是数组长度。
第四步：将当前对应的 hash，key，value封装成一个 Entry，去数组中查找当前位置有没有元素，如果没有，放在这个位置上；如果此位置上已经存在链表，那么遍历链表，如果链表上某个节点的 key 与当前key 进行 equals 比较后结果为 true，则把原来节点上的value 返回，将当前新的 value替换掉原来的value，如果遍历完链表，没有找到key 与当前 key equals为 true的，就把刚才封装的新的 Entry中next 指向当前链表的始节点，也就是说当前节点现在在链表的第一个位置，简单来说即，先来的往后退。此时已经将当前的 key-value 存储到了容器中。PUT 是操作HashMap的最基础操作，了解了 PUT 的机制后，再去看 API其他方法源码的时候你会有所眉目，可以带着这种初知去探究 HashMap 的其他方法。
扩容机制：
HashMap 使用 “懒扩容” ，只会在 PUT 的时候才进行判断，然后进行扩容。
将数组长度扩容为原来的2 倍
将原来数组中的元素进行重新放到新数组中
需要注意的是，每次扩容之后，都要重新计算原来的 Entry 在新数组中的位置，为什么数组扩容了，Entry 在数组中的位置发生变化了呢？所以我们会想到计算位置的 indexFor 方法，为什么呢，该方法部分源码：
static int indexFor(int h, int length) { // h 为key 的 hash值；length 是数组长度
return h & (length-1);
}
由源码得知，元素所在位置是和数组长度是有关系的，既然扩容后数组长度发生了变化，那么元素位置肯定是要发生变化了。HashMap 计算元素位置采用的是 &运算，为什么 HashMap使用这种方式计算在数组中位置呢？
按照我们的潜意识，取模就可以了。hashMap 用与运算主要是提升计算性能。这又带来一个新问题，为什么与运算要用 length -1 呢，回看 hashmap初始化的时候，数组长度 length必须是2的整次幂（如果手动传参数组长度为奇数n，hashMap会自动转换长度为距离n最近的2的整次幂数），只有这样， h & (length-1) 的值才会和 h % length 计算的结果是一样的。这就是它的原因所在。另外，当length是2的整次幂的时候，length-1的结果都是低位全部是1，为后面的扩容做了很好的准备，这里先不扯这个，先理解一下这个意思。
我们来写个单元测试验证下：
public static void main(String[] args) {
//定义数组长度为2的整次幂，2^4
int length = 16;
//定义key，并计算k的hash值
String k = "China";
int h = k.hashCode();
//分别使用两种方式计算在数组中的位置
int index1 = h % length;
int index2 = h & (length - 1);
//验证结果
System.out.println(index1 == index2);
//结果为 true
}
public static void main(String[] args) {
//假设数组长度不是2的整次幂，2^4-1
int length = 15;
//定义key，并计算k的hash值
String k = "China";
int h = k.hashCode();
//分别使用两种方式计算在数组中的位置
int index1 = h % length;
int index2 = h & (length - 1);
//验证结果
System.out.println(index1 == index2);
//打印结果：false
}
一个可视化的计算过程熟悉一下每种二进制运算符：
计算 8 & 6 = 0的过程如下：
1 0 0 0 // 8的二进制数
& 0 1 1 0 // 6的二进制数
___________ // 运算规则：该位置上有一个是0 结果就是0
0 0 0 0 // 二进制数计算结果
答：HashMap 中equals 相同的两个key， 容器中只会保留后进来的key 的value。进入问题中即：我先存储了 Lucy的信息，后来又有一个 Lucy，这个时候再存储 Lucy，容器中保留的是第二个 Lucy 的信息，这种情况，我们可以考虑使用 List
二者的存储结构和解决冲突的方法都是相同的。
| HashMap | HashTable | |
| 在不指定容量的情况下的默认容量 | 16 | 为11， |
| 底层数组的容量 | 要求一定为2的整数次幂 | 不要求一定要为2的整数次幂 |
| 能否为null | key和value都允许为 null（key只能有一个为null，而value则可以有多个为 null） | key和 value都不允许为 null（但是如果在 Hashtable中有类似 put( null, null)的操作，编译同样可以通过，因为 key和 value都是Object类型，但运行时会抛出 NullPointerException异常。） |
| 扩容后容量 | 容量变为原来的2倍 | 原来的2倍+1 |
| hash 值 | 重新计算了key的hash值 | 计算hash值，直接用key的hashCode() |
| 在计算hash值对应的位置索引时 | &运算 | %运算 |
| 线程安全 | 否 | 是 |
| 去掉了 Hashtable 中的 contains 方法 | ||
| 父类 | 继承自 AbstractMap 类 | 继承自 Dictionary 类 |
4、如何优化 HashMap？
初始化 HashMap 的时候，我们可以自定义数组容量及加载因子的大小。所以，优化 HashMap 从这两个属性入手，但是，如果你不能准确的判别你的业务所需的大小，请使用默认值，否则，一旦手动配置的不合适，效果将适得其反。
threshold = (int)( capacity * loadFactor );
阈值 = 容量 X 负载因子；
初始容量默认为16,负载因子(loadFactor)默认是0.75; map扩容后，要重新计算阈值；当元素个数 大于新的阈值时，map再自动扩容；以默认值为例，阈值=16*0.75=12，当元素个数大于12时就要扩容；那剩下的4个数组位置还没有放置对象就要扩容，造成空间浪费，所以要进行时间和空间的折中考虑；
loadFactor过大时，map内的数组使用率高了，内部极有可能形成Entry链，影响查找速度；
loadFactor过小时，map内的数组使用率较低，不过内部不会生成Entry链，或者生成的Entry链很短，由此提高了查找速度，不过会占用更多的内存；所以可以根据实际硬件环境和程序的运行状态来调节loadFactor；
所以，务必合理的初始化 HashMap
hashCode 与 equals 两个对象的 hashCode() 相同，则 equals() 也一定为 true，对吗？为什么重写equals时必须重写hashCode方法
hashCode() 的作用是获取哈希码，也称为散列码；它实际上是返回一个int整数。这个哈希码的作用是确定该对象在哈希表中的索引位置。hashCode() 定义在JDK的Object.java中，这就意味着Java中的任何类都包含有hashCode()函数。散列表存储的是键值对(key-value)，它的特点是：能根据“键”快速的检索出对应的“值”。这其中就利用到了散列码（可以快速找到所需要的对象）
当把对象加入 HashSet 时，HashSet 会先计算对象的 hashcode 值来判断对象加入的位置，同时也会与其他已经加入的对象的 hashcode 值作比较，如果没有相符的hashcode，HashSet会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用 equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让其加入操作成功。如果不同的话，就会重新散列到其他位置。这就是HashSet检查重复的方法，这种方法大大减少了 equals 的次数，相应就大大提高了执行速度。hashCode() 的默认行为是对堆上的对象产生独特值。因此如果两个对象相等，则hashcode一定相同；那么，如果hashcode相同，两个对象就一定相等吗，答案是否定的，两个对象有相同的hashcode值，它们也不一定相等，有一个概念叫hash冲突，在产生hash冲突时,两个不相等的对象就会有相同的 hashcode 值，当hash冲突产生时，一般有以下几种方式来处理：
1.拉链法:每个哈希表节点都有一个next指针,多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表进行存储。
2.开放定址法:一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入。
3.再哈希:又叫双哈希法,有多个不同的Hash函数.当发生冲突时,使用第二个,第三个….等哈希函数计算地址,直到无冲突。
可以在hashcode中使用随机数字吗?
不行,因为同一对象的 hashcode 值必须是相同的.
两个对象相等，对两个对象分别调用equals方法都返回true。如果没有重写 hashCode()，则该 class 的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）
因此，equals 方法被覆盖过，则 hashCode 方法也必须被覆盖
对象的相等与指向他们的引用相等，两者有什么不同？
对象的相等 比的是内存中存放的内容是否相等而 引用相等 比较的是他们指向的内存地址是否相等。
以下说法正确的是
ArrayList的写性能要优于linkedList，在写多于读的场景，建议使用ArrayList；
For循环以及迭代循环遍历一个linkedList的效果都是一样的；
HashMap是由数组、链表、红黑树组成，链表长度超过阈值时，会再转红黑树；
JDK1.8版本中，HashMap使用了红黑树优化哈希碰撞所带来的链表过长的问题。
