Java集合容器入门

集合类图

什么是HashMap

众所周知，HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫Entry。这些键值对分散在一个数组中，这个数组就是HashMap的主干。

HashMap数组的每一个初始值都是Null

HashMap用数组+链表的形式解决Hash函数下index的冲突情况，比如下面这种情况

hash冲突你还知道哪些解决办法？(1) 开放地址法（2）链地址法（3）再哈希法（4）公共溢出区域法

HashMap数组的每一个元素不止是一个Entry对象，也是一个链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。当新来的Entry映射到冲突的数组位置时，只需要插入到对应的链表即可。

由于刚才所说的Hash冲突，同一个位置有可能匹配到多个Entry，这时候就需要顺着对应链表的头节点，一个一个向下来查找。假设我们要查找的Key是“apple”：

需要注意的是，新来的Entry节点插入链表时，使用的是“头插法”。是因为HashMap的发明者认为，后插入的Entry被查找的可能性更大。

HashMap面试问题

HashMap面试必问的6个点，你知道几个？原作者【程序员追风】链接 基于此文做了小量摘抄和补充

HashMap默认的初始长度是多少？为什么这么规定？

• HashMap默认初始长度是16，并且每次自动扩展或是手动初始化时，长度必须是2的幂
  • 长度16或者其他2的幂，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。
• HashMap的函数采用的位运算的方式

**可以用LinkedList代替数组结构嘛？**ps：Entry就是一个链表节点

意思源码中的

Entry[] table = new Entry[capacity] 

用

List<Entry> table = new LinkedList<Entry>();

表示是否可行，答案很明显，必须是可以

既然可以，为什么HashMap不用LinkedList，而使用数组？

因为数组效率更高，并且采用基本数组结构，可以自己定义扩容机制，比如HashMap中数组扩容是2的次幂，在做取模运算的时候效率高，而ArrayList的扩容机制是1.5倍扩容

HashMap在什么条件下扩容

load factor为0.75，为了最大程度避免哈希冲突，也就是当load factor * current cpacity(当前数组大小)时，就要resize

为什么扩容是2的次幂?

HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算法；这个算法实际就是取模，hash%length。

但是，大家都知道这种运算不如位移运算快。

因此，源码中做了优化hash&(length-1)。

也就是说hash%length==hash&(length-1)

那为什么是2的n次方呢？

因为2的n次方实际就是1后面n个0，2的n次方-1，实际就是n个1。

例如长度为8时候，3&(8-1)=3 2&(8-1)=2 ，不同位置上，不碰撞。

而长度为5的时候，3&(5-1)=0 2&(5-1)=0，都在0上，出现碰撞了。

所以，保证容积是2的n次方，是为了保证在做(length-1)的时候，每一位都能&1 ，也就是和1111……1111111进行与运算。

知道hashmap中put元素的过程是什么样么?

1. 对key的hashCode()做hash运算，计算index；

   此处注意，对于key的判断如下((k = p.key) == key || (key != null && key.equals(k)))只要满足其一就会被算作重复，然后覆盖，也就是如下代码，Map的大小为1

   HashMap<String,Integer> map = new HashMap();
   map.put("A", 1);
   map.put(new String("A"), 1);
   System.out.println(map.size());	//大小为1
   

2. 如果没碰撞直接放到bucket里；

3. 如果碰撞了，以链表的形式存在buckets后；

4. 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树(JDK1.8中的改动)；

5. 如果节点已经存在就替换old value(保证key的唯一性)

6. 如果bucket满了(超过load factor*current capacity)，就要resize。

hashmap中get元素的过程？

1. 对key的hashCode()进行hash运算，得到index
2. 去bucket中查找对应的index，如果命中，则直接返回
3. 如果有冲突，则通过key的equals去查找对应的entry；
   • 若为树，则在树中查找，时间复杂度为O(logn)
   • 若为链表，则在链表中查找，时间复杂度为O(n)

还知道哪些Hash算法？

比较出名的有MD4、MD5等

String的hashcode的实现？

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

String类中的hashCode计算方法还是比较简单的，就是以31为权，每一位为字符的ASCII值进行运算，用自然溢出来等效取模。

知道jdk1.8中hashmap改了啥么?

• 由数组+链表的结构改为数组+链表+红黑树。
• 优化了高位运算的hash算法：h^(h>>>16)
• 扩容后，元素要么是在原位置，要么是在原位置再移动2次幂的位置，且链表顺序不变。

最后一条是重点，因为最后一条的变动，hashmap在1.8中，不会在出现死循环问题。

为什么在解决hash冲突的时候，不直接用红黑树?而选择先用链表，再转红黑树?

补充：解决hash冲突的方法还有开放地址法、链地址法、再哈希法、建立公共溢出区

因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。

当元素小于8个当时候，此时做查询操作，链表结构已经能保证查询性能。当元素大于8个的时候，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。

因此，如果一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑这是浪费性能的。

我不用红黑树，用二叉查找树可以么?

可以。但是二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。

当链表转为红黑树后，什么时候退化为链表?

为6的时候退转为链表。中间有个差值7可以防止链表和树之间频繁的转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。

HashMap在并发编程环境下有什么问题啊?

• 多线程扩容，引起的死循环问题
• 多线程put的时候可能导致元素丢失
• put非null元素后get出来的却是null

在jdk1.8中还有这些问题么?

在jdk1.8中，死循环问题已经解决。其他两个问题还是存在。

你一般怎么解决这些问题的？

比如ConcurrentHashmap，Hashtable等线程安全等集合类。

HashMap的键可以为Null嘛

可以

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

你一般用什么作为HashMap的key?

一般用Integer、String这种不可变类当HashMap当key，而且String最为常用。

• 因为字符串是不可变的，所以在它创建的时候hashcode就被缓存了，不需要重新计算。这就使得字符串很适合作为Map中的键，字符串的处理速度要快过其它的键对象。这就是HashMap中的键往往都使用字符串。
• 因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的,这些类已经很规范的覆写了hashCode()以及equals()方法。
• 用可变类当HashMap的key有什么问题? hashcode可能发生改变，导致put进去的值，无法get出

其实严格来说，String并不是一个严谨的不可变类，在Java1.5以后，我们可以通过反射技术修改String里的value[]数组的值。

如果让你实现一个自定义的class作为HashMap的key该如何实现？

此题考察两个知识点

• 重写hashcode和equals方法注意什么?
• 如何设计一个不变类

针对问题一，记住下面四个原则即可

(1)两个对象相等，hashcode一定相等

(2)两个对象不等，hashcode不一定不等

(3)hashcode相等，两个对象不一定相等

(4)hashcode不等，两个对象一定不等

针对问题二，记住如何写一个不可变类

(1)类添加final修饰符，保证类不被继承。

如果类可以被继承会破坏类的不可变性机制，只要继承类覆盖父类的方法并且继承类可以改变成员变量值，那么一旦子类以父类的形式出现时，不能保证当前类是否可变。

(2)保证所有成员变量必须私有，并且加上final修饰

通过这种方式保证成员变量不可改变。但只做到这一步还不够，因为如果是对象成员变量有可能再外部改变其值。所以第4点弥补这个不足。

(3)不提供改变成员变量的方法，包括setter

避免通过其他接口改变成员变量的值，破坏不可变特性。

(4)通过构造器初始化所有成员，进行深拷贝(deep copy)

如果构造器传入的对象直接赋值给成员变量，还是可以通过对传入对象的修改进而导致改变内部变量的值。例如：

public final class ImmutableDemo {  
    private final int[] myArray;  
    public ImmutableDemo(int[] array) {  
        this.myArray = array; // wrong  
    }  
}

这种方式不能保证不可变性，myArray和array指向同一块内存地址，用户可以在ImmutableDemo之外通过修改array对象的值来改变myArray内部的值。

为了保证内部的值不被修改，可以采用深度copy来创建一个新内存保存传入的值。正确做法：

public final class MyImmutableDemo {  
    private final int[] myArray;  
    public MyImmutableDemo(int[] array) {  
        this.myArray = array.clone();   
    }   
}

这里要注意，Object对象的clone()方法，实现了对象中各个属性的复制，但它的可见范围是protected的，所以实体类使用克隆的前提是：

① 实现Cloneable接口，这是一个标记接口，自身没有方法。
② 覆盖clone()方法，可见性提升为public。

也就是说，一个默认的clone()方法实现机制，仍然是赋值。

如果一个被复制的属性都是基本类型，那么只需要实现当前类的cloneable机制就可以了，此为浅拷贝。

如果被复制对象的属性包含其他实体类对象引用，那么这些实体类对象都需要实现cloneable接口并覆盖clone()方法。

(5)在getter方法中，不要直接返回对象本身，而是克隆对象，并返回对象的拷贝

这种做法也是防止对象外泄，防止通过getter获得内部可变成员对象后对成员变量直接操作，导致成员变量发生改变。

准备用HashMap存1w条数据，构造时传10000还会触发扩容吗？

• 在 HashMap 中，提供了一个指定初始容量的构造方法 HashMap(int initialCapacity)，这个方法最终会调用到 HashMap 另一个构造方法，其中的参数 loadFactor 就是默认值 0.75f。

• 从构造方法的逻辑可以看出，HashMap 并不是直接使用外部传递进来的 initialCapacity，而是经过了 tableSizeFor() 方法的处理，再赋值到 threshole 上。

• 在 tableSizeFor() 方法中，通过逐步位运算，就可以让返回值，保持在 2 的 N 次幂。以方便在扩容的时候，快速计算数据在扩容后的新表中的位置。

  那么当我们从外部传递进来 1w 时，实际上经过 tableSizeFor() 方法处理之后，就会变成 2 的 14 次幂 16384，再算上负载因子 0.75f，实际在不触发扩容的前提下，可存储的数据容量是 12288（16384 * 0.75f）。

  这种场景下，用来存放 1w 条数据，绰绰有余了，并不会触发我们猜想的扩容。

unmodify不可变的集合

概述：通常用于方法的返回值，通知调用者该方法是只读的，并且不期望对方修改状态

补充：Arrays.asList返回的Arrays.ArrayList其实并非不可变，只是add方法没有重写，但是可以通过set进行下标数据交换

在Java 8我们可以使用Collections来实现返回不可变集合

Java集合类：“随机访问” 的RandomAccess接口

如果我们用Java做开发的话，最常用的容器之一就是List集合了，而List集合中用的较多的就是ArrayList 和 LinkedList 两个类，这两者也常被用来做比较。因为最近在学习Java的集合类源码，对于这两个类自然是不能放过，于是乎，翻看他们的源码，我发现，ArrayList实现了一个叫做 RandomAccess 的接口，而 LinkedList 是没有的

• RandomAccess 是一个标志接口，表明实现这个这个接口的 List 集合是支持快速随机访问的。也就是说，实现了这个接口的集合是支持 快速随机访问 策略的。

• 同时，官网还特意说明了，如果是实现了这个接口的 List，那么使用for循环的方式获取数据会优于用迭代器获取数据。

Stream流操作注意事项

stream.of()，最好不要传基本类型，因为 Stream主要用于对象类型的集合 ，如果传基本类型，会将基本类型数组当做一个对象处理。

当然JDK还提供了基本类型的Stream，例如我们可以直接使用IntStream，而不是Stream。

Java 集合框架基础运用

集合接口

• Collection实现Interable接口
  • 所有java.util下的集合类都是fast-fail(快速失败)的
  • 结论：Iterator迭代器只能在 next() 方法执行后，通过 remove() 移除数据，也无法对源 Collection 对象操作
• 接口分类 (Collection为主，Map为辅)
• 基于 java.util.Collection 接口的单维度数据集合
  • 基于 java.util.Map 接口的双维度数据集合或其他接口
• 数组的Copy和集合对象的clone是类似的，均为浅克隆
• 几乎所有遗留集合实现是线程安全
  • Vector、HashTable、Stack等

java.util.Collection 接口

• 通用接口
  * java.util.List(有序,允许重复,允许null)

  * java.util.Set(无序,不可重复,不允许null)
      * Set集合底层使用hash表实现，所以不可重复，每次add的时候都会调用自己的hashCode()方法去判断是否发生碰撞，然后是否替换等操作
      * HashSet在一些特殊场景是有序的，如字母、数字
      
  * java.util.SortedSet  
  
      * TreeSet实现了SortedSet,提供了Compare和CompareTo来定制排序
      
  * java.util.NavigableSet（since Java 1.6）
  

Collection接口下面已细化了List,Set和Queue子接口，未什么又定义了AbstractCollection这个抽象类？

三者都是Collection，总还是有共同行为的。

• 抽象实现基于 java.util.Collection 接⼝
  • java.util.AbstractCollection
  • java.util.AbstractList
  • java.util.AbstractSet
  • java.util.AbstractQueue（Since Java 1.5）

ArrayList集合之subList

• subList实际是原列表的一个视图，对视图的操作全部会被反映到原列表上
• 对于局部列表的操作可以使用sublist，例如删除20-30的下标元素，List.sublist(20,30).clear();
• 生成子列表后不要操作原列表，会抛ConcrrentModificationException异常

通常 Set 是 Map Key 的实现，Set 底层运用 Map 实现
在HashSet中，元素都存到HashMap键值对的Key上面，而Value时有一个统一的值private static final Object PRESENT = new Object();，(定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final)

java.util.Map接口

• HashMap和HashTable区别【扩展ConcurrentHashMap】
  • HashMap线程非安全(写操作)，HashTable线程安全
  • HashMap允许value为null，HashTable的key和value不允许为null，ConcurrentHashMap的key 与 value 不允许 null
  • 如果 value 为空的话，ConcurrentHashMap 在查询数据时，会产生歧义。到底是值为 null，还是线程不可见
• 抽象实现基于 java.util.Map 接⼝
  • java.util.AbstractMap

ArrayList和CopyOnWriteArrayList的区别

• CopyOnWriteArrayList
• 实现了List接口
  • 内部持有一个ReentrantLock lock = new ReentrantLock();
  • 底层是用volatile transient声明的数组 array
  • 读写分离，写时复制出一个新的数组，完成插入、修改或者移除操作后将新数组赋值给array

• ArrayList
  • 底层是数组，初始大小为10
  • 插入时会判断数组容量是否足够，不够的话会进行扩容
  • 所谓扩容就是新建一个新的数组，然后将老的数据里面的元素复制到新的数组里面
  • 移除元素的时候也涉及到数组中元素的移动，删除指定index位置的元素，然后将index+1至数组最后一个元素往前移动一个格

Vector是增删改查方法都加了synchronized，保证同步，但是每个方法执行的时候都要去获得锁，性能就会大大下降，而CopyOnWriteArrayList 只是在增删改上加锁，但是读不加锁，在读方面的性能就好于Vector，CopyOnWriteArrayList支持读多写少的并发情况

Collections便利实现

接口类型

• 单例集合接口（Collections.singleton*） 不可变集合、只有一个元素
  • 主要用于只有一个元素的优化，减少内存分配，无需分配额外的内存
• 空集合接口（Collections.empty*） *
• 转换集合接口（Collections.、Arrays.*） *
• 列举集合接口（*.of(…)）

集合算法运用

• 计算复杂度：最佳、最坏以及平均复杂度
• 内存使用：空间复杂度
• 递归算法：排序算法中是否⽤到了递归
• 稳定性：当相同的健存在时，经过排序后，其值也保持相对的顺序（不发生变化）
• 比较排序：集合中的两个元素进行比较排序

ArrayList 、HashSet、HashMap不安全，实现安全的几种方式

实现线程安全的几种方式

1. JUC并发包下的

   new CopyOnWriteArrayList<>();new CopyOnWriteArraySet<>();new ConcurrentHashMap<>();

2. new Vector<>();

3. Collections.synchronizedList(); and Set 、Map;

BlockingQueue解读

首先，最基本的来说， BlockingQueue 是一个先进先出的队列（Queue），为什么说是阻塞（Blocking）的呢？是因为 BlockingQueue 支持当获取队列元素但是队列为空时，会阻塞等待队列中有元素再返回；也支持添加元素时，如果队列已满，那么等到队列可以放入新元素时再放入。

BlockingQueue 是一个接口，继承自 Queue，所以其实现类也可以作为 Queue 的实现来使用，而 Queue 又继承自 Collection 接口。

BlockingQueue 对插入操作、移除操作、获取元素操作提供了四种不同的方法用于不同的场景中使用：1、抛出异常；2、返回特殊值（null 或 true/false，取决于具体的操作）；3、阻塞等待此操作，直到这个操作成功；4、阻塞等待此操作，直到成功或者超时指定时间。总结如下：

3分钟了解Java中System.arraycopy的用法

System提供了一个静态方法arraycopy(),我们可以使用它来实现数组之间的复制。其函数原型是：

Copypublic static native void arraycopy(Object src,int srcPos,Object dest, int destPos,int length)；

Copy* @param      src      the source array. 源数组
* @param      srcPos   starting position in the source array. 源数组的起始位置
* @param      dest     the destination array. 目标数组
* @param      destPos  starting position in the destination data. 目标数组的起始位置
* @param      length   the number of array elements to be copied. 复制的长度

举个栗子：

将array数组复制到新的数组中；

Copyint[] array = {1, 2, 3, 4, 5};
int[] targetArr = new int[array.length];
System.arraycopy(array,0,targetArr,0,array.length);