JAVA-Container

引言：

Java集合框架笔记

Java集合框架（Java Collections Framework（JCF））提供了数据持有对象的方式，提供了对数据集合的操作。Java 集合框架位于 java.util 包下，主要有三个大类：Collection(接口)、Map(接口)、集合工具类。

Collection

• ArrayList：线程不同步。默认初始容量为 10，当数组大小不足时容量扩大为 1.5 倍。为追求效率，ArrayList 没有实现同步（synchronized），如果需要多个线程并发访问，用户可以手动同步，也可使用 Vector 替代。
• LinkedList：线程不同步。双向链接实现。LinkedList 同时实现了 List 接口和 Deque 接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列（Queue），同时又可以看作一个栈（Stack）。这样看来，LinkedList 简直就是个全能冠军。当你需要使用栈或者队列时，可以考虑使用 LinkedList，一方面是因为 Java 官方已经声明不建议使用 Stack 类，更遗憾的是，Java 里根本没有一个叫做 Queue 的类（它是个接口名字）。关于栈或队列，现在的首选是 ArrayDeque，它有着比 LinkedList（当作栈或队列使用时）有着更好的性能。
• Stack and Queue：Java 里有一个叫做 Stack 的类，却没有叫做 Queue 的类（它是个接口名字）。当需要使用栈时，Java 已不推荐使用 Stack，而是推荐使用更高效的 ArrayDeque；既然 Queue 只是一个接口，当需要使用队列时也就首选 ArrayDeque 了（次选是 LinkedList ）。
• Vector：线程同步。默认初始容量为 10，当数组大小不足时容量扩大为 2 倍。它的同步是通过 Iterator 方法加 synchronized 实现的。
• Stack：线程同步。继承自 Vector，添加了几个方法来完成栈的功能。现在已经不推荐使用 Stack，在栈和队列中有限使用 ArrayDeque，其次是 LinkedList。
• TreeSet：线程不同步，内部使用 NavigableMap 操作。默认元素 “自然顺序” 排列，可以通过 Comparator 改变排序。TreeSet 里面有一个 TreeMap（适配器模式）
• HashSet：线程不同步，内部使用 HashMap 进行数据存储，提供的方法基本都是调用 HashMap 的方法，所以两者本质是一样的。集合元素可以为 NULL。
• Set：Set 是一种不包含重复元素的 Collection，Set 最多只有一个 null 元素。Set 集合通常可以通过 Map 集合通过适配器模式得到。
• PriorityQueue：Java 中 PriorityQueue 实现了 Queue 接口，不允许放入 null 元素；其通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为 PriorityQueue 的底层实现。
  • 优先队列的作用是能保证每次取出的元素都是队列中权值最小的（Java 的优先队列每次取最小元素，C++ 的优先队列每次取最大元素）。这里牵涉到了大小关系，元素大小的评判可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较器（Comparator）。
• NavigableSet：添加了搜索功能，可以对给定元素进行搜索：小于、小于等于、大于、大于等于，放回一个符合条件的最接近给定元素的 key。
• EnumSet：线程不同步。内部使用 Enum 数组实现，速度比 HashSet 快。只能存储在构造函数传入的枚举类的枚举值。

Map

• TreeMap：线程不同步，基于红黑树（Red-Black tree）的 NavigableMap 实现，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用 Iterator 遍历 TreeMap 时，得到的记录是排过序的。
• Hashtable：线程安全，HashMap 的迭代器 (Iterator) 是 fail-fast 迭代器。Hashtable 不能存储 NULL 的 key 和 value。
• HashMap：线程不同步。根据key的hashcode进行存储，内部使用静态内部类Node的数组进行存储，默认初始大小为 16，每次扩大一倍。当发生 Hash 冲突时，采用拉链法（链表）。JDK 1.8中：当单个桶中元素个数大于等于8时，链表实现改为红黑树实现；当元素个数小于6时，变回链表实现。由此来防止hashCode攻击。
  • Java HashMap 采用的是冲突链表方式。
  • HashMap 是 Hashtable 的轻量级实现，可以接受为 null 的键值 (key) 和值 (value)，而 Hashtable 不允许。
• LinkedHashMap：保存了记录的插入顺序，在用 Iterator 遍历 LinkedHashMap 时，先得到的记录肯定是先插入的。也可以在构造时用带参数，按照应用次数排序。在遍历的时候会比 HashMap 慢，不过有种情况例外，当 HashMap 容量很大，实际数据较少时，遍历起来可能会比 LinkedHashMap 慢，因为 LinkedHashMap 的遍历速度只和实际数据有关，和容量无关，而 HashMap 的遍历速度和他的容量有关。
• WeakHashMap：从名字可以看出它是某种 Map。它的特殊之处在于 WeakHashMap 里的 entry 可能会被 GC 自动删除，即使程序员没有调用remove()或者clear()方法。 WeakHashMap 的存储结构类似于HashMap
  • 既然有 WeekHashMap，是否有 WeekHashSet 呢？答案是没有！不过 Java Collections 工具类给出了解决方案，Collections.newSetFromMap(Map map) 方法可以将任何 Map包装成一个Set。

工具类

• Collections、Arrays：集合类的一个工具类帮助类，其中提供了一系列静态方法，用于对集合中元素进行排序、搜索以及线程安全等各种操作。
• Comparable、Comparator：一般是用于对象的比较来实现排序，两者略有区别。

Collections

Collections 工具类常用方法:

排序
查找,替换操作
同步控制(不推荐，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合)

排序操作

void reverse(List list)//反转
void shuffle(List list)//随机排序
void sort(List list)//按自然排序的升序排序
void sort(List list, Comparator c)//定制排序，由Comparator控制排序逻辑
void swap(List list, int i , int j)//交换两个索引位置的元素
void rotate(List list, int distance)//旋转。当distance为正数时，将list后distance个元素整体移到前面。当distance为负数时，将 list的前distance个元素整体移到后面。

示例：

 ArrayList<Integer> arrayList = new ArrayList<Integer>();
 arrayList.add(-1);
 arrayList.add(3);
 arrayList.add(3);
 arrayList.add(-5);
 arrayList.add(7);
 arrayList.add(4);
 arrayList.add(-9);
 arrayList.add(-7);
 System.out.println("原始数组:");
 System.out.println(arrayList);
 // void reverse(List list)：反转
 Collections.reverse(arrayList);
 System.out.println("Collections.reverse(arrayList):");
 System.out.println(arrayList);


Collections.rotate(arrayList, 4);
System.out.println("Collections.rotate(arrayList, 4):");
System.out.println(arrayList);

// void sort(List list),按自然排序的升序排序
Collections.sort(arrayList);
System.out.println("Collections.sort(arrayList):");
System.out.println(arrayList);

// void shuffle(List list),随机排序
Collections.shuffle(arrayList);
System.out.println("Collections.shuffle(arrayList):");
System.out.println(arrayList);

// void swap(List list, int i , int j),交换两个索引位置的元素
Collections.swap(arrayList, 2, 5);
System.out.println("Collections.swap(arrayList, 2, 5):");
System.out.println(arrayList);

// 定制排序的用法
Collections.sort(arrayList, new Comparator<Integer>() {

@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
System.out.println("定制排序后：");
System.out.println(arrayList);

查找,替换

int binarySearch(List list, Object key)//对List进行二分查找，返回索引，注意List必须是有序的
int max(Collection coll)//根据元素的自然顺序，返回最大的元素。 类比int min(Collection coll)
int max(Collection coll, Comparator c)//根据定制排序，返回最大元素，排序规则由Comparatator类控制。类比int min(Collection coll, Comparator c)
void fill(List list, Object obj)//用指定的元素代替指定list中的所有元素。
int frequency(Collection c, Object o)//统计元素出现次数
int indexOfSubList(List list, List target)//统计target在list中第一次出现的索引，找不到则返回-1，类比int lastIndexOfSubList(List source, list target).
boolean replaceAll(List list, Object oldVal, Object newVal), 用新元素替换旧元素

示例代码：

ArrayList<Integer> arrayList = new ArrayList<Integer>();
arrayList.add(-1);
arrayList.add(3);
arrayList.add(3);
arrayList.add(-5);
arrayList.add(7);
arrayList.add(4);
arrayList.add(-9);
arrayList.add(-7);
ArrayList<Integer> arrayList2 = new ArrayList<Integer>();
arrayList2.add(-3);
arrayList2.add(-5);
arrayList2.add(7);
System.out.println("原始数组:");
System.out.println(arrayList);

System.out.println("Collections.max(arrayList):");
System.out.println(Collections.max(arrayList));

System.out.println("Collections.min(arrayList):");
System.out.println(Collections.min(arrayList));

System.out.println("Collections.replaceAll(arrayList, 3, -3):");
Collections.replaceAll(arrayList, 3, -3);
System.out.println(arrayList);

System.out.println("Collections.frequency(arrayList, -3):");
System.out.println(Collections.frequency(arrayList, -3));

System.out.println("Collections.indexOfSubList(arrayList, arrayList2):");
System.out.println(Collections.indexOfSubList(arrayList, arrayList2));

System.out.println("Collections.binarySearch(arrayList, 7):");
// 对List进行二分查找，返回索引，List必须是有序的
Collections.sort(arrayList);
System.out.println(Collections.binarySearch(arrayList, 7));

同步控制

Collections提供了多个synchronizedXxx()方法·，该方法可以将指定集合包装成线程同步的集合，从而解决多线程并发访问集合时的线程安全问题。

我们知道 HashSet，TreeSet，ArrayList,LinkedList,HashMap,TreeMap 都是线程不安全的。Collections提供了多个静态方法可以把他们包装成线程同步的集合。

最好不要用下面这些方法，效率非常低，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合。

方法如下：

synchronizedCollection(Collection<T>  c) //返回指定 collection 支持的同步（线程安全的）collection。
synchronizedList(List<T> list)//返回指定列表支持的同步（线程安全的）List。
synchronizedMap(Map<K,V> m) //返回由指定映射支持的同步（线程安全的）Map。
synchronizedSet(Set<T> s) //返回指定 set 支持的同步（线程安全的）set。

Arrays

1. 排序 : sort()
2. 查找 : binarySearch()
3. 比较: equals()
4. 填充 : fill()
5. 转列表: asList()
6. 转字符串 : toString()
7. 复制: copyOf()

排序 : sort()

// *************排序 sort****************
int a[] = { 1, 3, 2, 7, 6, 5, 4, 9 };
// sort(int[] a)方法按照数字顺序排列指定的数组。
Arrays.sort(a);
System.out.println("Arrays.sort(a):");
for (int i : a) {
    System.out.print(i);
}
// 换行
System.out.println();

// sort(int[] a,int fromIndex,int toIndex)按升序排列数组的指定范围
int b[] = { 1, 3, 2, 7, 6, 5, 4, 9 };
Arrays.sort(b, 2, 6);
System.out.println("Arrays.sort(b, 2, 6):");
for (int i : b) {
    System.out.print(i);
}
// 换行
System.out.println();

int c[] = { 1, 3, 2, 7, 6, 5, 4, 9 };
// parallelSort(int[] a) 按照数字顺序排列指定的数组(并行的)。同sort方法一样也有按范围的排序
Arrays.parallelSort(c);
System.out.println("Arrays.parallelSort(c)：");
for (int i : c) {
    System.out.print(i);
}
// 换行
System.out.println();

// parallelSort给字符数组排序，sort也可以
char d[] = { 'a', 'f', 'b', 'c', 'e', 'A', 'C', 'B' };
Arrays.parallelSort(d);
System.out.println("Arrays.parallelSort(d)：");
for (char d2 : d) {
    System.out.print(d2);
}
// 换行
System.out.println();

在做算法面试题的时候，我们还可能会经常遇到对字符串排序的情况,Arrays.sort() 对每个字符串的特定位置进行比较，然后按照升序排序。

String[] strs = { "abcdehg", "abcdefg", "abcdeag" };
Arrays.sort(strs);
System.out.println(Arrays.toString(strs));//[abcdeag, abcdefg, abcdehg]

查找 : binarySearch()

// *************查找 binarySearch()****************
char[] e = { 'a', 'f', 'b', 'c', 'e', 'A', 'C', 'B' };
// 排序后再进行二分查找，否则找不到
Arrays.sort(e);
System.out.println("Arrays.sort(e)" + Arrays.toString(e));
System.out.println("Arrays.binarySearch(e, 'c')：");
int s = Arrays.binarySearch(e, 'c');
System.out.println("字符c在数组的位置：" + s);

比较: equals()

// *************比较 equals****************
char[] e = { 'a', 'f', 'b', 'c', 'e', 'A', 'C', 'B' };
char[] f = { 'a', 'f', 'b', 'c', 'e', 'A', 'C', 'B' };
/*
* 元素数量相同，并且相同位置的元素相同。 另外，如果两个数组引用都是null，则它们被认为是相等的 。
*/
// 输出true
System.out.println("Arrays.equals(e, f):" + Arrays.equals(e, f));

填充 : fill()

// *************填充fill(批量初始化)****************
int[] g = { 1, 2, 3, 3, 3, 3, 6, 6, 6 };
// 数组中所有元素重新分配值
Arrays.fill(g, 3);
System.out.println("Arrays.fill(g, 3)：");
// 输出结果：333333333
for (int i : g) {
    System.out.print(i);
}
// 换行
System.out.println();

int[] h = { 1, 2, 3, 3, 3, 3, 6, 6, 6, };
// 数组中指定范围元素重新分配值
Arrays.fill(h, 0, 2, 9);
System.out.println("Arrays.fill(h, 0, 2, 9);：");
// 输出结果：993333666
for (int i : h) {
    System.out.print(i);
}

转列表 asList()

// *************转列表 asList()****************
/*
* 返回由指定数组支持的固定大小的列表。
*（将返回的列表更改为“写入数组”。）该方法作为基于数组和基于集合的API之间的桥梁，与Collection.toArray()相结合 。
* 返回的列表是可序列化的，并实现RandomAccess 。
* 此方法还提供了一种方便的方式来创建一个初始化为包含几个元素的固定大小的列表如下：
*/
List<String> stooges = Arrays.asList("Larry", "Moe", "Curly");
System.out.println(stooges);

转字符串 toString()

// *************转字符串 toString()****************
/*
* 返回指定数组的内容的字符串表示形式。
*/
char[] k = { 'a', 'f', 'b', 'c', 'e', 'A', 'C', 'B' };
System.out.println(Arrays.toString(k));// [a, f, b, c, e, A, C, B]

复制 copyOf()

// *************复制 copy****************
// copyOf 方法实现数组复制,h为数组，6为复制的长度
int[] h = { 1, 2, 3, 3, 3, 3, 6, 6, 6, };
int i[] = Arrays.copyOf(h, 6);
System.out.println("Arrays.copyOf(h, 6);：");
// 输出结果：123333
for (int j : i) {
    System.out.print(j);
}
// 换行
System.out.println();
// copyOfRange将指定数组的指定范围复制到新数组中
int j[] = Arrays.copyOfRange(h, 6, 11);
System.out.println("Arrays.copyOfRange(h, 6, 11)：");
// 输出结果66600(h数组只有9个元素这里是从索引6到索引11复制所以不足的就为0)
for (int j2 : j) {
    System.out.print(j2);
}
// 换行
System.out.println();

迭代器（Iterator）

JCF的迭代器（Iterator）为我们提供了遍历容器中元素的方法。只有容器本身清楚容器里元素的组织方式，因此迭代器只能通过容器本身得到。每个容器都会通过内部类的形式实现自己的迭代器。相比STL的迭代器，JCF的迭代器更容易使用。

//visit a list with iterator
ArrayList<String> list = new ArrayList<String>();
list.add(new String("Monday"));
list.add(new String("Tuesday"));
list.add(new String("Wensday"));
Iterator<String> it = list.iterator();//得到迭代器
while(it.hasNext()){
    String weekday = it.next();//访问元素
    System.out.println(weekday.toUpperCase());
}

JDK 1.5 引入了增强的for循环，简化了迭代容器时的写法。

//使用增强for迭代
ArrayList<String> list = new ArrayList<String>();
list.add(new String("Monday"));
list.add(new String("Tuesday"));
list.add(new String("Wensday"));
for(String weekday : list){//enhanced for statement
	System.out.println(weekday.toUpperCase());
}

List介绍

• List集合的特点就是：有序(存储顺序和取出顺序一致),可重复

List集合常用的子类有三个：

• ArrayList
  • 底层数据结构是数组。线程不安全
• LinkedList
  • 底层数据结构是链表。线程不安全
• Vector
  • 底层数据结构是数组。线程安全

ArrayList

定义

先来看看ArrayList的定义：

public class ArrayList<E> extends AbstractList<E> implements List<E>,RandomAccess,Cloneable,java.io.Serializable

从中我们可以了解到：

• ArrayList：说明ArrayList支持泛型。
• extends AbstractList ：继承了AbstractList。AbstractList提供List接口的骨干实现，以最大限度地减少“随机访问”数据存储（如ArrayList）实现Llist所需的工作。
• implements List：实现了List。实现了所有可选列表操作。
• implements RandomAccess：表明ArrayList支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。
• implements Cloneable：表明其可以调用clone()方法来返回实例的field-for-field拷贝。
• implements java.io.Serializable：表明该类具有序列化功能。

ArrayList源码属性：

/**
 * 初始化默认容量为10。
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * 指定该ArrayList容量为0时，返回该空数组。
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 当调用无参构造方法，返回的是该数组。刚创建一个ArrayList 时，其内数据量为0。
 * 它与EMPTY_ELEMENTDATA的区别就是：该数组是默认返回的，而后者是在用户指定容量为0时返回。
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 保存添加到ArrayList中的元素。
 * ArrayList的容量就是该数组的长度。
 * 该值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时，当第一次添加元素进入ArrayList中时，数组将扩容值DEFAULT_CAPACITY。
 * 被标记为transient，在对象被序列化的时候不会被序列化。
 */
transient Object[] elementData; // non-private to simplify nested class access

/**
 * ArrayList的实际大小（数组包含的元素个数）。
 * @serial
 */
private int size;

• 底层：ArrayList是List接口的大小可变数组的实现。
• 是否允许null：ArrayList允许null元素。
• 时间复杂度：size、isEmpty、get、set、iterator和listIterator方法都以固定时间运行，时间复杂度为O(1)。add和remove方法需要O(n)时间。与用于LinkedList实现的常数因子相比，此实现的常数因子较低。
• 容量：ArrayList的容量可以自动增长。
• 是否同步：ArrayList不是同步的。
• 迭代器：ArrayList的iterator和listIterator方法返回的迭代器是fail-fast的。

ArrayList底层其实就是一个数组，ArrayList中有扩容这么一个概念，正因为它扩容，所以它能够实现“动态”增长

ArrayList提供了三种构造方法。

• ArrayList(int initialCapacity)：构造一个指定容量为capacity的空ArrayList。
• ArrayList()：构造一个初始容量为 10 的空列表。
• ArrayList(Collection<? extends E> c)：构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。

核心方法

方法名	时间复杂度
add(E e)	O(1)
add(int index,E element)	O(n)
get(int index)	O(1)
set(int index,E element)	O(1)
remove(int index)	O(n)

Add方法

add方法可以说是ArrayList比较重要的方法了，我们来总览一下：

// 直接添加元素
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

// 插入到特定位置
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

add(E e)

步骤：

• ensureCapacityInternal() 检查是否需要扩容
• 插入元素

/**
* 数组容量检查，不够时则进行扩容，只供类内部使用。
* @param minCapacity    想要的最小容量
*/
private void ensureCapacityInternal(int minCapacity) {
    // 若elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则取minCapacity为DEFAULT_CAPACITY(10)和参数minCapacity之间的最大值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

/**
* 数组容量检查，不够时则进行扩容，只供类内部使用
* @param minCapacity 想要的最小容量
*/
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // 当指定的最小容量 > 数组当前的长度 
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

grow()是怎么实现的~

private void grow(int minCapacity) {
    // 获取当前数组的容量
    int oldCapacity = elementData.length;
    // 扩容。新的容量=当前容量+当前容量/2.即将当前容量增加一半。
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //如果扩容后的容量还是小于想要的最小容量
    if (newCapacity - minCapacity < 0)
        //将扩容后的容量再次扩容为想要的最小容量
        newCapacity = minCapacity;
    //如果扩容后的容量大于临界值，则进行大容量分配
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData,newCapacity);
}

扩容方法总结如下：

1. 进行空间检查ensureCapacityInternal(int minCapacity)，决定是否进行扩容，以及确定最少需要的容量
2. 如果确定扩容，就执行grow(int minCapacity)，minCapacity为最少需要的容量
3. 第一次扩容，逻辑为newCapacity = oldCapacity + (oldCapacity >> 1);即在原有的容量基础上增加一半。
4. 第一次扩容后，如果容量还是小于minCapacity，就将容量扩充为minCapacity。
5. 对扩容后的容量进行判断，如果大于允许的最大容量MAX_ARRAY_SIZE，则将容量再次调整为MAX_ARRAY_SIZE。至此扩容操作结束。

copyOf()函数~

Arrays.copyOf(elementData,newCapacity);
===========================================================================
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

arraycopy()函数~

System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
===========================================================================
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

add(int index, E element)

步骤：

• 检查角标
• 空间检查，如果有需要进行扩容
• 插入元素

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

get方法

步骤：

• 检查角标
• 返回索引值

public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

E elementData(int index) {
    return (E) elementData[index];
}

set方法

步骤：

• 检查角标
• 替代元素
• 返回旧值

public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    // 返回旧值
    return oldValue;
}

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

remove方法

步骤：

• 检查角标
• 删除元素
• 计算出需要移动的个数，并移动
• 设置为null，让Gc回收

remove(int index)

// 根据索引删除
public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}

remove(Object o)

// 根据对象删除
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

// 私有的删除方法，根据索引来，省略了角标检查和旧值返回
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

细节再说明

• ArrayList是基于动态数组实现的，在增删时候，需要数组的拷贝复制。
• ArrayList的默认初始化容量是10，每次扩容时候增加原先容量的一半，也就是变为原来的1.5倍
• 删除元素时不会减少容量，若希望减少容量则调用trimToSize()
• 它不是线程安全的。它能存放null值。

其他函数

ensureCapacity(int minCapacity)

public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        // any size if not default element table
        ? 0
        // larger than default for default empty table. It's already
        // supposed to be at default size.
        : DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

size()

public int size() {
    return size;
}

isEmpty()

public boolean isEmpty() {
    return size == 0;
}

contains(Object o)

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

indexOf(Object o)

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

lastIndexOf(Object o)

public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

clear()

public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

总结

• 基于数组实现，无容量的限制。
• 在执行插入元素时可能要扩容，在删除元素时并不会减小数组的容量，在查找元素时要遍历数组，对于非null的元素采取equals的方式寻找。
• 是非线程安全的。
• 注意点：
  1. ArrayList随机元素时间复杂度O(1)，插入删除操作需大量移动元素，效率较低
  2. 为了节约内存，当新建容器为空时，会共享Object[] EMPTY_ELEMENTDATA = {}和 Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}空数组
  3. 容器底层采用数组存储，每次扩容为1.5倍
  4. ArrayList的实现中大量地调用了Arrays.copyof()和System.arraycopy()方法，其实Arrays.copyof()内部也是调用System.arraycopy()。System.arraycopy()为Native方法
  5. 两个ToArray方法
     • Object[] toArray()方法。该方法有可能会抛出java.lang.ClassCastException异常
     • T[] toArray(T[] a)方法。该方法可以直接将ArrayList转换得到的Array进行整体向下转型
  6. ArrayList可以存储null值
  7. ArrayList每次修改（增加、删除)容器时，都是修改自身的modCount；在生成迭代器时，迭代器会保存该modCount值，迭代器每次获取元素时，会比较自身的modCount与ArrayList的modCount是否相等，来判断容器是否已经被修改，如果被修改了则抛出异常（fast-fail机制)。

Fail-Fast

什么是 fail-fast 机制?

fail-fast 机制在遍历一个集合时，当集合结构被修改，会抛出 Concurrent Modification Exception。

fail-fast 会在以下两种情况下抛出 Concurrent Modification Exception

（1）单线程环境

• 集合被创建后，在遍历它的过程中修改了结构。
• 注意 remove() 方法会让 expectModcount 和 modcount 相等，所以是不会抛出这个异常。

（2）多线程环境

• 当一个线程在遍历这个集合，而另一个线程对这个集合的结构进行了修改。

modCount 用来记录 ArrayList 结构发生变化的次数。结构发生变化是指添加或者删除至少一个元素的所有操作，或者是调整内部数组的大小，仅仅只是设置元素的值不算结构发生变化。

protected transient int modCount = 0;

在进行序列化或者迭代等操作时，需要比较操作前后 modCount 是否改变，如果改变了需要抛出 Concurrent Modification Exception。

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

Vector

同步

它的实现与 ArrayList 类似，但是使用了 synchronized 进行同步。

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    return elementData(index);
}

ArrayList 与 Vector

• Vector 是同步的，因此开销就比 ArrayList 要大，访问速度更慢。最好使用 ArrayList 而不是 Vector，因为同步操作完全可以由程序员自己来控制；
• Vector 每次扩容请求其大小的 2 倍空间，而 ArrayList 是 1.5 倍。

Vector 替代方案

synchronizedList

为了获得线程安全的 ArrayList，可以使用 Collections.synchronizedList(); 得到一个线程安全的 ArrayList。

List<String> list = new ArrayList<>();
List<String> synList = Collections.synchronizedList(list);

CopyOnWriteArrayList

也可以使用 concurrent 并发包下的 CopyOnWriteArrayList 类。

List<String> list = new CopyOnWriteArrayList<>();

CopyOnWrite 容器即写时复制的容器。通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行 Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。这样做的好处是我们可以对 CopyOnWrite 容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。所以 CopyOnWrite 容器也是一种读写分离的思想，读和写不同的容器。

public boolean add(T e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        // 复制出新数组
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // 把新元素添加到新数组里
        newElements[len] = e;
        // 把原数组引用指向新数组
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

final void setArray(Object[] a) {
    array = a;
}

读的时候不需要加锁，如果读的时候有多个线程正在向 ArrayList 添加数据，读还是会读到旧的数据，因为写的时候不会锁住旧的 ArrayList。

public E get(int index) {
    return get(getArray(), index);
}

CopyOnWrite的缺点

• CopyOnWrite 容器有很多优点，但是同时也存在两个问题，即内存占用问题和数据一致性问题。所以在开发的时候需要注意一下。

内存占用问题。

• 因为 CopyOnWrite 的写时复制机制，所以在进行写操作的时候，内存里会同时驻扎两个对象的内存，旧的对象和新写入的对象（注意：在复制的时候只是复制容器里的引用，只是在写的时候会创建新对象添加到新容器里，而旧容器的对象还在使用，所以有两份对象内存）。如果这些对象占用的内存比较大，比如说 200M 左右，那么再写入 100M 数据进去，内存就会占用 300M，那么这个时候很有可能造成频繁的 Yong GC 和 Full GC。之前我们系统中使用了一个服务由于每晚使用 CopyOnWrite 机制更新大对象，造成了每晚 15 秒的 Full GC，应用响应时间也随之变长。
• 针对内存占用问题，可以通过压缩容器中的元素的方法来减少大对象的内存消耗，比如，如果元素全是 10 进制的数字，可以考虑把它压缩成 36 进制或 64 进制。或者不使用 CopyOnWrite 容器，而使用其他的并发容器，如 ConcurrentHashMap 。

数据一致性问题。

• CopyOnWrite 容器只能保证数据的最终一致性，不能保证数据的实时一致性。所以如果你希望写入的的数据，马上能读到，请不要使用 CopyOnWrite 容器。

LinkedList

LinkedList和ArrayList与Vector同样实现了List接口，但它执行某些操作如插入和删除元素操作比ArrayList与Vector更高效，而随机访问操作效率低。

定义

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable

• LinkedList：说明它支持泛型。
• extends AbstractSequentialList
  AbstractSequentialList 继承自AbstractList，但AbstractSequentialList 只支持按次序访问，而不像 AbstractList 那样支持随机访问。这是LinkedList随机访问效率低的原因之一。
• implements List：说明它支持集合的一般操作。
• implements Deque：Deque，Double ended queue，双端队列。LinkedList可用作队列或双端队列就是因为实现了它。
• implements Cloneable：表明其可以调用clone()方法来返回实例的field-for-field拷贝。
• implements java.io.Serializable：表明该类是可以序列化的。

与ArrayList对比发现，LinkedList并没有实现RandomAccess，而实现RandomAccess表明其支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。这是LinkedList随机访问效率低的原因之一。

全局变量

/**
 * LinkedList节点个数
 */
transient int size = 0;

/**
 * 指向头节点的指针
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;

/**
 * 指向尾节点的指针
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

构造方法

LinkedList的构造方法有两个：

public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

add方法

一个是 add(E e)，该方法在 LinkedList 的末尾插入元素，因为有 last 指向链表末尾，在末尾插入元素的花费是常数时间。只需要简单修改几个相关引用即可；另一个是 add(int index, E element)，该方法是在指定下表处插入元素，需要先通过线性查找找到具体位置，然后修改相关引用完成插入操作。

add(E e)

• add方法实际上就是往链表最后添加元素

public boolean add(E e) {
    linkLast(e);
    return true;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

add(int index, E element)

1. 先根据 index 找到要插入的位置；
2. 修改引用，完成插入操作。

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

remove方法

一个是删除跟指定元素相等的第一个元素 remove(Object o)，另一个是删除指定下标处的元素 remove(int index)。

两个删除操作都要：

1. 先找到要删除元素的引用；
2. 修改相关引用，完成删除操作。

在寻找被删元素引用的时候 remove(Object o) 调用的是元素的 equals 方法，而 remove(int index) 使用的是下标计数，两种方式都是线性时间复杂度。在步骤 2 中，两个 revome() 方法都是通过 unlink(Node x) 方法完成的。这里需要考虑删除元素是第一个或者最后一个时的边界情况。

remove(Object o)

public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

remove(int index)

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

Node<E> node(int index) {
    // 下标小于长度的一半就从头遍历
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        // 否则就从尾遍历
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

get方法

可以看到get方法实现就两段代码：

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

由此可以看出是使用二分查找来看 index 离 size 中间距离来判断是从头结点正序查还是从尾节点倒序查。node() 会以O(n/2)的性能去获取一个结点。这样的效率是非常低的，特别是当 index 越接近 size 的中间值时。

set方法

set方法和get方法其实差不多，根据下标来判断是从头遍历还是从尾遍历

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

其他函数

public boolean contains(Object o) {
    return indexOf(o) != -1;
}

public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))java
                return index;
            index++;
        }
    }
    return -1;
}

小结：

ArrayList：

• 底层实现是数组
• ArrayList的默认初始化容量是10，每次扩容时候增加原先容量的一半，也就是变为原来的1.5倍
• 在增删时候，需要数组的拷贝复制(navite 方法由C/C++实现)

LinkedList：

• 底层实现是双向链表[双向链表方便实现往前遍历]

Vector：

• 底层是数组，现在已少用，被ArrayList替代，原因有两个：
  • Vector所有方法都是同步，有性能损失。
  • Vector初始length是10 超过length时 以100%比率增长，相比于ArrayList更多消耗内存。

总的来说：查询多用ArrayList，增删多用LinkedList。

ArrayList增删慢不是绝对的(在数量大的情况下，已测试)：

• 如果增加元素一直是使用add()(增加到末尾)的话，那是ArrayList要快
• 一直删除末尾的元素也是ArrayList要快【不用复制移动位置】
• 至于如果删除的是中间的位置的话，还是ArrayList要快！

但一般来说：增删多还是用LinkedList，因为上面的情况是极端的~

Stack

Stack继承了Vector，特点是先进后出(FILO, First In Last Out)。

定义

public class Stack<E> extends Vector<E>

构造方法

public Stack() {
}

方法

/**
 * 添加元素的到栈顶。
 * @param   item  要添加的元素
 * @return  被添加的元素
 * @see     java.util.Vector#addElement
 */
public E push(E item) {
    addElement(item);
    return item;
}

/**
 * 返回栈顶元素，并将其从栈中删除
 * @return  栈顶元素
 * @throws  EmptyStackException 如果栈为空
 */
public synchronized E pop() {
    E obj;
    int len = size();
    obj = peek();
    removeElementAt(len - 1);
    return obj;
}

/**
 * 返回栈顶元素，不删除。
 * @return  栈顶元素
 * @throws  EmptyStackException  如果栈为空
 */
public synchronized E peek() {
    int len = size();

    if (len == 0)
        throw new EmptyStackException();
    return elementAt(len - 1);
}

/**
 * 判断栈是否为空
 * @return  栈是否有元素
 */
public boolean empty() {
    return size() == 0;
}

/**
 * 栈底向栈顶方向遍历，查找指定对象o在栈中的位置。
 * @param   o   指定对象
 * @return  o的索引，如果没找到，返回-1
 */
public synchronized int search(Object o) {
    int i = lastIndexOf(o);

    if (i >= 0) {
        return size() - i;
    }
    return -1;
}

Map介绍

Java为数据结构中的映射定义了一个接口java.util.Map，此接口主要有四个常用的实现类，分别是HashMap、Hashtable、LinkedHashMap和TreeMap，类继承关系如下图所示：

无论是Set还是Map，我们会发现都会有对应的–>HashSet，HashMap

散列表为每个对象计算出一个整数，称为散列码。根据这些计算出来的整数（散列码）保存在对应的位置上！后面介绍的集合类都会以此为基础。

HashMap

0.概述

• 底层：HashMap是Map接口基于哈希表的实现。
• 是否允许null：HashMap允许key和value为null。
• 是否有序：HashMap不保证映射的顺序，特别是它不保证该顺序恒久不变。
• HashMap有两个影响性能的重要参数：初始化容量initial capacity、加载因子load factor。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。initial capacity*load factor就是当前允许的最大元素数目，超过initial capacity*load factor之后，HashMap就会进行扩容，扩容后的的容量为之前的两倍。
• 是否同步：HashMap不是同步的。
• 迭代器：迭代器是fast-fail的。

定义：

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

可以了解到：

• HashMap<K,V>：HashMap是以key-value形式存储数据的。
• extends AbstractMap<K,V>：继承了AbstractMap，大大减少了实现Map接口时需要的工作量。
• implements Map<K,V>：实现了Map，提供了所有可选的Map操作。
• implements Cloneable：表明其可以调用clone()方法来返回实例的field-for-field拷贝。
• implements Serializable：表明该类是可以序列化的。

属性：

静态全局变量

/**
 * 默认初始化容量，值为16
 * 必须是2的n次幂.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * 最大容量, 容量不能超出这个值。如果一个更大的初始化容量在构造函数中被指定，将被MAXIMUM_CAPACITY替换.
 * 必须是2的倍数。最大容量为1<<30，即2的30次方。
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 默认的加载因子。
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 将链表转化为红黑树的临界值。
 * 当添加一个元素被添加到有至少TREEIFY_THRESHOLD个节点的桶中，桶中链表将被转化为树形结构。
 * 临界值最小为8
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 恢复成链式结构的桶大小临界值
 * 小于TREEIFY_THRESHOLD，临界值最大为6
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 桶可能被转化为树形结构的最小容量。当哈希表的大小超过这个阈值，才会把链式结构转化成树型结构，否则仅采取扩容来尝试减少冲突。
 * 应该至少4*TREEIFY_THRESHOLD来避免扩容和树形结构化之间的冲突。
 */
static final int MIN_TREEIFY_CAPACITY = 64;

1. 存储结构

JDK1.8之前

底层为数组和链表结合的方式，地址冲突时通过拉链法解决。

「拉链法」又叫做链地址法，即在每个数组元素上存储的都是一个链表。

JDK1.8之后

底层为数组+链表+红黑树的方式，地址冲突时通过链表和红黑树解决。

• 当处理如果 hash 值冲突较多的情况下，链表的长度就会越来越长，此时的时间复杂度达到 O(n)，
• 链表长度超过 TREEIFY_THRESHOLD = 8 的时候，会将单链表转化为红黑树。
  • 红黑树是一种易于增删改查的二叉树，对与数据的查询的时间复杂度是 O(logn) 级别

这里需要讲明白两个问题：数据底层具体存储的是什么？这样的存储方式有什么优点呢？

（1）从源码可知，HashMap 类中有一个非常重要的字段，就是 Node[] table，即哈希桶数组，明显它是一个 Node 的数组。

/**
 * HashMap的节点类型。既是HashMap底层数组的组成元素，又是每个单向链表的组成元素
 */
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;    //用来定位数组索引位置
    final K key;
    V value;
    Node<K,V> next;   //链表的下一个node

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

Node 是 HashMap 的一个内部类，实现了 Map.Entry 接口，本质是就是一个映射（键值对）。上图中的每个黑色圆点就是一个Node对象。

（2）HashMap 就是使用哈希表来存储的。哈希表为解决冲突，可以采用开放地址法和链地址法等来解决问题， Java 中 HashMap 采用了链地址法。链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被 Hash 后，得到数组下标，把数据放在对应下标元素的链表上。示例

map.put("美团","小美");

系统将调用 “美团” 这个 key 的 hashCode() 方法得到其 hashCode 值（该方法适用于每个 Java 对象），然后再通过 Hash 算法的后两步运算（高位运算和取模运算，下文有介绍）来定位该键值对的存储位置，有时两个 key 会定位到相同的位置，表示发生了 Hash 碰撞。当然 Hash 算法计算结果越分散均匀，Hash 碰撞的概率就越小，map 的存取效率就会越高。

如果哈希桶数组很大，即使较差的 Hash 算法也会比较分散，如果哈希桶数组数组很小，即使好的 Hash 算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的 hash 算法减少 Hash 碰撞。

那么通过什么方式来控制 map 使得 Hash 碰撞的概率又小，哈希桶数组（Node[] table）占用空间又少呢？

答案就是好的 Hash 算法和扩容机制。

在理解 Hash 和扩容流程之前，我们得先了解下 HashMap 的几个字段。从 HashMap 的默认构造函数源码可知，构造函数就是对下面几个字段进行初始化，源码如下：

int threshold;             // 所能容纳的key-value对极限 
final float loadFactor;    // 负载因子
int modCount;  
int size;

• Node[] table的初始化长度 length (默认值是16)，Load factor 为负载因子(默认值是0.75)，
• threshold 是 HashMap 所能容纳的最大数据量的 Node (键值对)个数。threshold = length * Load factor。
• size 这个字段其实很好理解，就是 HashMap 中实际存在的键值对数量。注意和 table 的长度 length、容纳最大键值对数量 threshold 的区别。而
• modCount 字段主要用来记录 HashMap 内部结构发生变化的次数，主要用于迭代的快速失败。强调一点，内部结构发生变化指的是结构发生变化，例如 put 新键值对，但是某个 key 对应的 value 值被覆盖不属于结构变化。

2. 重要参数

参数	说明
buckets	在 HashMap 的注释里使用哈希桶来形象的表示数组中每个地址位置。注意这里并不是数组本身，数组是装哈希桶的，他可以被称为哈希表。
capacity	table 的容量大小，默认为 16。需要注意的是 capacity 必须保证为 2 的 n 次方。
size	table 的实际使用量。
threshold	size 的临界值，size 必须小于 threshold，如果大于等于，就必须进行扩容操作。
loadFactor	装载因子，table 能够使用的比例，threshold = capacity * loadFactor。
TREEIFY_THRESHOLD	树化阀值，哈希桶中的节点个数大于该值（默认为8）的时候将会被转为红黑树行存储结构。
UNTREEIFY_THRESHOLD	非树化阀值，小于该值（默认为 6）的时候将再次改为单链表的格式存储

3. 确定索引

很多操作都需要先确定一个键值对所在的桶下标。

int hash = hash(key);
int i = indexFor(hash, table.length);

（一）计算 hash 值

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

从代码中可以看到，计算hash分为三步，

• 第一步，取key的hashCode（该方法在其静态内部类中），
• 第二步，key的hashCode高16位异或低16位，
• 第三步，将第一步和第二部得到的结果进行取模运算。

（二）取模

令 x = 1<<4，即 x 为 2 的 4 次方，它具有以下性质：

x   : 00010000
x-1 : 00001111

令一个数 y 与 x-1 做与运算，可以去除 y 位级表示的第 4 位以上数：

y       : 10110010
x-1     : 00001111
y&(x-1) : 00000010

这个性质和 y 对 x 取模效果是一样的：

y   : 10110010
x   : 00010000
y%x : 00000010

位运算的代价比求模运算小的多，因此在进行这种计算时用位运算的话能带来更高的性能。

（三）确定桶下标

确定桶下标的最后一步是将 key 的 hash 值对桶个数取模：hash%capacity，如果能保证 capacity 为 2 的 n 次方，那么就可以将这个操作转换为位运算。

static int indexFor(int h, int length) {
    return h & (length-1);
}

4. put方法

图示：

1. 判断键值对数组 table[i] 是否为空或为 null，否则执行 resize() 进行扩容；

2. 根据键值 key 计算 hash 值得到插入的数组索引 i，如果 table[i]==null，直接新建节点添加，转向 6，如果table[i] 不为空，转向 3；

3. 判断 table[i] 的首个元素是否和 key 一样，如果相同直接覆盖 value，否则转向 4，这里的相同指的是 hashCode 以及 equals；

4. 判断table[i] 是否为 treeNode，即 table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向 5；

5. 遍历 table[i]，判断链表长度是否大于 8，大于 8 的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现 key 已经存在直接覆盖 value 即可；

6. 插入成功后，判断实际存在的键值对数量 size 是否超多了最大容量 threshold，如果超过，进行扩容。

JDK1.8 HashMap 的 put 方法源码如下:

public V put(K key, V value) {
    // 对key的hashCode()做hash
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 步骤①：tab为空则创建
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 步骤②：计算index，并对null做处理 
    if ((p = tab[i = (n - 1) & hash]) == null) 
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 步骤③：节点key存在，直接覆盖value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 步骤④：判断该链为红黑树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 步骤⑤：该链为链表
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key,value,null);
                     //链表长度大于8转换为红黑树进行处理
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
                        treeifyBin(tab, hash);
                    break;
                }
                 // key已经存在直接覆盖value
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))) 
                           break;
                p = e;
            }
        }

        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 步骤⑥：超过最大容量 就扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

5. get方法

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

get(Object key) 可以分为三个步骤：

1. 通过hash(Object key)方法计算key的哈希值hash。
   1. 上文中计算方法hash(Object key)
2. 通过getNode( int hash, Object key)方法获取node。
3. 如果node为null，返回null，否则返回node.value。

6. resize方法

方法是使用一个新的数组代替已有的容量小的数组

我们分析下 resize 的源码，鉴于 JDK1.8 融入了红黑树，较复杂，为了便于理解我们仍然使用 JDK1.7 的代码，好理解一些，本质上区别不大，具体区别后文再说。

// jdk1.7
void resize(int newCapacity) {   //传入新的容量
    // 引用扩容前的Entry数组
    Entry[] oldTable = table;    
    int oldCapacity = oldTable.length;      
    // 扩容前的数组大小如果已经达到最大(2^30)
    if (oldCapacity == MAXIMUM_CAPACITY) { 
        //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
        threshold = Integer.MAX_VALUE; 
        return;
    }
    // 初始化一个新的Entry数组
    Entry[] newTable = new Entry[newCapacity];  
    // 将数据转移到新的Entry数组里
    transfer(newTable);
    // 将HashMap的table属性引用新的Entry数组
    table = newTable;
    // 修改阈值
    threshold = (int)(newCapacity * loadFactor);
}

这里就是使用一个容量更大的数组来代替已有的容量小的数组，transfer() 方法将原有 Entry 数组的元素拷贝到新的 Entry 数组里。

void transfer(Entry[] newTable) {
    // src引用了旧的Entry数组
    Entry[] src = table;                   
    int newCapacity = newTable.length;
    // 遍历旧的Entry数组
    for (int j = 0; j < src.length; j++) { 
        // 取得旧Entry数组的每个元素
        Entry<K,V> e = src[j];             
        if (e != null) {
            // 释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
            src[j] = null;
            do {
                // 保存下一次循环的 Entry<K,V>
                Entry<K,V> next = e.next;
                // 重新计算每个元素在数组中的位置
                int i = indexFor(e.hash, newCapacity); 
                // 采用链头插入法将e插入i位置，最后的链表相对于原table正好是头尾相反的
                e.next = newTable[i]; 
                // 将元素放在数组上
                newTable[i] = e;      
                // 访问下一个Entry链上的元素
                e = next;             
            } while (e != null);
        }
    }
}

newTable[i] 的引用赋给了 e.next，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到 Entry 链的尾部，这一点和 Jdk1.8 有区别，下文详解。

例子：

假设 hash = key mod table.length。哈希桶数组 table 的 size=2，元素 key = 3、7、5，put 顺序依次为 5、7、3。在 mod 2 以后都冲突在 table[1] 这里了。假设负载因子 loadFactor=1，即当键值对的实际大小 size 大于 table 的实际大小时进行扩容。接下来的三个步骤是哈希桶数组 resize 成 4，然后所有的 Node 重新 rehash 的过程。

下面我们讲解下 JDK1.8 做了哪些优化。经过观测可以发现，我们使用的是 2 次幂的扩展 (指长度扩为原来 2 倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动 2 次幂的位置。

看下图可以明白这句话的意思，n 为 table 的长度，图（a）表示扩容前的 key1 和 key2 两种 key 确定索引位置的示例，图（b）表示扩容后 key1 和 key2 两种 key 确定索引位置的示例，其中 hash1 是 key1 对应的哈希与高位运算结果。

元素在重新计算 hash 之后，因为 n 变为 2 倍，那么 n-1 的 mask 范围在高位多 1bit (红色)，因此新的 index 会有两种情况：

1. 原位置
2. 原位置 + 原数组长度

因此，我们在扩充 HashMap 的时候，不需要像 JDK1.7 的实现那样重新计算 hash，只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就好了，是 0 的话索引没变，是 1 的话索引变成“原索引+oldCap”，可以看看下图为 16 扩充为 32 的 resize 示意图：

这个设计确实非常的巧妙，既省去了重新计算 hash 值的时间，而且同时，由于新增的 1bit 是 0 还是 1 可以认为是随机的，因此 resize 的过程，均匀的把之前的冲突的节点分散到新的 bucket 了。这一块就是 JDK1.8 新增的优化点。另外，JDK1.7 中 rehash 的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8 不会倒置

/**
 * 对table进行初始化或者扩容。
 * 如果table为null，则对table进行初始化
 * 如果对table扩容，因为每次扩容都是翻倍，与原来计算（n-1）&hash的结果相比，节点要么就在原来的位置，要么就被分配到“原位置+旧容量”这个位置。
 */
final Node<K,V>[] resize() {
    //新建oldTab数组保存扩容前的数组table
    Node<K,V>[] oldTab = table;
    //使用变量oldCap扩容前table的容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //保存扩容前的临界值
    int oldThr = threshold;
    int newCap, newThr = 0;
    //如果扩容前的容量 > 0
    if (oldCap > 0) {
        //如果当前容量>=MAXIMUM_CAPACITY
        if (oldCap >= MAXIMUM_CAPACITY) {
            //扩容临界值提高到正无穷
            threshold = Integer.MAX_VALUE;
            //无法进行扩容，返回原来的数组
            return oldTab;
        }
        //如果现在容量的两倍小于MAXIMUM_CAPACITY且现在的容量大于DEFAULT_INITIAL_CAPACITY
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)
            //临界值变为原来的2倍
            newThr = oldThr << 1; 
    }//如果旧容量 <= 0，而且旧临界值 > 0
    else if (oldThr > 0) 
        //数组的新容量设置为老数组扩容的临界值
        newCap = oldThr;
    else {//如果旧容量 <= 0，且旧临界值 <= 0，新容量扩充为默认初始化容量，新临界值为DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {//在当上面的条件判断中，只有oldThr > 0成立时，newThr == 0
        //ft为临时临界值，下面会确定这个临界值是否合法，如果合法，那就是真正的临界值
        float ft = (float)newCap * loadFactor;
        //当新容量< MAXIMUM_CAPACITY且ft < (float)MAXIMUM_CAPACITY，新的临界值为ft，否则为Integer.MAX_VALUE
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    //将扩容后hashMap的临界值设置为newThr
    threshold = newThr;
    //创建新的table，初始化容量为newCap
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    //修改hashMap的table为新建的newTab
    table = newTab;
    //如果旧table不为空，将旧table中的元素复制到新的table中
    if (oldTab != null) {
        //遍历旧哈希表的每个桶，将旧哈希表中的桶复制到新的哈希表中
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            //如果旧桶不为null，使用e记录旧桶
            if ((e = oldTab[j]) != null) {
                //将旧桶置为null
                oldTab[j] = null;
                //如果旧桶中只有一个node
                if (e.next == null)
                    //将e也就是oldTab[j]放入newTab中e.hash & (newCap - 1)的位置
                    newTab[e.hash & (newCap - 1)] = e;
                //如果旧桶中的结构为红黑树
                else if (e instanceof TreeNode)
                    //将树中的node分离
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { //如果旧桶中的结构为链表。
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    //遍历整个链表中的节点
                    do {
                        next = e.next;
                        // 原索引
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 原索引+oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原索引放到bucket里
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 原索引+oldCap放到bucket里
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

7. 线程安全性

在多线程使用场景中，应该尽量避免使用线程不安全的 HashMap，而使用线程安全的 ConcurrentHashMap。那么为什么说 HashMap 是线程不安全的，下面举例子说明在并发的多线程使用场景中使用 HashMap 可能造成死循环。代码如下：

public class HashMapInfiniteLoop {  
    private static HashMap<Integer,String> map = new HashMap<Integer,String>(2，0.75f);  
    public static void main(String[] args) {  
        map.put(5， "C");  

        new Thread("Thread1") {  
            public void run() {  
                map.put(7, "B");  
                System.out.println(map);  
            };  
        }.start();  
        new Thread("Thread2") {  
            public void run() {  
                map.put(3, "A);  
                System.out.println(map);  
            };  
        }.start();        
    }  
}

jdk1.7HashMap线程不安全总结：

HashMap在put的时候，插入的元素超过了容量（由负载因子决定）的范围就会触发扩容操作，会重新将原数组的内容重新hash到新的扩容数组中，在多线程的环境下，存在同时其他的元素也在进行put操作，如果hash值相同，可能出现同时在同一数组下用链表表示，造成闭环，导致在get时会出现死循环，所以HashMap是线程不安全的。

jdk1.8HashMap线程不安全总结：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null) // 如果没有hash碰撞则直接插入元素
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

其中第六行代码是判断是否出现hash碰撞，假设两个线程A、B都在进行put操作，并且hash函数计算出的插入下标是相同的，当线程A执行完第六行代码后由于时间片耗尽导致被挂起，而线程B得到时间片后在该下标处插入了元素，完成了正常的插入，然后线程A获得时间片，由于之前已经进行了hash碰撞的判断，所有此时不会再进行判断，而是直接进行插入，这就导致了线程B插入的数据被线程A覆盖了，从而线程不安全。

除此之前，还有就是代码的第38行处有个++size，假设还是线程A、B，这两个线程同时进行put操作时，且当前HashMap的zise大小为10，当线程A执行到第38行代码时，从主内存中获得size的值为10后准备进行+1操作，但是由于时间片耗尽只好让出CPU，线程B快乐的拿到CPU还是从主内存中拿到size的值10进行+1操作，完成了put操作并将size=11写回主内存，然后线程A再次拿到CPU并继续执行(此时size的值仍为10)，当执行完put操作后，还是将size=11写回内存，此时，线程A、B都执行了一次put操作，但是size的值只增加了1，所有说还是由于数据覆盖又导致了线程不安全。

总结

HashMap的线程不安全主要体现在下面两个方面：
1.在JDK1.7中，当并发执行扩容操作时会造成环形链和数据丢失的情况。
2.在JDK1.8中，在并发执行put操作时会发生数据覆盖的情况。

8. 自定义类主键

需要同时重写该类的hashCode()方法和它的equals()方法。

• 从源码可以得知，在插入元素的时候是先算出该对象的hashCode。如果hashcode相等话的。那么表明该对象是存储在同一个位置上的。
• 如果调用equals()方法，两个key相同，则替换元素
• 如果调用equals()方法，两个key不相同，则说明该hashCode仅仅是碰巧相同，此时是散列冲突，将新增的元素放在桶子上

一般来说，我们会认为：只要两个对象的成员变量的值是相等的，那么我们就认为这两个对象是相等的！因为，Object底层比较的是两个对象的地址，而对我们开发来说这样的意义并不大~这也就为什么我们要重写equals()方法

重写了equals()方法，就要重写hashCode()的方法。因为equals()认定了这两个对象相同，而同一个对象调用hashCode()方法时，是应该返回相同的值的！

自定义一个类Key，如下：

class Key implements Comparable<Key> {

    private final int value;

    Key(int value) {
        this.value = value;
    }

    @Override
    public int compareTo(Key o) {
        return Integer.compare(this.value, o.value);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass())
            return false;
        Key key = (Key) o;
        return value == key.value;
    }

    @Override
    public int hashCode() {
        return value;
    }
}

这个类复写了equals方法，并且使用属性值value当做hashcode。

9. HashMap与Hashtable

1. Hashtable 使用 synchronized 来进行同步。
2. HashMap 可以插入键为 null 的 Entry。
3. HashMap 的迭代器是 fail-fast 迭代器。
4. HashMap 不能保证随着时间的推移 Map 中的元素次序是不变的。

10. 小结

1. 扩容是一个特别耗性能的操作，所以当程序员在使用 HashMap 的时候，估算 map 的大小，初始化的时候给一个大致的数值，避免 map 进行频繁的扩容。
2. 负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊。
3. HashMap 是线程不安全的，不要在并发的环境中同时操作 HashMap，建议使用 ConcurrentHashMap。
4. JDK1.8 引入红黑树大程度优化了 HashMap 的性能。

11. 知识点

不同对象hashCode值有可能相等的问题

public static int hashCode(Object o) {
    return o != null ? o.hashCode() : 0;
}

hashCode是所有Java对象的固有方法，如果不重写的话，返回的实际上是该对象在jvm的堆上的内存地址，而不同对象的内存地址肯定不同，所以这个hashCode也就肯定不同了。如果重写了的话，由于采用的算法的问题，有可能导致两个不同对象的hashCode相同。

HashMap 的长度为什么是2的幂次方

HashCode的范围在 ±20亿，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个40亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。

常用的取余为 % ，但是除数是2的幂次则等价于与其除数减一的与操作：即 hash % length == hash & (length-1)，并且采用二进制位操作 &，相对于%能够提高运算效率

HashTable（了解）

Hashtable和HashMap，从存储结构和实现来讲基本上都是相同的。它和HashMap的最大的不同是它是线程安全的，另外它不允许key和value为null。Hashtable是个过时的集合类，不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。

HashMap&Hashtable

共同点：

• 从存储结构和实现来讲基本上都是相同的，都是实现Map接口~

区别：

• 同步性：
  • HashMap是非同步的
  • Hashtable是同步的，因为对put和get都上锁
  • 需要同步的时候，我们往往不使用，而使用ConcurrentHashMap
• 是否允许为null：
  • HashMap允许为null
  • Hashtable不允许为null
• contains方法
  • Hashtable有contains方法
  • HashMap把Hashtable的contains方法去掉了，改成了containsValue和containsKey
• 继承不同：
  • HashMap<K,V> extends AbstractMap<K,V>
  • public class Hashtable<K,V> extends Dictionary<K,V>

总结

不同点	HashMap	Hashtable
数据结构	数组+链表+红黑树	数组+链表
继承的类不同	继承AbstractMap	继承Dictionary
是否线程安全	否	是
性能高低	高	低
默认初始化容量	16	11
扩容方式不同	原始容量x2	原始容量x2 + 1
底层数组的容量为2的整数次幂	要求一定为2的整数次幂	不要求
确认key在数组中的索引的方法不同	i = (n - 1) & hash;	index = (hash & 0x7FFFFFFF) % tab.length;
遍历方式	Iterator(迭代器)	Iterator(迭代器)和Enumeration(枚举器)
Iterator遍历数组顺序	索引从小到大	索引从大到小

ConcurrentHashMap

概述

HashMap ：先说 HashMap，HashMap 是线程不安全的，在并发环境下，可能会形成环状链表（扩容时可能造成），导致 get 操作时，cpu 空转，所以，在并发环境中使 用HashMap 是非常危险的。

Hashtable ： Hashtable 和 HashMap的实现原理几乎一样，差别无非是：（1）Hashtable不允许key和value为null；（2）Hashtable是线程安全的。

但是 Hashtable 线程安全的策略实现代价却太大了，简单粗暴，get/put 所有相关操作都是 synchronized 的，这相当于给整个哈希表加了一把大锁，多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，相当于将所有的操作串行化，在竞争激烈的并发场景中性能就会非常差。

jdk1.7 中 ConcurrentHashMap 所采用的 “分段锁“ 思想。相当于容器中有多把锁，每一把锁锁一段数据，这样在多线程访问时不同段的数据时，就不会存在锁竞争了，这样便可以有效地提高并发效率。

jdk1.8 中 ConcurrentHashMap 取消了 Segment 分段锁，采用 CAS 和synchronized 来保证并发安全。数据结构跟HashMap1.8 的结构类似，数组+链表/红黑二叉树。

synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍。

put

• CAS + Synchronized

如果Key对应的数组元素为null，则通过CAS操作将其设置为当前值。如果Key对应的数组元素（也即链表表头或者树的根元素）不为null，则对该元素使用synchronized关键字申请锁，然后进行操作。如果该put操作使得当前链表长度超过一定阈值（8），则将链表（寻址时间复杂度为O(N)）转换为红黑树（寻址时间复杂度为O(log(N))，插入操作完成之后如果所有元素的数量大于当前容量（默认16）*负载因子（默认0.75）就进行扩容。

• 根据 key 计算出 hashcode 。
• 判断是否需要进行初始化。
• f 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
• 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
• 如果都不满足，则利用 synchronized 锁写入数据。
• 如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。

get

• 无锁

对于读操作，由于数组被volatile关键字修饰，因此不用担心数组的可见性问题。同时每个元素是一个Node实例，它的Key值和hash值都由final修饰，不可变更，无须关心它们被修改后的可见性问题。而其Value及对下一个元素的引用由volatile修饰，可见性也有保障。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
}

对于Key对应的数组元素的可见性，由Unsafe的getObjectVolatile方法保证。

static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
    return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}

• 根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。
• 如果是红黑树那就按照树的方式获取值。
• 不满足那就按照链表的方式遍历获取值。

size

put方法和remove方法都会通过addCount方法维护Map的size。size方法通过sumCount获取由addCount方法维护的Map的size。

LinkedHashMap

概述

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

LinkedHashMap继承了HashMap，是Map接口的哈希表和链接列表实现。

哈希表的功能通过继承HashMap实现了。

LinkedHashMap还维护着一个双重链接链表。每次向linkedHashMap插入键值对，除了将其插入到哈希表的对应位置之外，还要将其插入到双向循环链表的尾部。

此链表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。

• 基本数据结构：数组＋双向链表＋红黑树

• 因为继承HashMap，故常用属性和HashMap都一样。

• 对于几个node指针的分析：

  • HashMap中的Map.Entry：只有next
  • LinkedHashMap中的Entry：before，after，next。其中next指针因为继承Map.Entry得到

• LHM和TreeMap都实现了entry的排序，有什么区别：

  • TreeMap按照key排序，而LHM按照entry的插入or访问顺序排序。
  • 因为LHM保持entry有序的方式是调整双向链表的before，after指针，而TreeMap保持entry有序的方式是对tree结构作调整，因此显然LHM的代价更小。

• 特殊的构造函数LinkedHashMap(int,float,boolean)

  • boolean=true时，迭代器顺序遵循LRU规则，最近最少访问的entry会被最先遍历到。这种Map非常适合构建LRU缓存。

• removeEldestEntry(Map.Entry)

  • 通过覆写，可以实现：当添加新的映射到map中时,强制自动移除过期的映射.
  • 过期数据：
    • 双向链表按插入entry排序，则为最早插入双向链表的entry。
    • 双向链表按访问entry排序，则为最近最少访问的entry。

• 和HashMap的比较

  • 常规操作，如add,contains,remove等，比HashMap稍微差一些，因为需要维护双向链表。

  • 视图迭代器执行时间长短的影响因素

    • LHM：和size成比例
    • HashMap：和capacity成比例
    • 因此HashMap相对比较费时,因为 size<=capacity。

  • 非线程安全，元素允许为null

• 3个特殊回调方法

  • afterNodeRemoval，删除节点后，双向链表中unlink
  • afterNodeInsertion，插入节点后，是否删除eldest节点
  • afterNodeAccess，访问节点后，是否调整当前访问节点的顺序
  • 这3个方法保证了双向链表的有序性。在HashMap中方法体为空，此处是进行了覆写。

LinkedHashMap和HashMap有何不同？

• 数据结构上LinkedHashMap多了一条双向链表
• 迭代器的实现上不同，LinkedHashMap是从双向链表头开始遍历，HashMap是按照table[ ]的索引开始读。
• 性能上HashMap比LinkedHashMap要高，因为LinkedHashMap需要比HashMap多维护一条双向链表的开销

内部维护了一个双向链表，用来维护插入顺序或者 LRU 顺序。

/**
 * The head (eldest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> head;

/**
 * The tail (youngest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> tail;

accessOrder 决定了顺序，默认为 false，此时维护的是插入顺序。

final boolean accessOrder;

LinkedHashMap 最重要的是以下用于维护顺序的函数，它们会在 put、get 等方法中调用。

void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }

afterNodeAccess()

当一个节点被访问时，如果 accessOrder 为 true，则会将该节点移到链表尾部。也就是说指定为 LRU 顺序之后，在每次访问一个节点时，会将这个节点移到链表尾部，保证链表尾部是最近访问的节点，那么链表首部就是最近最久未使用的节点。

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

afterNodeInsertion()

在 put 等操作之后执行，当 removeEldestEntry() 方法返回 true 时会移除最晚的节点，也就是链表首部节点 first。

evict 只有在构建 Map 的时候才为 false，在这里为 true。

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

removeEldestEntry() 默认为 false，如果需要让它为 true，需要继承 LinkedHashMap 并且覆盖这个方法的实现，这在实现 LRU 的缓存中特别有用，通过移除最近最久未使用的节点，从而保证缓存空间足够，并且缓存的数据都是热点数据。

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

LRU 缓存

以下是使用 LinkedHashMap 实现的一个 LRU 缓存：

• 设定最大缓存空间 MAX_ENTRIES 为 3；
• 使用 LinkedHashMap 的构造函数将 accessOrder 设置为 true，开启 LRU 顺序；
• 覆盖 removeEldestEntry() 方法实现，在节点多于 MAX_ENTRIES 就会将最近最久未使用的数据移除。

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private static final int MAX_ENTRIES = 3;

    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_ENTRIES;
    }

    LRUCache() {
        super(MAX_ENTRIES, 0.75f, true);
    }
}
public static void main(String[] args) {
    LRUCache<Integer, String> cache = new LRUCache<>();
    cache.put(1, "a");
    cache.put(2, "b");
    cache.put(3, "c");
    cache.get(1);
    cache.put(4, "d");
    System.out.println(cache.keySet());
}
// [3, 1, 4]

属性：

下面为LinkedHashMap特有，别的属性全部继承HashMap;

private transient Entry<K,V> header; //头结点

private final boolean accessOrder;//顺序性； true(访问有序); false(插入有序)

Entry类

Entry继承了HashMap中的Node类，仅仅多了两个属性before和after用来维护双向链表。

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

方法

添加节点：

HashMap的put()方法：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
                   
    {.........}

    //当table中索引位没有结点时创建新结点放入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {

        //当key相同时覆盖
        {.........}

        //当结点时红黑树结点时添加TreeNode，putTreeVal添加时调用了newTreeNode()
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {

            //循环遍历链表
            {
                //链表尾部加入新节点
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //长度大于等于7转换成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }

                //链表中发现相同的key覆盖
                {........}

            }
        }


        //判断是否需要扩容，modCount++
        {...........}

        return null;
    }

LinkedHashMap中重写的newNode()和newTreeNode()

   Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
   	//创建LinkedHashMap重写的Entry类
       LinkedHashMap.Entry<K,V> p =
           new LinkedHashMap.Entry<K,V>(hash, key, value, e);
        //调用维护双向链表的函数
       linkNodeLast(p);
       return p;
   }

//维护双向链表的函数
   private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
       LinkedHashMap.Entry<K,V> last = tail;
       //将尾部指针指向新添加的Entry  p
       tail = p;
       if (last == null)
           head = p;
       else {
       	//p的前驱指向之前的尾结点
           p.before = last;
           //之前的尾节点的后继指向p
           last.after = p;
       }
   }

//红黑树结点的双向链表维护和上述的雷同，不赘述
   TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
       TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
       linkNodeLast(p);
       return p;
   }

总结方法过程：

• 调用父类的put函数
• put函数中创建新节点的函数newNode和newTreeNode被重写，多态的特性使得调用了LinkedHashMap重写的创建方式
• 在LinkedHashMap重写的函数中创建结点的同时维护了双向链表的关系

删除结点

HashMap中的remove()

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;

    //根据key在table中寻找对应的结点node
    {...........}

    //从链表或者红黑树中移除node，并维护链表或红黑树关系
    {...........}

    //执行完以上操作后调用的回调函数，在LinkedHashMap中重写
    afterNodeRemoval(node);
}

LinkedHashMap中重写的afterNodeRemoval()函数，用于维护remove后双向链表的关系

void afterNodeRemoval(Node<K,V> e) { // unlink
	//向下转型，转成LinkedHashMap重写的Entry
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}

遍历分析

在概述中我们知道LinkedHashMap的遍历是有序的，而HashMap是无序的，分析一下原因。

LinkedHashMap<Object, Object> linkedHashMap = new LinkedHashMap<>();
        linkedHashMap.put("源码",1);
        linkedHashMap.put("分析",2);
        linkedHashMap.put("博客",3);
        Set<Object> keySet = linkedHashMap.keySet();
        for (Object obj : keySet) {
            System.out.print(obj);
        }

        System.out.println();

        HashMap<Object, Object> hashMap = new HashMap<>();
        hashMap.put("源码", 1);
        hashMap.put("分析", 2);
        hashMap.put("博客", 3);
        Set<Object> keySet2 = hashMap.keySet();
        for (Object obj : keySet2) {
            System.out.print(obj);
        }
// 输出
源码分析博客
分析博客源码

Map的遍历本质上是先遍历key再通过Key去获得value，返回的keySet的遍历方式有迭代器和for循环，增强for在编译后也是转换成迭代器实现，所以只需要分析LinkedHashMap的迭代器是如何实现的就可以知道它为何能有序输出了。（EntrySet也是同理，keySet只是在最后多调用了getKey()）

/**
 * 返回linkedHashMap中所有key的视图。
 * 改变linkedHashMap会影响到set，反之亦然。
 * 如果当迭代器迭代set时，linkedHashMap被修改(除非是迭代器自己的remove()方法)，迭代器的结果是不确定的。
 * set支持元素的删除，通过Iterator.remove、Set.remove、removeAll、retainAll、clear操作删除hashMap中对应的键值对。不支持add和addAll方法。
 *
 * @return 返回linkedHashMap中所有key的set视图
 */
public Set<K> keySet() {
        Set<K> ks = keySet;
        if (ks == null) {
        	//新建LinkedKeySet对象
            ks = new LinkedKeySet();
            keySet = ks;
        }
        return ks;
    }

final class LinkedKeySet extends AbstractSet<K> {
        public final Iterator<K> iterator() {
        	//新建LinkedKeyIterator对象
            return new LinkedKeyIterator();
        }
 }

//继承了LinkedHashIterator
final class LinkedKeyIterator extends LinkedHashIterator
        implements Iterator<K> {
       
        public final K next() { 
        	//调用父类的nextNode(在下面)获得node再返回Key
        	return nextNode().getKey(); 
        }
    }

    abstract class LinkedHashIterator {
        LinkedHashMap.Entry<K,V> next;
        LinkedHashMap.Entry<K,V> current;
        int expectedModCount;

        LinkedHashIterator() {
        	//初始化时从双向链表头开始读
            next = head;
            //fail-fast机制
            expectedModCount = modCount;
            current = null;
       }
		
		public final boolean hasNext() {return next != null;}

        final LinkedHashMap.Entry<K,V> nextNode() {
            LinkedHashMap.Entry<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            current = e;
            
			//读取的是当前结点的后继
            next = e.after;
            return e;
        }
 }

简单总结一下步骤，并和HashMap进行对比更加直观。

步骤	LinkedHashMap	HashMap
1	获取keySet对象	同左
2	获取keySet实现的迭代器	同左
3	迭代器初始化next=双向链表头，获得next时获取的是后继	迭代器初始化时获得table[ ]，next()是按照table的索引遍历

TreeMap

TreeMap是Map接口基于红黑树的实现，键值对是有序的。TreeMap根据键的自然顺序进行排序，或者根据创建map时提供的Comparator进行排序，使用哪种取决于使用的哪个构造方法。

• TreeMap继承于AbstractMap，实现了Map, Cloneable, NavigableMap, Serializable接口。
• TreeMap 继承于AbstractMap，而AbstractMap实现了Map接口，并实现了Map接口中定义的方法，减少了其子类继承的复杂度；
• TreeMap 实现了Map接口，成为Map框架中的一员，可以包含着key–value形式的元素；
• TreeMap 实现了NavigableMap接口，意味着拥有了更强的元素搜索能力；
• TreeMap 实现了Cloneable接口，实现了clone()方法，可以被克隆；
• TreeMap 实现了Java.io.Serializable接口，支持序列化操作，可通过Hessian协议进行传输；

public interface SortedMap<K,V> extends Map<K,V> {

    //返回元素比较器。如果是自然顺序，则返回null；
    Comparator<? super K> comparator();

    //返回从fromKey到toKey的集合：含头不含尾
    java.util.SortedMap<K,V> subMap(K fromKey, K toKey);

    //返回从头到toKey的集合：不包含toKey
    java.util.SortedMap<K,V> headMap(K toKey);

    //返回从fromKey到结尾的集合：包含fromKey
    java.util.SortedMap<K,V> tailMap(K fromKey);

    //返回集合中的第一个元素：
    K firstKey();

    //返回集合中的最后一个元素：
    K lastKey();

    //返回集合中所有key的集合：
    Set<K> keySet();

    //返回集合中所有value的集合：
    Collection<V> values();

    //返回集合中的元素映射：
    Set<Map.Entry<K, V>> entrySet();
}

public interface NavigableMap<K,V> extends SortedMap<K,V> {

    //返回小于key的第一个元素：
    Map.Entry<K,V> lowerEntry(K key);

    //返回小于key的第一个键：
    K lowerKey(K key);

    //返回小于等于key的第一个元素：
    Map.Entry<K,V> floorEntry(K key);

    //返回小于等于key的第一个键：
    K floorKey(K key);

    //返回大于或者等于key的第一个元素：
    Map.Entry<K,V> ceilingEntry(K key);

    //返回大于或者等于key的第一个键：
    K ceilingKey(K key);

    //返回大于key的第一个元素：
    Map.Entry<K,V> higherEntry(K key);

    //返回大于key的第一个键：
    K higherKey(K key);

    //返回集合中第一个元素：
    Map.Entry<K,V> firstEntry();

    //返回集合中最后一个元素：
    Map.Entry<K,V> lastEntry();

    //返回集合中第一个元素，并从集合中删除：
    Map.Entry<K,V> pollFirstEntry();

    //返回集合中最后一个元素，并从集合中删除：
    Map.Entry<K,V> pollLastEntry();

    //返回倒序的Map集合：
    java.util.NavigableMap<K,V> descendingMap();

    NavigableSet<K> navigableKeySet();

    //返回Map集合中倒序的Key组成的Set集合：
    NavigableSet<K> descendingKeySet();

    java.util.NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                                       K toKey, boolean toInclusive);

    java.util.NavigableMap<K,V> headMap(K toKey, boolean inclusive);

    java.util.NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);

    SortedMap<K,V> subMap(K fromKey, K toKey);

    SortedMap<K,V> headMap(K toKey);

    SortedMap<K,V> tailMap(K fromKey);
}

使用元素自然排序

在使用自然顺序排序时候，需要区分两种情况：一种是Jdk定义的对象，一种是我们应用自己定义的对象；

public class SortedTest implements Comparable<SortedTest> {
    private int age;
    public SortedTest(int age){
        this.age = age;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    //自定义对象，实现compareTo(T o)方法：
    public int compareTo(SortedTest sortedTest) {
        int num = this.age - sortedTest.getAge();
        //为0时候，两者相同：
        if(num==0){
            return 0;
        //大于0时，传入的参数小：
        }else if(num>0){
            return 1;
        //小于0时，传入的参数大：
        }else{
            return -1;
        }
    }
}

public class TreeMapTest {
    public static void main(String[] agrs){
        //自然顺序比较
        naturalSort();
    }
     //自然排序顺序：
    public static void naturalSort(){
        //第一种情况：Integer对象
        TreeMap<Integer,String> treeMapFirst = new TreeMap<Integer, String>();
        treeMapFirst.put(1,"jiaboyan");
        treeMapFirst.put(6,"jiaboyan");
        treeMapFirst.put(3,"jiaboyan");
        treeMapFirst.put(10,"jiaboyan");
        treeMapFirst.put(7,"jiaboyan");
        treeMapFirst.put(13,"jiaboyan");
        System.out.println(treeMapFirst.toString());

        //第二种情况:SortedTest对象
        TreeMap<SortedTest,String> treeMapSecond = new TreeMap<SortedTest, String>();
        treeMapSecond.put(new SortedTest(10),"jiaboyan");
        treeMapSecond.put(new SortedTest(1),"jiaboyan");
        treeMapSecond.put(new SortedTest(13),"jiaboyan");
        treeMapSecond.put(new SortedTest(4),"jiaboyan");
        treeMapSecond.put(new SortedTest(0),"jiaboyan");
        treeMapSecond.put(new SortedTest(9),"jiaboyan");
        System.out.println(treeMapSecond.toString());
    }
}

在自然顺序比较中，需要让被比较的元素实现Comparable接口，否则在向集合里添加元素时报：”java.lang.ClassCastException: com.jiaboyan.collection.map.SortedTest cannot be cast to java.lang.Comparable”异常；

这是因为在调用put()方法时，会将传入的元素转化成Comparable类型对象，所以当你传入的元素没有实现Comparable接口时，就无法转换，遍会报错；

使用自定义比较器排序

使用自定义比较器排序，需要在创建TreeMap对象时，将自定义比较器对象传入到TreeMap构造方法中；

自定义比较器对象，需要实现Comparator接口，并实现比较方法compare(T o1,T o2)；

值得一提的是，使用自定义比较器排序的话，被比较的对象无需再实现Comparable接口了；

public class SortedTest {
    private int age;
    public SortedTest(int age){
        this.age = age;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
}
public class SortedTestComparator implements Comparator<SortedTest> {
    //自定义比较器：实现compare(T o1,T o2)方法：
    public int compare(SortedTest sortedTest1, SortedTest sortedTest2) {
        int num = sortedTest1.getAge() - sortedTest2.getAge();
        if(num==0){//为0时候，两者相同：
            return 0;
        }else if(num>0){//大于0时，后面的参数小：
            return 1;
        }else{//小于0时，前面的参数小：
            return -1;
        }
    }
}

public class TreeMapTest {
    public static void main(String[] agrs){
        //自定义顺序比较
        customSort();
    }
    //自定义排序顺序:
    public static void customSort(){
        TreeMap<SortedTest,String> treeMap = new TreeMap<SortedTest, String>(new SortedTestComparator());
        treeMap.put(new SortedTest(10),"hello");
        treeMap.put(new SortedTest(21),"my");
        treeMap.put(new SortedTest(15),"name");
        treeMap.put(new SortedTest(2),"is");
        treeMap.put(new SortedTest(1),"jiaboyan");
        treeMap.put(new SortedTest(7),"world");
        System.out.println(treeMap.toString());
    }
}

总结

不同点	HashMap	TreeMap
数据结构	数组+链表+红黑树	红黑树
是否有序	否	是
是否实现NavigableMap	否	是
增删改查操作的时间复杂度	O(1)	log(n)

相同点

• 都以键值对的形式存储数据。
• 都继承了AbstractMap，实现了Map、Cloneable、Serializable。
• 都是非同步的。

小结

实现类	数据结构	是否线程安全	key是否可为null	是否有序
HashMap	数组+链表+红黑树（since JDK1.8）	否	是	否
Hashtable	数组+链表	是	否	否
LinkedHashMap	数组+链表+红黑树(since JDK1.8)+ 双重链接列表	否	是	是
TreeMap	红黑树	否	否	是

Set介绍

Set接口继承了Collection接口。特点是不保存重复的元素。

equals和hashCode方法

关键结论：

• 无论何时重写equals()方法，就必须重写hashCode()的方法
• equals()方法默认是比较对象的地址，使用的是==等值运算符
• hashCode()方法对底层是散列表的对象有提升性能的功能
• 同一个对象(如果该对象没有被修改)：那么重复调用hashCode()那么返回的int是相同的！
• hashCode()方法默认是由对象的地址转换而来的（类似于逻辑地址）
• equals()方法还有5个默认的原则：
  • 自反性—>只要对象的不为null，x.equals(x)应该返回的是true
  • 一致性—>只要对象没有被修改，那么多次调用还是返回对应的结果！
  • 传递性—>x.equals(y)和y.equals(z)都返回true，那么可以得出：x.equals(z)返回true
  • 对称性—>x.equals(y)和y.equals(x)结果应该是相等的。
  • 传入的参数为null，返回的是false

Hash

散列（哈希）函数

• 把任意长度的输入（又叫做预映射）通过散列算法变换成固定长度的输出，该输出就是散列值。
• 或者说一种将任意长度的消息压缩到某一固定长度消息的函数。

性质

1. 如果散列表中存在和散列原始输入K相等的记录，那么K必定在f(K)的存储位置上
2. 不同关键字经过散列算法变换后可能得到同一个散列地址，这种现象称为碰撞
3. 如果两个Hash值不同（前提是同一Hash算法），那么这两个Hash值对应的原始输入必定不同

hashCode

hashCode是Object的一个方法，hashCode方法返回一个hash code值。在Object类中的默认实现是“将该对象的内部地址转换成一个整数返回”。

/**
 * @return  a hash code value for this object.
 */
public native int hashCode();

且这个方法是为了更好的支持hash表，比如String，Set，HashTable、HashMap等。

1. hashCode的存在主要是为了查找的快捷性，hashCode是用来在散列存储结构中确定对象的存储地址的
2. 如果两个对象equals相等，那么这两个对象的HashCode一定也相同
3. 如果对象的equals方法被重写，那么对象的HashCode方法也一定重写

String中使用

• 可以直接使用String.equals()来判断两个字符串是否相等！

Collection中使用

Java中的集合（Collection）有两类，一类是List，再有一类是Set。前者集合内的元素是有序的，元素可以重复；

后者元素无序，但元素不可重复。那么这里就有一个比较严重的问题了：要想保证元素不重复，可两个元素是否重复应该依据什么来判断呢？这就是Object.equals方法了。但是，如果每增加一个元素就检查一次，那么当元素很多时，后添加到集合中的元素比较的次数就非常多了。这显然会大大降低效率。

于是，Java采用了哈希表的原理。hash算法也称为散列算法，是将数据依特定hash算法直接指定到一个地址上。

即调用键值（key）对象的hashCode()方法，在无重写时返回的是对象的hash code（可以理解为该对象的内部地址）

这样一来，当集合要添加新的元素时，会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的hashcode值作比较，如果没有相符的hashcode，HashSet会假设对象没有重复出现。但是如果发现有相同hashcode值的对象，这时会调用equals（）方法来检查hashcode相等的对象是否真的相同。如果两者相同，就不会让其加入操作成功。不相同就散列其它的地址。所以这里存在一个冲突解决的问题。这样一来实际调用equals方法的次数就大大低了，几乎只需要一两次。

为什么重写eqauls一定要重写hashcode

由于为了提高程序的效率才实现了hashcode方法，先进行hashcode的比较，如果不同，那没就不必在进行equals的比较了，这样就大大减少了equals比较的次数，这对比需要比较的数量很大的效率提高是很明显的。

其实简单的说就是为了保证同一个对象，保证在equals相同的情况下hashcode值必定相同，如果重写了equals而未重写hashcode方法，可能就会出现两个没有关系的对象equals相同的（因为equal都是根据对象的特征进行重写的），但hashcode却不相同的。

如果只重写equals，比如认定id相同的对象相等，在不重写hashCode时（不按照id值返回对应hash code值），存在两个相同id的对象，理论上要认定为相等，若要存储到去重的集合中时，就会将两个都保存而达不到去重目的。

不重写equals方法，比较的是对象地址，即==等值比较。

HashSet

HashSet是依赖于HashMap的。所以HashSet的数据结构也是哈希表+链表+红黑树。它不保证set的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用 null 元素。

//HashSet是对HashMap的简单包装
public class HashSet<E>{
    ......
    // HashSet里面有一个HashMap
    private transient HashMap<E,Object> map;
    private static final Object PRESENT = new Object();
    public HashSet() {
        map = new HashMap<>();
    }
    ......
    public boolean add(E e) {//简单的方法转换
        return map.put(e, PRESENT)==null;
    }
    ......
}

比较关键的就是这个 add() 方法。 可以看出它是将存放的对象当做了 HashMap 的健，value 都是相同的 PRESENT 。由于 HashMap 的 key 是不能重复的，所以每当有重复的值写入到 HashSet 时，value 会被覆盖，但 key 不会收到影响，这样就保证了 HashSet 中只能存放不重复的元素。

对比

HashSet如何检查重复

当你把对象加入HashSet时，HashSet会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相符的 hashcode，HashSet会假设对象没有重复出现。但是如果发现有相同hashcode值的对象，这时会调用equals()方法来检查hashcode相等的对象是否真的相同。如果两者相同，HashSet就不会让加入操作成功。

hashCode（）与equals（）的相关规定：

1. 如果两个对象相等，则hashcode一定也是相同的
2. 两个对象相等，对两个equals方法返回true
3. 两个对象有相同的hashcode值，它们也不一定是相等的
4. 综上，equals方法被覆盖过，则hashCode方法也必须被覆盖
5. hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该class的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。

==与equals的区别

1. ==是判断两个变量或实例是不是指向同一个内存空间 equals是判断两个变量或实例所指向的内存空间的值是不是相同
2. ==是指对内存地址进行比较 equals()是对字符串的内容进行比较
3. ==指引用是否相同 equals()指的是值是否相同

TreeSet

基于TreeMap的NavigableSet实现。使用元素的自然顺序对元素进行排序，或者根据创建set时提供的Comparator进行排序，具体取决于使用的构造方法。

小结

Collection

1. List

• Arraylist： Object数组
• Vector： Object数组
• LinkedList： 双向链表(JDK1.6之前为循环链表，JDK1.7取消了循环)

2. Set

• HashSet（无序，唯一）: 基于 HashMap 实现的，底层采用 HashMap 来保存元素
• LinkedHashSet： LinkedHashSet 继承与 HashSet，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 Hashmap 实现一样，不过还是有一点点区别的。
• TreeSet（有序，唯一）： 红黑树(自平衡的排序二叉树。)

Map

• HashMap： JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间
• LinkedHashMap： LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
• Hashtable： 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的
• TreeMap： 红黑树（自平衡的排序二叉树）

QA

并发集合类是什么？

Java1.5并发包（java.util.concurrent）包含线程安全集合类，允许在迭代时修改集合。

• 迭代器被设计为fail-fast的，会抛出ConcurrentModificationException。
• 一部分类为：
  • CopyOnWriteArrayList
  • ConcurrentHashMap
  • CopyOnWriteArraySet

Arraylist 与 LinkedList 区别?

• 1. 是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
• 2. 底层数据结构： Arraylist 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构（JDK1.6之前为循环链表，JDK1.7取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）
• 3. 插入和删除是否受元素位置的影响： ① ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② LinkedList 采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似 O（1）而数组为近似 O（n）。
• 4. 是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
• 5. 内存空间占用： ArrayList的空 间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。

HashMap和Hashtable的区别

共同点：

• 从存储结构和实现来讲基本上都是相同的，都是实现Map接口~

区别：

• 同步性：
  • HashMap是非同步的
  • Hashtable是同步的
  • 需要同步的时候，我们往往不使用，而使用ConcurrentHashMap
• 是否允许为null：
  • HashMap允许为null
  • Hashtable不允许为null
• contains方法
  • Hashtable有contains方法
  • HashMap把Hashtable的contains方法去掉了，改成了containsValue和containsKey
• 继承不同：
  • HashMap<K,V> extends AbstractMap<K,V>
  • public class Hashtable<K,V> extends Dictionary<K,V>

HashMap 和 HashSet区别

如果你看过 HashSet 源码的话就应该知道：HashSet 底层就是基于 HashMap 实现的。（HashSet 的源码非常非常少，因为除了 clone()、writeObject()、readObject()是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

HashMap	HashSet
实现了Map接口	实现Set接口
存储键值对	仅存储对象
调用 put（）向map中添加元素	调用 add（）方法向Set中添加元素
HashMap使用键（Key）计算Hashcode	HashSet使用成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以equals()方法用来判断对象的相等性，

HashMap中的key可以是任何对象或数据类型吗?

• 可以为null，但不能是可变对象，如果是可变对象的话，对象中的属性改变，则对象 HashCode 也进行相应的改变，导致下次无法查找到已存在Map中的数据。
• 如果可变对象在 HashMap 中被用作键，那就要小心在改变对象状态的时候，不要改变它的哈希值了。我们只需要保证成员变量的改变能保证该对象的哈希值不变即可。

Hash冲突的解决办法

• 链地址法
• 开放地址法（向后一位）
• 再哈希法

什么是迭代器

Java 集合框架的集合类，我们有时候称之为容器。容器的种类有很多种，比如 ArrayList、LinkedList、HashSet…，每种容器都有自己的特点，ArrayList 底层维护的是一个数组；LinkedList 是链表结构的；HashSet 依赖的是哈希表，每种容器都有自己特有的数据结构。

因为容器的内部结构不同，很多时候可能不知道该怎样去遍历一个容器中的元素。所以为了使对容器内元素的操作更为简单，Java 引入了迭代器模式！

把访问逻辑从不同类型的集合类中抽取出来，从而避免向外部暴露集合的内部结构。

迭代器模式：就是提供一种方法对一个容器对象中的各个元素进行访问，而又不暴露该对象容器的内部细。

public static void main(String[] args) {
    // 使用迭代器遍历ArrayList集合
    Iterator<String> listIt = list.iterator();
    while(listIt.hasNext()){
        System.out.println(listIt.hasNext());
    }
    // 使用迭代器遍历Set集合
    Iterator<String> setIt = set.iterator();
    while(setIt.hasNext()){
        System.out.println(listIt.hasNext());
    }
    // 使用迭代器遍历LinkedList集合
    Iterator<String> linkIt = linkList.iterator();
    while(linkIt.hasNext()){
        System.out.println(listIt.hasNext());
    }
}

构造相同hash的字符串进行攻击该如何处理？

攻击原理：

当客户端发送一个请求到服务器，如果该请求中带有参数，服务器端会将 参数名-参数值 作为 key-value 保存在 HashMap 中。如果有人恶意构造请求，在请求中加入大量相同 hash 值的 String 参数名（key），那么在服务器端用于存储这些 key-value 对的 HashMap 会被强行退化成链表，如图：

怎么处理

1. 限制 POST 和 GET 请求的参数个数
2. 限制 POST 请求的请求体大小
3. Web Application FireWall（WAF）

JDK7如何处理

HashMap 会动态的使用一个专门 TreeMap 实现来替换掉它。

Set如何保证元素不重复?

在Java的Set体系中，根据实现方式不同主要分为两大类。HashSet和TreeSet。

• TreeSet 是二叉树实现的，TreeSet中的数据是自动排好序的，不允许放入null值
• HashSet 是哈希表实现的,HashSet中的数据是无序的，可以放入null，但只能放入一个null，两者中的值都不能重复，就如数据库中唯一约束

在HashSet中，基本的操作都是有HashMap底层实现的，因为HashSet底层是用HashMap存储数据的。当向HashSet中添加元素的时候，首先计算元素的hashcode值，然后通过扰动计算和按位与的方式计算出这个元素的存储位置，如果这个位置位空，就将元素添加进去；如果不为空，则用equals方法比较元素是否相等，相等就不添加，否则找一个空位添加。

TreeSet的底层是TreeMap的keySet()，而TreeMap是基于红黑树实现的，红黑树是一种平衡二叉查找树，它能保证任何一个节点的左右子树的高度差不会超过较矮的那棵的一倍。

TreeMap是按key排序的，元素在插入TreeSet时compareTo()方法要被调用，所以TreeSet中的元素要实现Comparable接口。TreeSet作为一种Set，它不允许出现重复元素。TreeSet是用compareTo()来判断重复元素的。