Java集合框架

发布于 15 天前  2 次阅读


一、List

ArrayList与Vector异同点

相同点

  1. 都是实现了List接口
  2. 都是有序的
  3. 底层都是由动态数组实现

不同点

  • ArrayList是线程不安全,适合单线程使用,效率较高。
  • Vector是线程安全,适合多线程操作时使用,效率较低。
  • ArrayList当达到容量大小时,每次增长为原来的1.5倍(即比原来多了50%),可以声明容量大小。
  • Vector当达到容量大小时,每次增长为原来的2倍(比原来多了100%),可以声明容量大小,也可以设置每次增长的大小。

ArrayList,Vector, LinkedList 的存储性能和特性

  • ArrayList与Vector都是以数组方式来存储数据,由于Vector的方法是同步的,所以在存储效率上ArrayList更好。
  • LinkedList是采用双向链表存储的,且线程也不安全。
  • 以数组方式存储数据的查找速度更快,以双向链表方式存储数据的插入与删除速度更快。

二、Map

HashMap

  • HashMap是根据HashCode值来存储的,多数情况下可以直接定位到值,HashMap中允许存在Key为null的一条记录,但是允许多数值为null,他的存储和插入都是根据键的HashCode值计算出具体的存储位置,HashMap的线程不安全,在多线程情况下使用容易造成死循环。

HashMap中可能出现的问题

  • 哈希冲突:若干Key的哈希值按数组大小取模后,如果落在同一个数组下标上,将组成一条Entry链,对Key的查找需要遍历Entry链上的每个元素执行equals()比较
  • 加载因子:为了降低哈希冲突的概率,默认当HashMap中的键值对达到数组大小的75%时,即会触发扩容。因此,如果预估容量是100,即需要设定100/0.75=134的数组大小。
  • 空间换时间:如果希望加快Key查找的时间,还可以进一步降低加载因子,加大初始大小,以降低哈希冲突的概率。

HashTable

  • 底层数组+链表实现,无论key还是value都不能为null,线程安全,实现线程安全的方式是在修改数据时锁住整个HashTable,效率低,ConcurrentHashMap做了相关优化
  • 初始size为11,扩容:newsize = olesize*2+1
  • 计算index的方法:index = (hash & 0x7FFFFFFF) % tab.length

HashMap的数据结构

  • 由数组与链表实现,也称为链表散列。当链表中的存储个数超过阈值(8个),为了加快搜索速度,链表转为红黑树

HashMap的工作原理

  • HashMap是基于hashing的原理,我们使用put(key, value)存储对象到HashMap中,使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时,我们先对键调用hashCode()方法,计算并返回的hashCode是用于找到Map数组的bucket位置来储存Node 对象。这里关键点在于指出,HashMap是在bucket中储存键对象和值对象,作为Map.Node 。

HashMap与ConcurrentHashMap的区别

  • HashMap线程不安全,ConcurrentHashMap线程安全,但是后者不是在方法上加了synchronized,而是引入了分段锁的概念,每个值都会根据hashCode对应不同的分段

For sharing , For emulating , For enterprising