面试题-集合

面试题-集合

一 集合

1.HashMap是如何工作

HashMap是一个针对数据结构的键值，每个键都会有相应的值，关键是识别这样的值。HashMap基于hashing（哈希）原理，我们通过put ()和get ()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode ()方法来计算 hashcode，然后找到bucket位置来储存值对象。当获取对象时，通过键对象的 equals ()方法找到正确的键值对，然后返回值对象。HashMap使用LinkedList 来解决碰撞问题，当发生碰撞了，对象将会储存在LinkedList的下一个节点中。 HashMap在每个LinkedList节点中储存键值对对象。

2.ConcurrentHashMap

ConcurrentHashMap被作为故障安全迭代器的一个实例，它允许完整的并发检索和更新。当有大量的并发更新时，ConcurrentHashMap此时可以被使用。这非常类似于Hashtable，但ConcurrentHashMap不锁定整个表来提供并发，所以从这点上ConcurrentHashMap的性能似乎更好一些。所以当有大量更新时ConcurrentHashMap应该被使用

1.ConcurrentHashMap工作原理及实现

ConcurrentHashMap 采用了非常精妙的"分段锁"策略，ConcurrentHashMap 的主干是个 Segment 数组。Segment 继承了 ReentrantLock，所以它就是一种可重入锁（ReentrantLock)。在 ConcurrentHashMap，一个 Segment 就是一个子哈希表，Segment 里维护了一个 HashEntry 数组，并发环境下，对于不同Segment 的数据进行操作是不用考虑锁竞争的。

3.LinkedList和ArrayList区别

LinkedList和ArrayList是另个不同变量列表的实现。ArrayList的优势在于动态的 增长数组，非常适合初始时总长度未知的情况下使用。LinkedList的优势在于在中间位置插入和删除操作，速度是最快的.LinkedList实现了 List接口，允许null元素。此外LinkedList提供额外的get, remove, insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作 堆栈（stack），队列（queue）或双向队列（deque）。由于它的底层是用双向链表实现的，所以它对元素的增加、删除效率要比ArrayList好；它是一个双向链表，没有初始化大小，也没有扩容的机制，就是一直在前面或者后面新增就好。ArrayList实现了可变大小的数组。它允许所有元素，包括null。每个ArrayList实 例都有一个容量（Capacity），即用于存储元素的数组的大小。这个容量可随着 不断添加新元素而自动增加，但是增长算法并没有定义。当需要插入大量元素 时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效 率。ArrayList初始大小为10，每次1.5倍进行扩容；它的底层是用数组实现的，所以查询速度相对LinkedList要快。

4.Iterator和Listiterator区别

Listiterator有add方法，可以向List中添加对象，而Iterator不能。都可实现删除对象,但是ListIterator可以实现对象的修改，set方法可以实现。Iierator仅能遍历，不能修改。Listiterator和Iterator都有hasNext。和next0方法，可以实现顺序向后遍历， 但是Listiterator有hasPrevious。和previous。方法，可以实现逆向（顺序向前）遍历。Iterator就不可以。注意：我们可以使用Iterator来遍历Set和List集合，而Listiterator只能遍历List。Iterator只可以向前遍历，而Listiterator可以双向遍历。

5.Hashmap如何同步

当我们需要一个同步的HashMap时，有两种选择:1.使用Collections.synchronizedMap (..)来同步HashMap2.使用 ConcurrentHashMap注意：这两个选项之间的首选是使用ConcurrentHashMap，这是因为我们不需要锁定整个对象，以及通过ConcurrentHashMap分区地图来获得锁。方法一：通过Collections.synchronizedMap。返回一个新的Map,这个新的map就是线程安全的.这个要求大家习惯基于接口编程，因为返回的并不是HashMap, 而是一个Map的实现.Map map = Collections.synchronizedMap(new HashMap());方法二:使用 ConcurrentHashMapMap concurrentHashMap = new ConcurrentHashMap

6.IdentityHashMap和HashMap区别

IdentityHashMap是Map接口的实现。不同于HashMap的，这里采用参考平等。1.在HashMap中如果两个元素是相等的，则key1.equals(key2);2.在IdentityHashMap中如果两个元素是相等的，则key1 == key2.

7.HashMap的实现原理

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

1. HashMap概述

2.HashMap的数据结构

3.HashMap的存取实现

从下面的源代码中可以看出：当我们往HashMap中put元素的时候，先根据key的hashCode重新计算hash值，根据hash值得到这个元素在数组中的位置（即下标），如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。public V put(K key, V value) { // HashMap允许存放null键和null值。 // 当key为null时，调用putForNullKey方法，将value放置在数组第一个位置。 if (key == null) return putForNullKey(value); // 根据key的keyCode重新计算hash值。 int hash = hash(key.hashCode()); // 搜索指定hash值在对应table中的索引。 int i = indexFor(hash, table.length); // 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。 for (Entry 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; } } // 如果i索引处的Entry为null，表明此处还没有Entry。 modCount++; // 将key、value添加到i索引处。 addEntry(hash, key, value, i); return null; }addEntry(hash, key, value, i)方法根据计算出的hash值，将key-value对放在数组table的i索引处。addEntry 是 HashMap 提供的一个包访问权限的方法,代码如下：void addEntry(int hash, K key, V value, int bucketIndex) { // 获取指定 bucketIndex 索引处的 Entry Entry e = table[bucketIndex]; // 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry table[bucketIndex] = new Entry(hash, key, value, e); // 如果 Map 中的 key-value 对的数量超过了极限 if (size++ >= threshold) // 把 table 对象的长度扩充到原来的2倍。 resize(2 * table.length); }

8.HashMap与HashTable区别

1.HashMap允许键和值是null,而Hashtable不允许键或者值是null2.Hashtable是同步的，而HashMap不是。因此，HashMap更适合于单线程环境， 而Hashtable适合于多线程环境。注意：最大的不同是，Hashtable的方法是Synchronized的，而HashMap不是，在多个线程访问Hashtable时，不需要自己为它的方法实现同步，而HashMap 就必须为之提供外同步(Collections.synchronizedMap)。由于 HashTable 是线程安全的也是 synchronized，所以在单线程环境下它比HashMap 要慢。如果你不需要同步，只需要单一线程，那么使用 HashMap 性能要好过 HashTable。Hashtable的put方法如下public synchronized V put(K key, V value) { //###### 注意这里1 // Make sure the value is not null if (value == null) { //###### 注意这里 2 throw new NullPointerException(); } // Makes sure the key is not already in the hashtable. Entry tab[] = table; int hash = key.hashCode(); //###### 注意这里 3 int index = (hash & 0x7FFFFFFF) % tab.length; for (Entry e = tab[index]; e != null; e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { V old = e.value; e.value = value; return old; } } modCount++; if (count >= threshold) { // Rehash the table if the threshold is exceeded rehash(); tab = table; index = (hash & 0x7FFFFFFF) % tab.length; } // Creates the new entry. Entry e = tab[index]; tab[index] = new Entry(hash, key, value, e); count++; return null;}

9.Hashset的实现原理

1. HashSet概述

HashSet实现Set接口，它是基于HashMap实现的，HashSet底层使用HashMap来保存所有元素，（实际上是一个HashMap实例）支持。它不保证set 的迭代顺序,此类允许使用null元素。public class HashSet extends AbstractSet implements Set, Cloneable, java.io.Serializable { static final long serialVersionUID = -5024744406713321676L; // 底层使用HashMap来保存HashSet中所有元素。 private transient HashMap map; // 定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final。 private static final Object PRESENT = new Object(); /** * 默认的无参构造器，构造一个空的HashSet。 * * 实际底层会初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75。 */ public HashSet() { map = new HashMap(); } /** * 构造一个包含指定collection中的元素的新set。 * * 实际底层使用默认的加载因子0.75和足以包含指定 * collection中所有元素的初始容量来创建一个HashMap。 * @param c 其中的元素将存放在此set中的collection。 */ public HashSet(Collection c) { map = new HashMap(Math.max((int) (c.size()/.75f) + 1, 16)); addAll(c); } /** * 以指定的initialCapacity和loadFactor构造一个空的HashSet。 * * 实际底层以相应的参数构造一个空的HashMap。 * @param initialCapacity 初始容量。 * @param loadFactor 加载因子。 */ public HashSet(int initialCapacity, float loadFactor) { map = new HashMap(initialCapacity, loadFactor); } /** * 以指定的initialCapacity构造一个空的HashSet。 * * 实际底层以相应的参数及加载因子loadFactor为0.75构造一个空的HashMap。 * @param initialCapacity 初始容量。 */ public HashSet(int initialCapacity) { map = new HashMap(initialCapacity); } /** * 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。 * 此构造函数为包访问权限，不对外公开，实际只是是对LinkedHashSet的支持。 * * 实际底层会以指定的参数构造一个空LinkedHashMap实例来实现。 * @param initialCapacity 初始容量。 * @param loadFactor 加载因子。 * @param dummy 标记。 */ HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap(initialCapacity, loadFactor); } /** * 返回对此set中元素进行迭代的迭代器。返回元素的顺序并不是特定的。 * * 底层实际调用底层HashMap的keySet来返回所有的key。 * 可见HashSet中的元素，只是存放在了底层HashMap的key上， * value使用一个static final的Object对象标识。 * @return 对此set中元素进行迭代的Iterator。 */ public Iterator iterator() { return map.keySet().iterator(); } /** * 返回此set中的元素的数量（set的容量）。 * * 底层实际调用HashMap的size()方法返回Entry的数量，就得到该Set中元素的个数。 * @return 此set中的元素的数量（set的容量）。 */ public int size() { return map.size(); } /** * 如果此set不包含任何元素，则返回true。 * * 底层实际调用HashMap的isEmpty()判断该HashSet是否为空。 * @return 如果此set不包含任何元素，则返回true。 */ public boolean isEmpty() { return map.isEmpty(); } /** * 如果此set包含指定元素，则返回true。 * 更确切地讲，当且仅当此set包含一个满足(o==null ? e==null : o.equals(e)) * 的e元素时，返回true。 * * 底层实际调用HashMap的containsKey判断是否包含指定key。 * @param o 在此set中的存在已得到测试的元素。 * @return 如果此set包含指定元素，则返回true。 */ public boolean contains(Object o) { return map.containsKey(o); } /** * 如果此set中尚未包含指定元素，则添加指定元素。 * 更确切地讲，如果此 set 没有包含满足(e==null ? e2==null : e.equals(e2)) * 的元素e2，则向此set 添加指定的元素e。 * 如果此set已包含该元素，则该调用不更改set并返回false。 * * 底层实际将将该元素作为key放入HashMap。 * 由于HashMap的put()方法添加key-value对时，当新放入HashMap的Entry中key * 与集合中原有Entry的key相同（hashCode()返回值相等，通过equals比较也返回true）， * 新添加的Entry的value会将覆盖原来Entry的value，但key不会有任何改变， * 因此如果向HashSet中添加一个已经存在的元素时，新添加的集合元素将不会被放入HashMap中， * 原来的元素也不会有任何改变，这也就满足了Set中元素不重复的特性。 * @param e 将添加到此set中的元素。 * @return 如果此set尚未包含指定元素，则返回true。 */ public boolean add(E e) { return map.put(e, PRESENT)==null; } /** * 如果指定元素存在于此set中，则将其移除。 * 更确切地讲，如果此set包含一个满足(o==null ? e==null : o.equals(e))的元素e， * 则将其移除。如果此set已包含该元素，则返回true * （或者：如果此set因调用而发生更改，则返回true）。（一旦调用返回，则此set不再包含该元素）。 * * 底层实际调用HashMap的remove方法删除指定Entry。 * @param o 如果存在于此set中则需要将其移除的对象。 * @return 如果set包含指定元素，则返回true。 */ public boolean remove(Object o) { return map.remove(o)==PRESENT; } /** * 从此set中移除所有元素。此调用返回后，该set将为空。 * * 底层实际调用HashMap的clear方法清空Entry中所有元素。 */ public void clear() { map.clear(); } /** * 返回此HashSet实例的浅表副本：并没有复制这些元素本身。 * * 底层实际调用HashMap的clone()方法，获取HashMap的浅表副本，并设置到HashSet中。 */ public Object clone() { try { HashSet newSet = (HashSet) super.clone(); newSet.map = (HashMap) map.clone(); return newSet; } catch (CloneNotSupportedException e) { throw new InternalError(); } } }

10.ArrayList,Vector, LinkedList

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

11.Collections类

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

12.Map与Collection关系

注意：为何Map接口不继承C ollection接口？尽管Map接口和它的实现也是集合框架的一部分，但Map不是集合，集合也不是 Map。因此，Map继承Collection毫无意义，反之亦然。如果Map继承Collection接口，那么元素去哪儿？ Map包含key-value对，它提供抽取key或value列表集合的方法，但是它不适合“一组对象”规范。

13.hashCode()与equals()

HashMap使用Key对象的hashCode()和equals()方法去决定key-value对的索引。 当我们试着从HashMap中获取值的时候，这些方法也会被用到。如果这些方法没 有被正确地实现，在这种情况下，两个不同Key也许会产生相同的hashCode()和 equals()输出，HashMap将会认为它们是相同的，然后覆盖它们，而非把它们存储到不同的地方。同样的，所有不允许存储重复数据的集合类都使用hashCode()和equals()去查找重复，所以正确实现它们非常重要。equals()和hashCode()的实现应该遵循以下规则：1.如果o1.equals(o2),那么ol.hashCode()== o2.hashCode()总是为true的。2.如果 ol.hashCode()== o2.hashCode()，并不意味着 o1.equals(o2)会为 true。

14.Java集合框架优点

(1)使用核心集合类降低开发成本，而非实现我们自己的集合类。(2)随着使用经过严格测试的集合框架类，代码质量会得到提高。(3)通过使用JDK附带的集合类，可以降低代码维护成本。(4)复用性和可操作性。注意：集合框架中的泛型有什么优点？Java1.5引入了泛型，所有的集合接口和实现都大量地使用它。泛型允许我们为 集合提供一个可以容纳的对象类型，因此，如果你添加其它类型的任何元素，它会在编译时报错。这避免了在运行时出现ClassCastException，因为你将会在编译时得到报错信息。泛型也使得代码整洁，我们不需要使用显式转换和nstanceOf操作符。它也给运行时带来好处，因为不会产生类型检查的字节码指令

15.如何选用HashMap和TreeMap

对于在Map中插入、删除和定位元素这类操作，HashMap是最好的选择。然而， 假如你需要对一个有序的key集合进行遍历，TreeMap是更好的选择。

16.ArrayList和Vector异同

相同点：1.两者都是基于索引的，内部由一个数组支持。2.ArrayList和Vector两者允许null值，也可以使用索引值对元素进行随机访问。不同点：1.Vector是同步的，而ArrayList不是

17.ArrayList和LinkedList区别

1.ArrayList是由Array所支持的基于一个索引的数据结构，所以它提供对元素的随机访问，复杂度为O⑴，但LinkedList存储一系列的节点数据，每个节点都与 前一个和下一个节点相连接。所以，尽管有使用索引获取元素的方法，内部实现是从起始点开始遍历，遍历到索引的节点然后返回元素，时间复杂度为O(n)，比ArrayList要慢。2.与ArrayList相比，在LinkedList中插入、添加和删除一个元素会更快，因为在—个元素被插入到中间的时候，不会涉及改变数组的大小，或更新索引。3.LinkedList比ArrayList消耗更多的内存，因为LinkedList中的每个节点存储了前后节点的引用。因为 ArrayList 的每个索引的位置是实际的数据，而 LinkedList 中的每个节点中存储的是实际的数据和前后节点的位置。4.相对于 ArrayList，LinkedList 插入是更快的。因为 LinkedList 不像 ArrayList一样，不需要改变数组的大小，也不需要在数组装满的时候要将所有的数据重新装入一个新的数组注意：如果你的应用经常需要随机访问数据,则考虑使用ArrayList。因为如果需要LinkedList 中的第 n 个元素的时候，你需要从第一个元素顺序数到第 n 个数据，然后读取数据。你的应用经常进行插入和删除元素，更少的读取数据,考虑使用LinkedList。因为插入和删除元素不涉及重排数据，所以它要比 ArrayList 要快。

18.队列和栈

栈和队列两者都被用来预存储数据。java.util.Queue是一个接口，它的实现类在 Java并发包中。队列允许先进先出(FIFO)检索元素，但并非总是这样。Deque 接口允许从两端检索元素。栈(Stack)与队列(Queue)很相似，但它允许对元素进行后进先出（LIFO）进行检索。Stack是一个扩展自Vector的类，而Queue是一个接口。

18.ArrayList的实现原理

1.ArrayList概述

ArrayList是List接口的可变数组的实现。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。 每个ArrayList实例都有一个容量，该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素，其容量也自动增长。自动增长会带来数据向新数组的重新拷贝，因此，如果可预知数据量的多少，可在构造ArrayList时指定其容量。在添加大量元素前，应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量，这可以减少递增式再分配的数量。 注意，此实现不是同步的。如果多个线程同时访问一个ArrayList实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。

2.ArrayList的实现

对于ArrayList而言，它实现List接口、底层使用数组保存所有元素 1) 底层使用数组实现 //Java代码private transient Object[] elementData;2) 构造方法ArrayList提供了三种方式的构造器，可以构造一个默认初始容量为10的空列表、构造一个指定初始容量的空列表以及构造一个包含指定collection的元素的列表，这些元素按照该collection的迭代器返回它们的顺序排列的。 public ArrayList() { this(10); } public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; } public ArrayList(Collection c) { elementData = c.toArray(); size = elementData.length; // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }3) 存储 ArrayList提供了set(int index, E element)、add(E e)、add(int index, E element)、addAll(Collection c)、addAll(int index, Collection c) //这些添加元素的方法。下面我们一一讲解 // 用指定的元素替代此列表中指定位置上的元素，并返回以前位于该位置上的元素。 public E set(int index, E element) { RangeCheck(index); E oldValue = (E) elementData[index]; elementData[index] = element; return oldValue; } // 将指定的元素添加到此列表的尾部。 public boolean add(E e) { ensureCapacity(size + 1); elementData[size++] = e; return true; } // 将指定的元素插入此列表中的指定位置。 // 如果当前位置有元素，则向右移动当前位于该位置的元素以及所有后续元素（将其索引加1）。 public void add(int index, E element) { if (index > size || index < 0) throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size); // 如果数组长度不足，将进行扩容。 ensureCapacity(size+1); // Increments modCount!! // 将 elementData中从Index位置开始、长度为size-index的元素， // 拷贝到从下标为index+1位置开始的新的elementData数组中。 // 即将当前位于该位置的元素以及所有后续元素右移一个位置。 System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }

3.调整数组容量

从上面介绍的向ArrayList中存储元素的代码中，我们看到，每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。在实际添加大量元素前，我也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。public void ensureCapacity(int minCapacity) { modCount++; int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { Object oldData[] = elementData; int newCapacity = (oldCapacity * 3)/2 + 1; if (newCapacity < minCapacity) newCapacity = minCapacity; // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } }从上述代码中可以看出，数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用ensureCapacity方法来手动增加ArrayList实例的容量。

19.List与Map区别

List 特点∶元素有放入顺序，元素可重复; Map 特点∶元素按键值对存储，无放入顺序 ;List 接 口 有 三 个 实 现 类 ∶LinkedList，ArrayList，Vector; LinkedList∶底层基于链表实现，链表内存是散乱的，每一个元素存储本身内存地址的同时还存储下一个元素的地址。链表增删快，查找慢;Map 接口有三个实现类∶HashMap，HashTable，LinkedHashMapMap 相当于和 Collection 一个级别的;Map 集合存储键值对，且要求保持键的唯一性;

20.List与Set区别

List, Set 都是继承自 Collection 接口List 特点∶元素有放入顺序，元素可重复。Set 特点∶元素无放入顺序，元素不可重复（注意∶元素虽然无放入顺序，但是元素在 set 中的位置是有该元素的 HashCode 决定的，其位置其实是固定的）List 接口有三个实现类∶LinkedList，ArrayList，Vector。Set 接口有两个实现类∶HashSet(底层由 HashMap 实现)，LinkedHashSet

21.HashMap和ConcurrentHashMap区别

放入 HashMap 的元素是 key-value 对。底层说白了就是散列结构。要将元素放入到 HashMap 中，那么 key 的类型必须要实现 hashcode 方法，默认这个方法是根据对象的地址来计算的，接着还必须覆盖对象的equals() 方法。ConcurrentHashMap 对整个桶数组进行了分段，而 HashMap 则没有ConcurrentHashMap 在每一个分段上都用锁进行保护，从而让锁的粒度更精细一些，并发性能更好，而 HashMap 没有锁机制，不是线程安全的

22.HashSet和HashMap区别

HashMap 实现了 Map 接口HashMap 储存键值对使用 put() 方法将元素放入 map 中HashMap 中使用键对象来计算hashcode 值HashMap比较快，因为是使用唯一的键来获取对象HashSet 实现了 Set 接口HashSet 仅仅存储对象使用 add() 方法将元素放入 set 中HashSet 使用成员对象来计算 hash值，对于两个对象来说 hashcode()方法用来判断对象的相等性，如果false，则存储HashSet 较 HashMap 来说比较慢

23.HashMap碰撞问题

1.Hash碰撞是什么

在HashMap的查询和添加过程中，绕不过去的是计算元素在数组的位置index，key的HashCode作为这个计算的基础。计算后的Hash值存在相同的情况，hash与长度取余的结果也有相同的情况，这个时候运算结果相同的两个对象就需要存储到同一个链表中，这就是HashMap中的Hash碰撞。这样会引起什么问题呢，碰撞严重的话，大量的元素都存储在一个链表中，检索过程中的第三步，遍历链表会耗费大量的时间，严重极端情况下会遍历所有元素，检索效率会很低。和HashMap快速检索的设计严重不符。

2.HashMap碰撞优化

1.HashMap使用LinkedList 来解决碰撞问题，当发生碰撞了，对象将会储存在LinkedList的下一个节点中。 HashMap在每个LinkedList节点中储存键值对对象。

24.fail-fast与fail-safe的区别

1.快速失败

我们知道java.util.HashMap不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了 map，那么将抛ConcurrentModificationException，这就是所谓 fail-fast 策略。由所有HashMap类的“collection视图方法”所返回的迭代器都是快速失败的：在 迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器本身的 remove方法，其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完 全失败

2.安全失败

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

25.Java的concurrent包中有哪些API

java.util.concurrent 包是专为 Java并发编程 而设计的包。包下的所有类可以分为如下几大类∶1.locks部分∶显式锁(互斥锁和速写锁)相关;2.atomic部分∶原子变量类相关，是构建非阻塞算法的基础; executor部分∶线程池相关;3.collections部分∶并发容器相关;4.tools部分∶同步工具相关，如信号量、闭锁、栅栏等功能;

1.BlockingQueue

此接口是一个线程安全的 存取实例的队列。使用场景:BlockingQueue通常用于一个线程生产对象，而另外一个线程消费这些对象的场 景。

2.ArrayBlockingQueue

ArrayBlockingQueue 是一个有界的阻塞队列内部实现是将对象放到一个数组里。数组有个特性∶一旦初始化，大小就无法修改。因此无法修改ArrayBlockingQueue初始化时的上限。ArrayBlockingQueue 内部以 FIFO(先进先出)的顺序对元素进行存储。队列中的头元素在所有元素之中是放入时间最久的那个，而尾元素则是最短的那个。

3.ConcurrentMap

一个能够对别人的访问(插入和提取)进行并发处理的 java.util.Map接口ConcurrentMap 除了从其父接口 java.util.Map 继承来的方法之外还有一些额外的原子性方法。实现类因为是接口，必须用实现类来使用它，其实现类为ConcurrentHashMapConcurrentHashMap与HashTable比较更好的并发性能，在你从中读取对象的时候 ConcurrentHashMap 并不会把整个Map 锁住，只是把 Map 中正在被写入的部分进行锁定。在被遍历的时候，即使是 ConcurrentHashMap 被改动，它也不会抛ConcurrentModificationException。

4.Lock

Lock 是一个类似于 synchronized 块的线程同步机制。但是 Lock 比synchronized 块更加灵活、精细。实现类Lock是一个接口，其实现类包括∶ ReentrantLock示例:Lock lock = new ReentrantLock();lock.lock(); //critical section lock.unlock(); 调用lock() 方法之后，这个 lock 实例就被锁住啦。当lock示例被锁后，任何其他再过来调用 lock() 方法的线程将会被阻塞住，直到调用了unlock() 方法。unlock() 被调用了，lock 对象解锁了，其他线程可以对它进行锁定了

5.Lock 和 synchronized区别

synchronized 代码块不能够保证进入访问等待的线程的先后顺序。你不能够传递任何参数给一个 synchronized 代码块的入口。因此，对于synchronized 代码块的访问等待设置超时时间是不可能的事情。synchronized 块必须被完整地包含在单个方法里。而一个 Lock 对象可以把它的 lock() 和 unlock() 方法的调用放在不同的方法里。

26.Collection和Collections的区别

1、java.util.Collection 是一个集合接口（集合类的一个顶级接口）。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式，其直接继承接口有List与Set。 Collection ├List │├LinkedList │├ArrayList │└Vector │　└Stack └Set2、Collections则是集合类的一个工具类/帮助类，其中提供了一系列静态方法，用于对集合中元素进行排序、搜索以及线程安全等各种操作。

lock示例被锁后，任何其他再过来调用 lock() 方法的线程将会被阻塞住，直到调用了unlock() 方法。

unlock() 被调用了，lock 对象解锁了，其他线程可以对它进行锁定了

5.Lock 和 synchronized区别

synchronized 代码块不能够保证进入访问等待的线程的先后顺序。你不能够传递任何参数给一个 synchronized 代码块的入口。因此，对于synchronized 代码块的访问等待设置超时时间是不可能的事情。synchronized 块必须被完整地包含在单个方法里。而一个 Lock 对象可以把它的 lock() 和 unlock() 方法的调用放在不同的方法里。

26.Collection和Collections的区别

1、java.util.Collection 是一个集合接口（集合类的一个顶级接口）。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式，其直接继承接口有List与Set。 Collection ├List │├LinkedList │├ArrayList │└Vector │　└Stack └Set2、Collections则是集合类的一个工具类/帮助类，其中提供了一系列静态方法，用于对集合中元素进行排序、搜索以及线程安全等各种操作。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。