Java集合类学习 | Laqudee.Z

1、说说list、set、map三者的区别？

list：list接口存储一组不唯一（可以有多个元素引用相同的对象），有序的对象
set：不允许重复的集合，不会有多个元素引用相同的对象
map：使用键值对存储，map会维护与Key有关联的值。两个Key可以引用相同的对象，但Key不能重复，典型的Key是String类型，但也可以是任何对象。

2、arraylist与linkedlist区别？

1、是否保证线程安全：arraylist和linkedlist都是不同步的，也就是不保证线程安全；
2、底层数据结构：arraylist底层使用的是Object数组；LinkedList底层使用的是双向链表数据结构；
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更多的空间（因为要存放直接后继和直接前驱以及数据）

3、RandomAccess接口

public interface RandomAccess{

}

源码中，RandomAcccess接口什么都没有定义，所以RandomAccess接口不过是一个标识。标识实现这个接口的类具有随机访问功能。

在binarySearch()方法中，它要判断传入的list是否是RandomAccess的实例，如果是，调用indexBinarySearch()方法，if not，调用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 接口才具有快速随机访问功能的！

4、list的遍历方式选择

实现RandomAccess接口的list，优先选择普通for循环，其次for each；
为实现RandomAccess接口的list，优先选择iterator遍历（for each遍历底层也是通过iterator实现的），大size的数据，千万不要使用for循环。

5、双向链表和双向循环链表

双向链表：包含两个指针，一个prev指向前一个节点，一个next指向后一个节点。
双向循环链表：最后一个节点的 next 指向head，而 head 的prev指向最后一个节点，构成一个环。

6、arraylist与vector区别？为什么要用arraylist取代vector？

vector类的所有方法都是同步的，可以由两个线程安全地访问一个vector对象，但是一个线程访问vector的话代码要在同步操作上耗费大量的时间。
Arraylist不是同步的，所以在不需要保证线程安全时使用arraylist

7、hashmap和hashtable的区别？

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

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

public HashMap(int initialCapacity, float loadFactor){
    if (initialCapacity < 0){
        throw new IllegalArgumentException("Illegal initial capacity: " + 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的幂作为哈希表的大小。

/**
* 返回一个以2为底数的指数为capacity的值
*/
static final int tableSizeFor(int cap){
    int n = cap - 1;
    n |= n >> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

9、HashMap和HashSet区别

在hashSet源码中，HashSet底层是基于HashMap实现的。
HashSet 的源码非常非常少，因为除了 clone()、writeObject()、readObject()是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

10、hashSet如何检查重复

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

11、hashcode() 和 equals()方法的相关规定

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

12、==与equals()区别？

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

13、hashMap的底层实现

JDK1.8之前
- HashMap 底层是数组和链表结合在一起使用也就是链表散列。HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。
- 扰动函数指的是hashMap的hash方法。使用hash方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法换句话说使用扰动函数之后可以减少碰撞。
JDK1.8 hashMap的hash方法源码：
- jdk1.8的hash方法相比于jdk1.7hash方法更加简化，但原理不变

static final int hash(Object key){
    int h;
    //key.hashCode():return 散列值也就是hashcode
    //^ :按位异或
    //>>>:无符号右移，空位都补零
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

对比以下JDK1.7的hashMap的hash方法

static int hash(int h){
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).

    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
 //相比于 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。
}

14、拉链法

将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

拉链法

15、HashMap的底层实现

JDK1.8之后
- 相比于之前的版本， JDK1.8之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。
- TreeMap、TreeSet以及JDK1.8之后的HashMap底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。
- 推荐阅读open in new window

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

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。我们上面也讲到了过了，Hash 值的范围值-2147483648到2147483647，前后加起来大概40亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个40亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“ (n - 1) & hash”。（n代表数组长度）。这也就解释了 HashMap 的长度为什么是2的幂次方。
这个算法应该如何设计？
- 我们首先可能会想到采用%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 并且采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是2的幂次方。

17、HashMap多线程操作导致死循环问题

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

详细查看open in new window

18、ConcurrentHashMap 和 HashTable的区别？

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

底层数据结构：
- JDK1.7的concurrentHashMap底层采用分段的数组+链表实现
- Jdk1.8采用的数据结构跟Hashmap的底层数据结构一样，数组+链表/红黑二叉树
- 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，竞争会越来越激烈效率越低。

hashtable

JDK1.7的concurrenthashmap

JDK1.8的concurrenthashmap concurrenthashmap-1.8

19、集合的选用

主要是根据集合的特点和实际应用场景来选用

需要根据键值获取到元素值时就选用Map接口下的集合；
需要排序时，选择TreeMap；
不需要排序时就选择HashMap;
需要保证线程安全就选用concurrenthashmap;
只需要存放元素值时，选择实现Collection接口的集合；
需要保证元素唯一是选择实现set接口的集合比如TreesSet或hashSet；
不需要就选择实现List接口的比如ArrayList或LinkedList；然后再根据实现这些接口的集合的特点来选用。

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

Collection

1)List
- Arraylist :Object数组
- Vector：Object数组
- LinkedList：双向链表（JDK1.6之前为循环链表，JDK1.7取消循环）
2）Set
- HashSet（无序，唯一）：基于HashMap实现，底层采用HashMaP来保存元素
- LinkedHashSet：LinkedHashSet继承HashSet，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 Hashmap 实现一样，不过还是有一点点区别的。
- TreeSet（有序，唯一）：红黑树（自平衡的排序二叉树）
3）Map
- HashMap： JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间
- LinkedHashMap： LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
- Hashtable：数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的
- TreeMap：红黑树（自平衡的排序二叉树）

20、comparable 和comparator的区别？

comparable接口实际上是出自java.lang包它有一个 compareTo(Object obj)方法用来排序
comparator接口实际上是出自 java.util 包它有一个compare(Object obj1, Object obj2)方法用来排序

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

本文是基于小专栏open in new window教程编写的学习笔记，只做个人知识库使用！首次发布于 YunLongBlogopen in new window, 作者 Laqudeeopen in new window ,转载请保留原文链接.

# 1、说说list、set、map三者的区别？

# 2、arraylist与linkedlist区别？

# 3、RandomAccess接口

# 4、list的遍历方式选择

# 5、双向链表和双向循环链表

# 6、arraylist与vector区别？为什么要用arraylist取代vector？

# 7、hashmap和hashtable的区别？

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

# 9、HashMap和HashSet区别

# 10、hashSet如何检查重复

# 11、hashcode() 和 equals()方法的相关规定

# 12、==与equals()区别？

# 13、hashMap的底层实现

# 14、拉链法

# 15、HashMap的底层实现

# 16、HashMap的长度为什么是2的幂次方？

# 17、HashMap多线程操作导致死循环问题

# 18、ConcurrentHashMap 和 HashTable的区别？

# 19、集合的选用

# 集合框架底层数据结构总结

# 20、comparable 和comparator的区别？