List、Set、Map各子类的特点及对比

List、Set、Map各子类的特点及对比

微信搜索 zze_coding 或扫描 👉 二维码关注我的微信公众号获取更多资源推送:

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)

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://www.zze.xyz/archives/java-list-set-map.html

Buy me a cup of coffee ☕.