Java集合框架知识点总结

发表于 | 分类于 | 次

一、Map

1. HashMap

  1. hashMap和ConcurrentHashMap的区别？
    ConcurrentHashMap：java5中新增了ConcurrentMap接口和它的一个实现类ConcurrentHashMap。
    ConcurrentHashMap具体是怎么实现线程安全的呢？从ConcurrentHashMap代码中可以看出，它引入了一个“分段锁”的概念，具体可以理解为把一个大的Map拆分成N个小的HashTable，根据key.hashCode()来决定把key放到哪个HashTable中。通过把整个Map分为N个Segment（类似HashTable），可以提供相同的线程安全，但是效率提升N倍，默认提升16倍。
    hashMap： 从JDK1.2起，就有了HashMap，正如前一篇文章所说，HashMap不是线程安全的，因此多线程操作时需要格外小心。

  2. hashMap内部具体如何实现的？
    HashMap是典型的空间换时间的一种技术手段。HashMap底层使用哈希表（数组 + 链表 + 红黑树）实现。
    （1）put()方法：存储对象时，我们将K/V传给put方法时，对key的hashCode做hash操作得到桶中的存储位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。
    （2）get()方法：获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，如果产生碰撞，进一步调用equals()方法确定键值对。
    （3）哈希碰撞：如果发生碰撞（键的哈希值存在冲突碰撞，也就是不同的键的哈希值可能相等）的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。
    （4）解决碰撞的方法有： 

    1. 链地址法/拉链法（Hashmap使用）：就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。有时两个key会定位到相同的位置，表示发生了Hash碰撞。当然Hash算法计算结果越分散均匀，Hash碰撞的概率就越小，map的存取效率就会越高。那么通过什么方式来控制map使得Hash碰撞的概率又小，哈希桶数组（我们上面说到HashMap的基础就是一个线性数组，这个数组就是Entry[]，Map里面的内容都保存在Entry[]里面）占用空间又少呢？答案就是好的Hash算法和扩容机制。首先，Node[] table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。超过threshold这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。而当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。
2. 再哈希法：就是算hashcode的方法不止一个，一个要是算出来重复啦，再用另一个算法去算。 
3. 开放地址法：当发生地址冲突后，求解下一个地址用。

    （5）HashMap的扩容机制：当hashmap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对hashmap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，所以这是一个通用的操作，很多人对它的性能表示过怀疑，不过想想我们的“均摊”原理，就释然了，而hashmap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。那么hashmap什么时候进行扩容呢？当hashmap中的元素个数超过数组大小loadFactor时，就会进行数组扩容，loadFactor的 默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过160.75=12的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。
    （6）HashMap中hash函数怎么是是实现的？还有哪些 hash 的实现方式？
    　　1. 对key的hashCode做hash操作（高16bit不变，低16bit和高16bit做了一个异或；
    　　2. h & (length-1); //通过位操作得到下标index；

  3. 如果hashMap的key是一个自定义的类，怎么办？
    使用HashMap，如果key是自定义的类，就必须重写hashcode()和equals()。 因为在HashMap中，如果要比较key是否相等，要同时使用这两个函数。
    equals()很明显是对两个对象的地址值进行的比较（即比较引用是否相同）.

  4. HashMap与HashTable区别？
    HashMap的一些特性，譬如HashMap可以接受null键（只能有1个null键）和值，而Hashtable则不能；HashMap是非synchronized;HashMap非线程安全，但是个很快。

  5. 为什么String, Interger这样的类适合作为键？
    因为这些对象是不可变的，而且已经重写了equals()和hashCode()方法了。作为不可变类天生是线程安全的，而且可以很好的优化比如可以缓存hash值，避免重复计算等等。

  6. 能否让HashMap同步？
    HashMap可以通过下面的语句进行同步：Map m = Collections.synchronizeMap(hashMap);

  7. 为什么重写equals一定要重写hashCode？
    面临问题：若两个对象equals相等，但不在一个区间，根本没有机会进行比较，会被认为是不同的对象。所以Java对于eqauls方法和hashCode方法是这样规定的：

    1. 如果两个对象相同，那么它们的hashCode值一定要相同。也告诉我们重写equals方法，一定要重写hashCode方法。
    2. 如果两个对象的hashCode相同，它们并不一定相同，这里的对象相同指的是用eqauls方法比较。

  8. 你了解重新调整HashMap大小存在什么问题吗？
    当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。HashMap在resize时候如果多个线程并发操作如何导致死锁。此时为什么不使用CocurrentHashMap?

  9. 设计一个HashMap。
    自己写一个HashMap

  10. 为什么HashMap初始容量是16？HashMap的容量是2的n次方？
    hash()方法：因为HashMap要求key的hashCode值分布越均匀性能就越好。所以HashMap内部有一个hash()方法，能够对hashCode进行重新计算，以期望得到更加分布均衡的hashCode值。
    indexFor()方法是根据hash值和Entry[]的长度进行取模运算，确定数组的index。在计算机数学里有这么一个法则：当SIZE满足大小是2的幂的时候，X % SIZE（取模操作）和 X & (SIZE-1）是等价的。并且后者的效率更高。

  11. Map有几种遍历方式？
    keySet集合迭代，entrySet集合迭代，keySet 集合for-each 循环，entrySet集合for-each循环。（for,Iterator）

  12. ==比较的是什么？ equals方法与‘==’运算符有什么区别？为什么重写equals一定要重写hashcode？
    对于基本数据类型，==比较的是他们的值；对于引用数据类型，==比较的是他们在内存中的存放地址；
    在Object类中equals()方法实际上是判断两个对象是否具有相同的引用。
    默认情况下也就是从超类Object继承而来的equals方法与‘==’是完全等价的，比较的都是对象的内存地址，但我们可以重写equals方法，使其按照我们的需求的方式进行比较，如String类重写了equals方法，使其比较的是字符的序列，而不再是内存地址。
    Map接口的类会使用到键对象的哈希码，当我们调用put方法或者get方法对Map容器进行操作时，都是根据键对象的哈希码来计算存储位置的，因此如果我们对哈希码的获取没有相关保证，就可能会得不到预期的结果。

  13. 为什么hashmap的大小初始值为16?为什么初始加载因子设置为0.75？
    如果桶初始化桶数组设置太大，就会浪费内存空间，16是一个折中的大小；
    加载因子设置为0.75而不是1，是因为设置过大，桶中键值对碰撞的几率就会越大，同一个桶位置可能会存放好几个value值，这样就会增加搜索的时间，性能下降，设置过小也不合适，如果是0.1，那么10个桶，threshold为1，你放两个键值对就要扩容，太浪费空间了。

  14. Object若不重写hashCode()的话，hashCode()如何计算出来的？
    说如果对象不重写该方法，则返回相应对象的JVM内存地址的映射。public native int hashCode();native关键字说明其修饰的方法是一个原生态方法，方法对应的实现不是在当前文件，而是在用其他语言（如C和C++）实现的文件中。JNI允许Java代码使用以其他语言编写的代码和代码库。

  15. Object作为HashMap的key的话，对Object有什么要求吗？
    如果HashMap Key的哈希值在存储键值对后发生改变，Map可能再也查找不到这个Entry了。如果Key对象是可变的，那么Key的哈希值就可能改变。在HashMap中可变对象作为Key会造成数据丢失。
    在HashMap中使用不可变对象作为key。在HashMap中，使用String、Integer等不可变类型用作Key是非常明智的。如果可变对象在HashMap中被用作键，那就要小心在改变对象状态的时候，不要改变它的哈希值了。

  16. 如何自实现一个不可变（Immutable）类？
    定义类的时候，对用于计算hashCode的某个数据域只给get方法，而不提供set方法，使其不能被改变。

  17. 问HashMap什么情况下发生死链

2. Hashtable

Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。

  1. Hashtable对null的处理是怎样的？
    在使用Hashtable时，如果传入的键的值为空，则会抛出NullPointerException。而HashMap中可以存放键为null的映射。

3. LinkedHashMap

LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。可以作为Queue的实现类。

4. TreeMap

TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

  1. TreeMap底层实现原理？红黑树原理?
    红黑树又称红-黑二叉树，它首先是一颗二叉树，它具体二叉树所有的特性。同时红黑树更是一颗自平衡的排序二叉树。红黑树的规则：
    1. 每个节点都只能是红色或者黑色
    2. 根节点是黑色
    3. 每个叶节点（NIL节点，空节点）是黑色的。
    4. 如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
    5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
      所以红黑树它是复杂而高效的，其检索效率O(log n)。

二、Collection

1. List

可以允许重复的对象。可以插入多个null元素。是一个有序容器，保持了每个元素的插入顺序，输出的顺序就是插入的顺序。常用的实现类有 ArrayList、LinkedList 和 Vector。ArrayList 最为流行，它提供了使用索引的随意访问，而 LinkedList 则对于经常需要从 List中添加或删除元素的场合更为合适。

  1. ArrayList和LinkedList？LinkedList,ArrayList末尾插入谁效率高？
    ArrayList和LinkedList都实现了List接口。ArrayList的底层实现用的是数组，LinkedList实现是基于链表，ArrayList适合查找，LinkedList适合增删。在末尾插入的话，ArrayList效率更高。

  2. ArrayList的sublist修改是否影响list本身？
    ArrayList.subList(int fromIndex, int toIndex)方法返回一个List: 此List的值包含fromIndex所在的值, 但不包含toIndex所在的值. 如果fromIndex等于toIndex, 那么会返回一个没有任何元素的空List. 返回的List支持java.util.List接口的所有操作.
    ArrayList的subList方法获取到的是ArrayList的一段list，只是其中的一段视图。所以修改subList, ArrayList同时会修改，因为本来就是同一个东西。

  3. ArrayList和LinkedList你知道吗？你知道它怎么动态扩容的吗？
    ArrayList的底层是动态数组，初始容量为10，增长因子为1.5。jdk1.8时，ArrayList的扩充规则为：当第一次调用add方法时，首先对数组中元素的个数进行增加，其次调用ensureExplicitCapacity方法进行数组的初始化工作，接着调用ensureExplicitCapacity方法查看已有的元素是否大于数组的长度，如果不大于则不进行扩充，如果大于则进行调用grow方法进行扩充。
    扩充一共分为5步，第一步先获取原数组容量，然后设置新数组的容量是原数组容量的1.5倍，如果新容量小于老容量则将老容量的值设置给新容量。如果新容量的值大于数组的最大值调用hugeCapacity方法。最后调用copyOf在原数组上增加容量。

2. Set

  1. Set如何保证不重复？
    因为map中的key是不允许重复的，所以set中的元素不能重复。
    HashSet中add()中调用了HashMap的put()，将一个key-value对放入HashMap中。add方法的参数（要存储的value）作为HashMap的key，PRESENT（Object PRESENT = new Object();）作为固定value。当向HashSet中添加元素的时候，首先计算元素的hashcode值，然后用这个值计算出这个元素的存储位置，如果这个位置位空，就将元素添加进去；如果不为空，则用equals方法比较元素是否相等，相等就不添加，否则找一个空位添加。