跳跃表学习笔记

跳跃表学习笔记

跳跃表(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用于提高性能的重要实现依据

阅读更多