【Java】Java常见面试题(二）JAVA集合类

快来打我* 2022-06-18 09:00 196阅读 0赞

# JAVA集合类图： #

![20150421143615036][]

#     #

# 1. hashmap原理,与hashtable区别 #

Java中的HashMap是以键值对(key-value)的形式存储元素的。HashMap需要一个hash函数，它使用hashCode()和equals()方法来向集合/从集合添加和检索元素。当调用put()方法的时候，HashMap会计算key的hash值，然后把键值对存储在集合中合适的索引上。如果key已经存在了，value会被更新成新值。HashMap的一些重要的特性是它的容量(capacity)，负载因子(load factor)和扩容极限(threshold resizing)。

附上put的源码：

**\[java\]**  [view plain][]   [copy][view plain]

1.  **public** V put(K key, V value) \{  
2.      // HashMap允许存放null键和null值。  
3.      // 当key为null时，调用putForNullKey方法，将value放置在数组第一个位置。  
4.      **if** (key == **null**)  
5.          **return** putForNullKey(value);  
6.      // 根据key的keyCode重新计算hash值。  
7.      **int** hash = hash(key.hashCode());  
8.      // 搜索指定hash值在对应table中的索引。  
9.      **int** i = indexFor(hash, table.length);  
10.     // 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。  
11.     **for** (Entry<K,V> e = table\[i\]; e != **null**; e = e.next) \{  
12.         Object k;  
13.         **if** (e.hash == hash && ((k = e.key) == key || key.equals(k))) \{  
14.             V oldValue = e.value;  
15.             e.value = value;  
16.             e.recordAccess(**this**);  
17.             **return** oldValue;  
18.         \}  
19.     \}  
20.     // 如果i索引处的Entry为null，表明此处还没有Entry。  
21.     modCount++;      //这个mod是用于线程安全的，下文有讲述  
22.     // 将key、value添加到i索引处。  
23.     addEntry(hash, key, value, i);  
24.     **return** **null**;  
25. \}

addEntry:

**\[java\]**  [view plain][]   [copy][view plain]

1.  **void** addEntry(**int** hash, K key, V value, **int** bucketIndex) \{  
2.      // 获取指定 bucketIndex 索引处的 Entry   
3.      Entry<K,V> e = table\[bucketIndex\];  
4.      // <strong><span style="color:\#ff0000;">将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry  </span></strong>  
5.      table\[bucketIndex\] = **new** Entry<K,V>(hash, key, value, e);  
6.      // 如果 Map 中的 key-value 对的数量超过了极限  
7.      **if** (size++ >= threshold)  
8.      // 把 table 对象的长度扩充到原来的2倍。  
9.          resize(2 \* table.length);  
10. \}

更详细的原理请看:  http://zhangshixi.iteye.com/blog/672697

## 区别:   ##

## http://blog.csdn.net/shohokuf/article/details/3932967 ##

*  HashMap允许键和值是null，而Hashtable不允许键或者值是null。
 *  Hashtable是同步的，而HashMap不是。因此，HashMap更适合于单线程环境，而Hashtable适合于多线程环境。
 *  HashMap提供了可供应用迭代的键的集合，因此，HashMap是快速失败（具体看下文)的。另一方面，Hashtable提供了对键的列举(Enumeration)。
    
     *  一般认为Hashtable是一个遗留的类。

# 2.让hashmap变成线程安全的两种方法 #

方法一:通过Collections.synchronizedMap()返回一个新的Map,这个新的map就是线程安全的. 这个要求大家习惯基于接口编程,因为返回的并不是HashMap,而是一个Map的实现.

**\[java\]**  [view plain][]   [copy][view plain]

1.  Map map = Collections.synchronizedMap(**new** HashMap());

方法二:使用ConcurrentHashMap

**\[java\]**  [view plain][]   [copy][view plain]

1.  Map<String, Integer> concurrentHashMap = **new** ConcurrentHashMap<String, Integer>();

# 3.ArrayList也是非线程安全的 #

一个 ArrayList 类，在添加一个元素的时候，它可能会有两步来完成：1. 在 Items\[Size\] 的位置存放此元素；2. 增大 Size 的值。  
在单线程运行的情况下，如果 Size = 0，添加一个元素后，此元素在位置 0，而且 Size=1；  
而如果是在多线程情况下，比如有两个线程，线程 A 先将元素存放在位置 0。但是此时 CPU 调度线程A暂停，线程 B 得到运行的机会。线程B也将元素放在位置0，（因为size还未增长），完了之后，两个线程都是size++，结果size变成2，而只有 items\[0\]有元素。  
util.concurrent包也提供了一个线程安全的ArrayList替代者CopyOnWriteArrayList。

# 4. hashset原理 #

基于 HashMap 实现的， HashSet 底层使用 HashMap 来保存所有元素（**看了源码之后我发现就是用hashmap的keyset来保存的**），因此 HashSet  的实现比较简单，相关 HashSet 的操作，基本上都是直接调用底层 HashMap 的相关方法来完成，  HashSet 的源代码如下：

**\[java\]**  [view plain][]   [copy][view plain]

1.  **public** **class** HashSet<E>  
2.      **extends** AbstractSet<E>  
3.      **implements** Set<E>, Cloneable, java.io.Serializable  
4.  \{  
5.      **static** **final** **long** serialVersionUID = -5024744406713321676L;  
6.    
7.      // 底层使用HashMap来保存HashSet中所有元素。  
8.      **private** **transient** HashMap<E,Object> map;  
9.        
10.     // 定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final。  
11.     **private** **static** **final** Object PRESENT = **new** Object();  
12.   
13.     /\*\* 
14.      \* 默认的无参构造器，构造一个空的HashSet。 
15.      \*  
16.      \* 实际底层会初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75。 
17.      \*/  
18.     **public** HashSet() \{  
19.     map = **new** HashMap<E,Object>();  
20.     \}  
21.   
22.     /\*\* 
23.      \* 构造一个包含指定collection中的元素的新set。 
24.      \* 
25.      \* 实际底层使用默认的加载因子0.75和足以包含指定 
26.      \* collection中所有元素的初始容量来创建一个HashMap。 
27.      \* @param c 其中的元素将存放在此set中的collection。 
28.      \*/  
29.     **public** HashSet(Collection<? **extends** E> c) \{  
30.     map = **new** HashMap<E,Object>(Math.max((**int**) (c.size()/.75f) + 1, 16));  
31.     addAll(c);  
32.     \}  
33.   
34.     /\*\* 
35.      \* 以指定的initialCapacity和loadFactor构造一个空的HashSet。 
36.      \* 
37.      \* 实际底层以相应的参数构造一个空的HashMap。 
38.      \* @param initialCapacity 初始容量。 
39.      \* @param loadFactor 加载因子。 
40.      \*/  
41.     **public** HashSet(**int** initialCapacity, **float** loadFactor) \{  
42.     map = **new** HashMap<E,Object>(initialCapacity, loadFactor);  
43.     \}  
44.   
45.     /\*\* 
46.      \* 以指定的initialCapacity构造一个空的HashSet。 
47.      \* 
48.      \* 实际底层以相应的参数及加载因子loadFactor为0.75构造一个空的HashMap。 
49.      \* @param initialCapacity 初始容量。 
50.      \*/  
51.     **public** HashSet(**int** initialCapacity) \{  
52.     map = **new** HashMap<E,Object>(initialCapacity);  
53.     \}  
54.   
55.     /\*\* 
56.      \* 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。 
57.      \* 此构造函数为包访问权限，不对外公开，实际只是是对LinkedHashSet的支持。 
58.      \* 
59.      \* 实际底层会以指定的参数构造一个空LinkedHashMap实例来实现。 
60.      \* @param initialCapacity 初始容量。 
61.      \* @param loadFactor 加载因子。 
62.      \* @param dummy 标记。 
63.      \*/  
64.     HashSet(**int** initialCapacity, **float** loadFactor, **boolean** dummy) \{  
65.     map = **new** LinkedHashMap<E,Object>(initialCapacity, loadFactor);  
66.     \}  
67.   
68.     /\*\* 
69.      \* 返回对此set中元素进行迭代的迭代器。返回元素的顺序并不是特定的。 
70.      \*  
71.      \* 底层实际调用底层HashMap的keySet来返回所有的key。 
72.      \* 可见HashSet中的元素，只是存放在了底层HashMap的key上， 
73.      \* value使用一个static final的Object对象标识。 
74.      \* @return 对此set中元素进行迭代的Iterator。 
75.      \*/  
76.     **public** Iterator<E> iterator() \{  
77.     **return** map.keySet().iterator();  
78.     \}  
79.   
80.     /\*\* 
81.      \* 返回此set中的元素的数量（set的容量）。 
82.      \* 
83.      \* 底层实际调用HashMap的size()方法返回Entry的数量，就得到该Set中元素的个数。 
84.      \* @return 此set中的元素的数量（set的容量）。 
85.      \*/  
86.     **public** **int** size() \{  
87.     **return** map.size();  
88.     \}  
89.   
90.     /\*\* 
91.      \* 如果此set不包含任何元素，则返回true。 
92.      \* 
93.      \* 底层实际调用HashMap的isEmpty()判断该HashSet是否为空。 
94.      \* @return 如果此set不包含任何元素，则返回true。 
95.      \*/  
96.     **public** **boolean** isEmpty() \{  
97.     **return** map.isEmpty();  
98.     \}  
99.   
100.     /\*\* 
101.      \* 如果此set包含指定元素，则返回true。 
102.      \* 更确切地讲，当且仅当此set包含一个满足(o==null ? e==null : o.equals(e)) 
103.      \* 的e元素时，返回true。 
104.      \* 
105.      \* 底层实际调用HashMap的containsKey判断是否包含指定key。 
106.      \* @param o 在此set中的存在已得到测试的元素。 
107.      \* @return 如果此set包含指定元素，则返回true。 
108.      \*/  
109.     **public** **boolean** contains(Object o) \{  
110.     **return** map.containsKey(o);  
111.     \}  
112.   
113.     /\*\* 
114.      \* 如果此set中尚未包含指定元素，则添加指定元素。 
115.      \* 更确切地讲，如果此 set 没有包含满足(e==null ? e2==null : e.equals(e2)) 
116.      \* 的元素e2，则向此set 添加指定的元素e。 
117.      \* 如果此set已包含该元素，则该调用不更改set并返回false。 
118.      \* 
119.      \* 底层实际将将该元素作为key放入HashMap。 
120.      \* 由于HashMap的put()方法添加key-value对时，当新放入HashMap的Entry中key 
121.      \* 与集合中原有Entry的key相同（hashCode()返回值相等，通过equals比较也返回true）， 
122.      \* 新添加的Entry的value会将覆盖原来Entry的value，但key不会有任何改变， 
123.      \* 因此如果向HashSet中添加一个已经存在的元素时，新添加的集合元素将不会被放入HashMap中， 
124.      \* 原来的元素也不会有任何改变，这也就满足了Set中元素不重复的特性。 
125.      \* @param e 将添加到此set中的元素。 
126.      \* @return 如果此set尚未包含指定元素，则返回true。 
127.      \*/  
128.     **public** **boolean** add(E e) \{  
129.     **return** map.put(e, PRESENT)==**null**;  
130.     \}  
131.   
132.     /\*\* 
133.      \* 如果指定元素存在于此set中，则将其移除。 
134.      \* 更确切地讲，如果此set包含一个满足(o==null ? e==null : o.equals(e))的元素e， 
135.      \* 则将其移除。如果此set已包含该元素，则返回true 
136.      \* （或者：如果此set因调用而发生更改，则返回true）。（一旦调用返回，则此set不再包含该元素）。 
137.      \* 
138.      \* 底层实际调用HashMap的remove方法删除指定Entry。 
139.      \* @param o 如果存在于此set中则需要将其移除的对象。 
140.      \* @return 如果set包含指定元素，则返回true。 
141.      \*/  
142.     **public** **boolean** remove(Object o) \{  
143.     **return** map.remove(o)==PRESENT;  
144.     \}  
145.   
146.     /\*\* 
147.      \* 从此set中移除所有元素。此调用返回后，该set将为空。 
148.      \* 
149.      \* 底层实际调用HashMap的clear方法清空Entry中所有元素。 
150.      \*/  
151.     **public** **void** clear() \{  
152.     map.clear();  
153.     \}  
154.   
155.     /\*\* 
156.      \* 返回此HashSet实例的浅表副本：并没有复制这些元素本身。 
157.      \* 
158.      \* 底层实际调用HashMap的clone()方法，获取HashMap的浅表副本，并设置到HashSet中。 
159.      \*/  
160.     **public** Object clone() \{  
161.         **try** \{  
162.             HashSet<E> newSet = (HashSet<E>) **super**.clone();  
163.             newSet.map = (HashMap<E, Object>) map.clone();  
164.             **return** newSet;  
165.         \} **catch** (CloneNotSupportedException e) \{  
166.             **throw** **new** InternalError();  
167.         \}  
168.     \}  
169. \}

# 5. ArrayList,Vector, LinkedList的存储性能和特性 #

**ArrayList 和Vector都是使用数组方式存储数据**，此数组元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢**，Vector由于使用了synchronized方法（线程安全），通常性能上较ArrayList差**，而**LinkedList使用双向链表实现存储**，按序号索引数据需要进行前向或后向遍历，但是插入数据时只需要记录本项的前后项即可，所以插入速度较快。

# 6.快速失败(fail-fast)和安全失败(fail-safe) #

Fail-Fast机制：

我们知道[Java][].util.HashMap不是线程安全的，因此如果**在使用迭代器的过程中**有其他线程修改了map，那么将抛ConcurrentModificationException，这就是所谓fail-fast策略。

这一策略在源码中的实现是通过modCount域，modCount顾名思义就是修改次数，对HashMap内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。

Java代码   ![收藏代码][icon_star.png]

1.  HashIterator() \{  
2.      expectedModCount = modCount;  
3.      **if** (size > 0) \{ // advance to first entry  
4.      Entry\[\] t = table;  
5.      **while** (index < t.length && (next = t\[index++\]) == **null**)  
6.          ;  
7.      \}  
8.  \}

在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map：

注意到modCount声明为volatile，保证线程之间修改的可见性。

Java代码   ![收藏代码][icon_star.png]

1.  **final** Entry<K,V> nextEntry() \{     
2.      **if** (modCount != expectedModCount)     
3.          **throw** **new** ConcurrentModificationException();

在HashMap的API中指出：

由所有HashMap类的“collection 视图方法”所返回的迭代器都是快速失败的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器本身的 remove 方法，其他任何时间任何方式的修改，迭代器都将抛出**ConcurrentModificationException**。因此，面对并发的修改，迭代器很快就会完全失败，而不冒在将来不确定的时间发生任意不确定行为的风险。

注意，迭代器的快速失败行为不能得到保证，一般来说，存在非同步的并发修改时，不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此，**编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。**

Fail-Safe机制：

Iterator的安全失败是**基于对底层集合做拷贝**，因此，它不受源集合上修改的影响。java.util包下面的所有的集合类都是快速失败（一般的集合类)的，而java.util.concurrent包下面的所有的类(比如CopyOnWriteArrayList，ConcurrentHashMap ）都是安全失败的。快速失败的迭代器会抛出ConcurrentModificationException异常，而安全失败的迭代器永远不会抛出这样的异常。

# 7.传递一个集合作为参数给函数时，我们如何能确保函数将无法对其进行修改 #

我们可以创建一个只读集合，使用Collections.unmodifiableCollection作为参数传递给使用它的方法，这将确保任何改变集合的操作将抛出UnsupportedOperationException。

# 8.Collections类的方法们 #

上面说到了很多了collections的方法，我们来深究一下这个类

Collections则是集合类的一个工具类/帮助类，其中提供了一系列**静态方法**，用于对集合中元素进行**排序、搜索以及线程安全**等各种操作。

## 1) 排序(Sort) ##

使用sort方法可以根据元素的自然顺序 对指定列表按升序进行排序。列表中的所有元素都必须实现** Comparable接口**。此列表内的所有元素都必须是使用指定比较器可相互比较的

可以直接Collections.sort(...)

或者可以指定一个比较器，让这个列表遵照在比较器当中所设定的排序方式进行排序，这就提供了更大的灵活性

public static void sort(List l,** Comparator**c)

这个**Comparator同样是一个在java.util包中的接口**。这个接口中有两个方法：int compare(T o1, T o2 )和boolean equals([Object][] obj)

## 2）很多常用的，没必要多讲的方法 ##

**shuffle(Collection)  **：对集合进行随机排序

**binarySearch**(Collection,Object)方法的使用(含义：查找指定集合中的元素，返回所查找元素的索引)

**max**(Collection),max(Collection,Comparator)方法的使用(前者采用Collection内含自然比较法，后者采用Comparator进行比较)

**min**(Collection),min(Collection,Comparator)方法的使用(前者采用Collection内含自然比较法，后者采用Comparator进行比较)。  
**indexOfSubList**(List list,List subList)方法的使用(含义：查找subList在list中首次出现位置的索引)。

**lastIndexOfSubList**(List source,List target)方法的使用与上例方法的使用相同，在此就不做介绍了。  
**replaceAll(**List list,Object old,Object new)方法的使用(含义：替换批定元素为某元素,若要替换的值存在刚返回true,反之返回false)。

以及等等等等。

## 3）我自己看看有哪些方法。 （这一段可以直接参考JAVA API说明  http://www.apihome.cn/api/java/Collections.html ） ##

![20150421143655924][]![20150421143659590][]![20150421143702523][]

除了2)中讲到的一些零碎的，可以看到还分成了checked ,  empty ,  singleton,  synchronized unmodifiable这几类。

checked：2个用途：

返回指定 collection 的一个动态类型安全视图。试图插入一个错误类型的元素将导致立即抛出 ClassCastException。假设在生成动态类型安全视图之前，collection 不包含任何类型不正确的元素，并且所有对该 collection 的后续访问都通过该视图进行，则可以保证 该 collection 不包含类型不正确的元素。

一般的编程语言机制中都提供了编译时（静态）**类型检查**，但是一些未经检查的强制转换可能会使此机制无效。通常这不是一个问题，因为编译器会在所有这类未经检查的操作上发出警告。但有的时候，只进行单独的静态类型检查并不够。例如，假设将 collection 传递给一个第三方库，则库代码不能通过插入一个错误类型的元素来毁坏 collection。

动态类型安全视图的另一个用途是**调试**。假设某个程序运行失败并抛出 ClassCastException，这指示一个类型不正确的元素被放入已参数化 collection 中。不幸的是，该异常可以发生在插入错误元素之后的任何时间，因此，这通常只能提供很少或无法提供任何关于问题真正来源的信息。如果问题是可再现的，那么可以暂时修改程序，使用一个动态类型安全视图来包装该 collection，通过这种方式可快速确定问题的来源。

unmodifiable:

返回指定 集合的不可修改视图。此方法允许模块为用户提供对内部 集合的“只读”访问。在返回的 集合 上执行的查询操作将“读完”指定的集合。试图修改返回的集合（不管是直接修改还是通过其迭代器进行修改）将导致抛出 UnsupportedOperationException。

synchronized：

public static <T> Collection<T> synchronizedCollection(Collection<T> c)

返回指定 collection 支持的同步（线程安全的）collection。为了保证按顺序访问，必须通过返回的 collection 完成 所有对底层实现 collection 的访问。

在返回的 collection 上进行迭代时，用户必须手工在返回的 collection 上进行同步：

Collection c = Collections.synchronizedCollection(myCollection);
         ...
      synchronized(c) {
          Iterator i = c.iterator(); // Must be in the synchronized block
          while (i.hasNext())
             foo(i.next());
      }

empty: (以set 为例，我没看懂到底是干嘛的。。）

public static final <T> Set<T> emptySet()

返回空的 set（不可变的）。此 set 是可序列化的。与  **like-named（找不到关于这个东西的资料。。） **字段不同，此方法是参数化的。

以下示例演示了获得空 set 的类型安全 (type-safe) 方式：

Set<String> s = Collections.emptySet();

# 9.Tree, Hash ,Linked #

再看看这个图。

![20150421143615036][]

**发现set和map的实现分成了 Tree,Hash,和Linked。**

以map为例，来看看这三者的区别.

TreeMap用**红黑树**实现，能够把它保存的记录**根据键排序**，默认是按升序排序，也可以指定排序的比较器。当用Iteraor遍历TreeMap时，得到的记录是排过序的。TreeMap的键和值都不能为空。

HashMap上文有说。

LinkedHashmap：它继承与HashMap、底层使用**哈希表与双向链表**来保存所有元素。其基本操作与父类HashMap相似，它通过重写父类相关的方法，来实现自己的链接列表特性。put方法没有重写，重写了addEntry()。（因为加入的时候要维护好一个双向链表的结构）LinkedHashMap重写了父类HashMap的get方法，实际在调用父类getEntry()方法取得查找的元素后，再判断当排序模式**accessOrder**为true时，记录访问顺序，**将最新访问的元素添加到双向链表的表头，并从原来的位置删除**。由于的链表的增加、删除操作是常量级的，故并不会带来性能的损失(accessOrder是LinkedHashmap中的一个属性，用来判断是否要根据读取顺序来重写调整结构。如果为false，就按照插入的顺序排序，否则按照最新访问的放在链表前面的顺序，以提高性能）。

我个人的理解是：LinedHashMap的作用就是在让经常访问的元素更快的被访问到。用双向链表可以方便地执行链表中元素的插入删除操作。

[20150421143615036]: /images/20220618/f74d152bd6a140ae92e6cc2c183f29b4.png
[view plain]: http://blog.csdn.net/u012422829/article/details/45170157#
[Java]: http://lib.csdn.net/base/javase
[icon_star.png]: /images/20220618/4caa121a80d44a3a97c6b822a1a7e94a.png
[Object]: http://download.oracle.com/javase/7/docs/index.html
[20150421143655924]: https://img-blog.csdn.net/20150421143655924
[20150421143659590]: https://img-blog.csdn.net/20150421143659590
[20150421143702523]: /images/20220618/9a93a7308f934cf6bc4043d11958f8e0.png