List
元素是有顺序的,元素可以重复因为每个元素有自己的角标(索引)。
实现类 | 特点 |
---|---|
ArrayList | 底层的数据结构是数组结构,特点是:查询很快,增、删稍微慢点,线程不同步。 |
LinkedList | 底层使用的是链表数据结构,特点是:增、删很快,查询慢 , 线程不同步。 |
Vector | 底层是数组数据结构,线程同步,被 ArrayList 代替了,现在用的只有它的枚举。 |
Set
元素是无序的,且不可以重复,线程不同步。
实现类 | 特点 |
---|---|
HashSet | 底层是哈希表数据结构。根据 hashCode 和 equals 方法来确定元素的唯一性。 |
TreeSet | 可以对 Set 集合中的元素进行排序(自然排序),底层的数据结构是二叉树, 也可以自己写个类实现 Comparable 或者 Comparator 接口,定义自己的比较器,将其作为参数传递给 TreeSet 的构造函数。 |
Map
这个集合是存储键值对的,一对一对往里存,键唯一。
实现类 | 特点 |
---|---|
HashTable | 出现于 JDK1.0,底层是哈希表数据结构,不可以存入 null 键和 null 值,该集合线程是同步的,效率比较低。 |
HashMap | 出现于 JDK 1.2,底层是哈希表数据结构,可以存入 null 键和 null 值,线程不同步,效率较高,代替了 HashTable。 |
TreeMap | 底层是二叉树数据结构,线程不同步,可以用于给 Map 集合中的键进行排序。 |
HashTable与HashMap的比较
HashTable:
- 底层数组 + 链表实现,无论 key 还是 value 都不能为null,线程安全,实现线程安全的方式是在修改数据时锁住整个 HashTable,效率低,ConcurrentHashMap 做了相关优化;
- 初始 size 为 11,扩容:
newsize = oldsize*2+1
; - 计算 index 的方法:
index = (hash & 0x7FFFFFFF) % tab.length
;
HashMap:
- 底层数组 + 链表实现,可以存储 null 键和 null 值,线程不安全;
- 初始 size 为 16,扩容:
newsize = oldsize*2
,size 一定为 2 的 n 次幂; - 扩容针对整个 Map,每次扩容时,原来数组中的元素依次重新计算存放位置,并重新插入,
插入元素后才判断该不该扩容,有可能无效扩容(插入后如果扩容,如果没有再次插入,就会产生无效扩容); - 当 Map 中元素总数超过 Entry 数组的 75%,触发扩容操作,为了减少链表长度,元素分配更均匀;
- 计算 index 方法:
index = hash & (tab.length – 1)
;
评论区