木西笔记

个人博客

Redis系列之数据结构篇(3)

跳表和压缩表

本文转自 redis 的设计与实现 跳表 – 跳表的结构 跳跃表(skiplist)是一种随机化的数据, 跳跃表以有序的方式在层次化的链表中保存元素, 效率和平衡树媲美 —— 查找、删除、添加等操作都可以在对数期望时间下完成, 并且比起平衡树来说, 跳跃表的实现要简单直观得多。 以下是个典型的跳跃表例子(图片来自维基百科): 从图中可以看到, 跳跃表主要由以下部分构成: 表头(hea...

大数据算法之空间亚线性算法(二)

Misra-Gries 算法(数据流中最频繁的的数字)

概诉 水库抽样算法 样算法虽然是抽样算法却不是近似算法。本节分享一下有限内存利用近似解求数据流中最频繁的元素。 Misra-Gries算法是频繁项挖掘中一个著名的算法。频繁项就是那些在数据流中出现频率最高的数据项。频繁项挖掘,这个看似简单的任务却是很多复杂算法的基础,同时也有着广泛的应用。 对于频繁项挖掘而言,一个简单的想法是,为所有的数据项分配计数器,当一个数据项到达,我们即增加相应计数器...

大数据算法之空间亚线性算法(一)

水库抽样算法

问题描述 输入:一组数据,大小未知 输出:这组数据的K个均匀抽取 要求:仅扫描一次 总体要求:从N个元素中随机的抽取k个元素,其中N无法确定,保证每个元素抽到的概率相同 问题难点 首先明确什么叫均匀抽样,就是每个数据被等概率抽取呗。即当样本总体为n 时候,每个样本被抽取的概率为1/n,如果要抽取k个元素,那么每个样本被抽到的概率为k/n。但是我们实现不知道总体的数量n。如果就只有n=K个...

Redis系列之数据结构篇(4)

对象简介

本文转自 redis 的设计与实现 简介 我们陆续介绍了 Redis 用到的所有主要数据结构, 比如简单动态字符串(SDS)、双端链表、字典、压缩列表、整数集合, 等等。 Redis 并没有直接使用这些数据结构来实现键值对数据库, 而是基于这些数据结构创建了一个对象系统, 这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象, 每种对象都用到了至少一种我们前...

Java8使用@sun.misc.Contended避免伪共享

什么是伪共享 缓存系统中是以缓存行(cache line)为单位存储的。缓存行是2的整数幂个连续字节,一般为32-256个字节。最常见的缓存行大小是64个字节。当多线程修改互相独立的变量时,如果这些变量共享同一个缓存行,就会无意中影响彼此的性能,这就是伪共享。 缓存行上的写竞争是运行在SMP系统中并行线程实现可伸缩性最重要的限制因素。有人将伪共享描述成无声的性能杀手,因为从代码中很难看清楚...

Java类加载机制

Java类加载机制的七个阶段 当我们的Java代码编译完成后,会生成对应的 class 文件。接着我们运行java Demo命令的时候,我们其实是启动了JVM 虚拟机执行 class 字节码文件的内容。而 JVM 虚拟机执行 class 字节码的过程可以分为七个阶段:加载、验证、准备、解析、初始化、使用、卸载。 加载 下面是对于加载过程最为官方的描述。 加载阶段是类加载过程的第一个阶段。在...

Redis系列之数据结构篇(2)

字典

本文转自 redis 的设计与实现 结构 Redis 的 Hash 类型键使用以下两种数据结构作为底层实现: 字典; 压缩列表; 因为压缩列表比字典更节省内存, 所以程序在创建新 Hash 键时, 默认使用压缩列表作为底层实现, 当有需要时, 程序才会将底层实现从压缩列表转换到字典。 Dict哈希表 Redis 字典所使用的哈希表由 dict.h/dictht 结构定义: 12345...

Redis系列之数据结构篇(1)

SDS和链表

概诉 本文转自 redis 的设计与实现 SDS SDS 简介 Redis 没有直接使用 C 语言传统的字符串表示(以空字符结尾的字符数组,以下简称 C 字符串), 而是自己构建了一种名为简单动态字符串(simple dynamic string,SDS)的抽象类型, 并将 SDS 用作 Redis 的默认字符串表示。 举个例子, 如果客户端执行命令: 12redis> SET m...

源码分析系列(2)

为什么禁止在 foreach 循环里进行元素的 remove/add 操作

在阿里巴巴Java开发手册中,有这样一条规定: foreach循环 123for(元素类型t 元素变量x : 遍历对象obj){ 引用了x的java语句; } 以下实例演示了 普通for循环 和 foreach循环使用: 1234567891011121314public static void main(String[] args) { /...

JAVA多线程之AQS分析(1)

ReentrantLock的源码分析独占锁的实现

概述 谈到并发,不得不谈ReentrantLock;而谈到ReentrantLock,不得不谈AbstractQueuedSynchronized(AQS)!,类如其名,抽象的队列式的同步器,AQS定义了一套多线程访问共享资源的同步器框架,许多同步类实现都依赖于它,如常用的ReentrantLock/Semaphore/CountDownLatch…。我们以ReentrantLock作为讲解...