List

1 引言之前介绍了Redis的数据存储及String类型的实现，接下来再来看下List、Hash、Set及Sorted Set的数据结构的实现。 2 ListList类型通常被用作异步音讯队列、文章列表查问等；存储有序可反复数据或做为简略的音讯推送机制时，能够应用Redis的List类型。对于这些数据的存储通常会应用链表或者数组作为存储构造。 应用数组存储，随机拜访节点通过索引定位工夫复杂度为O(1)。但在初始化时须要调配间断的内存空间；在减少数据时，如果超过以后调配空间，须要将数据整体搬迁徙到新数组中。应用链表存储，在进行前序遍历或后续遍历，以后节点中要存储前指针和后指针，这两个指针在别离须要8byte共16byte空间存储，存在大量节点会因指针占用过多空间。链表尽管不须要间断空间存储能够进步内存利用率，但频繁的减少和删除操作会使内存碎片化，影响数据读写速率。如果咱们可能将链表和数组的特点联合起来就可能很好解决List类型的数据存储。 2.1 ZipList3.2之前Redis应用的是ZipList，具体构造如下： zlbytes: 4byte 记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重调配， 或者计算 zlend 的地位时应用。zltail：4byte 记录压缩列表表尾节点间隔压缩列表的起始地址有多少字节： 通过这个偏移量，程序毋庸遍历整个压缩列表就能够确定表尾节点的地址。zllen：2byte 记录了压缩列表蕴含的节点数量： 当这个属性的值小于 UINT16\_MAX（65535）时， 这个属性的值就是压缩列表蕴含节点的数量； 当这个值等于UINT16\_MAX 时，节点的实在数量须要遍历整个压缩列表能力计算得出。entry X：压缩列表蕴含的各个节点，节点的长度由节点保留的内容决定。蕴含属性如下：prerawlen：记录前一个节点所占内存的字节数，不便查找上一个元素地址len：data依据len的首个byte选用不同的数据类型来存储datadata：本元素的信息zlend: 尾节点 恒等于255ziplist是一个间断的内存块，由表头、若干个entry节点和压缩列表尾部标识符zlend组成，通过一系列编码规定，进步内存的利用率，应用于存储整数和短字符串。每次减少和删除数据时，所有数据都在同一个ziplist中都会进行搬移操作。如果将一个组数据按阈值进行拆分出多个数据，就能保障每次只操作某一个ziplist。3.2之后应用的quicklist与ziplist。 2.2 QuickListquicklist就是保护了一种宏观上的双端链表(相似于B树)，链表的节点为对ziplist包装的quicklistNode，每个quciklistNode都会通过前后指针互相指向，quicklist蕴含头、尾quicklistNode的指针。 typedef struct quicklist {quicklistNode *head;quicklistNode *tail;unsigned long count; /* total count of all entries in all ziplists */unsigned long len; /* number of quicklistNodes */int fill : QL_FILL_BITS; /* fill factor for individual nodes */unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */...} quicklist;*head：表头节点*tail：表尾节点count：节点蕴含entries数量len：quicklistNode节点计数器fill：保留ziplist的大小，配置文件设定compress：保留压缩水平值，配置文件设定quicklistNode： ...

/** * 利用subList办法进行分页 * * @param list 分页数据 * @param pagesize 页面大小 * @param currentPage 以后页面 */private List pageBySubList(List list, int pagesize, int currentPage) { int totalcount = list.size(); int pagecount = 0; List<String> subList; int m = totalcount % pagesize; if (m > 0) { pagecount = totalcount / pagesize + 1; } else { pagecount = totalcount / pagesize; } if (m == 0) { subList = list.subList((currentPage - 1) * pagesize, pagesize * (currentPage)); } else { if (currentPage == pagecount) { subList = list.subList((currentPage - 1) * pagesize, totalcount); } else { subList = list.subList((currentPage - 1) * pagesize, pagesize * (currentPage)); } } return subList;}

前言：for循环能够删除汇合元素吗，往往咱们失去的答案有时候就是不能够，平安起见，要迭代器，包含我在阿里的开发标准里也写了这么一句话， 不要在 foreach 循环里进行元素的 remove / add 操作。remove 元素请应用 iterator 形式，如果并发操作，须要对 iterator 对象加锁  仍然记得刚来第三天写个接口我就for循环内删除元素，过后很沙雕，恰好又被代码走查看到了，难堪的我挖了个洞将for改成了迭代器形式遍历，这两天看个大佬的代码，他就是for循环并remove其中元素，我开心的认为发现了一个bug，嗯，再往下看不对，这代码妙啊，百度了一下，有了这篇文章 上面咱们通过几个例子以及剖析源码的形式来看看问题，nice 问题一List<String> list = new ArrayList();list.add("111");list.add("222");list.add("222");list.add("333");list.add("222");list.add("555");//list.stream().forEach(System.out::println);for(int i = 0;i < list.size();i++){ if(StrUtil.equals("222",list.get(i))){ list.remove(i); }}咱们先看下下面这个用例，这个后果是啥呢？是111 222 333 555，咦，明明等于222的移除了啊，怎么没移掉，而且还没报错，通常咱们移除元素会报错呀，其实这种for办法在咱们循环遍历的时候list.remove(i);会删除对应的元素不会报错，然而呢，删除的元素地位会空进去，前面的元素会往前移一位，这样如果有两个元素的地位是间断的话，那么前面这个元素是不会进行判断的，这样就不会合乎咱们的剖析场景的， 咱们按代码程序翻一下，索引在范畴内，则获取remove的元素，而后将list的元素大小减一，如果还存在，就进行元素的copy，从源数组的index+1地位开始要复制的数组元素的数量numMoved，到指标数组的指定地位，而后通过GC将最初一个地位内存回收，哦。原来是这样的，至于说的报错咱们上面在剖析 问题二for (String ll : list) { if(StrUtil.equals(ll,"333")){ list.remove(ll); }}如上代码，当咱们应用foreach的时候咱们须要remove的是一个对象，而不是for时的下标，这里会报错java.util.ConcurrentModificationException，这就是咱们说的报错了，我先把后果说了吧，这里咱们删除元素的话其实并不会报错，报错的是for循环哪里，在你remove后下一次遍历的时候才会报错，报异样的办法是java.util.ArrayList$Itr.checkForComodification，一看就是办法里的迭代器报错 一个是删除后元素地位前挪了导致间断相等的元素判断不到一个是删除元素后改变的次数变得和冀望变动的次数不一样了导致的这些异样信息for(int i = list.size()-1;i>=0;i--){ if(StrUtil.equals("222",list.get(i))){ String remove = list.remove(i); System.out.println("shanchu"+ remove); }}

本节，咱们实现一个极简版的虚构列表，固定尺寸的虚构列表，麻雀虽小，却是五脏俱全哦！ 需要实现一个固定尺寸的虚构渲染列表组件，props属性如下： props: { width: number; height: number; itemCount: number; itemSize: number;}应用形式: const Row = (..args) => (<div className="Row"></div>);<List className={"List"} width={300} height={300} itemCount={10000} itemSize={40}> {Row}</List>实现什么技术栈都能够，这里我的项目应用的react，那就选用react来实现。 初始化我的项目应用create-react-app初始化一个利用，而后启动，清理掉demo的代码。 虚构列表依据上一节的剖析，咱们核心技术实现是 一个render渲染函数，用来渲染数据；一个onScroll函数监听滚动事件，去更新 数据区间[startIndex, endIndex]，而后从新render。大略伪代码如下： class List extends React.PureComponent { state = {}; render() {}; onScroll() {};}接下来咱们进行细节填充实现，首先咱们须要依据数据渲染出第一屏初始化的dom，即要先实现render函数逻辑，咱们采纳相对定位的形式进行dom排版。 render() { // 从props解析属性 const { children, width, height, itemCount, layout, itemKey = defaultItemKey, } = this.props; // 预留方向设定属性 const isHorizontal = layout === "horizontal"; // 假如有一个函数_getRangeToRender能够帮咱们计算出 渲染区间 const [startIndex, stopIndex] = this._getRangeToRender(); const items = []; if (itemCount > 0) { // 循环创立元素 for (let index = startIndex; index <= stopIndex; index++) { items.push( createElement(children, { data: {}, key: itemKey(index), index, style: this._getItemStyle(index), // 帮忙计算dom的地位款式 }) ); } } // 假如getEstimatedTotalSize函数能够帮忙咱们计算出总尺寸 const estimatedTotalSize = getEstimatedTotalSize( this.props, ); return createElement( "div", { onScroll: this.onScroll, style: { position: "relative", height, width, overflow: "auto", WebkitOverflowScrolling: "touch", willChange: "transform", }, }, createElement("div", { children: items, style: { height: isHorizontal ? "100%" : estimatedTotalSize, pointerEvents: "none", width: isHorizontal ? estimatedTotalSize : "100%", }, }) );}OK，到了这里render函数的逻辑就写完了，是不是超级简略。接下来咱们实现以下 render函数外面应用到的辅助函数. ...