跳跃表学习笔记

跳跃表学习笔记

跳跃表(Skip List),是一种基于概率,提供了查找、插入、删除近似于O(logN)性能的数据结构。

这篇文章是学习跳跃表的一个记录,包含了跳跃表的原理以及其Java实现

阅读更多

Java容器之Map(JDK1.6)

Java容器之Map(JDK1.6)

Map是Java众多容器家族中一个重要的成员….

Map一个数据结构,对于数据结构而言,最重要的其实就是数据的组织形式,也就是数据在该结构中如何存放,其组织形式也最终决定了其功能、性能,其核心点在于初始化、增加元素、查找元素、删除元素等方面,因此,下面的内容都是围绕这些核心点进行展开

Map接口是Java容器框架重要的一员,其核心是将一个key映射为value,其中key必须是一个可序列化的类型,而value则没有限制,根据实现的不同,Map有几个重要的子类,如

  1. 基于Hash算法的HashMap,提供了接近O(1)的查找、修改、删除性能
  2. 同样基于Hash算法,并且提供插入顺序或者访问顺序获取的LinkedHashMap
  3. 同样基于Hash算法,并且具备并发性能的ConcurrentHashMap
  4. 基于红黑树,提供了基于key排序的TreeMap等

当然,此外还有很多基于其他算法的Map,不过最常用到的也就是上面的几种了,这篇文章大致分析了这几个实现的代码包括了结构特点,初始化、插入、查找、删除等

这篇文章基于JDK1.6,原因是1.6的代码比较直观,没有过多的为了性能优化而简化的逻辑,相对来说比较适合入门分析,之后会抽时间再分析1.7、1.8的实现

阅读更多

红黑树学习笔记

这篇文章是红黑树学习过程中的笔记,主要涉及到二叉搜索树、二叉平衡树、2-3树、红黑树,前面的每一种树都存在着各自的缺点,科学家们通过对这些缺点进行改进(现实世界不一定是按照这个顺序、过程来的,这里是我自己的理解,推导的过程),最终得到了红黑树这种数据结构

红黑树是一种高性能的二叉搜索树,提供了在极端情况下,插入、删除、查找都是O(Log(N))的性能,同时也是Java中TreeMap,以及JDK1.8中HashMap用于提高性能的重要实现依据

阅读更多

记一次神奇的RedisLockRegistry异常分析过程

一次神奇的RedisLockRegistry异常,程序运行过程中一直抛出java.nio.BufferOverflowException,百思不得其解,最后终于通过跟踪源代码,定位到问题,最终发现是低版本Spring-Redis的一个Bug

阅读更多

AQS之同步工具

在前面一篇文章中,详细分析了AQS的原理,但没有涉及到AQS的使用,对于AQS我们也只是知其所以然而不止其然,只知道AQS长什么样,有什么用,是怎么实现的,但却缺少了最核心的,AQS要怎么用

在这篇文章中,我们将详细分析众多基于AQS实现的同步工具,如ReentrantLockCountdownLatch等,通过这些工具的实现来了解AQS的使用,从而打通AQS使用、分析的整个过程

阅读更多

AQS之AQS分析

接下来的这篇文章将详细分析AQS,AQS全称是AbstractQueuedSynchronizer,翻译过来是抽象队列同步器,也即AQS是一个基于队列实现的抽象同步器

AQS封装了获取锁,释放锁等操作,同时暴露一些try开头的方法交给子类来实现,通过继承AQS可以非常方便地实现一个线程安全的并发同步器,在java.util.concurrent包中的大多数高层次同步器,如CountdownLatchReentrantLock等都是通过AQS实现的

常用的基于AQS高层次同步器有如下几个

  • CountdownLatch
  • CyclicBarrier
  • Semaphore
  • ReentrantLock

这篇文章只分析AQS提供的通用逻辑实现,分析完AQS之后,后面再用新的篇章分析基于AQS的同步工具的具体实现细节

本文参考自javadoop

一行一行源码分析清楚AbstractQueuedSynchronizer

一行一行源码分析清楚 AbstractQueuedSynchronizer (二)

非常感谢大神无私地分享

阅读更多

LockSupport使用及分析

这篇文章主要是对LockSupport工具进行分析,LockSupport是提供给concurrent包中的其他工具使用的底层工具,主要是用于线程的阻塞以及唤醒

阅读更多

TimeUnit使用及分析

这篇文章主要是学习TimeUnit过程的一个记录及分析

TimeUnit是java.util.concurrent包下一个非常有用而且非常好用的工具,用于方便地进行各种时间单位的转换以及提供一些多时间单位的工具

阅读更多

AtomicXXX使用及分析

这篇文章主要是学习java.util.concurrent.atomic包过程中的记录及分析

atomic包下提供了众多的无锁的,线程安全的并发工具,在某些程度上扩充了Java的并发体系

阅读更多