Java子弹

Java 集合工具包

2022-08-29  本文已影响0人  一只阿木木

Java 集合工具包

Java集合是java提供的工具包，包含了常用的数据结构：集合、链表、队列、栈、数组、映射等。

Java集合工具包位置是java.util.*
Java集合主要可以划分为4个部分：

image

集合的作用

与数组的对比—————为何选择集合而不是数组

一：集合框架

看上面的框架图，先抓住它的主干，即Collection和Map。

Collection接口、子接口以及实现类
Collection接口

List接口

Set接口

Map和HashMap

Map接口
HashMap类

Comparable和Comparator

Comparable接口——可比较的
Comparator接口——比较工具接口

Iterator接口

image

二：arrayList

ArrayList继承了AbstractList，实现了List。
构造图如下:
蓝色线条：继承
绿色线条：接口实现

image 
 public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList 是一个数组队列，相当于 动态数组。与Java中的数组相比，它的容量能动态增长。它继承于AbstractList，实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。

ArrayList就是用数组实现的List容器,底层用数组实现，ArrayList包含了两个重要的对象：elementData 和 size。

// 保存ArrayList中数据的数组
private transient Object[] elementData;
// ArrayList中实际数据的数量
private int size;

ArrayList 实现了RandmoAccess接口，即提供了随机访问功能。

ArrayList 实现了Cloneable接口，即覆盖了函数clone()，能被克隆。

ArrayList 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。

ArrayList支持3种遍历方式

遍历ArrayList时，使用随机访问(即，通过索引序号访问)效率最高，而使用迭代器的效率最低！

ArrayList中的操作不是线程安全的！

所以，建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList

小结：

ArrayList和LinkedList的区别

ArrayList和Vector的区别

三：LinkedList

与ArrayList一样，实现List接口，只是ArrayList是List接口的大小可变数组的实现，LinkedList是List接口链表的实现。基于链表实现的方式使得LinkedList在插入和删除时更优于ArrayList，而随机访问则比ArrayList逊色些。
构造图如下:
蓝色线条：继承
绿色线条：接口实现

image

总结：

小结

ArrayList和LinkedList的比较

1、顺序插入速度ArrayList会比较快，因为ArrayList是基于数组实现的，数组是事先new好的，只要往指定位置塞一个数据就好了；LinkedList则不同，每次顺序插入的时候LinkedList将new一个对象出来，如果对象比较大，那么new的时间势必会长一点，再加上一些引用赋值的操作，所以顺序插入LinkedList必然慢于ArrayList

2、基于上一点，因为LinkedList里面不仅维护了待插入的元素，还维护了Entry的前置Entry和后继Entry，如果一个LinkedList中的Entry非常多，那么LinkedList将比ArrayList更耗费一些内存

3、数据遍历的速度，ArrayList使用最普通的for循环遍历比较快，LinkedList使用foreach循环比较快。如果各自比较，结论是：使用各自遍历效率最高的方式，ArrayList的遍历效率会比LinkedList的遍历效率高一些

4、有些说法认为LinkedList做插入和删除更快，这种说法其实是不准确的：

（1）LinkedList做插入、删除的时候，慢在寻址，快在只需要改变前后Entry的引用地址

（2）ArrayList做插入、删除的时候，慢在数组元素的批量copy，快在寻址

所以，如果待插入、删除的元素是在数据结构的前半段尤其是非常靠前的位置的时候，LinkedList的效率将大大快过ArrayList，因为ArrayList将批量copy大量的元素；越往后，对于LinkedList来说，因为它是双向链表，所以在第2个元素后面插入一个数据和在倒数第2个元素后面插入一个元素在效率上基本没有差别，但是ArrayList由于要批量copy的元素越来越少，操作速度必然追上乃至超过LinkedList。

从这个分析看出，如果你十分确定你插入、删除的元素是在前半段，那么就使用LinkedList；如果你十分确定你删除、删除的元素在比较靠后的位置，那么可以考虑使用ArrayList。如果你不能确定你要做的插入、删除是在哪儿呢？那还是建议你使用LinkedList吧，因为一来LinkedList整体插入、删除的执行效率比较稳定，没有ArrayList这种越往后越快的情况；二来插入元素的时候，弄得不好ArrayList就要进行一次扩容。

记住，ArrayList底层数组扩容是一个既消耗时间又消耗空间的操作。

四：HashMap

ArrayList、LinkedList，反映的是两种思想：

ArrayList以数组形式实现，顺序插入、查找快，插入、删除较慢
LinkedList以链表形式实现，顺序插入、查找较慢，插入、删除方便
那么是否有一种数据结构能够结合上面两种的优点呢？有，答案就是HashMap。

HashMap是基于哈希表的 Map 接口的实现，以key-value的形式存在。
构造图如下:
蓝色线条：继承
绿色线条：接口实现

image

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。
HashMap继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。
HashMap 的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。

HashMap的底层结构是一个数组，而数组的元素是一个单向链表

HashMap和Hashtable的区别

Hashtable的实现方法里面都添加了synchronized关键字来确保线程同步，因此相对而言HashMap性能会高一些，我们平时使用时若无特殊需求建议使用HashMap，在多线程环境下若使用HashMap需要使用Collections.synchronizedMap()方法来获取一个线程安全的集合（Collections.synchronizedMap()实现原理是Collections定义了一个SynchronizedMap的内部类，这个类实现了Map接口，在调用方法时使用synchronized来保证线程同步,当然了实际上操作的还是我们传入的HashMap实例，简单的说就是Collections.synchronizedMap()方法帮我们在操作HashMap时自动添加了synchronized来实现线程同步，类似的其它Collections.synchronizedXX方法也是类似原理）

虽说HashMap支持null值作为key，不过建议还是尽量避免这样使用，因为一旦不小心使用了，若因此引发一些问题，排查起来很是费事

HashMap以null作为key时，总是存储在table数组的第一个节点上

HashMap扩容时是当前容量翻倍即:capacity2，Hashtable扩容时是容量翻倍+1即:capacity2+1

Hashtable计算hash是直接使用key的hashcode对table数组的长度直接进行取模

int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

HashMap计算hash对key的hashcode进行了二次hash，以获得更好的散列值，然后对table数组长度取摸

static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

 static int indexFor(int h, int length) {
        return h & (length-1);
    }

五：TreeMap

TreeMap是基于红黑树结构实现的一种Map，要分析TreeMap的实现首先就要对红黑树有所了解。
构造图如下:
蓝色线条：继承
绿色线条：接口实现

image 
public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

TreeMap 是一个有序的key-value集合，它是通过红黑树实现的。
TreeMap 继承于AbstractMap，所以它是一个Map，即一个key-value集合。
TreeMap 实现了NavigableMap接口，意味着它支持一系列的导航方法。比如返回有序的key集合。
TreeMap 实现了Cloneable接口，意味着它能被克隆。
TreeMap 实现了java.io.Serializable接口，意味着它支持序列化。

TreeMap基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。
TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。
另外，TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fast的。

六：HashSet

Set的实现类都是基于Map来实现的(HashSet是通过HashMap实现的)。
构造图如下:
蓝色线条：继承
绿色线条：接口实现

image 
public class HashSet<E>
     extends AbstractSet<E>
     implements Set<E>, Cloneable, java.io.Serializable

HashSet 是一个没有重复元素的集合。
它是由HashMap实现的，不保证元素的顺序，而且HashSet允许使用 null 元素。
HashSet是非同步的。如果多个线程同时访问一个哈希 set，而其中至少一个线程修改了该 set，那么它必须 保持外部同步。这通常是通过对自然封装该 set 的对象执行同步操作来完成的。如果不存在这样的对象，则应该使用 Collections.synchronizedSet 方法来“包装” set。最好在创建时完成这一操作，以防止对该 set 进行意外的不同步访问：

Set s = Collections.synchronizedSet(new HashSet(...));

HashSet通过iterator()返回的迭代器是fail-fast的。

// 底层使用HashMap来保存HashSet的元素
    private transient HashMap<E,Object> map;
    // Dummy value to associate with an Object in the backing Map
    // 由于Set只使用到了HashMap的key，所以此处定义一个静态的常量Object类，来充当HashMap的value
    private static final Object PRESENT = new Object();

HashSet是用HashMap来保存数据，而主要使用到的就是HashMap的key。

小结

HashSet和HashMap、Hashtable的区别

HashMap HashSet
HashMap 实现了Map 接口 HashSet实现了set 接口
HashMap 储存键值对 HashSet仅仅存储对象
使用put()方法将元素放入map 中 使用add()方法将元素放入set 中
HashMap中使用键对象来计算 hashCode值 HashSet使用成员对象来计算hashcode 值，对于两个对象来说hashcode 可能相同，所以equals（）方法用来判断对象的相等性，如果两个对象不同的话，那么返回false
HashMap 比较快，因为是使用唯一的键来获取对象 HashSet较HashMap 来说比较慢
上一篇 下一篇

猜你喜欢

热点阅读