手记

CoreJava笔记 - 集合类

Java集合框架

  1. 接口与实现分离
    ArrayDequeArrayList都实现了Queue<E>接口,在实际应用中只有创建的时候需要选择采用数组还是链表,之后都采用一样的接口来操作数据集。

  2. Collection接口
    Collection是所有集合类的基本接口。接口中有两个方法最基本:

  • boolean add(E):添加后如果集合变了,就返回true,否则返回false

  • iterator():返回Iterator(),用来遍历集合。

Iterator
Iterator有4个方法:

  • next()iterator像一个指针。Java的iterator不指向节点,而是在节点之前。调用next()时,指针越过并返回当前节点。如果已经在尾部,则抛出NoSuchElementException

  • hasNext():监测是否有下一个节点,常常作为控制循环的条件。

  • remove():不能直接调用这个函数,必须调用next(),获取当前节点后,才能对当前节点进行操作。

  • forEachRemaining():传入一个Lambda作为参数,可以完成for each循环的功能。

Collection接口中其它有用的方法

  • size(), isEmpty()

  • contains(), containsAll(),

  • equals()

  • addAll(), remove(), removeAll(), clear(), retainAll()

  • toArray(), <T> T[] toArray(T[] arrayToFill)

  • removeIf(Predicate<? super E> filter)

集合类中的接口


集合类中的接口

  • Collection接口:

  • Map接口:处理键值对。Map.put(K, V)、Map.get(K)。

  • List接口:提供随机访问。RandomAccess是一个tagging接口,用于判断集合是不是很好的支持随机访问(链表实现 vs. 数组实现)。

  • Set接口:与Collection相比更加严格。元素的值不能重复,equals()不要求顺序,hashCode()要保证元素相同code就相同。

  • SortedSet和SortedMap接口:用于排序的比较器对象,并支持得到集合的子集视图。

  • NavigableSet和NavigableMap接口:搜索和遍历。TreeSet和TreeMap实现了这些接口。

具体的集合

集合类

  1. 链表
    在Java中,链表是双向链接的。在链表中,LinkedList.add()只将节点添加到末尾,如果想在链表中间添加节点,则需要使用Iterator.add()。迭代器的add()方法会在下一个节点之前插入新节点。

    注意:add()方法只依赖于迭代器的位置,而remove()方法还依赖于迭代器的状态(刚刚越过的节点)。
    注意:多个迭代器引用同一个容器时,若一个迭代器修改了容器结构,则另一个迭代器在访问容器时会得到ConcurrentModificationException。一般设计为:1个读写迭代器,多个只读迭代器。检测原理:容器喝迭代器都维护着一个修改次数,当迭代器发现自己的修改次数与容器的修改次数不符,则必有其他迭代器修改了容器结构。

  2. 数组列表
    ArrayListVector:Vector是线程安全的,效率远逊ArrayList

  3. 散列集
    散列集的作用是放弃认为安排节点位置的权利。由算法自动安排节点的位置,目的在于快速查找。

    在Java中散列集是个链表数组,数组中的每一项是一个Hash桶。先计算节点的hashCode,与桶数取模,决定放入哪个桶。当某个桶被占满时,发生散列冲突,可能需要再散列。

    注意:一般认为桶数是元素个数的75%-150%,当元素达到装填因子(如75%),进行再散列。在标准库中桶数是2的幂,但是有些研究者认为桶数设为质数比较好。

    Java中的HashSet类是采用散列集实现的set类型。

  4. 树集
    Java中的TreeSet的实现是红黑树。树集中的元素会自动进行排序。

    常用接口:

  • Comparator<? super E> SortedSet.comparator()

  • E SortedSet.first()

  • E SortedSet.last()

  • E NavigableSet.higher(E)

  • E NavigableSet.lower(E)

  • E NavigableSet.celling(E)

  • E NavigableSet.floor(E)

  • E NavigableSet.pollFirst()

  • E NavigableSet.pollLast()

  • Iterator<E> NavigableSet.descendingIterator()

队列与双端队列
Deque接口在Java中由ArrayDequeLinkedList类实现。

常用接口:

  • 接口Queue<E>Deque<E>ArrayDeque<E>

  • 方法add()offer()remove()poll()element()/get()peek()

优先级队列
Java中PriorityQueue的实现方式是堆(Heap),Iterator遍历不是排序的,但是如果调用remove()方法,则总是移除最小的节点。节点必须可以比较。

映射-MAP

  1. 基本操作
    Java为map提供了两个类:HashMapTreeMapHashMap对键进行散列,而TreeMap对键进行排序。HashMap高效,尽量使用HashMap

    采用map.forEach(lambda)方法是最高效的访问方式。

  2. 更新映射项

    和merge()类似的函数还有:

  • compute()

  • computerIfPresent()

  • computerIfAbsent()

  • replaceAll()

  • map.put(key, map.getOrDefault(key, 0)+1);

  • map.putIfAbsent(key, 0);

  • map.merge(key, 1, Integer.sum);

映射视图

  • map.keySet()

  • map.values()

  • map.entrySet()

弱散列映射
WeakHashMap类:当map中的key值已经失去引用,这个(k, v)项就没有意义了,可以被垃圾回收。WeakHashMap中对象引用使用WeakReference类,如果某个对象只有WeakReference引用,那么GC就会回收该对象。

链接散列集与映射
LinkedHashSet类和LinkedHashMap类:HashSetHashMap的节点同时是个双向链表,可以保持相互顺序。
而且每次get或者set,都会让节点移动到链表尾部,这样链表开头都是就不需要频繁访问的节点,可以借此机制实现缓存或者释放有限资源。

枚举集与映射
EnumSet是枚举的高效实现,基于bit。EnumSet没有构造,只有厂方法:allOfnoneOfrangeof
EnumMap是将枚举值作为key的map:
EnumMap<Weekday, Employee> personInCharge = new EnumMap<>(Weekday.class);

标识散列映射
IdentityHashMap的散列值是根据内存位置计算得出的,因此就算内容相同的两个对象也是不等的。该对象的比较用==,不用equals

视图与包装器

容器类返回一个集合类的接口对象,通过这个集合类的接口对象,像操作某种集合一样来操作容器中的原有节点,这就是视图。

  1. 轻量级集合包装器

    Card[] c = new Card[54];//返回视图对象,不能add/remove,会抛出UnsupportedOperationExceptionList<Card> list = Arrays.asList(c);//生成100个元素的List,每个元素都是“Default”,存储代价极小List<String> list = Collections.nCopies(100, "Default");//返回一个不可修改的单元素集Collections.singleton(anObject);//Collections还可以生成空集、列表、映射,等。而且,编译器可以推测出集合的类型信息。Set<String> deepThoughts = Collections.emptySet();
  2. 子范围
    可以为许多集合建立子范围视图(区间范围是前闭后开):[start, end)
    List sl = aCollection.subList(start, end);

    对视图进行的操作会反应到原有集合:sl.clear();会删除视图涉及的所有元素。

    对于有序接口:SortedSetSortedMapNavigatableSet,可以使用排序建立视图:subSet/subMapheadSet/headMaptailSet/tailMap

  3. 不可修改的视图

    注意:unmodifiableCollectionsynchronizedCollectioncheckedCollection返回的集合,其equalshashCode是底层Object的方法。而unmodifiableListunmodifiableSet调用的是原集合的equalshashCode方法。

  • Collections.unmodifiableCollection

  • Collections.unmodifiableList

  • Collections.unmodifiableSet

  • Collections.unmodifiableSortedSet

  • Collections.unmodifiableNavigableSet

  • Collections.unmodifiableMap

  • Collections.unmodifiableSortedMap

  • Collections.unmodifiableNavigableMap

同步视图
synchronizedCollecton用于多线程同步。

受查视图
用于调试,及时检查插入时的类型错误。

关于可选操作的说明
视图有很多限制,而类支持更多方法。但是视图和类都用了一套接口,这就让视图中很多接口方法是Unsupported或者可选的。
不应该把这种设计风格带到用户开发领域。

算法

通过接口和范型,主要算法只需要实现一次。

  1. 排序与混排
    排序算法要求集合或者视图是可以修改的(支持set方法),但不必是可以改变大小的(支持)。
    Collections.sort():稳定排序,复杂度NLogN。Java中的链表排序是将链表转为数组,进行排序后,再将数组转回链表。
    Collections.shuffle():复杂度N。
    List.sort(Comparator):可以对于非Comparable的对象进行排序
    Collections.reverseOrder()
    Comparator.reversed()

  2. 二分查找
    Collection.binarySearch():返回大于或等于0,就是找到的索引。如果返回小于0的负数,则表示可以插入的位置:if (r < 0) list.add(-r - 1, element);
    如果传入链表,会自动转为线性查找。

  3. 简单算法

  • minmax

  • copyfill

  • addAllreplaceAll

  • indexOfSubListlastIndexOfSubList

  • swapreverserotate

  • frequencydisjoint

  • removeIf

批操作
很多算法是对元素进行批量处理的。

  • removeAll()

  • retainAll()

  • addAll()

  • clear()

集合与数组的转换
因为Java的类库大都是支持范型前就创建的。所以提供了一些数组与容器类的转换。

  • list.toArray():返回Object[],不可转换为其他类型的数组。如:(String[]) list.toArray()是错误的。

  • list.toArray(new String[0]):生成一个指定类型的数组。

  • list.toArray(new String[list.size()]):填充指定数组,这种情况下不生成新数组。

  • Arrays.asList():把数组包装成容器。

编写自己的算法

// 参数是接口void fillMenu(JMenu menu, Collection<JMenuItem> items) {    for (JMenuItem item : items) 
        menu.add(item);
}// 返回值是接口的两个例子,但是只要返回是接口,上层就不需要修改:List<JMenuItem> getAllItems(JMenu menu) {
    List<JMenuItem> items = new ArrayList();    for (int i = 0; i < menu.getItemCount(); i++) {
        items.add(menu.getItem(i));
    } 
    return items;
}// 返回一个AbstractList类的不可修改的视图List<JMenuItem> getAllItems(final JMenu menu) {    return new AbstractList<>() {        public JMenuItem get(int i) {            return menu.getItem(i);
        }        public int size() {            return menu.getItemCount();
        }
    }
}
  • 最好用集合类接口作为参数。

  • 如果要返回一个集合,最好也返回接口。

遗留的集合

  1. VectorHashtable
    ArrayListHashMap的线程安全版本。并发访问的版本是ConcurrentHashMap

  2. Enumeration:遗留的Iterator
    Collections.enumeration:产生一个Enumeration用于遗留代码。

  3. Properties:数据类型都是字符串的(K,V)对儿,可以自文件加载,也可以保存到文件。

  4. 栈:Stack

  5. 位集:BitSet
    例子:筛选素数。



作者:杀死BL
链接:https://www.jianshu.com/p/2eac74bf7bfa


0人推荐
随时随地看视频
慕课网APP