Java开发面试指南系列-Java集合

1.List,Set,Map三者的区别？

• List(对付顺序的好帮⼿)： List接⼝存储⼀组不唯⼀（可以有多个元素引⽤相同的对象），有序的对象
• Set(注重独⼀⽆⼆的性质): 不允许重复的集合。不会有多个元素引⽤相同的对象。
• Map(⽤Key来搜索的专家): 使⽤键值对存储。Map会维护与Key有关联的值。两个Key可以引⽤相同的对象，但Key不能重复，典型的Key是String类型，但也可以是任何对象。

2.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 采⽤链表存储，所以对于 add(​E e) ⽅法的插⼊，删除元素时间复杂度不受元素位置的影响，近似 O（1），如果是要在指定位置 i 插⼊和删除元素的话（ (add(int index, E element) ） 时间复杂度近似为 o(n)) 因为需要先移动到指定位置再插⼊。
4. 是否⽀持快速随机访问： LinkedList 不⽀持⾼效的随机元素访问，⽽ ArrayList ⽀持。快速随机访问就是通过元素的序号快速获取元素对象(对应于 get(int index) ⽅法)。
5. 内存空间占⽤： ArrayList的空 间浪费主要体现在在list列表的结尾会预留⼀定的容量空间，⽽LinkedList的空间花费则体现在它的每⼀个元素都需要消耗⽐ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。

补充内容:RandomAccess接⼝

public interface RandomAccess {
}

查看源码我们发现实际上 RandomAccess 接⼝中什么都没有定义。所以，在我看来RandomAccess 接⼝不过是⼀个标识罢了。标识什么？ 标识实现这个接⼝的类具有随机访问功能。

在 binarySearch（ ）⽅法中，它要判断传⼊的list 是否 RamdomAccess 的实例，如果是，调⽤ indexedBinarySearch（） ⽅法，如果不是，那么调⽤ iteratorBinarySearch（） ⽅法

public static <T>

int binarySearch(List<? extends Comparable<? super T>> list, T key) {

if (list instanceof RandomAccess || list.size() <BINARYSEARCH_THRESHOLD)

return Collections.indexedBinarySearch(list, key);

else

return Collections.iteratorBinarySearch(list, key);

}

ArrayList 实现了 RandomAccess 接⼝， ⽽ LinkedList 没有实现。为什么呢？我觉得还是和底层数据结构有关！ ArrayList 底层是数组，⽽ LinkedList 底层是链表。数组天然⽀持随机访问，时间复杂度为 O（1），所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素，时间复杂度为 O（n），所以不⽀持快速随机访问。， ArrayList 实现了 RandomAccess 接⼝，就表明了他具有快速随机访问功能。RandomAccess 接⼝只是标识，并不是说 ArrayList 实现 RandomAccess 接⼝才具有快速随机访问功能的！

下⾯再总结⼀下 list 的遍历⽅式选择：

• 实现了 RandomAccess 接⼝的list，优先选择普通 for 循环 ，其次 foreach
• 未实现 RandomAccess 接⼝的list，优先选择iterator遍历（foreach遍历底层也是通过iterator实现的,），⼤size的数据，千万不要使⽤普通for循环

补充内容:双向链表和双向循环链表

双向链表： 包含两个指针，⼀个prev指向前⼀个节点，⼀个next指向后⼀个节点。

另外推荐⼀篇把双向链表讲清楚的⽂章：https://juejin.im/post/5b5d1a9af265da0f47352f14

双向循环链表： 最后⼀个节点的 next 指向head，⽽ head 的prev指向最后⼀个节点，构成⼀个环。

3.ArrayList 与 Vector 区别呢?为什么要⽤Arraylist取代Vector呢？

• Vector 类的所有⽅法都是同步的。可以由两个线程安全地访问⼀个Vector对象、但是⼀个线程访问Vector的话代码要在同步操作上耗费⼤量的时间。
• Arraylist 不是同步的，所以在不需要保证线程安全时建议使⽤Arraylist。

4.说⼀说 ArrayList 的扩容机制吧

ArrayList底层是数组elementData，用于存放插入的数据，初始大小是0，当有数据插入时，默认大小DEFAULT_CAPACITY = 10。

扩容，当添加元素时，如果元素个数+1> 当前数组长度 【size + 1 > elementData.length】时，进行扩容，扩容后的数组大小是： oldCapacity + (oldCapacity >> 1) 可以理解成1.5倍扩容。

最后将旧数组内容调用Arrays.copyof，再通过调用System.arraycopy()方法（native修饰）进行复制，达到扩容的目的，此时新旧列表的size大小相同，但elementData的长度即容量不同。

为什么放大因子是1.5，扩容容量不能太小，防止频繁扩容，频繁申请内存空间 + 数组频繁复制；扩容容量不能太大，需要充分利用空间，避免浪费过多空间；为了能充分使用之前分配的内存空间，最好把增长因子设为 1<k<2；并且充分利用移位操作（右移一位），扩容后的数组大小是： oldCapacity + (oldCapacity >> 1)，减少浮点数或者运算时间和运算次数。

5.HashMap 和 Hashtable 的区别

1. 线程是否安全： HashMap 是⾮线程安全的，HashTable 是线程安全的；HashTable 内部的⽅法基本都经过 synchronized 修饰。（如果你要保证线程安全的话就使⽤ ConcurrentHashMap吧！）；
2. 效率： 因为线程安全的问题，HashMap 要⽐ HashTable 效率⾼⼀点。另外，HashTable 基本被淘汰，不要在代码中使⽤它；
3. 对Null key 和Null value的⽀持： HashMap 中，null 可以作为键，这样的键只有⼀个，可以有⼀个或多个键所对应的值为 null。。但是在 HashTable 中 put 进的键值只要有⼀个 null，直接抛出NullPointerException。
4. 初始容量⼤⼩和每次扩充容量⼤⼩的不同 ： ①创建时如果不指定容量初始值，Hashtable 默认的初始⼤⼩为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化⼤⼩为16。之后每次扩充，容量变为原来的2倍。②创建时如果给定了容量初始值，那么 Hashtable 会直接使⽤你给定的⼤⼩，⽽ HashMap 会将其扩充为2的幂次⽅⼤⼩（HashMap 中的 tableSizeFor() ⽅法保证，下⾯给出了源代码）。也就是说 HashMap 总是使⽤2的幂作为哈希表的⼤⼩,后⾯会介绍到为什么是2的幂次⽅。
5. 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了᫾⼤的变化，当链表⻓度⼤于阈值（默认为8）时，将链表转化为红⿊树，以减少搜索时间。Hashtable 没有这样的机制。

HashMap 中带有初始容量的构造函数：

public HashMap(int initialCapacity, float loadFactor) {

if (initialCapacity < 0)

throw new IllegalArgumentException(“Illegal initialcapacity: ” +initialCapacity);

if (initialCapacity > MAXIMUM_CAPACITY)

initialCapacity = MAXIMUM_CAPACITY;

if (loadFactor äã 0 || Float.isNaN(loadFactor))

throw new IllegalArgumentException(“Illegal load factor: ” +loadFactor);

this.loadFactor = loadFactor;

this.threshold = tableSizeFor(initialCapacity);

}

public HashMap(int initialCapacity) {

this(initialCapacity, DEFAULT_LOAD_FACTOR);

}

下⾯这个⽅法保证了 HashMap 总是使⽤2的幂作为哈希表的⼤⼩。

static final int tableSizeFor(int cap) {

int n = cap – 1;

n |= n j>k 1;

n |= n j>k 2;

n |= n j>k 4;

n |= n j>k 8;

n |= n j>k 16;

return (n < 0) ? 1 : (n åã MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY: n + 1;

}

6.HashMap 和 HashSet区别

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

7.HashSet如何检查重复

当你把对象加⼊ HashSet 时，HashSet会先计算对象的 hashcode 值来判断对象加⼊的位置，同时也会与其他加⼊的对象的hashcode值作⽐᫾，如果没有相符的hashcode，HashSet会假设对象没有重复出现。但是如果发现有相同hashcode值的对象，这时会调⽤ equals（） ⽅法来检查hashcode相等的对象是否真的相同。如果两者相同，HashSet就不会让加⼊操作成功。（摘⾃我的Java启蒙书《Head fistjava》第⼆版）

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

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

==与equals的区别:

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

8.HashMap的底层实现

JDK1.8之前

JDK1.8 之前 HashMap 底层是 数组和链表 结合在⼀起使⽤也就是 链表散列。HashMap 通过 key 的hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n – 1) & hash 判断当前元素存放的位置（这⾥的 n 指的是数组的⻓度），如果当前位置存在元素的话，就判断该元素与要存⼊的元素的 hash值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash ⽅法。使⽤ hash ⽅法也就是扰动函数是为了防⽌⼀些实现⽐较差的 hashCode() ⽅法 换句话说使⽤扰动函数之后可以减少碰撞。

JDK 1.8 HashMap 的 hash ⽅法源码:

JDK 1.8 的 hash⽅法 相⽐于 JDK 1.7 hash ⽅法更加简化，但是原理不变。

static final int hash(Object key) {

int h;

// key.hashCode()：返回散列值也就是hashcode

// ^ ：按位异或

// >>>: ⽆符号右移，忽略符号位，空位都以0补⻬

return (key WX null) ? 0 : (h = key.hashCode()) ^ (h j>k 16);

}

对⽐⼀下 JDK1.7的 HashMap 的 hash ⽅法源码

static int hash(int h) {

h ^= (h j>k 20) ^ (h j>k 12);

return h ^ (h >>> 7) ^ (h >>> 4);

}

相⽐于 JDK1.8 的 hash ⽅法 ，JDK 1.7 的 hash ⽅法的性能会稍差⼀点点，因为毕竟扰动了 4 次。所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建⼀个链表数组，数组中每⼀格就是⼀个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

JDK1.8之后

相⽐于之前的版本， JDK1.8之后在解决哈希冲突时有了᫾⼤的变化，当链表⻓度⼤于阈值（默认为8）时，将链表转化为红⿊树，以减少搜索时间。

TreeMap、TreeSet以及JDK1.8之后的HashMap底层都⽤到了红⿊树。红⿊树就是为了解决⼆叉查找树的缺陷，因为⼆叉查找树在某些情况下会退化成⼀个线性结构。

推荐阅读：《Java 8系列之重新认识HashMap》 ：https://zhuanlan.zhihu.com/p/21673805

9.HashMap 的⻓度为什么是2的幂次⽅

为了能让 HashMap 存取⾼效，尽量᫾少碰撞，也就是要尽量把数据分配均匀。我们上⾯也讲到了过了，Hash 值的范围值-2147483648到2147483647，前后加起来⼤概40亿的映射空间，只要哈希函数映射得比较均匀松散，⼀般应⽤是很难出现碰撞的。但问题是⼀个40亿⻓度的数组，内存是放不下的。所以这个散列值是不能直接拿来⽤的。⽤之前还要先做对数组的⻓度取模运算，得到的余数才能⽤来要存放的位置也就是对应的数组下标。这个数组下标的计算⽅法是“ (n – 1) & hash ”。（n代表数组⻓度）。这也就解释了 HashMap 的⻓度为什么是2的幂次⽅。

这个算法应该如何设计呢？

我们⾸先可能会想到采⽤%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是2的幂次则等价于与其除数减⼀的与(&)操作（也就是说 hash%lengthdehash&(length-1)的前提是 length 是2的n 次⽅；）。” 并且 采⽤⼆进制位操作 &，相对于%能够提⾼运算效率，这就解释了 HashMap 的⻓度为什么是2的幂次⽅。

10.HashMap 多线程操作导致死循环问题

主要原因在于 并发下的Rehash 会造成元素之间会形成⼀个循环链表。不过，jdk 1.8 后解决了这个问题，但是还是不建议在多线程下使⽤ HashMap,因为多线程下使⽤ HashMap 还是会存在其他问题⽐如数据丢失。并发环境下推荐使⽤ ConcurrentHashMap 。

从前我们的Java代码因为一些原因使用了HashMap这个东西，但是当时的程序是单线程的，一切都没有问题。后来，我们的程序性能有问题，所以需要变成多线程的，于是，变成多线程后到了线上，发现程序经常占了100%的CPU，查看堆栈，你会发现程序都Hang在了HashMap.get()这个方法上了，重启程序后问题消失。但是过段时间又会来。而且，这个问题在测试环境里可能很难重现。

我们简单的看一下我们自己的代码，我们就知道HashMap被多个线程操作。而Java的文档说HashMap是非线程安全的，应该用ConcurrentHashMap。

Hash表数据结构

我需要简单地说一下HashMap这个经典的数据结构。

HashMap通常会用一个指针数组（假设为table[]）来做分散所有的key，当一个key被加入时，会通过Hash算法通过key算出这个数组的下标i，然后就把这个<key, value>插到table[i]中，如果有两个不同的key被算在了同一个i，那么就叫冲突，又叫碰撞，这样会在table[i]上形成一个链表。

我们知道，如果table[]的尺寸很小，比如只有2个，如果要放进10个keys的话，那么碰撞非常频繁，于是一个O(1)的查找算法，就变成了链表遍历，性能变成了O(n)，这是Hash表的缺陷

所以，Hash表的尺寸和容量非常的重要。一般来说，Hash表这个容器当有数据要插入时，都会检查容量有没有超过设定的thredhold，如果超过，需要增大Hash表的尺寸，但是这样一来，整个Hash表里的无素都需要被重算一遍。这叫rehash，这个成本相当的大。相信大家对这个基础知识已经很熟悉了。

HashMap的rehash源代码

下面，我们来看一下Java的HashMap的源代码。

Put一个Key,Value对到Hash表中：

public V put(K key, V value)
{
    ......
    //算Hash值
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    //如果该key已被插入，则替换掉旧的value （链接操作）
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    //该key不存在，需要增加一个结点
    addEntry(hash, key, value, i);
    return null;
}

检查容量是否超标

void addEntry(int hash, K key, V value, int bucketIndex)
{
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    //查看当前的size是否超过了我们设定的阈值threshold，如果超过，需要resize
    if (size++ >= threshold)
        resize(2 * table.length);
}

新建一个更大尺寸的hash表，然后把数据从老的Hash表中迁移到新的Hash表中。

void resize(int newCapacity)
{
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    ......
    //创建一个新的Hash Table
    Entry[] newTable = new Entry[newCapacity];
    //将Old Hash Table上的数据迁移到New Hash Table上
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

迁移的源代码，注意高亮处：

void transfer(Entry[] newTable)
{
    Entry[] src = table;
    int newCapacity = newTable.length;
    //下面这段代码的意思是：
    //  从OldTable里摘一个元素出来，然后放到NewTable中
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

好了，这个代码算是比较正常的。而且没有什么问题。

正常的ReHash的过程

画了个图做了个演示。

• 我假设了我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。
• 最上面的是old hash 表，其中的Hash表的size=2, 所以key = 3, 7, 5，在mod 2以后都冲突在table[1]这里了。
• 接下来的三个步骤是Hash表 resize成4，然后所有的<key,value> 重新rehash的过程

并发下的Rehash

假设我们有两个线程。我用红色和浅蓝色标注了一下。我们再回头看一下我们的 transfer代码中的这个细节：

do {
    Entry<K,V> next = e.next; // <--假设线程一执行到这里就被调度挂起了
    int i = indexFor(e.hash, newCapacity);
    e.next = newTable[i];
    newTable[i] = e;
    e = next;
} while (e != null);

而我们的线程二执行完成了。于是我们有下面的这个样子。

注意，因为Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的链表。我们可以看到链表的顺序被反转后。

线程一被调度回来执行。

• 先是执行 newTalbe[i] = e;
• 然后是e = next，导致了e指向了key(7)，
• 而下一次循环的next = e.next导致了next指向了key(3)

线程一接着工作。把key(7)摘下来，放到newTable[i]的第一个，然后把e和next往下移。

环形链接出现。

e.next = newTable[i] 导致  key(3).next 指向了 key(7)

注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。

于是，当我们的线程一调用到，HashTable.get(11)时，悲剧就出现了——Infinite Loop。

11.ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的⽅式上不同。

• 底层数据结构： JDK1.7的 ConcurrentHashMap 底层采⽤ 分段的数组+链表 实现，JDK1.8 采⽤的数据结构跟HashMap1.8的结构⼀样，数组+链表/红⿊⼆叉树。Hashtable 和 JDK1.8 之前的HashMap 的底层数据结构类似都是采⽤ 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突⽽存在的；
• 实现线程安全的⽅式（重要）： ① 在JDK1.7的时候，ConcurrentHashMap（分段锁） 对整个桶数组进⾏了分割分段(Segment)，每⼀把锁只锁容器其中⼀部分数据，多线程访问容器⾥不同数据段的数据，就不会存在锁竞争，提⾼并发访问率。 到了 JDK1.8 的时候已经摒弃了Segment的概念，⽽是直接⽤ Node 数组+链表+红⿊树的数据结构来实现，并发控制使⽤ synchronized 和CAS 来操作。（JDK1.6以后 对 synchronized锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在JDK1.8中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；② Hashtable(同⼀把锁) :使⽤ synchronized 来保证线程安全，效率⾮常低下。当⼀个线程访问同步⽅法时，其他线程也访问同步⽅法，可能会进⼊阻塞或轮询状态，如使⽤ put 添加元素，另⼀个线程不能使⽤ put 添加元素，也不能使⽤ get，竞争会越来越激烈效率越低。

两者的对⽐图：

JDK1.7的ConcurrentHashMap：

JDK1.8的ConcurrentHashMap（TreeBin: 红⿊⼆叉树节点 Node: 链表节点）：

12.ConcurrentHashMap线程安全的具体实现⽅式/底层具体实现

JDK1.7（上⾯有示意图）

⾸先将数据分为⼀段⼀段的存储，然后给每⼀段数据配⼀把锁，当⼀个线程占⽤锁访问其中⼀个段数据时，其他段的数据也能被其他线程访问。

ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。

Segment 实现了 ReentrantLock,所以 Segment 是⼀种可重⼊锁，扮演锁的⻆⾊。HashEntry ⽤于存储键值对数据。

static class Segment<K,V> extends ReentrantLock implements Serializable
{
}

⼀个 ConcurrentHashMap ⾥包含⼀个 Segment 数组。Segment 的结构和HashMap类似，是⼀种数组和链表结构，⼀个 Segment 包含⼀个 HashEntry 数组，每个 HashEntry 是⼀个链表结构的元素，每个Segment 守护着⼀个HashEntry数组⾥的元素，当对 HashEntry 数组的数据进⾏修改时，必须⾸先获得对应的 Segment的锁。

JDK1.8 （上⾯有示意图）

ConcurrentHashMap取消了Segment分段锁，采⽤CAS和synchronized来保证并发安全。数据结构跟HashMap1.8的结构类似，数组+链表/红⿊⼆叉树。Java 8在链表⻓度超过⼀定阈值（8）时将链表（寻址时间复杂度为O(N)）转换为红⿊树（寻址时间复杂度为O(log(N))）

synchronized只锁定当前链表或红⿊⼆叉树的⾸节点，这样只要hash不冲突，就不会产⽣并发，效率⼜提升N倍。

13.comparable 和 Comparator的区别

• comparable接⼝实际上是出⾃java.lang包 它有⼀个 compareTo(Object obj) ⽅法⽤来排序
• comparator接⼝实际上是出⾃ java.util 包它有⼀个 compare(Object obj1, Objectobj2) ⽅法⽤来排序

⼀般我们需要对⼀个集合使⽤⾃定义排序时，我们就要重写 compareTo() ⽅法或 compare() ⽅法，当我们需要对某⼀个集合实现两种排序⽅式，⽐如⼀个song对象中的歌名和歌⼿名分别采⽤⼀种排序⽅法的话，我们可以重写 compareTo() ⽅法和使⽤⾃制的Comparator⽅法或者以两个Comparator来实现歌名排序和歌星名排序，第⼆种代表我们只能使⽤两个参数版的 Collections.sort() .

Comparator定制排序

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);
// void sort(List list),按⾃然排序的升序排序
Collections.sort(arrayList);
System.out.println(“Collections.sort(arrayList):”);
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);

Output:

原始数组:
[-1, 3, 3, -5, 7, 4, -9, -7]
Collections.reverse(arrayList):
[-7, -9, 4, 7, -5, 3, 3, -1]
Collections.sort(arrayList):
[-9, -7, -5, -1, 3, 3, 4, 7]
定制排序后：
[7, 4, 3, 3, -1, -5, -7, -9]

重写compareTo⽅法实现按年龄来排序

// person对象没有实现Comparable接⼝，所以必须实现，这样才不会出错，才可
以使treemap中的数据按顺序排列
// 前⾯⼀个例⼦的String类已经默认实现了Comparable接⼝，详细可以查看
String类的API⽂档，另外其他
// 像Integer类等都已经实现了Comparable接⼝，所以不需要另外实现了
public class Person implements Comparable<Person> {
private String name;
private int age;
public Person(String name, int age) {
super();
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
/**
* TODO重写compareTo⽅法实现按年龄来排序
*/
@Override
public int compareTo(Person o) {
// TODO Auto-generated method stub
if (this.age > o.getAge()) {
return 1;
} else if (this.age < o.getAge()) {
return -1;
}
return age;
}
}

public static void main(String[] args) {
TreeMap<Person, String> pdata = new TreeMap<Person, String>();
pdata.put(new Person(“张三”, 30), “zhangsan”);
pdata.put(new Person(“李四”, 20), “lisi”);
pdata.put(new Person(“王五”, 10), “wangwu”);
pdata.put(new Person(“⼩红”, 5), “xiaohong”);
// 得到key的值的同时得到key所对应的值
Set<Person> keys = pdata.keySet();
for (Person key : keys) {
System.out.println(key.getAge() + “-” + key.getName());
}
}

Output：

5-⼩红
10-王五
20-李四
30-张三

14.集合框架底层数据结构总结

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： 红⿊树（⾃平衡的排序⼆叉树）

15.如何选⽤集合?

主要根据集合的特点来选⽤，⽐如我们需要根据键值获取到元素值时就选⽤Map接⼝下的集合，需要排序时选择TreeMap,不需要排序时就选择HashMap,需要保证线程安全就选⽤ConcurrentHashMap.当我们只需要存放元素值时，就选择实现Collection接⼝的集合，需要保证元素唯⼀时选择实现Set接⼝的集合⽐如TreeSet或HashSet，不需要就选择实现List接⼝的⽐如ArrayList或LinkedList，然后再根据实现这些接⼝的集合的特点来选⽤。