数据结构分析
本文最后更新于158 天前,其中的信息可能已经过时,如有错误请发送邮件到3368129372@qq.com

ArrayList

  1. 初始化时长度为0
  2. 添加一个数字后长度变为10
  3. 后面每添加一个数字,校验(动态数组)长度够不够,不够的话长度扩充为原来的1.5倍
  4. 如果声明时指定了长度,底层调用的就是新建这个长度的数组,没有扩容

    数组与list相互转换

  5. list = Arrays.asList(array);这里面array修改时,list受到影响(只涉及引用,未创建新对象)
  6. T[] array = list.toArray(new T[size]);list改变时,array不受影响(使用了System.arraycopy(),创建了新的对象)

    与LinkedList

    1. 都是线程不安全的
    2. 为保证线程安全可以:
      • 在方法内使用,局部变量是线程安全的
      • Collections.syncronizedList(new LinkedList<>());来创建list对象

HashMap

数据结构实现

  • java8之前是数组+链表,java8之后是数组+链表或数组+红黑树。
  • 链表长度大于8且数组长度大于64时会采用红黑树提高性能(同时也能防止ddos),在扩容时树节点小于等于6个又会退化成链表

代码实现

  • 懒加载,初始化时未加载数组
  • 默认加载因子为0.75
  • 第一次添加元素或者长度大于数组长度*加载因子时就会扩容(第一次添加为16)
  • 扩容的长度为原来的2倍
  • 然后遍历旧数组,把原来的老的元素存到新的数组中(原哈希值与运算老的长度等于零则留在老的位置,否则移到老位置+老数组长度)
  • 哈希值运算(扰动算法):(h = key.hashCode())^(h>>>16)为的是让其更加均匀
  • 取模运算:hash &(n-1),当n为2的n次幂时,这完全等价于hash%n但效率更高

冲突解决

- 散列冲突-拉链法:每个下标称之为桶(bucket)或者槽(slot),每个桶或者槽对应一个链表

concurrentHashMap

  1. jdk1.7之前
    • hashcode->segment(数组默认为8,一定为2的幂次方)->对应的(原)hashMap(最小与默认为2),长度为两个相乘(默认为16)
    • 算出的段不同则不需要加锁,相同则使用分段锁提高性能
    • 修改时先使用tryLock()非阻塞加锁,自旋了64次(多核,单核为1次)之后会改用lock加锁。
    • 调用put方法会查看key是否存在(可在自旋时检查),存在则直接覆盖,不存在则创建
    • 创建时会多次检测是否已经创建,使用了cas方法(不加锁),最终保证只会创建一个对象
  2. jdk1.8之后
    • 进入乐观锁,进行初始化操作(如果还没初始化)
    • cas去判空与新建与1.7一样
    • 如果需要扩容,先扩容
    • (产生哈希冲突)加锁,遍历链表,选择覆盖操作还是新建操作,调用的syncronized的锁

Hashtable与concurrentHashMap区别

同步性

  • Hashtable: 整个Hashtable 的方法都是同步的,即每个方法都被 synchronized 关键字修饰,保证了线程安全。这意味着在并发访问时,只能有一个线程执行任何Hashtable 方法。
  • ConcurrentHashMap: ConcurrentHashMap 使用了更细粒度的锁机制,采用分段锁的方式。不同的段(Segment)上的操作是相互独立的,可以并发执行,提高了并发性能。

    Null键值:

  • Hashtable: 不允许键或值为null。
  • ConcurrentHashMap: 允许null键和null值。

    迭代器弱一致性:

  • Hashtable: 使用迭代器遍历时是安全的,因为迭代器是同步的,但可能会抛出ConcurrentModificationException 异常。
  • ConcurrentHashMap: 支持并发修改,并且迭代器是弱一致的,允许在迭代过程中修改集合,并不一定能够反映出最新的修改。

    容量扩充:

  • Hashtable: 在容量达到一定阈值时会自动扩充。
  • ConcurrentHashMap: 采用了分段锁的设计,每个段都有自己的大小和阈值,因此可以更灵活地进行扩充。

    总体而言,ConcurrentHashMap 是在高并发环境下更推荐使用的 Map 实现,因为它提供了更好的性能和灵活性。但在特定情况下,例如要求完全同步的场景,Hashtable 仍然可以考虑。

ThreaLocal

  • 功能: 独立线程与线程之间的数据
  • 实现: 一共有三个方法:get()、set()、remove()。看了半天,说人话应该就是新建一个Map(默认16长度),使用哈希取余那套,根据key(线程)去设置到对应的Map中,每次取Map对应的那个value。
感谢您的收看~
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇