Java集合包

 

整体架构

基础的定义接口有5个:

  • List 是有序的,可以重复的元素的线性表。
  • Queue 对线性表的访问加以控制,一端入、一端出、先入先出。
  • Deque 同样是对线性表的访问加以控制,两端都可以出入、先入先出。
  • Map 是不重复的键值对。
  • Set 是不重复的数据集合。

在实现时,考虑几个特性:

  • 无序/有序的线形表/有序的树;
  • 顺序储存/链式储存;
  • 非同步/同步非阻塞/同步阻塞。

另外,还有一些遍历、添加、删除、过滤、反转的工具类。

另外,还有一个操作char集合的类——String。

ArrayList和LinkedList

ArrayList是顺序存储结构的线性表,查找效率高,插入删除效率低。 LinkedList是链表,查找效率低,插入删除效率高。 另外,注意到LinkedList也实现了Deque接口,即它也可以当作队列、双端队列使用。

ArrayList是如何实现动态容量的?

初始化时数组的容量为0;执行add()时,会先计算出目标容量,如果目标容量大于当前容量,会创建一个新的、长度为目标容量的数组,然后把原数组复制到新数组的前几位,最后把新元素赋值给新数组的原长度+1的位置。

为什么说LinkedList的查找效率低,插入删除效率高?

LinkedList是链表结构,它的get()的实现是,从第一个元素开始,递归查找下一个元素的指针,找第i个元素就需要递归i次;而ArrayList是顺序存储结构,它的get()的实现是,直接返回下标为i的元素,所以ArrayList比LinkedList的查找效率高。同时,LinkedList执行删除操作时,只需将其目标元素的后驱的引用赋值给目标元素的前驱的指针域;而ArrayList的实现是,先将目标元素后面的所有元素复制到各自的前一位,再将最后一位设置为null,所以LinkedList比ArrayList的删除效率高。插入同理。

Map和Set

Set是基于Map的

例如HashSet是基于HashMap的,只是将要保存的对象作为key,将空对象(new Object())作为value。

如何解决保证“不重复”的效率问题?

在有大量元素的集合中,为保证数据不重复,若调用equals()比较元素效率太低,于是采取哈希算法。哈希算法也称为散列算法,是将数据依特定算法直接指定到一个地址上。

具体地说,当集合要添加新的元素时,先调用这个元素的hashcode()获取一个值,这个值就是它应该放置的物理地址的值。

如果这个位置上没有元素,它就可以直接存储在这个位置上,不用再进行任何比较了; 如果这个位置上已经有元素了,就调用它的equals()与新元素进行比较,相同的话就不存了; 不相同的话,也就是发生了Hash key相同导致冲突的情况,那么就在这个Hash key的地方产生一个链表,将所有产生相同HashCode的对象放到这个单链表上去,串在一起。 这样一来实际调用equals()的次数就大大降低了,提高了效率。

从Object角度看,JVM每new一个Object,它都会将这个Object丢到一个Hash表中去,这样的话,下次做Object的比较或者取这个对象的时候(读取过程),它会根据对象的HashCode直接从Hash表中取这个对象。这样做的目的是提高取对象的效率。若HashCode相同再去调用equals()。

==和equals()和hashCode()的区别?

  • 对于值类型,==是比较“值”。对于引用类型,==是比较“地址”。
  • Object对象的equals()其实就是“==”,其子类会重写equals(),达到比较“值”的效果。
  • Object对象的hashcode()是一个Native方法,由“地址”构造出一个int值。

重写equals()和hashCode()

当子类重写equals()时,要满足4个性质:

  • 对称性:如果x.equals(y)返回是“true”,那么y.equals(x)也应该返回是“true”;
  • 反身性:x.equals(x)必须返回是“true”;
  • 类推性:如果x.equals(y)返回是“true”,而且y.equals(z)返回是“true”,那么z.equals(x)也应该返回是“true”;
  • 一致性:如果x.equals(y)返回是“true”,只要x和y内容一直不变,不管重复x.equals(y)多少次,返回都是“true”。

当子类重写equals()时,为了保证集合操作的效率,也要重写hashcode(),并且保证:

  • 如果x.equals(y)返回“true”,那么x和y的hashCode()必须相等;
  • 如果x和y的hashCode()不等,那么x.equals(y)必须返回“false”。

HashMap的实现原理

HashMap 是基于哈希表的 Map 接口的非同步实现,是一种“链表散列”的数据结构。它的成员变量table是一个数组,数组中的元素是一个链表,链表的元素是一个键值对Entry。当插入新的键值对时,先用key计算出hash,再由hash值计算出数组下标,再遍历数组中该位置的链表,如果有相同的key,则更新value,否则把键值对加入链表的末端。

HashTable和HashMap的区别?

HashMap 是基于哈希表的 Map 接口的非同步实现,是一种“链表散列”的数据结构。它的成员变量table是一个数组,数组中的元素是一个链表,链表的元素是一个键值对Entry。当插入新的键值对时,先用key计算出hash,再由hash值计算出数组下标,再遍历数组中该位置的链表,如果有相同的key,则更新value,否则把键值对加入链表的末端。

LinkedHashMap是如何保证顺序的?

LinkedHaskSet的线性表实现原理也是一样的

LinkedHashMap使用继承自Entry的LinkedHashMapEntry作为元素,LinkedHashMapEntry中多了两个成员变量before和after,分别用于保存上一个和下一个元素的引用;它们与LinkedHashMap的成员变量header共同构成了双向链表结构。当插入新的键值对时,LinkedHashMap重写了HashMap的createEntry()和addEntry(),不仅把新键值对加入到table中,还加入到header的链表中。另外LinkedHashMap的成员变量accessOrder还定义了排序模式,为 true时为访问顺序,即迭代顺序就是最后访问其条目的顺序(可用于实现LRU),实现方式是重写recordAccess(),将目标元素移动到header的末端;为 false时为插入顺序;默认是false。accessOrder被final修饰,意味着只能在创建LinkedHashMap时指定排序模式。

TreeMap是如何保证顺序的?

TreeSet的树实现原理也是一样的

TreeMap使用继承自Entry的TreeMapEntry作为元素,TreeMapEntry中多了三个成员变量left、right和parent,分别用于保存左兄弟、右兄弟和双亲的引用;它们与TreeMap的成员变量root共同构成了树结构。当插入新的键值对时,TreeMap重写了HashMap的createEntry()和addEntry(),不仅把新键值对加入到table中,还加入到root的树中。

操作工具

如何正确地循环删除集合中的元素?

  • 循环删除集合中一个元素的,可使用for循环/foreach,但是在删除后必须立即停止循环。
  • 循环删除多个元素的,应该使用迭代器iterator循环,并且使用iterator.remove()删除,并且保证iterator.next()在iterator.remove()前被调用。

如何对集合进行排序?

Comparator接口

for循环、foreach循环、iterator循环有什么区别?

String

为什么String要设计成不可变的?

  • 字符串常量池是Java堆内存中一个特殊的存储区域, 当创建一个String对象时,假如此字符串值已经存在于常量池中,则不会创建一个新的对象,而是引用已经存在的对象。假若字符串对象允许改变,那么将会导致各种逻辑错误,比如改变一个对象会影响到另一个独立对象。
  • 字符串不变性保证了hash码的唯一性,因此hash码可以缓存到String对象的成员变量hashcode,提高效率。
  • String被许多的Java类库用来当做参数,不可变在一定程度上保障了安全。

String、StringBuffer、StringBuilder区别?

  • String对象是不可变对象。每次修改String对象相当于新建一个String对象并丢掉原来的对象,容易引起GC,所以效率很低。
  • StringBuffer和StringBuilder对象都是可变的,内部维护1个char数组。
  • StringBuffer和StringBuilder对象的区别在于,StringBuilder对象不保证同步,而StringBuffer对象的方法都用synchronized修饰以保证同步。