xindoo

xindoo 查看完整档案

北京编辑青岛理工大学  |  软件工程 编辑小米  |  后端开发 编辑 zxs.io 编辑
编辑

9年技术博主,CSDN认证博客专家
曾在阿里做过3年运维相关工作,现为某厂Java后端开发工程师,拥有丰富的 挖坑 踩坑 填坑 背锅经验 [手动狗头]

个人动态

xindoo 发布了文章 · 10月18日

Redis源码剖析之快速列表(quicklist)

何为quicklist,上次说到ziplist每次变更的时间复杂度都非常高,因为必须要重新生成一个新的ziplist来作为更新后的list,如果一个list非常大且更新频繁,那就会给redis带来非常大的负担。如何既保留ziplist的空间高效性,又能不让其更新复杂度过高? redis的作者给出的答案就是quicklist。

其实说白了就是把ziplist和普通的双向链表结合起来。每个双链表节点中保存一个ziplist,然后每个ziplist中存一批list中的数据(具体ziplist大小可配置),这样既可以避免大量链表指针带来的内存消耗,也可以避免ziplist更新导致的大量性能损耗,将大的ziplist化整为零

数据结构

quicklist

一图胜千言,我们来看下一个实际的quicklist在内存中长啥样。
在这里插入图片描述

大致介绍下上图中不同的节点,所有redis中list其实都是quicklist,所以像pop push等命令中的list参数都是quicklist。quicklist各字段及其含义如下。

typedef struct quicklist {
    quicklistNode *head;        /* 头结点 */
    quicklistNode *tail;        /* 尾结点 */
    unsigned long count;        /* 在所有的ziplist中的entry总数 */
    unsigned long len;          /* quicklist节点总数 */
    int fill : QL_FILL_BITS;              /* 16位,每个节点的最大容量 */
    unsigned int compress : QL_COMP_BITS; /* 16位,quicklist的压缩深度,0表示所有节点都不压缩,否则就表示从两端开始有多少个节点不压缩 */
    unsigned int bookmark_count: QL_BM_BITS;  /*4位,bookmarks数组的大小,bookmarks是一个可选字段,用来quicklist重新分配内存空间时使用,不使用时不占用空间*/
    quicklistBookmark bookmarks[];
} quicklist;

可以看出quicklist其实就是简单的双链表,但这里多出来几个字段,先重点介绍下compress。在上图中我用了两种不同颜色的节点,其中绿色是普通的ziplist节点,而红色是被压缩后的ziplist节点(LZF节点),LZF是种无损压缩算法。redis为了节省内存空间,会将quicklist的节点用LZF压缩后存储,但这里不是全部压缩,可以配置compress的值,compress为0表示所有节点都不压缩,否则就表示从两端开始有多少个节点不压缩,像我上图图示中,compress就是1,表示从两端开始,有1个节点不做LZF压缩。compress默认是0(不压缩),具体可以根据你们业务实际使用场景去配置。

为什么不全部节点都压缩,而是流出compress这个可配置的口子呢?其实从统计而已,list两端的数据变更最为频繁,像lpush,rpush,lpop,rpop等命令都是在两端操作,如果频繁压缩或解压缩会代码不必要的性能损耗。从这里可以看出 redis其实并不是一味追求性能,它也在努力减少存储占用、在存储和性能之间做trade-off

这里还有个fill字段,它的含义是每个quicknode的节点最大容量,不同的数值有不同的含义,默认是-2,当然也可以配置为其他数值,具体数值含义如下:

  • -1: 每个quicklistNode节点的ziplist所占字节数不能超过4kb。(建议配置)
  • -2: 每个quicklistNode节点的ziplist所占字节数不能超过8kb。(默认配置&建议配置)
  • -3: 每个quicklistNode节点的ziplist所占字节数不能超过16kb。
  • -4: 每个quicklistNode节点的ziplist所占字节数不能超过32kb。
  • -5: 每个quicklistNode节点的ziplist所占字节数不能超过64kb。
  • 任意正数: 表示:ziplist结构所最多包含的entry个数,最大为215215。

quicklistNode

quicklistNode就是双链表的节点封装了,除了前后节点的指针外,这里还包含一些本节点的其他信息。比如是否是LZF压缩的节点、ziplist相关信息…… 具体如下:

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;           /* quicklist节点对应的ziplist */
    unsigned int sz;             /* ziplist的字节数 */
    unsigned int count : 16;     /* ziplist的item数*/
    unsigned int encoding : 2;   /* 数据类型,RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* 这个节点以前压缩过吗? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* 未使用到的10位 */
} quicklistNode;

从上文中我们已经了解了一个quicklist某个时刻在内存中的样子,接下我们来看下它是如何在数据插入删除时变化的。

quicklist的操作

创建

/* 创建一个新的quicklist.
 * 使用quicklistRelease()释放quicklist. */
quicklist *quicklistCreate(void) {
    struct quicklist *quicklist;

    quicklist = zmalloc(sizeof(*quicklist));
    quicklist->head = quicklist->tail = NULL;
    quicklist->len = 0;
    quicklist->count = 0;
    quicklist->compress = 0;
    quicklist->fill = -2;
    quicklist->bookmark_count = 0;
    return quicklist;
}

create就没啥好说的了,但这里需要提醒下,fill值默认是-2,也就是说每个quicklistNode中的ziplist最长是8k字节,可以更具自己业务需求调整具体配置。

头插和尾插

对于list而已,头部或者尾部插入是最常见的操作了,但其实头插和尾插还算是比较简单。

/* 在quicklist的头部插入一条数据  
 * 如果在已存在节点插入,返回0
 * 如果是在新的头结点插入,返回1 */
int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
    quicklistNode *orig_head = quicklist->head;
    if (likely(
            _quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
        quicklist->head->zl =
            ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);  // 在头结点对应的ziplist中插入 
        quicklistNodeUpdateSz(quicklist->head);
    } else { // 否则新建一个头结点,然后插入数据 
        quicklistNode *node = quicklistCreateNode();
        node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);

        quicklistNodeUpdateSz(node);
        _quicklistInsertNodeBefore(quicklist, quicklist->head, node);
    }
    quicklist->count++;
    quicklist->head->count++;
    return (orig_head != quicklist->head);
}

/* 在quicklist的尾部插入一条数据  
 * 如果在已存在节点插入,返回0
 * 如果是在新的头结点插入,返回1 */
int quicklistPushTail(quicklist *quicklist, void *value, size_t sz) {
    quicklistNode *orig_tail = quicklist->tail;
    if (likely(
            _quicklistNodeAllowInsert(quicklist->tail, quicklist->fill, sz))) {
        quicklist->tail->zl =
            ziplistPush(quicklist->tail->zl, value, sz, ZIPLIST_TAIL);
        quicklistNodeUpdateSz(quicklist->tail);
    } else {
        quicklistNode *node = quicklistCreateNode();
        node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_TAIL);

        quicklistNodeUpdateSz(node);
        _quicklistInsertNodeAfter(quicklist, quicklist->tail, node);
    }
    quicklist->count++;
    quicklist->tail->count++;
    return (orig_tail != quicklist->tail);
}

头插和尾插都调用了_quicklistNodeAllowInsert先判断了是否能直接在当前头|尾节点能插入,如果能就直接插入到对应的ziplist里,否则就需要新建一个新节点再操作了。 还记得上文中我们说的fill字段吗,_quicklistNodeAllowInsert其实就是根据fill的具体值来判断是否已经超过最大容量。

特定位置插入

头插尾插比较简单,但quicklist在非头尾插入就比较繁琐了,因为需要考虑到插入位置、前节点、后节点的存储情况。

/* 在一个已经存在的entry前面或者后面插入一个新的entry 
 * 如果after==1表示插入到后面,否则是插入到前面  */
REDIS_STATIC void _quicklistInsert(quicklist *quicklist, quicklistEntry *entry,
                                   void *value, const size_t sz, int after) {
    int full = 0, at_tail = 0, at_head = 0, full_next = 0, full_prev = 0;
    int fill = quicklist->fill;
    quicklistNode *node = entry->node;
    quicklistNode *new_node = NULL;

    if (!node) {
        /* 如果entry中未填node,则重新创建一个node并插入到quicklist中 */
        D("No node given!");
        new_node = quicklistCreateNode();
        new_node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
        __quicklistInsertNode(quicklist, NULL, new_node, after);
        new_node->count++;
        quicklist->count++;
        return;
    }

    /* 检查要插入的节点是否是满的 */
    if (!_quicklistNodeAllowInsert(node, fill, sz)) {
        D("Current node is full with count %d with requested fill %lu",
          node->count, fill);
        full = 1;
    }

    if (after && (entry->offset == node->count)) {
        D("At Tail of current ziplist");
        at_tail = 1;
        if (!_quicklistNodeAllowInsert(node->next, fill, sz)) {
            D("Next node is full too.");
            full_next = 1;
        }
    }

    if (!after && (entry->offset == 0)) {
        D("At Head");
        at_head = 1;
        if (!_quicklistNodeAllowInsert(node->prev, fill, sz)) {
            D("Prev node is full too.");
            full_prev = 1;
        }
    }

    /* 不确定把新元素插到哪 */
    if (!full && after) { // 如果当前节点不满,就直接插入 
        D("Not full, inserting after current position.");
        quicklistDecompressNodeForUse(node);
        unsigned char *next = ziplistNext(node->zl, entry->zi);
        if (next == NULL) {
            node->zl = ziplistPush(node->zl, value, sz, ZIPLIST_TAIL);
        } else {
            node->zl = ziplistInsert(node->zl, next, value, sz);
        }
        node->count++;
        quicklistNodeUpdateSz(node);
        quicklistRecompressOnly(quicklist, node);
    } else if (!full && !after) {
        D("Not full, inserting before current position.");
        quicklistDecompressNodeForUse(node);
        node->zl = ziplistInsert(node->zl, entry->zi, value, sz);
        node->count++;
        quicklistNodeUpdateSz(node);
        quicklistRecompressOnly(quicklist, node);
    } else if (full && at_tail && node->next && !full_next && after) {
        /* 如果当前节点是满的,要插入的位置是当前节点的尾部,且后一个节点有空间,那就插到后一个节点的头部。*/
        D("Full and tail, but next isn't full; inserting next node head");
        new_node = node->next;
        quicklistDecompressNodeForUse(new_node);
        new_node->zl = ziplistPush(new_node->zl, value, sz, ZIPLIST_HEAD);
        new_node->count++;
        quicklistNodeUpdateSz(new_node);
        quicklistRecompressOnly(quicklist, new_node);
    } else if (full && at_head && node->prev && !full_prev && !after) {
        /* 如果当前节点是满的,要插入的位置是当前节点的头部,且前一个节点有空间,那就插到前一个节点的尾部。  */
        D("Full and head, but prev isn't full, inserting prev node tail");
        new_node = node->prev;
        quicklistDecompressNodeForUse(new_node);
        new_node->zl = ziplistPush(new_node->zl, value, sz, ZIPLIST_TAIL);
        new_node->count++;
        quicklistNodeUpdateSz(new_node);
        quicklistRecompressOnly(quicklist, new_node);
    } else if (full && ((at_tail && node->next && full_next && after) ||
                        (at_head && node->prev && full_prev && !after))) {
        /* 如果当前节点是满的,前后节点也都是满的,那就创建一个新的节点插进去 */
        D("\tprovisioning new node...");
        new_node = quicklistCreateNode();
        new_node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
        new_node->count++;
        quicklistNodeUpdateSz(new_node);
        __quicklistInsertNode(quicklist, node, new_node, after);
    } else if (full) {
        /* 否则,当前节点是满的,我们需要把它分裂成两个新节点,一般用于插入到当前节点ziplist中间某个位置时 */
        D("\tsplitting node...");
        quicklistDecompressNodeForUse(node);
        new_node = _quicklistSplitNode(node, entry->offset, after);
        new_node->zl = ziplistPush(new_node->zl, value, sz,
                                   after ? ZIPLIST_HEAD : ZIPLIST_TAIL);
        new_node->count++;
        quicklistNodeUpdateSz(new_node);
        __quicklistInsertNode(quicklist, node, new_node, after);
        _quicklistMergeNodes(quicklist, node);
    }

    quicklist->count++;
}

代码比较长,总结如下:

  • 如果当前被插入节点不满,直接插入。
  • 如果当前被插入节点是满的,要插入的位置是当前节点的尾部,且后一个节点有空间,那就插到后一个节点的头部。
  • 如果当前被插入节点是满的,要插入的位置是当前节点的头部,且前一个节点有空间,那就插到前一个节点的尾部。
  • 如果当前被插入节点是满的,前后节点也都是满的,要插入的位置是当前节点的头部或者尾部,那就创建一个新的节点插进去。
  • 否则,当前节点是满的,且要插入的位置在当前节点的中间位置,我们需要把当前节点分裂成两个新节点,然后再插入。

数据删除

数据删除相对于插入而言应该是反着来的,看完下面的代码后你就会发现不完全是:

void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry) {
    quicklistNode *prev = entry->node->prev;
    quicklistNode *next = entry->node->next;
    int deleted_node = quicklistDelIndex((quicklist *)entry->quicklist,
                                         entry->node, &entry->zi);

    /* after delete, the zi is now invalid for any future usage. */
    iter->zi = NULL;

    /* If current node is deleted, we must update iterator node and offset. */
    if (deleted_node) {
        if (iter->direction == AL_START_HEAD) {
            iter->current = next;
            iter->offset = 0;
        } else if (iter->direction == AL_START_TAIL) {
            iter->current = prev;
            iter->offset = -1;
        }
    }
}
REDIS_STATIC int quicklistDelIndex(quicklist *quicklist, quicklistNode *node,
                                   unsigned char **p) {
    int gone = 0;

    node->zl = ziplistDelete(node->zl, p);
    node->count--;
    if (node->count == 0) {
        gone = 1;
        __quicklistDelNode(quicklist, node);
    } else {
        quicklistNodeUpdateSz(node);
    }
    quicklist->count--;
    /* If we deleted the node, the original node is no longer valid */
    return gone ? 1 : 0;
}

删除相对于插入而言简单多了,我先看的插入逻辑,插入中有节点的分裂,但删除里却没有节点的合并,quicklist有节点最大容量,但没有最小容量限制

其他API

理解了quicklist数据结构的设计,也基本就能猜测到每个api的具体实现了,这里我就不再罗列代码了,有兴趣可以自行查阅。

quicklist *quicklistCreate(void);  // 创建quicklist 
quicklist *quicklistNew(int fill, int compress);  // 用一些指定参数创建一个新的quicklist
void quicklistSetCompressDepth(quicklist *quicklist, int depth);  // 设置压缩深度 
void quicklistSetFill(quicklist *quicklist, int fill); // 设置容量上限 
void quicklistSetOptions(quicklist *quicklist, int fill, int depth); 
void quicklistRelease(quicklist *quicklist); // 释放quicklist
int quicklistPushHead(quicklist *quicklist, void *value, const size_t sz);  // 头部插入
int quicklistPushTail(quicklist *quicklist, void *value, const size_t sz);  // 尾部插入
void quicklistPush(quicklist *quicklist, void *value, const size_t sz, 
                   int where); // 指定头部或者尾部插入  
void quicklistAppendZiplist(quicklist *quicklist, unsigned char *zl); // 把一个ziplist放到quicklist中
quicklist *quicklistAppendValuesFromZiplist(quicklist *quicklist,   
                                            unsigned char *zl); // 把ziplist中的所有数据放到quicklist中
quicklist *quicklistCreateFromZiplist(int fill, int compress,
                                      unsigned char *zl);  // 从ziplist生成一个quicklist  
void quicklistInsertAfter(quicklist *quicklist, quicklistEntry *node,
                          void *value, const size_t sz);  
void quicklistInsertBefore(quicklist *quicklist, quicklistEntry *node,
                           void *value, const size_t sz);
void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry); // 数据删除 
int quicklistReplaceAtIndex(quicklist *quicklist, long index, void *data,
                            int sz);   // 数据替换 
int quicklistDelRange(quicklist *quicklist, const long start, const long stop);  // 范围删除  
quicklistIter *quicklistGetIterator(const quicklist *quicklist, int direction);  // 迭代器 
quicklistIter *quicklistGetIteratorAtIdx(const quicklist *quicklist,
                                         int direction, const long long idx);  // 从指定位置开始的迭代器  
int quicklistNext(quicklistIter *iter, quicklistEntry *node);   // 迭代器下一个位置  
void quicklistReleaseIterator(quicklistIter *iter);  // 释放迭代器  
quicklist *quicklistDup(quicklist *orig);  // 去重  
int quicklistIndex(const quicklist *quicklist, const long long index,
                   quicklistEntry *entry);  // 找到entry的下标索引 
void quicklistRewind(quicklist *quicklist, quicklistIter *li);
void quicklistRewindTail(quicklist *quicklist, quicklistIter *li);
void quicklistRotate(quicklist *quicklist);  // 选择quicklist  
int quicklistPopCustom(quicklist *quicklist, int where, unsigned char **data,
                       unsigned int *sz, long long *sval,
                       void *(*saver)(unsigned char *data, unsigned int sz)); 
int quicklistPop(quicklist *quicklist, int where, unsigned char **data, 
                 unsigned int *sz, long long *slong); // 数据pop 
unsigned long quicklistCount(const quicklist *ql);
int quicklistCompare(unsigned char *p1, unsigned char *p2, int p2_len); // 比较大小  
size_t quicklistGetLzf(const quicklistNode *node, void **data);  // LZF节点  

参考资料

本文是Redis源码剖析系列博文,同时也有与之对应的Redis中文注释版,有想深入学习Redis的同学,欢迎star和关注。
Redis中文注解版仓库:https://github.com/xindoo/Redis
Redis源码剖析专栏:https://zxs.io/s/1h
如果觉得本文对你有用,欢迎一键三连
查看原文

赞 0 收藏 0 评论 0

xindoo 发布了文章 · 10月5日

Redis源码剖析之压缩列表(ziplist)

本来打算只用一篇文章来讲解Redis中的list,在实际写作过程中发现Redis中有多种list的实现,所以准备拆成多篇文章,本文主要讲ziplist,ziplist也是quicklist的基础。另外还有skiplist,skiplist虽然是list,当主要和set命令相关,所以会放到后面。
本文主要涉及到的源码在ziplist.c

何为ziplist?我们可以在ziplist.c源码头部找到一段Redis作者的一段介绍。

The ziplist is a specially encoded dually linked list that is designed to be very memory efficient. It stores both strings and integer values, where integers are encoded as actual integers instead of a series of characters. It allows push and pop operations on either side of the list in O(1) time.However, because every operation requires a reallocation of the memory used by the ziplist, the actual complexity is related to the amount of memory used by the ziplist.

ziplist是为了提高存储效率而设计的一种特殊编码的双向链表。它可以存储字符串或者整数,存储整数时是采用整数的二进制而不是字符串形式存储。他能在O(1)的时间复杂度下完成list两端的push和pop操作。但是因为每次操作都需要重新分配ziplist的内存,所以实际复杂度和ziplist的内存使用量相关。

前半句还好理解,但每次操作都需要重新分配内存…… 就有点耐人寻味了。别急,你看完ziplist的具体实现就懂了。

ziplist在逻辑上是个双向链表,但它是存储在一大块连续的内存空间上的。与其说ziplist是个数据结构,倒不如说他是Redis中双向链表的序列化存储方式。

ziplist结构

整个ziplist在内存中的存储格式如下:
在这里插入图片描述
ziplist主要有这么几个部分:

  • zlbytes: 32位无符号整型,表示整个ziplist所占的空间大小,包含了zlbytes所占的4个字节。
  • 这个字段可以在重置整个ziplist大小时不需要遍历整个list来确定大小,空间换时间。
  • zltail: 32位无符号整型,表示整个list中最后一项所在的偏移量,方便在尾部做pop操作。
  • zllen: 16位,表示ziplist中所存储的entry数量,但是注意,这里最多表示$2^{16} -2$个entry, 如果是$2^{16}-1$有特殊含义,$2^{16}-1$表示存储数量超过了$2^{16}-2$个,但具体是多少个得遍历一次才能知道。
  • zlend: 8位,ziplist的末尾表示,值固定是255.
  • entry: 不定长,可能有多个,list中具体的数据项,下面会详细介绍。

entry

这里最核心的就是entry的数据格式,entry还真有些复杂,从上图中可以看出它主要有三个部分。

  • prelen: 前一个entry的存储大小,主要是为了方便从后往前遍历。
  • encoding: 数据的编码形式(字符串还是数字,长度是多少)
  • data: 实际存储的数据

比较复杂的是Redis为了节省内存空间,对上面三个字段设计了一套比较复杂的编码方式,本质上就是一套变长的编码协议,具体规则如下:

prelen

如果prelen数值小于254,那就只用一个字节来表示长度,如果长度大于等于254就用5个字节,第一个字节是固定值254(FE)来标识这是个特殊的数据,剩下的4个字节来表示实际的长度。

encoding

encoding的具体值取决于entry中具体的内容,当entry是个string时,encoding的前两字节存储了字符串的长度。当entry是一个整数的时候,前两字节默认都是1,后面两字节标识出后面存的是哪种类型的整数,第一个字节就足够判断出entry是什么类型了。不同的encoding类型示例如下:

  • |00pppppp| - 1字节
长度小于或者等于63的String类型,'pppppp'无符号6位数标识string长度。
  • |01pppppp|qqqqqqqq| - 2字节
长度小于或者等于16383的String类型(14位),注意:14位'pppppp'采用大端的方式存储
  • |10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5字节
长度大于等于16384的String类型,第二字节开始的qqrrsstt都是用来存储字符串长度的二进制位,可表示的字符串长度最大2^32-1,第一字节的低6位没有用,所以都是0。
注意: 32位数采用大端的方式存储
  • |11000000| - 3字节
存储int16_t (2字节).
  • |11010000| - 5字节
存储int32_t (4字节).
  • |11100000| - 9字节
存储int64_t (8字节).
  • |11110000| - 4字节
24位有符号类型整数 (3字节).
  • |11111110| - 2字节
8位有符号类型整数 (1字节).
  • |1111xxxx| - (xxxx在0001和1101之间) 4位无符号整数.
0到12的无符号整数.编码值实际上是从1到13,因为0000和1111不能使用,要留出一位表示0,所以应该从编码值中减去1才是准确值

在某些比较小的数值下,具体值可以直接存储到encoding字段里。

ziplist的API

ziplist.c代码也较多,双链表操作很多代码在ziplist中比较多,其实本质上都是它这复杂的存储格式导致的,实际上理解了它的编码格式,具体代码不难理解。这里我只列出几个我认为比较重要的API,其他可以参考源码ziplist.c

ziplist其实只是一种双向队列的序列化方式,是在内存中的存储格式,实际上并不能直接拿过来用,用户看到的ziplist只是一个char *指针,其中每个entry在实际使用中还需要反序列化成zlentry方便调用。

typedef struct zlentry {
    unsigned int prevrawlensize; /* 内存中编码后的prevrawlen用了多少字节 */
    unsigned int prevrawlen;     /* 前一个entry占用的长度,主要是为了entry之间跳转 */
    unsigned int lensize;        /* 内存中编码后的len用了多少字节 */
    unsigned int len;            /* 当前entry的长度,如果是string则表示string的长度,如果是整数,则len依赖于具体数值大小。*/
    unsigned int headersize;     /* prevrawlensize + lensize. entry的head部分用了多少字节 */
    unsigned char encoding;      /* 当前entry的编码格式 */
    unsigned char *p;            /* 指向数据域的指针 */
} zlentry;

另外有一点,ziplist在内存中是高度紧凑的连续存储,这意味着它起始对修改并不友好,如果要对ziplist做修改类的操作,那就需重新分配新的内存来存储新的ziplist,代价很大,具体插入和删除的代码如下。

/* 在p位置插入数据 *s. */
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
    size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen;
    unsigned int prevlensize, prevlen = 0;
    size_t offset;
    int nextdiff = 0;
    unsigned char encoding = 0;
    long long value = 123456789; /* initialized to avoid warning. Using a value
                                    that is easy to see if for some reason
                                    we use it uninitialized. */
    zlentry tail;

    /* 找到前一个节点计算出prevlensize和prevlen */
    if (p[0] != ZIP_END) {
        ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
    } else {
        unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
        if (ptail[0] != ZIP_END) {
            prevlen = zipRawEntryLength(ptail);
        }
    }

    /* See if the entry can be encoded */
    if (zipTryEncoding(s,slen,&value,&encoding)) {
        /* 'encoding' is set to the appropriate integer encoding */
        reqlen = zipIntSize(encoding);
    } else {
        /* 'encoding' is untouched, however zipStoreEntryEncoding will use the
         * string length to figure out how to encode it. */
        reqlen = slen;
    }
    /* We need space for both the length of the previous entry and
     * the length of the payload. */
    reqlen += zipStorePrevEntryLength(NULL,prevlen);
    reqlen += zipStoreEntryEncoding(NULL,encoding,slen);

    /* When the insert position is not equal to the tail, we need to
     * make sure that the next entry can hold this entry's length in
     * its prevlen field. */
    int forcelarge = 0;
    nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
    if (nextdiff == -4 && reqlen < 4) {
        nextdiff = 0;
        forcelarge = 1;
    }

    /* Store offset because a realloc may change the address of zl. */
    offset = p-zl;
    // 计算出需要的内存容量,然后重新生成一个新大小的zl替换掉原来的zl。
    zl = ziplistResize(zl,curlen+reqlen+nextdiff);
    p = zl+offset;

    /* 迁移数据,然后更新tail的offset */
    if (p[0] != ZIP_END) {
        /* Subtract one because of the ZIP_END bytes */
        memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);

        /* Encode this entry's raw length in the next entry. */
        if (forcelarge)
            zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
        else
            zipStorePrevEntryLength(p+reqlen,reqlen);

        /* Update offset for tail */
        ZIPLIST_TAIL_OFFSET(zl) =
            intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);

        /* When the tail contains more than one entry, we need to take
         * "nextdiff" in account as well. Otherwise, a change in the
         * size of prevlen doesn't have an effect on the *tail* offset. */
        zipEntry(p+reqlen, &tail);
        if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {
            ZIPLIST_TAIL_OFFSET(zl) =
                intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
        }
    } else {
        /* This element will be the new tail. */
        ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
    }

    /* When nextdiff != 0, the raw length of the next entry has changed, so
     * we need to cascade the update throughout the ziplist */
    if (nextdiff != 0) {
        offset = p-zl;
        zl = __ziplistCascadeUpdate(zl,p+reqlen);
        p = zl+offset;
    }

    /* 写入数据 */
    p += zipStorePrevEntryLength(p,prevlen);
    p += zipStoreEntryEncoding(p,encoding,slen);
    if (ZIP_IS_STR(encoding)) {
        memcpy(p,s,slen);
    } else {
        zipSaveInteger(p,value,encoding);
    }
    ZIPLIST_INCR_LENGTH(zl,1);
    return zl;
}

ziplist节点删除

unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) {
    unsigned int i, totlen, deleted = 0;
    size_t offset;
    int nextdiff = 0;
    zlentry first, tail;

    zipEntry(p, &first);
    for (i = 0; p[0] != ZIP_END && i < num; i++) {
        p += zipRawEntryLength(p);
        deleted++;
    }

    totlen = p-first.p; /* 删除元素后减少的内存空间(字节) */
    if (totlen > 0) {
        if (p[0] != ZIP_END) {
            /* Storing `prevrawlen` in this entry may increase or decrease the
             * number of bytes required compare to the current `prevrawlen`.
             * There always is room to store this, because it was previously
             * stored by an entry that is now being deleted. */
            nextdiff = zipPrevLenByteDiff(p,first.prevrawlen);

            /* Note that there is always space when p jumps backward: if
             * the new previous entry is large, one of the deleted elements
             * had a 5 bytes prevlen header, so there is for sure at least
             * 5 bytes free and we need just 4. */
            p -= nextdiff;
            zipStorePrevEntryLength(p,first.prevrawlen);

            /* Update offset for tail */
            ZIPLIST_TAIL_OFFSET(zl) =
                intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);

            /* When the tail contains more than one entry, we need to take
             * "nextdiff" in account as well. Otherwise, a change in the
             * size of prevlen doesn't have an effect on the *tail* offset. */
            zipEntry(p, &tail);
            if (p[tail.headersize+tail.len] != ZIP_END) {
                ZIPLIST_TAIL_OFFSET(zl) =
                   intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
            }

            /* 把tail移动到ziplist的前面*/
            memmove(first.p,p,
                intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1);
        } else {
            /* The entire tail was deleted. No need to move memory. */
            ZIPLIST_TAIL_OFFSET(zl) =
                intrev32ifbe((first.p-zl)-first.prevrawlen);
        }

        /* 更新ziplist大小 */
        offset = first.p-zl;
        zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);
        ZIPLIST_INCR_LENGTH(zl,-deleted); // 更新zllen 
        p = zl+offset;

        /* When nextdiff != 0, the raw length of the next entry has changed, so
         * we need to cascade the update throughout the ziplist */
        if (nextdiff != 0)
            zl = __ziplistCascadeUpdate(zl,p);
    }
    return zl;
}

插入删除的基本逻辑都是类似,先定位,然后算插入/删除后所需的内存空间变化,根据计算出来新的空间大小对zl做ziplistResize(),然后更新zl的元信息。
除了插入删除外,像ziplistPushziplistMerge,这这种带改动的API,最后都调用了 ziplistResizeziplistResize代码如下:

unsigned char *ziplistResize(unsigned char *zl, unsigned int len) {
    zl = zrealloc(zl,len);
    ZIPLIST_BYTES(zl) = intrev32ifbe(len);
    zl[len-1] = ZIP_END;
    return zl;
}

看起来很简短,其实大量的逻辑都在zrealloc中,zrealloc是个宏定义(突然感觉c的宏定义很骚),其实主要逻辑就是申请一块长度为len的空间,然后释放原来zl所指向的空间。这里可以看出 ziplist修改的代价是很高的 ,如果在使用中有频繁更新list的操作,建议对list相关的配置做些优化。

其他API

具体API定义列表见源码ziplist.h

unsigned char *ziplistNew(void);  // 新建ziplist
unsigned char *ziplistMerge(unsigned char **first, unsigned char **second);  // 合并两个ziplist 
unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where); // 在ziplist头部或者尾部push一个节点 
unsigned char *ziplistIndex(unsigned char *zl, int index); // 找到某个下标的节点  
unsigned char *ziplistNext(unsigned char *zl, unsigned char *p);  // 找到p节点的下一个节点 
unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p);  // 找到p节点的前一个节点  
unsigned int ziplistGet(unsigned char *p, unsigned char **sval, unsigned int *slen, long long *lval);  // 获取entry中存储的具体内容
unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen);  // 插入
unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p); // 删除  
unsigned char *ziplistDeleteRange(unsigned char *zl, int index, unsigned int num); // 删除某个下标区间内的节点 
unsigned int ziplistCompare(unsigned char *p, unsigned char *s, unsigned int slen);  // 比较两个节点的大小 
unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip); // 找到某个特定值的节点
unsigned int ziplistLen(unsigned char *zl);  // ziplist的长度  
size_t ziplistBlobLen(unsigned char *zl);  // ziplist的存储空间大小 
void ziplistRepr(unsigned char *zl);   // 

结语

ziplist其实是一个逻辑上的双向链表,可以快速找到头节点和尾节点,然后每个节点(entry)中也包含指向前/后节点的"指针",但作者为了将内存节省到极致,摒弃了传统的链表设计(前后指针需要16字节的空间,而且会导致内存碎片化严重),设计出了内存非常紧凑的存储格式。内存是省下来了,但操作复杂性也更新的复杂度上来了,当然Redis作者也考虑了这点,所以也设计出了ziplist和传统双向链表的折中——quicklist,我们将在下一篇博文中详细介绍quicklist。

本文是Redis源码剖析系列博文,同时也有与之对应的Redis中文注释版,有想深入学习Redis的同学,欢迎star和关注。
Redis中文注解版仓库:https://github.com/xindoo/Redis
Redis源码剖析专栏:https://zxs.io/s/1h
查看原文

赞 1 收藏 1 评论 0

xindoo 发布了文章 · 10月1日

面试题精选:单链表排序也能玩出花来

今天国庆节,祝大家中秋节快乐,顺便给大家拜个早年[狗头]。不过最近还在准备面试的同学们不要浪太狠,还是要好好学习的鸭。

单链表的排序在数据结构类的面试题中简直是集大成者,什么排序、链表、链表删除、添加…… 都能体现在单链表排序上,也非常考验候选者的编程基本功,思路说起来很简单,但能不能写出来又是另外一回事了。

有些人觉得面试面这种题意义不大,谁实际工作中会写过单链表的排序,不都是直接调Collections.sort()吗? 是,没错 是这样,也许对某些人而言,他会这道题和不会这道题对将来的工作产生不了任何影响,这就需要非常长的时间去验证了,显然招聘者等不了那么久,他们只想花最少的时间找到你的上限,摸到你的上限后他们就可以简单假设这条线下面的其他东西你都会了,虽然这种假设有局限性,会让那种恰巧准备了的人占了便宜,但这种方法却不失为成本最低的方法。这就好比高考一样,高考所考的内容大多数人一辈子都用不上,但高考仍有存在的意义。

扯远了,回到正题,单链表排序设计到的知识点都是大学本科数据结构里讲过的,所以对应届生而言这题完全不会超纲。对面试官而言,你能解释清楚思路 说明你在校数据结构学的还可以,你再能把你思路写出来,就能向面试官证明你编程能力可以。 (这里有个面试小技巧:知道思路不会写,先把思路给面试官讲一遍,你考数学写个解:还能得0.5分呢)

单链表排序可以用哪些排序算法? 我的回答是所有排序算法都可以用,但有些排序会相对简单些,本文我给出三种(选择、快排、归并)方法,剩余的几种排序算法有兴趣你可以自己实现下,当然有些可能会比较繁琐,是时候挑战下自己了[狗头]。这里我简化下题目,节点值为int整数,然后链表按增序排列。

这里先给出单链表节点类

public class LinkedNode {
    public int val;
    public LinkedNode next;
    public LinkedNode() {
        this(-1);
    }
    public LinkedNode(int val) {
        this.val = val;
    }
}

选择排序

选择排序的思路也很简单,每次从原链表中摘掉最小的一个节点,拼接到新链表中,直到原链表摘干净。

public class SelectSort implements SortStrategy {
    @Override
    public LinkedNode sort(LinkedNode head) {
        LinkedNode vHead = new LinkedNode(-1);
        vHead.next = head;
        // 增加虚拟头节点,方便操作,否则就需要用一堆if来判断了,代码会比较啰嗦 
        LinkedNode newHead = new LinkedNode(-1); 
        LinkedNode tail = newHead;  // tail指向新链表的末尾 
        // 每次从链表中摘出来最小的节点,拼接到新链表末尾
        while (vHead.next != null) {
            LinkedNode pre = vHead;
            LinkedNode cur = head;
            LinkedNode min = head;
            LinkedNode minPre = vHead;
            // 先遍历找最小的节点,记录下最小节点和它前面一个节点
            while (cur != null) {
                if (cur.val < min.val) {
                    minPre = pre;
                    min = cur;
                }
                pre = cur;
                cur = cur.next;
            }
            // 把min节点从原链表中摘除,并拼接到新链表中  
            tail.next = min;
            tail = tail.next;
            minPre.next = min.next;
        }
        return newHead.next; 
    }
}

归并

我个人感觉归并其实是最适合做单链表排序的算法,虽然代码稍微长有些,但思路清晰、好理解,而且时间复杂度只有O(nlogn)。归并的思路可以分为3个部分。

  1. 把链表分成两个链表;
  2. 分别对两个链表排序(可以递归做归并);
  3. 合并两个有序的单链表;

在这里插入图片描述
如图所示,红色为未排序链表,蓝色为排序后的链表,红色部分从上往下是拆分的过程,蓝色部分从上往下是合并的过程。 代码实现如下:

public class MergeSort implements SortStrategy {
    @Override
    public LinkedNode sort(LinkedNode head) {
        // 递归边界,如果有链表只有一个节点就没必要排序了  
        if (head == null || head.next == null) {
            return head;
        }
        // 新建了个头节点方便处理,否则就需要很多if来判断了
        LinkedNode l1 = new LinkedNode();
        LinkedNode l2 = new LinkedNode();
        LinkedNode p1 = l1;
        LinkedNode p2 = l2;
        LinkedNode p = head;
        // 将原链表一分为二,奇数编号节点在l1,偶数编号在l2
        while (p != null) {
            LinkedNode pnn = null;
            if (p.next != null) {
                pnn = p.next.next;
            }
            p1.next = p;
            p1 = p1.next;
            if (p.next != null) {
                p2.next = p.next;
                p2 = p2.next;
                p2.next = null;
            }
            p1.next = null;
            p = pnn;
        }
        // 递归将两个链表做归并排序.
        l1 = sort(l1.next);
        l2 = sort(l2.next);
        // 合并两个排序好的有序链表
        return merge(l1, l2);
    }

    // 合并两个有序链表 
    private LinkedNode merge(LinkedNode l1, LinkedNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        LinkedNode newHead = new LinkedNode();
        LinkedNode p = newHead;
        LinkedNode p1 = l1;
        LinkedNode p2 = l2;

        while (p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        while (p1 != null) {
            p.next = p1;
            p1 = p1.next;
            p = p.next;
        }
        while (p2 != null) {
            p.next = p2;
            p2 = p2.next;
            p = p.next;
        }
        return newHead.next;
    }
}

快排

快排整体的思路和归并差不多,都是拆分、递归、合并,但其拆分就要比归并的拆分策略复杂些。在上文归并算法中,我们只是简单将链表按奇偶变化拆分成了两个链表,但快排的拆分需要选择一个节点作为基准值,比它小的拆到左链表,反之的拆到右链表,然后递归对左右两个链表排序,最后合并。但它的合并就简单了,只需要 左链表+基准节点+又链表简单拼接在一起就可以了。
在这里插入图片描述

如图所示,黄色为我选中的基准节点(链表的头节点),红色为未排序链表,蓝色为排序后的链表,红色部分从上往下是拆分的过程,蓝色部分从上往下是合并的过程。具体代码实现如下:

public class QuickSort implements SortStrategy {
    @Override
    public LinkedNode sort(LinkedNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        LinkedNode left = new LinkedNode();
        LinkedNode right = new LinkedNode();
        LinkedNode p1 = left;
        LinkedNode p2 = right;
        LinkedNode p = head.next;
        LinkedNode base = head;  // 选取头节点为基准节点
        base.next = null;
        // 剩余节点中比基准值小就放left里,否则放right里,按照大小拆分为两条链表
        while (p != null) {
            LinkedNode pn = p.next;
            p.next = null;
            if (p.val < base.val) {
                p1.next = p;
                p1 = p1.next;
            } else {
                p2.next = p;
                p2 = p2.next;
            }
            p = pn;
        }
        // 递归对两条链表进行排序
        left.next = sort(left.next);
        right.next = sort(right.next);
        // 先把又链表拼到base后面 
        base.next = right.next;
        // 左链表+基准节点+右链表拼接,左链表有可能是空,所以需要特殊处理下
        if (left.next != null) {
            p = left.next;
            // 找到左链表的最后一个节点  
            while (p.next != null) {
                p = p.next;
            }
            // 把base拼接到左链表的末尾  
            p.next = base;
            return left.next;
        } else {
            return base;
        }
    }
}

面试题扩展

面试官也是要偷懒的,他们也懒得想题,再加上人的思维是具有连续性的,这就意味着大概率下一道面试题(如有)会和这道题相关,我总结这道题可以扩展的3个关键词单链表、排序、归并,基本上下一题都是这三个词的发散,这里我说下我可以发散出的题目。

  1. 单链相关的题,已经烂大街了,具体参考leetcode top100 链表题
  2. 排序相关:第k大的数,上文中快排可能出现的问题以及如何解决?(提示下,如果输入数据全为降序会怎么样)
  3. 归并:用一台2g内存的机器排序10个1g的文件。
欢迎关注我的面试专栏面试题精选永久免费 持续更新,本专栏会收集我遇到的比较经典面试题,除了提供详尽的解法外还会从面试官的角度提供扩展题,希望能帮助大家找到更好的工作。另外,也征集面试题,如果你遇到了不会的题 私信告诉我,有价值的题我会给你出一篇博客。
查看原文

赞 0 收藏 0 评论 0

xindoo 发布了文章 · 9月26日

Redis源码剖析之SDS(Simple Dynamic String)

SDS(simple dynamic string)是Redis提供的字符串的封装,在redis中也是存在最广泛的数据结构,它也是很多其他数据结构的基础,所以才选择先介绍SDS。 SDS也兼容部分C字符串API(strcmp,strlen),它如何兼容C字符串我觉得也是有个很sao的操作,等看完我这篇博客你就明白了。在开始正式内容前,我先抛几个问题(有些也是面试高频题),带着问题去学习也是一种非常好的学习方法。

  1. C语言中也算是支持String了,为什么Redis还要自己封装一个?
  2. SDS中的D(dynamic)到底是什么含义?
  3. SDS的数据结构是啥样的?为什么要那么设计?
  4. SDS是如何兼容C字符串的?

Redis中sds相关的源码都在src/sds.csrc/sds.h中(链接可以直接跳转到我中文注释版redis源码),其中sds.h中定义了所有SDS的api,当然也实现了部分几个api,比如sds长度、sds剩余可用空间……,不急着看代码,我们先看下sds的数据结构,看完后为什么代码那么写你就一目了然。

sdshdr数据结构

redis提供了sdshdr5 sdshdr8 sdshdr16 sdshdr32 sdshdr64这几种sds的实现,其中除了sdshdr5比较特殊外,其他几种sdshdr差不只在于两个字段的类型差别。我就拿 sdshdr8和sdshdr16来举例,其struct定义分别如下。

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 已使用空间大小 */
    uint8_t alloc; /* 总共可用的字符空间大小,应该是实际buf的大小减1(因为c字符串末尾必须是\0,不计算在内) */
    unsigned char flags; /* 标志位,主要是识别这是sdshdr几,目前只用了3位,还有5位空余 */
    char buf[];   /* 真正存储字符串的地方 */
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

sdshdr32 sdshdr64也和上面的结构一致,差别只在于len和alloc的数据类型不一样而已。相较于c原生的字符串,sds多了len、alloc、flag三个字段来存储一些额外的信息,redis考虑到了字符串拼接时带来的巨大损耗,所以每次新建sds的时候会预分配一些空间来应对未来的增长,sds和C string的关系熟悉java的旁友可能会决定就好比java中String和StringBuffer的关系。正是因为预留空间的机制,所以redis需要记录下来已分配和总空间大小,当然可用空间可用直接算出来。
在这里插入图片描述

下一个问题,为什么redis费心费力要提供sdshdr5到sdshdr64这五种SDS呢?我觉着这只能说明Redis作者抠内存抠到机制,牺牲了代码的简洁性换取了每个sds省下来的几个字节的内存空间。从sds初始化方法sdsnew和sdsnewlen中我们就可以看出,redis在新建sds时需要传如初始化长度,然后根据初始化的长度确定用哪种sdshdr,小于2^8长度的用sdshdr8,这样len和alloc只占用两个字节,比较短字符串可能非常多,所以节省下来的内存还是非常可观的,知道了sds的数据结构和设计原理,sdsnewlen的代码就非常好懂了,如下:

sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    // 根据初始化的长度确定用哪种sdshdr
    char type = sdsReqType(initlen);
    /* 空字符串大概率之后会append,但sdshdr5不适合用来append,所以直接替换成sdshdr8 */
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */

    sh = s_malloc(hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    /* 注意:返回的s并不是直接指向sds的指针,而是指向sds中字符串的指针,sds的指针还需要
     * 根据s和hdrlen计算出来 */
    s = (char*)sh+hdrlen;  
    fp = ((unsigned char*)s)-1;
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    s[initlen] = '\0';
    return s;
}

SDS的使用

上面代码中我特意标注了一个注意sdsnewlen()返回的sds指针并不是直接指向sdshdr的地址,而是直接指向了sdshdr中buf的地址。这样做有啥好处?好处就是这样可以兼容c原生字符串。buf其实就是C 原生字符串+部分空余空间,中间是特殊符号'0'隔开,‘0’有是标识C字符串末尾的符号,这样就实现了和C原生字符串的兼容,部分C字符串的API也就可以直接使用了。 当然这也有坏处,这样就没法直接拿到len和alloc的具体值了,但是也不是没有办法。

当我们拿到一个sds,假设这个sds就叫s吧,其实一开始我们对这个sds一无所知,连他是sdshdr几都不知道,这时候可以看下s的前面一个字节,我们已经知道sdshdr的数据结构了,前一个字节就是flag,根据flag具体的值我们就可以推断出s具体是哪个sdshdr,也可以推断出sds的真正地址,相应的就知道了它的len和alloc,知道了这点,下面这些有点晦涩的代码就很好理解了。

oldtype = s[-1] & SDS_TYPE_MASK; // SDS_TYPE_MASK = 7 看下s前面一个字节(flag)推算出sdshdr的类型。 

// 这个宏定义直接推算出sdshdr头部的内存地址
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)

// 获取sds支持的长度  
static inline size_t sdslen(const sds s) {
    unsigned char flags = s[-1];  // -1 相当于获取到了sdshdr中的flag字段  
    switch(flags&SDS_TYPE_MASK) {  
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->len;  // 宏替换获取到sdshdr中的len
        ...
        // 省略 SDS_TYPE_16 SDS_TYPE_32的代码…… 
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}
// 获取sds剩余可用空间大小 
static inline size_t sdsavail(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5: {
            return 0;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            return sh->alloc - sh->len;
        }
        ... 
        // 省略 SDS_TYPE_16 SDS_TYPE_32的代码…… 
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            return sh->alloc - sh->len;
        }
    }
    return 0;
}
/* 返回sds实际的起始位置指针 */
void *sdsAllocPtr(sds s) {
    return (void*) (s-sdsHdrSize(s[-1]));
}

SDS的扩容

在做字符串拼接的时候,sds可能剩余的可用空间不足,这个时候需要扩容,什么时候该扩容,又该怎么扩? 这是不得不考虑的问题。Java中很多数据结构都有动态扩容的机制,比如和sds很类似的StringBuffer,HashMap,他们都会在使用过程中动态判断是否空间充足,而且基本上都采用了先指数扩容,然后到一定大小限制后才开始线性扩容的方式,Redis也不例外,Redis在10241024以内都是2倍的方式扩容,只要不超出10241024都是先额外申请200%的空间,但一旦总长度超过10241024字节,那每次最多只会扩容10241024字节。 Redis中sds扩容的代码是在sdsMakeRoomFor(),可以看到很多字符串变更的API开头都直接或者间接调用这个。 和Java中StringBuffer扩容不同的是,Redis这里还需要考虑不同字符串长度时sdshdr类型的变化,具体代码如下:

// 扩大sds的实际可用空间,以便后续能拼接更多字符串。 
// 注意:这里实际不会改变sds的长度,只是增加了更多可用的空间(buf) 
sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK; // SDS_TYPE_MASK = 7 
    int hdrlen;

    /* 如果有足够的剩余空间,直接返回 */
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    // 在未超出SDS_MAX_PREALLOC前,扩容都是按2倍的方式扩容,超出后只能递增 
    if (newlen < SDS_MAX_PREALLOC)  // SDS_MAX_PREALLOC = 1024*1024
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;

    type = sdsReqType(newlen);

    /*  在真正使用过程中不会用到type5,如果遇到type5直接使用type8*/
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        // 扩容其实就是申请新的空间,然后把旧数据挪过去  
        newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }
    sdssetalloc(s, newlen);
    return s;
}

常用API

sds.c还有很多源码我都没有贴到,其他代码本质上都是围绕sdshdr数据结构和各种字符串操作写的(基本上都是各种字符串新建、拼接、拷贝、扩容……),只要知道了sds的设计原理,相信你也能轻易写出来,这里我就列一下所有sds相关的API,对源码有兴趣的旁友可以移步到src/sds.c,中文注释版的API列表见src/sds.c

sds sdsnewlen(const void *init, size_t initlen);  // 新建一个容量为initlen的sds
sds sdsnew(const char *init); // 新建sds,字符串为null,默认长度0 
sds sdsempty(void);  // 新建空字符“” 
sds sdsdup(const sds s); // 根据s的实际长度创建新的sds,目的是降低内存的占用
void sdsfree(sds s); // 释放sds 
sds sdsgrowzero(sds s, size_t len); // 把sds增长到指定的长度,增长出来的新的空间用0填充 
sds sdscatlen(sds s, const void *t, size_t len); // 在sds上拼接字符串t的指定长度部分 
sds sdscat(sds s, const char *t);  // 把字符串t拼接到sds上 
sds sdscatsds(sds s, const sds t); // 把两个sds拼接在一起  
sds sdscpylen(sds s, const char *t, size_t len); //  把字符串t指定长度的部分拷贝到sds上 
sds sdscpy(sds s, const char *t); // 把字符串t拷贝到sds上 

sds sdscatvprintf(sds s, const char *fmt, va_list ap); // 把用printf格式化后的字符拼接到sds上 

sds sdscatfmt(sds s, char const *fmt, ...);   // 将多个参数格式化成一个字符串后拼接到sds上 
sds sdstrim(sds s, const char *cset);  // 在sds中移除开头或者末尾在cset中的字符  
void sdsrange(sds s, ssize_t start, ssize_t end);  // 截取sds的子串 
void sdsupdatelen(sds s); // 更新sds字符串的长度 
void sdsclear(sds s);  // 清空sds中的内容,但不释放空间 
int sdscmp(const sds s1, const sds s2);  // sds字符串比较大小 
sds *sdssplitlen(const char *s, ssize_t len, const char *sep, int seplen, int *count);
void sdsfreesplitres(sds *tokens, int count);
void sdstolower(sds s); // 字符串转小写
void sdstoupper(sds s);  // 字符串转大写
sds sdsfromlonglong(long long value);  // 把一个long long型的数转成sds  
sds sdscatrepr(sds s, const char *p, size_t len); 
sds *sdssplitargs(const char *line, int *argc);
sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen);
sds sdsjoin(char **argv, int argc, char *sep); // 把字符串数组按指定的分隔符拼接起来
sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen); // 把sds数组按指定的分隔符拼接起来

/* sds底层api */
sds sdsMakeRoomFor(sds s, size_t addlen);  // sds扩容
void sdsIncrLen(sds s, ssize_t incr); // 扩容指定长度
sds sdsRemoveFreeSpace(sds s); // 释放sds占用的多余空间
size_t sdsAllocSize(sds s); // 返回sds总共占用的内存大小
void *sdsAllocPtr(sds s); // 返回sds实际的起始位置指针

void *sds_malloc(size_t size); // 为sds分配空间 
void *sds_realloc(void *ptr, size_t size); // 
void sds_free(void *ptr);  // 释放sds空间 

结语

回到开篇的几个问题,相信看完上面的内容后你都能回答上来了,如果回答不上来那就再多看两遍,本博客+源码搭配服用效果更佳。

为了控制博客篇幅,这里只讲解了核心代码,很多API的源码我都没有贴上来(毕竟太多),有兴趣的同学可以再看下源码 https://github.com/xindoo/redis/

本文是Redis源码剖析系列博文,同时也有与之对应的Redis中文注释版,有想深入学习Redis的同学,欢迎star和关注。
Redis中文注解版仓库:https://github.com/xindoo/redis
Redis源码剖析专栏:https://zxs.io/s/1h
查看原文

赞 0 收藏 0 评论 0

xindoo 关注了专栏 · 9月25日

SegmentFault 社区访谈

面向社区用户的访谈栏目,如果你愿意和我们分享你的故事,可以私信联系专栏入驻作者。

关注 2358

xindoo 发布了文章 · 9月20日

面试题精选:字符串替换

字符串处理在程序猿日常工作工作中非常常见,常见到几乎各种语言中都已经封装好了字符串相关的API,我们只需要直接拿过来用就好。就拿Java为例,jdk中的String()类几乎封装了所有字符串相关的操作,其方法数量有近百个,几乎满足了程序猿所有字符串相关的操作。
在这里插入图片描述
正是因为这么方便,估计大多数Java程序猿都没自己实现过字符串的replace。这里正式引入一下今天的精选面试题:不依赖第三方库 实现一个字符串替换replace(String str, String target, String replacement)函数,其功能是将str中所有的target替换为replacement。 其实这道题并不涉及任何复杂或者高深的算法,只需要掌握基本的编程就可以做,但当我某次把这道题拿出来面试某个应届生时,他代码写的磕磕绊绊的,后来我也陆陆续续用这题考过好几个人,鲜有顺畅写出来的,是我低估了这道题的难度??
在这里插入图片描述

解题思路

回到题目本身,我多说两句,仔细想想这道题其实也很简单,然而这就难倒了一大批人,大家刷面试题前还是要先打好编程基础。 这题的解题思路也很简单,我们新建个StringBuilder,只需要把str中不是target的部分加进去,如果是遇到target,就把replacement字符串加进去,真的没有任何复杂的算法 就是单纯考你编程的基本功,代码如下。

    public static String replace(String str, String target, String replacement) {
        // 正常这里需要对str,target,replacement做输入校验,这里我省略, 比如str比target端的时候可以直接返回空字符串  
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < str.length(); ) {
            if (isMatch(str, i, target)) {
                i += target.length();  // 如果匹配,需要直接向前跳target.length  
                res.append(replacement);
                continue;
            }
            res.append(str.charAt(i++));
        }
        return res.toString();
    }

    // 单纯确认从str的pos位置开始,是否和target相匹配  
    private static boolean isMatch(String str, int pos, String target) {
        for (int i = 0; i < target.length() && i + pos < str.length(); i++) {
            if (str.charAt(i + pos) != target.charAt(i)) {
                return false;
            }
        }
        return true;
    }

看吧,代码其实没啥难度,但咋就好多明显刷过其他面试题的人都不会呢!!!

Jdk中的replace实现

估计大多数人都没看过Jdk中的实现,所以顺带我们来欣赏下java String类中的replace方法是如何实现的。

    public String replace(CharSequence target, CharSequence replacement) {
        String tgtStr = target.toString();
        String replStr = replacement.toString();
        int j = indexOf(tgtStr);
        if (j < 0) {
            return this;
        }
        int tgtLen = tgtStr.length();
        int tgtLen1 = Math.max(tgtLen, 1);
        int thisLen = length();

        int newLenHint = thisLen - tgtLen + replStr.length();
        if (newLenHint < 0) {
            throw new OutOfMemoryError();
        }
        StringBuilder sb = new StringBuilder(newLenHint);
        int i = 0;
        do {
            sb.append(this, i, j).append(replStr);   // 先把未匹配字符添加进去,然后直接添加replStr  
            i = j + tgtLen;
        } while (j < thisLen && (j = indexOf(tgtStr, j + tgtLen1)) > 0);  // 找到下一个匹配的下标 
        return sb.append(this, i, thisLen).toString();
    }

jdk中的思路和我们上面写的思路是一致的,但jdk的代码更为精简,其实jdk也没用啥高深的东西,只是在indexOf()中考虑了更多数据编码的问题。

题目扩展

别看这道题简单,其实它也有好多可以扩展的地方,我来随便扩几个供大家参考下。

  1. Java中字符处理肯定免不了String StringBuffer和StringBuilder,都有啥区别?
  2. 之前老程序猿不推荐使用 str = str + "xx"的方式拼接字符串, 为什么? 而现在其实大多数情况下用StringBuilder.append和+拼接字符串就没那么多差异了? (提示:高版本的java对+的字符串拼接方式有优化)!
  3. 上文中我们用到了字符串匹配的方式,我们用的是最普通的匹配时间复杂度最差是O(mn),使用其他的匹配算法可以大幅提升性能,你都知道有哪些字符串匹配算法?(比如大家最耳熟能详的就是KMP)
欢迎关注我的面试专栏面试题精选永久免费 持续更新,本专栏会收集我遇到的比较经典面试题,除了提供详尽的解法外还会从面试官的角度提供扩展题,希望能帮助大家找到更好的工作。另外,也征集面试题,如果你遇到了不会的题 私信告诉我,有价值的题我会给你出一篇博客。
查看原文

赞 0 收藏 0 评论 0

xindoo 赞了文章 · 9月15日

熬夜7天,我总结了JavaScript与ES的25个重要知识点!

前言

说起JavaScript,大家都知道是一门脚本语言。那么ES是什么鬼呢?ES全称ECMAScript ,是JavaScript语言的国际标准。

最近总结了条js的基础特性相关的知识点,大家一起看一下吧

1.严格模式

  • 使用严格模式,可以在函数内部进行较为严格的全局和局部的错误条件检查
  • 严格模式的编译指示,"use strict"
  • 创建全局变量,未声明变量,非严格模式下为创建全局变量;严格模式下为抛出ReferenceError
  • 对变量调用delete操作符,删除变量,非严格模式下为静默失败;严格模式下为抛出ReferenceError
  • 操作对象情况下:a,只读属性赋值会抛出TypeError;b,对不可配置的属性使用delete操作符会抛出TypeError;c,为不可扩展的对象添加属性会抛出TypeError。
  • 重名属性情况:a,非严格模式下没有错误,以第二个属性为准;b,严格模式下会抛出语法错误。
  • 函数参数必须唯一,重名参数,在非严格模式下没有错误,只能访问第二个参数;严格模式下,会抛出错误。
function funValue(value) {
    value="dada";
    alert(value); // dada
    alert(argument[0]); // 非严格模式:dada
    // 严格模式模式 dadaqianduan
}

funValue('dadaqianduan');
  • 访问arguments.callee和arguments.caller,在非严格模式下没有问题,严格模式下抛出TypeError。

2.Class基础语法

在JavaScript当中如何声明一个类?如何定义类中的方法?如何实例化对象?

我们来看看下面的代码示例:

// es5

let dada = function(type) {
    this.type = type
}

dada.prototype.study = function() {
    console.log('魔王哪吒');
}

let da1 = new dada('程序员')
let da2 = new dada('It')

da1.constructor.prototype.study = function() {
    console.log('dadaqianduan');
}
da1.study()
JavaScript constructor 属性

定义和用法

constructor 属性返回对创建此对象的数组函数的引用。

语法

object.constructor

constructor 是一种用于创建和初始化class创建的对象的特殊方法。

// es6
class Da {
  constructor(name) { // 构造函数内写属性
    this.name = name;
  }
  eat() { // 构造函数外写方法
      console.log('i eat')
  }
}

const da1 = new Da('da1');

console.log(da1.name); // da1
console.log(da1);
  1. 一个类中只能有一个名为“constructor"的方法,出现多次构造函数constructor方法会抛出一个SyntaxError错误
  2. 在一个构造方法中可以使用super来调用一个父类的构造方法
  3. 如果没有指定一个构造函数方法constructor方法,就会使用一个默认的构造函数

3.类的属性Setter和Getter

var daObj = {
 get val() {
  return ;
 },
 set val(value) {
 }
}

get:

var da = {
    a: 1,
    get val(){
        return this.a + 1;
    }
}

console.log(da.val);//2
da.val = 100;
console.log(da.val);//2

class Da {
 constructor(type) {
  this.type = type
 }
 get age() {
  return 1
 }
 set age(val) {
  this.realAge = val
 }
 eat() {
  console.log('i am eat')
 }
}
let da1 = new Da('da1')
console.log(da1.age)
da1.age = 1
console.log(da1.realAge)
class Da {
 constructor(type, age) {
  this.type = type
  this.age1 = age
 }
 get age() {
  return this._age
 }
 set age(val) {
  this._age = val
 }
}
利用set/get实现对element.innerHTML封装
class myHTMLElement {
 constructor(element) {
  this.element = element
 }
 get html() {
  return this.element.innerHTML
 }
 set html(value) {
  this.element.innerHTML = value
 }
}

设置一个闭包,通过一定的规则来限制对它的修改:

let myName = 'dada'
class Da {
 constructor(type) {
  this.type = type
 }
 get name() {
  return myName
 }
 set name(val) {
  myName = val
 }
}

4.静态方法

在es5中实现的静态方法:

let Da = function (type) {
 this.type = type
 this.eat = function() {
  console.log('i eat')
 }
}
Da.study = function(book) {
 console.log('i book');
}
let Da = function(type) {
 this.type = type
}
Da.prototype.eat = function() {
 Da.walk()
 console.log('i am')
}
Da.walk = function(){
 console.log('walk')
}
let da1 = new Da('da1')
da1.eat()

// walk
// i am

静态方法在你的实例化对象是找不到的

在es6中的静态方法,标记static

class Da {
 constructor(type) {
  this.type = type
 }
 eat() {
  console.log('i eat')
 }
 static study() {
  console.log('i study')
 }
}

5.如何继承一个类

在es5中的继承:

// 定义一个父类
let Da = function(type) {
 this.type = type
}
// 定义方法
Da.prototype.eat = function() {
 console.log('i am')
}
// 定义静态方法
Da.study = function(book) {
 console.log('i study')
}
// 定义子类
let Da1 = function() {
 // 初始化父类
 Da.call(this, 'da1');
 this.run = function() {
  console.log('i run')
 }
}
// 继承
Da1.prototype = Da.prototype

在es6中的继承

class Da {
 constructor(type) {
  this.type = type
 }
 eat() {
  // Da.walk();
  console.log('i eat')
 }
 static walk(){
  console.log('i walk')
 }
}

class da extends Da {
 // 构造函数
 //constructor (type) {
  //super(type)
 //}
 run() {
  console.log('i run')
 }
}
let da1 = new da('da1')

6.面向对象编程Class

类的声明,属性,方法,静态方法,继承,多态,私有属性

// 类的声明
let Da = function(type) {
 this.type = type
 this.eat = function() {
  console.log('i eat');
 }
}

let da = new Da('da');
// prototype
let Da = function(type) {
 this.type = type
}
Da.prototype.eat = function() {
 console.log('i eat')
}
let da1 = new Da('da1')
es6中的Class
class Da {
 // 构造函数
 constructor(type) {
  this.type = type
 }
 // 方法
 walk() {
  console.log('i walk')
 }
}
let da = new Da('da');
// console.log(typeof Da); function

7.函数参数的默认值

函数参数是从左到右解析,如果没有默认值会被解析成 undefined
// 参数默认值
function da (x,y,z) {
}
function sum() {
 let num = 0
 Array.prototype.forEach.call(arguments, function(item){
  num += item * 1
 })
 Array.from(arguments).forEach(function(item){
  num += item * 1
 })
 return num
}
// 不确定
function sum(...nums) {
 let num = 0
 nums.forEach(function(item){
  num += item * 1
 })
 return num
}
console.log(sum(1,2,3,4,5))
function sum () {
  let num = 0
  Array.prototype.forEach.call(arguments, function (item) {
    num += item * 1
  })
  return num
}

function sum (...nums) {
  let num = 0
  nums.forEach(function (item) {
    num += item * 1
  })
  return num
}

8.es6箭头函数

箭头函数表达式的语法比函数表达式更简洁,并且没有自己的this,arguments,super或new.target。箭头函数表达式更适用于那些本来需要匿名函数的地方,并且它不能用作构造函数。

() => {}
// function Da() {}
// let da = function() {}
let da = () => {
 console.log('hello')
}
da()

let da = name => {}
const materials = [
  'Hydrogen',
  'Helium',
  'Lithium',
  'Beryllium'
];

console.log(materials.map(material => material.length));
// expected output: Array [8, 6, 7, 9]
拓展

判断函数有几个参数

  1. 在 ES5 中可以在函数体内使用 arguments 来判断。
  2. 在 ES6 中可以借助 Function.length 来判断。(统计第一个默认参数前面的变量数)
console.log(sum(...[4]))
console.log(sum.apply(null, [4]))

9.JavaScript中的三个点(…)

JavaScript当中,函数的参数前面有三个点,代表什么呢?我们看下代码示例:

function myFunc(a, b, ...args) {
 console.log(a); // 22
 console.log(b); // 98
 console.log(args); // [43, 3, 26]
};
myFunc(22, 98, 43, 3, 26);
function myFunc(x, y, ...params) { // used rest operator here
  console.log(x);
  console.log(y);
  console.log(params);
}

var inputs = ["a", "b", "c", "d", "e", "f"];
myFunc(...inputs); // used spread operator here
// "a"
// "b"
// ["c", "d", "e", "f"]
var obj1 = { foo: 'bar', x: 42 };
var obj2 = { foo: 'baz', y: 13 };

var clonedObj = { ...obj1 };
// Object { foo: "bar", x: 42 }

var mergedObj = { ...obj1, ...obj2 };
// Object { foo: "baz", x: 42, y: 13 }

10.Object Property

JS中对象的属性定义,代码示例如下:

let x = 'da1';
let y = 'da2';
let obj = {
 x,
 y
}
console.log(obj);

// 结果
{x:'da1',y:'da2'}
let x=1; let y=2; let z=3
let obj = {
 'x': x,
 y,
 [z+y]: 4,
 * hello() { // 异步
  console.log('dada')
 }
}
// function* functionName() {}
obj.hello()

11.Set数据结构

Set存储的成员不允许的重复的(它类似于数组)

Set 本身是一个构造函数,用来生成 Set 数据结构。

const s = new Set();

[2, 3, 5].forEach(x => s.add(x));

Set 函数可以接受一个数组(或类似数组的对象)作为参数,用来初始化

const set = new Set([1, 2, 3, 4, 4]);
实现数组去重
var arr = [1,1,2,2,3,3]; // step1:数组转集合
var s = new Set(arr); // 已经去掉重复值,当前不是数组,而集合
s.size; // 3
// step2:集合转数组
console.log([...s]); // 1,2,3;

// Array.form 方法可以将 Set 结构转为数组
const items = new Set([1, 2, 3]);
const arr = Array.from(items);

function dada(array) {
  return Array.from(new Set(array));
}

dada([1, 1, 2])
Set的遍历
  • keys():返回键名的遍历器
  • values():返回键值的遍历器
  • entries():返回键值对的遍历器
  • forEach():使用回调函数遍历每个成员
操作方法
  • add(value)添加某个值,返回Set结构本身。
  • delete(value)删除某个值,返回一个布尔值,表示删除是否成功。
  • has(value)返回一个布尔值,表示该值是否为Set的成员。
  • clear()清除所有成员,没有返回值。
let set = new Set([1, 2, 3, 4, 4]);

// 添加数据 
let addSet = set.add(5);
console.log(addSet); // Set(5) {1, 2, 3, 4, 5}

// 删除数据 
let delSet = set.delete(4);
console.log(delSet); // true

// 查看是否存在数据 4
let hasSet = set.has(4);
console.log(hasSet); // false

// 清除所有数据
set.clear();
console.log(set); // Set(0) {}
实现并集(Union)、交集(Intersect)和差集(Difference)
let a = new Set([1, 2, 3]);
let b = new Set([4, 3, 2, 1]);

// 并集
let union = new Set([...a, ...b]);
// Set {1, 2, 3, 4}

// 交集
let intersect = new Set([...a].filter(x => b.has(x)));
// set {1, 2, 3}

// 差集
let difference = new Set([...b].filter(x => !a.has(x)));
// Set {4}

12.Map数据结构

JS当中的哈希表,使用方法如下:

let map = new Map()
map.set(1, 2)
map.set(3, 4)
map.set(1, 3)
console.log(map)

创建
var da = new Map();
var jeskson = {};
遍历
da.forEach(function(value,key,map){}
长度
da.size
删除
//da.delete() 删除key,全部清楚da.clear()
新增
da.set(key,value)
da.has(查索引值)

da.forEach((value,key) =>{
})

for( let [key, value] of map){}

// let map = new Map( [[1,2], [3,4]] )

map的key任意都可以
let o = function() {
 console.log('o')
}
map.set(o, 3)
console.log(map.get(o)); // 3
// map.js
var Dictionary = function() {
 var items = {};
 // 检查键
 this.has = function(key) {
  return key in items;
 }
 // 添加键值对
 this.set = function(key, value){
  items[key] = value;
 }
 // 通过键移除元素
 this.delete = function(key) {
  if(this.has(key)){
   delete items[key]
   return true
  }
  return false
 }
 // 键获取值
 this.get = function(key){
  return this.has(key) ? items[key] : undefined;
 }
 // 列表返回字典值
 this.values = function() {
  var values = [];
  for(var k in items) {
   if(this.has(k)) {
    values.push(items[k])
   }
  }
  return values;
 }
 // 获取全部键名
 this.keys = function() {
  return Object.keys(items);
 }
 // 获取私有变量items
 this.getItems = function() {
  return items;
 }
}

Map数据结构,它类似于对象,也是键值对的集合,但是“键”的范围不限于字符串,各种类型的值(包括对象)都可以当作键。

13.Object.assign(对象的拷贝)

Object.assign() 方法用于将所有可枚举属性的值从一个或多个源对象复制到目标对象。它将返回目标对象。

const target = { a: 1, b: 2 };
const source = { b: 4, c: 5 };

const returnedTarget = Object.assign(target, source);

console.log(target);
// expected output: Object { a: 1, b: 4, c: 5 }

console.log(returnedTarget);
// expected output: Object { a: 1, b: 4, c: 5 }

> Object { a: 1, b: 4, c: 5 }
> Object { a: 1, b: 4, c: 5 }

语法

Object.assign(target, ...sources)
参数
target

目标对象

sources

源对象

返回值

目标对象。

const obj = { a: 1 };
const copy = Object.assign({}, obj);
console.log(copy); // { a: 1 }
  • Object.assign()拷贝的是(可枚举)属性值
  • Object.assign方法的第一个参数是目标对象,后面的参数都是源对象
  • 如果目标对象与源对象有同名属性,或多个源对象有同名属性,则后面的属性会覆盖前面的属性
  • 由于undefined和null无法转成对象,所以如果它们作为参数,就会报错
  • 如果undefined和null不在首参数,就不会报错
  • 如果源对象某个属性的值是对象,那么目标对象拷贝得到的是这个对象的引用(这个对象的任何变化,都会反映到目标对象上面。)
Object.assign(undefined) // 报错
Object.assign(null) // 报错

let obj = {a: 1};
Object.assign(obj, undefined) === obj // true
Object.assign(obj, null) === obj // true

const obj1 = {a: {b: 1}};
const obj2 = Object.assign({}, obj1);

obj1.a.b = 2;
obj2.a.b // 2

const target = { a: { b: 'c', d: 'e' } }
const source = { a: { b: 'hello' } }
Object.assign(target, source)
// { a: { b: 'hello' } }

const source = {
  get foo() { return 1 }
};
const target = {};

Object.assign(target, source)
// { foo: 1 }
Object.assign复制的是属性值value,如果属性值是一个引用类型,那么复制的其实是引用地址,就会存在引用共享的问题(Object.assign(target,source1,...,sourceN)浅拷贝的过程)

要点:

function ObjectAssign(target, ...sources) {
 // 对第一个参数的判断,不能为undefined和null
 if(target === undefined || target === null) {
  throw my TypeError('error');
 }
 // 将第一个参数转为对象(不是对象转换为对象)
 const targetObj = Object(target);
 // 将源对象自身的所有可枚举属性复制到目标对象
 for(let i = 0; i<sources.length; i++){
  let source = sources[i];
  // 对于undefined和null在源中不会报错,会直接跳过
  if(source !== undefined && source !== null) {
   // 将源象转换成对象
   // 需要将源自身的可枚举数据进行复制
   // Reflect.ownKeys(obj)
   const keysArray = Reflect.ownKeys(Object(source));
   for (let nextIndex = 0; nextIndex < keysArray.length; nextIndex++) {
    const nextKey = keysArray[nextIndex];
    // 去除不可枚举属性
    const desc = Object.getOwnPropertyDescriptor(source,nextKey);
    if(desc!==undefined&&desc.enumerable){
     targetObj[nextKey] = source[nextKey];
    }
   }
  }
 }
 return targetObj;
}
if(typeof Object.myAssign !== 'function'){
 Object.defineProperty(Object, 'myAssign', {
  value: ObjectAssign,
  writable: true,
  enumerable: false,
  configurable: true
 });
}

浅拷贝 Object.assign 的实现原理

拷贝第一层的基本类似值和第一层的引用类型地址:

let da1 = {
 name: 'da1',
 age: 1
}

let da2 = {
 name: 'da2',
 study: {
  title: 'web'
 }
}

let da3 = Object.assign(da1,da2);
console.log(da3);
// {
// name: 'da2',
// age: 1,
// study: { title: 'web' }
// }
console.log( da1 === da3); // true

da2.name = 'da22';
da2.study.title = 'web2';
console.log(da2);
// {
// name: 'da22',
// study: { title: 'web2' }
// }

console.log(da1);
// {
// age: 1,
// name: 'da2',
// study: { title: 'web2' }
// }
如果源对象的属性值是一个指向对象的引用,它也只拷贝这个引用地址哦!
let da1 = {
 name: 'da1',
 age: 1
}
let da2 = {
 a: Symbol('dadaqianduan'),
 b: null,
 c: undefined
}
let da3 = Object.assign(da1, da2);
console.log(da3);
// {
// name: 'da1',
// age: 1,
// a: Symbol('dadaqianduan'),
// b: null,
// c: undefined
// }
console.log(da1 === da3); // true

let map = new Map([iterable])
// Map是用来实现字典的功能-Object键值对

动态属性键

// ES5 code
var
  key1 = 'one',
  obj = {
    two: 2,
    three: 3
  };

obj[key1] = 1;

// obj.one = 1, obj.two = 2, obj.three = 3

// ES6 code
const
  key1 = 'one',
  obj = {
    [key1]: 1,
    two: 2,
    three: 3
  };

// obj.one = 1, obj.two = 2, obj.three = 3

// ES6 code
const
  i = 1,
  obj = {
    ['i' + i]: i
  };

console.log(obj.i1); // 1

补充:前端面试考点,HTML和CSS,性能优化,原型,作用域,异步,各种手写代码,DOM事件和Ajax,HTTP协议。

  • css(布局,定位,移动端响应式)
  • es(原型,原型链,作用域,闭包,异步,单线程)
  • webapi(DOM BOM,Ajax跨域,事件存储)
  • 开发环境(版本管理,调试抓包,打包构建)
  • 运行环境(页面渲染,性能优化,web安全)
  • 网络通讯
  1. 布局(盒模型,BFC,float,flex)
  2. 定位,图文样式,移动端响应式(rem,media query,vw/vh),动画、渐变
  3. 变量类型和计算(值类型和引用类型,类型判断,逻辑运算)
  4. 原型和原型链(class,继承,原型,原型链,instanceof)
  5. 作用域和闭包(作用域,自由变量,闭包,this)
  6. 异步(单线程,callback,应用场景,Promise,event-loop,async/await,微任务/宏任务)
  7. 模块化(ES6 Module)
  8. DOM(树形结构,节点操作,属性,树结构操作,性能)
  9. BOM(navigator,screen,location,history)
  10. 事件(绑定,冒泡,代理)
  11. ajax(XMLHttpRequest,状态码,跨域)
  12. 存储(cookie,localStorage,sessionStorage)
  13. 开发环境(git,调试,webpack和babel,linux命令)
  14. 运行环境(页面加载:加载,渲染。性能优化:加载资源优化,渲染优化。安全:xss,CSRF)
  15. HTTP协议:状态码,Method,Restful API,headers,缓存策略

14.模板文字

模板文字是es2015/es6的新功能,与es5及以下版本相比,可以通过新颖的方式使用字符串,先只需要反引号代替单引号或双引号即可:

const module_string = `dadaqianduan`

它们之所以独特是因为它们提供了很多用引号构建的普通字符串不具备的功能:

  1. 提供了定义多行字符串的语法;
  2. 提供了一种简单的方法来插值字符串中的变量和表达式
  3. 允许您使用模板标签创建DSL(领域特定的语言)
使用多行字符串

在es6之前的版本:

// 要创建跨越两行的字符串,必须\在行尾使用字符

const dada = 
 'dada \
  dadaqianduan'
  
// 呈现效果:在两行上创建一个字符串,但是仅在一行上呈现

要在多行上呈现,则需要使用\n在每行的末尾添加

const string = 
 'dada 魔王哪吒\n \
  dadaqianduan'

使用反引号打开模板文字后,只需要按enter键就行:

const dada = `dadaqianduan 
魔王哪吒`

在这里请记住空间是有意义的:

const da = `First
            Second`

使用trim()方法,可以消除第一个字符之前的任何空格

插补:模板文字提供了一种将变量和表达式插入字符串的简便的方法

const da = `dadaqianduan ${mydada}`

${}里面可以添加任何东西

const da1 = `dada ${1+2+3}`
const da2 = `dada ${dafun() ? 'x' : 'y'}`

15.什么是解构赋值

let da = ['hello', 'world']
let [firstName, surName] = da
cosole.log(firstName, surName);

解构赋值在于赋值,拷贝出来赋值给变量,而赋值的元素本身不会发生改变

默认值
let [da1, da2] = [];

console.log(da1); // undefined
console.log(da2); // undefined

给变量赋值(默认值),防止出现undefined的情况:

let [da1= 'da1', da2 = 'da2']=['dadaqianduan]

console.log(da1); // dadaqianduan
console..log(da2); // da2
解构分配

ES5中的索引提取这些值:

var myArray = ['a', 'b', 'c'];
var
  one   = myArray[0],
  two   = myArray[1],
  three = myArray[2];

// one = 'a', two = 'b', three = 'c'

ES6解构允许使用更简单方法:

const [one, , three] = myArray;

// one = 'a', three = 'c'

使用rest运算符(...)提取剩余元素:

const [one, ...two] = myArray;

// one = 'a', two = ['b, 'c']
const myObject = {
  one:   'a',
  two:   'b',
  three: 'c'
};

// ES6 destructuring example
const {one: first, two: second, three: third} = myObject;

// first = 'a', second = 'b', third = 'c'
可变值交换
var a = 1, b = 2;

// ES5 swap
var temp = a;
a = b;
b = temp;

// a = 2, b = 1

// ES6 swap back
[a, b] = [b, a];

// a = 1, b = 2

[b, c, d, e, a] = [a, b, c, d, e];

在ES6中,我们可以为任何参数分配默认值

function dada(param = {}) {
函数返回多个值(函数只能返回一个值,但可以是一个复杂的对象或多维数组)
function f() {
  return [1, 2, 3];
}

const [a, b, c] = f();

// a = 1, b = 2, c = 3
ES6 JavaScript深度解构

默认情况下,找不到的属性为undefined

var {da} = {bar: 'dada'}
console.log(da)
// undefined

如果访问不存在的父级的深层嵌套属性,则将获得异常。

var {da:{bar}} = {dada: 'dadaqianduan'}
// Exception
var key = 'dadaqianduan'
var { [key]: foo } = { dadaqianduan: 'bar' }
console.log(foo)
// 'bar'
var {da=3} = { da: 2 }
console.log(da)
// 2
var {da=3} = { da: undefined }
console.log(da)
// 3
var {da=3} = { bar: 2 }
console.log(da)
// 3

var [a] = []
console.log(a)
//  undefined
var [b=10] = [undefined]
console.log(b)
//  10
var [c=10] = []
console.log(c)
//  10

function da () {
  return {
    x: 1,
    y: 2
  }
}
var {x, y} = da()
console.log(x)
// 1
console.log(y)
// 2

16.异步操作

Callback

Promise

function loadScript(src) {
 return new Promise((resolve, reject) => {
  let script = document.createElement('script')
  script.src = src
  script.onload = () => resolve(src)
  script.onerror = (err) => reject(err)
  document.head.append(script)
 })
}
function loadScript(src) {
 let script = document.createElement('script');
 script.src = src;
 document.head.append(script)
}
var promise = new Promise(function(resolve, reject){
 resolve('传递给then的值')
})
promise.then(function(value){
 console.log(value)
},function(error){
 console.error(error)
})
Promise对象是用于表示一个异步操作的最终完成(或失败),以及其结果值。

示例:

const promise = new Promise((resolve, reject) => {
 setTimeout(() => {
  resolve('da');
 }, 200);
});

promise.then((value) => {
 console.log(value);
});

console.log(promise);

语法:

new Promise(function (resolve,reject){...});

描述:Promise对象是一个代理对象,被代理的值在Promise对象创建时可能是未知的,它允许你为异步操作的成功和失败分别绑定相应的处理方法,这让异步方法可以像同步方法那样返回值,但并不是立即返回最终执行结果,而是一个能代表未来出现的结果的promise对象。

一个Promise有以下几种状态:

  1. pending,初始状态,既不是成功,也不是失败状态。
  2. fulfilled,意味着操作成功完成。
  3. rejected,意味着操作失败。

pending状态的Promise对象可能会变为fulfilled状态并传递一个值给相应的状态处理方法。

Promise.prototype.thenPromise.prototype.catch方法返回promise对象,所以它们可以被链式调用。

方法:

Promise.all(iterable)

  1. 返回一个新的promise对象
  2. 在iterable参数对象里所有的promise对象都成功时,才会触发成功
  3. 当任何一个iterable里面的promise对象失败,才会触发promise对象的失败
  4. 成功状态会把一个包含iterable里所有promise返回值的数组作为成功回调的返回值,顺序和iterable的顺序一样
  5. 如果这个新的promise对象触发了失败,会把iterable里的第一个触发失败的promise对象的错误信息作为它的失败信息
  6. 场景,多用于处理多个promise对象的状态集合

Promise.any(iterable)

  1. 接收一个Promise对象的集合,当其中的一个promise成功,就返回那个成功的promise的值

Promise.reject(reason)

  1. 返回一个状态为失败的Promise对象,然后将失败信息传递给对应的处理方法

Promise.resolve(value)

  1. 返回一个状态由给定value决定的Promise对象
Promise原型

属性:Promise.prototype.constructor返回被创建的实例函数,默认为Promise函数。

方法:

  • Promise.prototype.catch(onRejected)
  • Promise.prototype.then(onFulfilled,onRejected)
  • Promise.prototype.finally(onFinally)
function myAsyncFunction(url) {
 return new Promise((resolve, reject) => {
  const xhr = new XMLHttpRequest();
  xhr.open('GET',url);
  xhr.onload = () => resolve(xhr.responseText);
  xhr.onerror = () => reject(xhr.statusText);
  xhr.send();
 });
}

17.ES6代理

  1. 默认情况下,代理不执行任何操作

示例:

var target = {}
var handler = {}
var proxy = new Proxy(target, handler)
proxy.a = 'b'
console.log(target.a)
// 'b'
console.log(proxy.c === undefined)
// true

为了更好地了解代理的有用性,让我们做一些小练习。

示例:

想象一下,您已经17岁了,即将满18岁。并且您希望您的程序在打开时自动向您祝贺。为此,您可以使用代理。

var person = {
  name: "dada",
  age: 17
};

person = new Proxy(person, {
  set(target, property, value) {
    if (value === 18) {
      console.log("Congratulations! You are of legal age");
      Reflect.set(target, property, value);
      return true;
    }
  }
});

person.age = 18;

if (value < 13 && value > 99) {
  throw new Error('The age should be between 13 and 99')
} else {
  Reflect.set(target, property, value)
}

语法:

let p = new Proxy(target, handler)
  1. target 用Proxy包装的目标对象
  2. handler 一个对象,其属性是当执行一个操作时定义代理的行为的函数

如果不想再调用key的时候,返回undefined:

console.log(o.dada || '')

使用Proxy

let o = {
 name: 'dada',
 age: 1
}

let handler = {
 get(obj, key) {
  return Reflect.has(obj, key)?obj[key]:''
 }
}

let p = new Proxy(o, handler)

console.log(p.from)

希望从服务器获取的数据只读,不允许修改:

for (let [key] of Object.entries(response.data)) { 
 Object.defineProperty(response.data, key, {
  writable: false
 })
}

使用Proxy:

let data = new Proxy(response.data, {
 set(obj, key, value) {
   return false
 }
})

检验逻辑代码:

// Validator.js

export default(obj, key, vlaue) => {
 if(Reflect.has(key) && value > 20) {
  obj[key] = value
 }
}

import Validator from './Validator'

let data = new Proxy(response.data, {
 set: Validator
})

使用Proxy,对读写进行监控:

let validator = {
 set(target, key, value) {
  if(key === 'age') {
   if(typeof value !== 'number' || Number.isNaN(value)) {
    throw new TypeError('Age must be a number')
   }
   if(value<=0){
    throw new TypeError('Age must be a positive number')
   }
  }
  return true
 }
}

const person = { age: 12 }
const proxy = new Proxy(person,validator)
proxy.age = 'dada' // TypeError number
proxy.age = NaN
proxy.age = 0 // positive number
proxy.age = 3

示例:每个对象都有一个自己的id

class Component {
 constructor() {
  this.proxy = new Proxy({
   id: Math.random().toString(36).slice(-8)
  })
 }
 get id() {
  return this.proxy.id
 }
}

18.Generator

function * dada() {
 for(let i=0; i<2; i++ {
  yield console.log(i);
 }
}

const da = dada()
da.next()
da.next()

Generator函数与普通函数的区别在于定义的时候有一个*,执行下面函数:

function* dada() {
console.log('dadaqianduan');
}
dada(); // 没有执行函数
 
如需要输出,改为:
var da = dada();
da.next();

要生成一个自增的id:

var count_id = 0;
function dada_id() {
count_id ++;
return count_id;
}
方法
Generator.prototype.next()
返回一个由 yield表达式生成的值。

Generator.prototype.return()
返回给定的值并结束生成器。

Generator.prototype.throw()
向生成器抛出一个错误。

书写风格:

function *da() {
}

function* da(){
}
方法

Generator对象方法:next,return,throw

通过Next方法来获取每一次遍历的结果,这个方法返回一个对象,这个对象包含两个value和done。

value:当前程序的运行结果
done:遍历是否结束

next是可以接收参数的,这个参数可以让你在generator外部给内部传递数据,这个参数就是作为yield的返回值。

return()方法可以让generator遍历终止

function * da() {
 yield 1
 yield 2
 yield 3
}
var d = da()
console.log(d.next()) // {value:1,done:false}
console.log(d.return()) // {value:undefined,done:true}
console.log(d.next()) // {value:undefined,done:true}

return可以传入参数,作为返回的value的值

function * da() {
 yield 1
 yield 2
 yield 3
}
var d = da()
console.log(d.nex()) // {value:1,done:false}
console.log(d.return(100)) // {value:100,done:true}
console.log(d.next()) // {value:undefined,done:true}

throw()方法在generator外部控制内部执行的“终断”

generator函数声明:

function* genFunc(){...}
const genObj = genFunc();

generator表达式:

const genFunc = function* () {...}
const genObj = genFunc();

对象中定义:

const obj = {
 * generatorMethod(){
  ...
 }
}
const genObj = obj.generatorMethod();

类定义(类声明或类表达式):

class MyClass{
 * generatorMethod(){
  ...
 }
}
const myInst = new MyClass();
const genObj = myInst.generatorMethod();

最简单的iterator遍历规范:

authors[Symbol.iterator] = function(){
 // this
 return {
  next(){
   return{
    done:false,
    value:1
   }
  }
 }
}

19.module

在es6前,js文件之间的导入,导出是借助require.js,sea.js,如现在使用import,export,来实现原生javascript的导入,导出。

export:

导出变量或者常量

export const da = 'dadaqianduan'
export let da1 = 'da1'
export var da2 = 'da1'

const name = 'dada'
let name1 = 'dada1'
export {
 name,
 name1
}

导出函数
export function da(value){
 console.log(value)
}

const da = (value) => {
 console.log(value);
}

export {
 da
}

导出Object
export({
 name: 'da1',
 message: 'dadaqianduan'
})

let da = {
 name: 'name1'
}
export {
 da
}

导出Class
class Da {
 constructor(){
  this.id = 1
 }
}
export {
 Da
}

export class Da {
 constructor() {
  this.id = 1
 }
}

修改导出名称
const name = 'da1'
export {
 name as cname
}
export default name

import

// 直接导入
const name = 'dada'
let name1 = 'dada1'
var name2 = 'dada2'
export {
 name as cname
}
export default name2

import name2, {name1, name} from A
export const sqrt = Math.sqrt;
export function square(x) {
 return x * x;
}
export function dada(x,y) {
 return sqrt(square(x) + square(y));
}

import {square,da} from 'da';
console.log(square(11)); // 121
console.log();
export default function() {...}
import myFunc from 'myFunc';
export default class{...}
import MyClass from 'MyClass';
const inst = new MyClass();

20.import, export

require
--lib.js--
function add(x,y){
 return x + y
}
module.exports = {
 add: add,
};

--main.js--
var add = require('lib').addd;
console.log(add(1,2));
import
--lib.js--
export function add(x,y) {
 return x + y
}
--main.js--
import {add} from 'lib';
console.log(add(1,2));
--lib.js--
export const sqrt = Math.sqrt;
export function square(x) {
 return x * x;
}
export function da(x,y) {
 return sqrt(square(x)+square(y));
}
--main.js--
import {square, da} from 'lib'


--myFunc.js--
export default function() {...};
--main.js--
import myFunc from 'myFunc';
myFunc();

21.Array.prototype.includes,Promise

该方法判断一个数组是否包含一个指定的值,返回布尔值

let da1 = [1,2,3];
console.log(da1.includes(2));
arr.find(function(item){
return item === 1;
})

arr.filter(function(item){
return item === 2;
})

Math.pow(2,3)->2**3
async function firstAsync(){
 let promise = new Promise ((resolve,reject) => {
  setTimeout(function(){
   resolve('dadaqianduan')
  },1000)
 })
 console.log(await promise)
 console.log(await Promise.resolve(1))
 console.log(2)
 return Promise.resolve(3)
}
firstAsync().then(val => {
 console.log(val)
})
await后面是Promise对象

Object.values()返回一个数组,其元素是再对象上找到的可枚举属性值。

let da = {
 'da': 1,
 'da2': 2
}
console.log(Object.value(da)) // [1,2]

Object.values是在对象上找到可枚举的属性的值,所以只要这个对象是可枚举的就可以

Object.entries()方法返回一个给定对象自身可枚举属性的键值对数组

22.JS异步进阶

题目一:

Promise.resolve().then(()=>{
 console.log(1)
}).catch(()=>{
 console.log(2)
}).then(()=>{
 console.log(3)
})

题目二:

Promise.resolve().then(()=>{
 console.log(1)
 throw new Error('da')
}).catch(()=>{
 console.log(2)
}).then(()=>{
 console.log(3)
})

题目三:

Promise.resolve().then(()=>{
 console.log(1)
 throw new Error('da')
}).catch(()=>{
 console.log(2)
}).catch(()=>{
 console.log(3)
})

题目四:

async function fn() {
 return 1
}
(async function() {
 const a = fn() // ??
 const b = await fn() // ??
})()

题目五:

console.log(100)
setTimeout( () => {
 console.log(200)
})
Promise.resolve().then( ()=> {
 console.log(300)
})
console.log(400)

题目六:

async function async1() {
 console.log('async1 start')
 await async2()
 console.log('async1 end')
}

async function async2 () {
 console.log('async2')
}

console.log('script start')

setTimeout(function(){
 console.log('setTimeout')
},0)

async1()

new Promise(function (resolve){
 console.log('promise1')
 resolve()
}).then(function(){
 console.log('promise2')
})

console.log('script end')

加载图片:

// 加载
function  loadImg(src) {
 const p = new Promise(
  (resolve,reject) => {
   const img = document.createElement('img')
   img.onload = () =>{
    resolve(img)
   }
   img.onerror = () =>{
    const err = new Error('图片加载失败')
    reject(err)
   }
   img.src = src
  }
 )
 return p
}
const url = 'https'
const p = loadImg(url)

p.then(img =>{
 console.log(img.width)
 return img
}).then(img =>{
 console.log(img.height)
}).catch(ex => {
 console.error(ex)
})
async function async1() {
 console.log('async1 start') // 2
 await async2() // undefined
 console.log('async1 end') // 5
}
async function async2() {
 console.log('async2') // 3
}
console.log('script start') // 1
async1()
console.log('script end') // 4
for...of常用于异步的遍历
function add(num) {
 return new Promise(resolve => {
  setTimeout(()=>{
   resolve(num*num)
  },1000)
 })
}
const nums = [1,2,3]
nums.forEach(async(i)=>{
 const res = await add(i)
})

23.宏任务和微任务

宏任务:setTimeout,setInterval,ajax等
微任务:Promise async/await

微任务执行时比宏任务要早:

宏任务:DOM渲染后触发,如setTimeout

微任务:DOM渲染前触发,如Promise

24.For await of 异步操作集合

function da(time) {
 return new Promise(function(resolve,reject){
  setTimeout(function(){
   resolve(time)
  },time)
 })
}
async function test() {
 let arr = [da(2000),da(1000),da(3000)]
 for await (let item of arr) {
  console.log(Date.now(), item)
 }
}
const input = {
 a: 1,
 b: 2
}
const output = {
 ...input,
 c: 3
}
console.log(output)

const input = {
 a: 1,
 b: 2,
 c: 3
}
let {a, ...rest } = input

25Array.prototype.flat()

该方法会按照一个可指定的深度递归遍历数组,并将所有元素与遍历到的子数组中的元素合为一个新数组。

Array.prototype.flat()建议将数组递归展平至指定范围depth并返回新数组。

depth(指定要提取嵌套数组的结构深度)

语法:Array.prototype.flat(depth)

depth —默认值1,Infinity用于展平所有嵌套数组。

const numbers = [1, 2, [3, 4, [5, 6]]];

// Considers default depth of 1
numbers.flat(); 

> [1, 2, 3, 4, [5, 6]]

// With depth of 2
numbers.flat(2); 

> [1, 2, 3, 4, 5, 6]

// Executes two flat operations
numbers.flat().flat(); 

> [1, 2, 3, 4, 5, 6]

// Flattens recursively until the array contains no nested arrays

numbers.flat(Infinity)
> [1, 2, 3, 4, 5, 6]

语法:Array.prototype.flatMap(callback)

callback:function产生新Array的元素。

const numbers = [1, 2, 3];

numbers.map(x => [x * 2]);
> [[2], [4], [6]]

numbers.flatMap(x => [x * 2]);
> [2, 4, 6]

Object.fromEntries

Object.fromEntries执行与的相反操作Object.entries。它将一组键值对转换为一个对象。

const records = [['name','da'], ['age', 32]];

const obj = Object.fromEntries(records);

> { name: 'da', age: 32}

Object.entries(obj);

> [['name','Mathew'], ['age', 32]];

Symbol.prototype.description

只读属性,返回Symbol对象的可选描述:

Symbol('desc').toString();
> "Symbol(desc)"

Symbol('desc').description;  
> "desc"

Symbol('').description;      
> ""

Symbol().description;
> undefined

点关注,不迷路

好了各位,以上就是这篇文章的全部内容,能看到这里的人都是人才。我后面会不断更新技术相关的文章,如果觉得文章对你有用,欢迎给个“赞”,也欢迎分享,感谢大家 !!

查看原文

赞 31 收藏 20 评论 0

xindoo 发布了文章 · 9月13日

程序猿职场求生指南


职场法则: 只要你努力工作,办事靠谱,思虑周全,从不给领导添麻烦,从不向领导提要求。勤勤恳恳,兢兢业业…… 坚持下去,公司里的杂活,破事儿,棘手的事就都成了你的,而且你的老板会更有钱。

如何在职场中干最少的活拿最多的钱,一定是困扰大部分社畜的终极难题,今天我将尝试从 工作、社交、生活、团队管理 四个维度来解答这个问题,相信大家看完之后在职场中肯定会如鱼得水。

工作篇

时间规划

作为久经沙场的社畜,深知时间规划的重要性,毕竟这是其他人(尤其是主管)感知你工作态度、工作效率、沟通能力、时间安排……等很多能力的最佳途径。

如何规划时间(黑话:排期), 每次评估工作时间前,心里一定要先默念下面这幅不怎么工整的对联。

排期五天,再加四天,三天开发,提前两天上线,年底一定加薪
自评一天,拖延两次,三天无果,老板四次催你,末了五味杂陈

横批:话不能说死

精髓就是能 3 天干完的活排期 5 天,然后提前 1 天上线,这样不仅你多了一天划水摸鱼的时间,而且需求方还会因为你提前上线对你感激涕零,老板也认为你工作高效 靠谱,反之就呵呵~~

向上管理

你忙不忙无所谓,一定要让老板觉得你忙。
你有没有成果无所谓,一定要让老板觉得你有成果。
你有没有能力无所谓,一定要让老板觉得你有能力。

这就涉及到向上管理了,何为向上管理,说白了就是向老板汇报工作。同样完成一项任务,通过简单修改和润色之后,可以给老板完全不同的印象,随便来举个例子。

经过我们充分的用户调研,发现大部分用户的有想隐藏自己某些数据的需求,我们初步排期发现需要两个月时间,最后我想到一个很巧妙的方案,只需要在数据库中加一个特殊的字段,在特定的情况下加一个特殊的标识,然后结合前后端的改动,仅仅用了两个礼拜就完美的解决了问题,得到了广大用户的好评。

说人话就是"我们在数据库上实现了逻辑删除,并在页面上加了个删除按钮" 。 总之做的事千万不要让老板觉得简单,我们一定要本着没有困难也要创造困难的态度去汇报。

另外,切记全知全能的老板他说的啥都是对的,千万不要犟,你非要犟老板会觉得你和他对着干,小心他给你穿小鞋。 什么! 万一老板给定的 KPI 完不成怎么办? 没关系,阿基米德曾经说过:给我一个 KPI,我就能假装完成了 KPI。

如何避免被裁

在今年的大环境下,如何避免被裁也是一个不得不考虑的问题!其实几百年前老朱(朱元璋)就给出了答案 “高筑墙,广积粮,缓称王”,核心观点就是提升自己在公司的不替代性,最好要那种你走了这个团队就跨了的效果。如何操作,其实具体点就是多揽活,但是不要揽那些谁都能干的脏活累活,要揽一些复杂点核心点的活,你偷偷摸摸做完,挥一挥衣袖不留下任何文档,让所有的信息都只存在于你的脑子里,从而制造出稀缺性,影视剧中男主都是靠毁掉唯一信息载体而仅靠自己的记忆要挟大 Boss 的。另外写代码的时候怎么难懂怎么写,用一些小众语言实现系统的核心模块。然后自己造各种轮子,对外可以用自主可控来糊弄老板,造轮子既提升了你的技术水平、又提升了你的不可替代性,何乐而不为。

还有另外一点,努力提升自己的性价比。大家都觉得公司喜欢那种干两个人的活,拿 1.5 个人工资的员工,大错特错,公司只喜欢干更多活拿更少钱的人,相比于干两个人活拿一个人工资的员工,前者瞬间就不香了。没错绝大多数公司不会要最优秀的人,只会要最具性价比的人,性价比是怎么来的,当然是比出来的。你看为啥有时候你会看到某些公司总拿老员工开刀,因为他们太贵了,相比于年轻人,他们的性价比太低了。

干最多的活,拿最少的钱,做最具性价比的员工。 你是不是觉得太苦逼了,错错错 还是那句话我不要你觉得,我只要老板觉得,你只需要让老板觉得你的最具性价比的员工即可,假装努力总比真的努力容易得多。当然如果你的“努力”已经到极限了,你还有另外一种选择就是降价,努力表现出一种与世无争的样子,不在意绩效 不在意涨薪 更不在意年终奖,毕竟每个团队总是需要一个人来垫底。

社交篇

日常拉近和同事的关系

如何拉近你和别人的关系,当然是日常夸奖别人,满足别人的虚荣心,记住 舔狗谁都喜欢。
夸奖不同程序猿有不同的技巧!

  • 通用:你这代码写得真好看。
  • 夸 C 程序猿:你这代码不看注释就能懂,写得真好。
  • 夸 Ruby 程序猿:哇!太神奇了,你怎么做到的!
  • 夸 Perl 程序猿:这个正则表达式碉堡了。
  • 夸 Python 程序猿:Pythonic!
  • 夸 Java 程序猿:你写的代码一点都不像 Java!
  • 夸 php 程序猿:看完你的代码,我一下子认同了 php 才是世界上最好的语言!

图片来自公众号“神秘的程序猿们”

朋友圈

职场朋友圈法则第一条: 同事的朋友圈一定要点赞,尤其是老板们的。

非工作时间你很难和自己的同事 老板有交集,而朋友圈就是其中为数不多的交集之一。面对不太熟悉的同事微信找个话题聊天显得有点尬,而轻轻点个赞不失为一种优雅得体的社交方式,它在不不经意间拉近里你和对方的关系。当然可能有人觉得时不时打开朋友圈给别人点赞太麻烦了,没关系 我早就给你们解决了这个问题,我的 送赞干部朋友圈自动点赞脚本了解下。 这里额外赠送大家一个小 tips 不要在工作时间给老板点赞,更不要在工作时间抢老板发的红包。

职场朋友圈法则第二条: 公司相关的正面信息一定到转发到自己朋友圈。

一定要有你的朋友圈就是公司的宣传栏的觉悟,公司官微发啥、老板朋友朋友圈转啥,你的朋友圈就要发啥,有没有给公司起到宣传的效果无所谓,但一定要让同事尤其是老板们觉得你在为公司尽职尽责的付出。当然,为了防止你被你其他的微信好友拉黑,发圈之前建议设置仅公司同事可见。

职场朋友圈法则第三条: 朋友圈也是向老板和同事们展示自己的最佳舞台。

这里我教大家如何在"不经意间"告诉你的老板和同事们你努力、有激情、愿意为公司付出。。。
在这里插入图片描述

生活篇

如何成为优秀员工

高端的社畜往往没有自己的生活,忙碌了一个礼拜,张师傅开始准备过他的周末,他打开了电脑连上了公司内网,又开始了一天的工作…… 他们往往拿着底层员工的薪资 操着 CEO 的心,当然这种员工往往也是 CEO 最喜欢的员工。对于他们而已,只要不病危 怎么都能联系上,只要有网 哪儿都是工位。
在这里插入图片描述
对于想要在职场中生存的人而言,你一定不能给别人留下不靠谱的影响,所以 7x24 小时不失联是最基本要求,如果你在任意时刻能 20 分钟内投入工作更好,最晚不能超过 1 小时。这些显然对你的设备提出了严苛的要求,首先你的手机不能关机、不能断网,另外建议你随时背着电脑,如果你要出远门去那些没有网络没有手机信号的地方,你还得需要卫星通讯设备。如果你要是去出海、漂流、游泳……还得要求你的设备具备防水的能力。

穷屌丝买不起这么高端的设备怎么办?我也为你准备了低成本的方案:手机 24 小时开机,并且从不静音;不出远门,即便出去吃饭也随时带着电脑;当然还有给老板微信设置强提醒,避免错过任何一条老板的指示。
在这里插入图片描述
总之只要你在公司一天,你就是公司的人,要随时准备好为公司工作。

如何轻松地成为优秀员工

我知道你不想努力 不想成为奋斗 x,不用说了 我懂! 永远记住本文最核心的一句话 我不要你觉得,我只要老板觉得,你真的靠不靠谱 负不负责无所谓,只要老板觉得你靠谱负责就行。 回到主题,仔细想想 如果老板真在非工作时间找你,必然是出了问题,是想让你解决问题而已,老板优先关注的是问题有没有解决。我知道你不想辛辛苦苦干活,你只需要把工作转交给别人即可,如果坐拥其工作成果,说起来有点虚,我来模拟个场景实操一下。

周五晚上 11 点半老板给你打来了电话
老板:喂,小张,这个方案客户有些不满意,你抓紧改一下,客户明天就要用了,你最好明天早上 8 点前发给我。。
你:好的老板,明天早上 8 点前一定发你,老板晚安
然后你转手打电话给自己带的实习生,把工作交给他。
你:小王啊,你来公司也有 1 个礼拜了,今晚正好给你争取到一个小项目,但是比较着急,明天早上 7 点就要了,你今天晚上加班改一下。这是一个很好的锻炼机会,对提升你的业务能力非常有帮助,对你以后转正也很有帮助,希望你抓住这次机会 好好努力,我相信你的能力,你一定可以的。
第二天早上 7 点起床,查收下实习生小王的改动,稍加修改转手发给给老板,告诉老板你已经通宵加班解决了。
为了让实习生以后更能心甘情愿给你干活,你要给实习生表现出认真负责的态度,记得回复实习生。
小张啊,你这份方案整体改的不错,非常好,但如果你能稍微注意下 xxx,xxx(一些无关紧要的问题),这就可以做为你实习转正的重要材料之一了,不过没关系后面还有很多机会,继续努力。哦 昨天辛苦了,抓紧休息吧,周一我请你喝饮料。

在这里插入图片描述
这就是非常有名的实习生工作法,有些搞算法的也有个类似的实习生梯度下降法,你学废了吗?

团队管理篇

如果你在工作中得到了老板的赏识,逐渐老板会让你管理团队,如果有人不幸成为你的下属,该如何压 zha...激励他们将会成为你最大的问题。

壮大团队

小团队很难立足,指不定哪天就被其他团队吞并了。所以要想在大公司稳定立足,就必须得壮大自己的团队,这也是继续向上升职必备的条件。 这么做?首先巧立一个名目,招到十来个人,然后如法炮制搞个大事情,再招个几十号人。
没项目没关系,可以编个项目。编的项目后期没成果怎么办?那就更好了,告诉老板这个项目难度太大,需要加人,一定要让老板觉得你有"给你 10 个女人你一个月就能生出一个孩子"。

如何激励员工

数据调查显示,优秀的管理者都会用以下手段激(ya)励(zha)自己的下属。
在这里插入图片描述
更高级的管理者激励员工能做到那种润物细无声的境界,参考以下话术。

  • 不难,要你干嘛?
  • 要么是态度问题,要么是能力问题,要么两者都有问题
  • 今天最好的表现是明天最低的要求
  • 当你感觉难受的时候是你成长的时候

你学废了吗?

人员管理

要记住,一个团队人员的流失 尤其是老员工的流失是团队最大的损失,一来他的离开可能让整个团队停摆,二来你可能要花很多的时间精力 花更多的钱来找到或者培养一个替代者,对你对公司可能也是极其不划算的。而且,如果你手底下流失了过多的员工,公司高层也会开始质疑你的管理能力。所以如何避免人员流失是一个优秀的管理者必备的品质。

员工为什么离职,你们的马爸爸总结了两点原因:钱给少了,受委屈了。 但是据我了解,优秀的员工基本上不会受委屈,而且钱给少了这点也不准确。 我总结的两点员工离职的理由:别的公司给的多、翅膀硬了。稍微解释下,每个人都有追求更好生活的本能,别的公司给出更诱人的薪资,而且老板一开心还得大半夜发奖金,这谁架得住啊。当员工翅膀硬了之后必然就会走上追求更优质生活的路,毕竟饱暖思淫欲,我们的老祖先早已看穿了一切。

当然你无法控制别的公司给多少,但你可以让你的员工翅膀硬不起来 走不了。How?高收益必然意味着高要求,你让自己的员工永远无法达到别的公司要求即可,这个时候你就要充分压榨员工的学习时间,必要时甚至压榨员工的社交和娱乐时间,你可以每个月给与员工一定的租房补贴,让他们住公司附近,最好公司食堂、健身房、便利店一应俱全,让员工们有种家的感觉,彻底把他们圈养起来。这样除了让员工死心塌地贡献自己的青春外,还可以让他们充分内卷,失去跳槽的能力。

结语

本文采用反讽的方式吐槽某些公司的某些现象,如有雷同 纯属你应该跳槽了,当然如果你觉得自己当前能力跳槽有问题的话,可以关注下我的专栏面试题精选,或者直接关注我。

码字不易,如果觉得我的文章写的还可以,请不要吝啬你的点赞,你的支持是我最大的动力。
查看原文

赞 3 收藏 0 评论 0

xindoo 发布了文章 · 9月13日

面试题精选:数据伪造

这道题应该算是我原创的的一道题,来源于我遇到的一个具体需求。大致需求是已知一批数和每个数出现的次数,然后写个接口,每次调用都能返回已知数据中的某个数,且返回的概率和原始数据中每个数出现的概率一致,题目描述起来有些绕口,我们来举个实际的例子。
在这里插入图片描述
以上面的输入为例,要求实现的接口必须以11.96%的概率返回5、18.10%的概率返回91……16.55%的概率返回98,当然我的要求不仅仅是这几个数,而是可能有10^5个数。 先别急着往下看,给你几分钟先思考下。

各种语言其实都内置了random函数,可以随机返回int或者long型的随机数,这里我们先不考虑溢出的问题。为了方便讲解,假设我们已有n个数存在在num[n]中,其出现的频次存放在fre[n]中。 借助已有的random(),我们很简单就可以生成0-n之间的一个随机数i,但是如果直接返回num[i]的话,每个数返回的概率是一致的,明显不满足我们的需求。

其实解决方案也很简单,我们按照每个数出现的频次大小,将其映射成不同的区间大小,出现的概率越大,区间越大。想象下,这些数据按不同的区间大小把一个飞镖盘分成不同的部分,我们生成数的时候就是拿个飞镖随机扎,扎到哪个算哪个。
在这里插入图片描述
当然我们可以直接用一位直线区间描述上面的二维飞镖盘模型。只需要随机生成0-100%之间的数即可,假设某次随机生成的数是0.65(65%),我们算一下 正好对应在数字58对应的区间上,所以这次直接返回58就是了,我们可以开始写代码了。
在这里插入图片描述

    int[] num; // 数字
    int[] fre; // 出现的频次
    double[] pro;  // 出现的概率
    int n;  // 数据量
    void init() {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += fre[i];
        }
        for (int i = 0; i < n; i++) {
            pro[i] = fre[i]/sum; // 计算出每个数出现的概率 
        }
    }
    
    int getRandom() {
        double rp = random.getNextDouble();
        double sum = 0;
        for (int i = 0; i < n; i++) {
            if (sum >= r && sum + pro[i] > rp) {  //找到命中的区间
                return num[i]; 
            }
            sum += pro[i];
        }
        return num[n-1];
    }

似乎一切都很完美,但每次getRandom()的时间复杂度是O(n),大量的使用性能也抗不太住。有没有更好的实现方式?既然写到这里了,必然是有的。

上面代码循环中有个sum += pro[i]; 每次计算都要累加,我们是不是可以提前在init()中累加好?然后你会发现因为每次累加的数都只正数,所以pro是个递增序列,对于有序序列的查找 二分必然是首选。这时候我们可以用二分重写上面代码。

    int[] num; // 数字
    int[] fre; // 出现的频次
    double[] pro;  // 出现的概率
    int n;  // 数据量
    void init() {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += fre[i];
        }
        for (int i = 0; i < n; i++) {
            pro[i] = fre[i]/sum; // 计算出每个数出现的概率
            if (i != 0) {
                pro[i] += pro[i-1];
            }
        }
    }

    int getRandom() {
        double rp = random.getNextDouble();
        int l = 0;
        int r = n-1;
        while (l != r) {   // 二分查找确定区间位置  
            int mid = (l + r) >> 1;
            if (pro[mid] < rp) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return num[n-1];
    }

到这里问题就彻底解决了,但是最后给大家留下一个思考题。

上述代码中pro[]的计算有必要吗? 能否直接用fre[]替代其功能?
查看原文

赞 0 收藏 0 评论 0

xindoo 发布了文章 · 9月6日

我背着CSDN偷偷记录了大半年我博客数据

作为一个数据控+一个有追求的技术博主,总是希望自己能知道自己博客历史每日粉丝数量、阅读量、积分、评论……的数据,然而官方博客管理后台给展示的数据太少了,只有每日访问量、评论数、粉丝数、收藏数这几个数据,而且目前最多只能看最近一个月的数据。
在这里插入图片描述
如果想看更久的数据、想看自己积分的变化、想看总排名 周排名的变化……
在这里插入图片描述
没有这些数据,我作为技术博主年底的年终总结怎么办?没有这些数据,我怎么知道自己长期是否进步了,进步速度又是什么样的? 这当然难不住一个优秀的程序猿,本着没有困难创造困难也要上的态度,我用Jsoup写了个简单的爬虫,记录了我博客2019年年底到现在每天的博客数据(除个别几天因为博客改版导致数据记录异常)。没错,这个功能已经上线大半年了,来先给大家展示下我的数据。

jsoup是一款Java的HTML解析器,可以从html中解析数想要的数据,是用java写爬虫必备的工具。
每日增量、总量数据随意切换

在这里插入图片描述

阅读量、粉丝量、评论数、点赞数、总排名、周排名…… 任意选取

在这里插入图片描述

随意选取时间区间

在这里插入图片描述

自从有了这个工具后,我博客一切数据尽收眼底,每天看着这数据一点点的变化,还是蛮有成就感、蛮开心的呢 !!

如何做?

秀完该告诉大家如何做的,首先你得有台能执行定时任务的主机,云主机或者你卧室的主机都可以,然后得有个数据库,至于整体功能其实就是一个简单的增删改查。哦 不对,只有增查没有删改,数据展示的话我用了蚂蚁金服开源的可视化库antv g2,我用的3.8 bug很多不推荐,推荐使用highchart

我认为其中比较复杂的部分应该是html数据解析的部分,这部分后面我会直接把我代码告诉你。其次就是数据库的存储和查询,我用spring-boot搭了个web服务,用了spring-boot-starter-quartz写了每天晚上11:55的定时任务,用mybatis-spring-boot-starter来读写数据库。

html的解析代码,需要看懂csdn博客页的html布局,然后逐渐调试获取数据,当然csdn官方一改版,代码就执行不了了,所幸这种致命性改版频率不会特别高,这大半年我就遇到过2-3次,代码如下,可以直接拿来用,把url换成自己博客url就可以了。

public class CommonUtils {
    private static Logger log = LoggerFactory.getLogger(CommonUtils.class);

    private static Map<String, String> headers;

    static {
        headers = new HashMap<>();
        headers.put("referer", "https://www.google.com/");
        headers.put("User-Agent", "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/85.0" +
                ".4183.83 Safari/537.36");
    }

    public static BlogInfoDao getBlogInfo() {
        int retry = 3;
        while (--retry > 0) {
            try {
                BlogInfoDao blogInfoDao = new BlogInfoDao();
                blogInfoDao.setDate(new Date());
                Document doc = Jsoup.connect("https://blog.csdn.net/xindoo").headers(headers).get();
                Element blogElement = doc.getElementsByClass("data-info d-flex item-tiling").get(0);
                // 文章数量
                int articleCnt = Integer.parseInt(blogElement.getElementsByTag("dl").get(0).attr("title"));
                blogInfoDao.setArticleCnt(articleCnt);
                // 周排名
                int wranking = Integer.parseInt(blogElement.getElementsByTag("dl").get(1).attr("title"));
                blogInfoDao.setWranking(wranking);
                // 总排名
                int ranking = Integer.parseInt(blogElement.getElementsByTag("dl").get(2).attr("title"));
                blogInfoDao.setRanking(ranking);
                // 总阅读量
                int viewCnt = Integer.parseInt(blogElement.getElementsByTag("dl").get(3).attr("title"));
                blogInfoDao.setViewCnt(viewCnt);

                blogElement = doc.getElementsByClass("data-info d-flex item-tiling").get(1);
                // 总积分
                int scoreCnt = Integer.parseInt(blogElement.getElementsByTag("dl").get(0).attr("title"));
                blogInfoDao.setScore(scoreCnt);
                // 粉丝数量
                int fansCnt = Integer.parseInt(blogElement.getElementsByTag("dl").get(1).attr("title"));
                blogInfoDao.setFansCnt(fansCnt);
                // 点赞量
                int likeCnt = Integer.parseInt(blogElement.getElementsByTag("dl").get(2).attr("title"));
                blogInfoDao.setLikeCnt(likeCnt);
                // 评论量
                int commentCnt = Integer.parseInt(blogElement.getElementsByTag("dl").get(3).attr("title"));
                blogInfoDao.setCommentCnt(commentCnt);
                // 收藏量
                int collectCnt = Integer.parseInt(blogElement.getElementsByTag("dl").get(4).attr("title"));
                blogInfoDao.setCollectCnt(collectCnt);

                return blogInfoDao;
            } catch (Exception e) {
                log.error("get bloginfo error, {}", e);
            }
        }
        return null;
    }
}

blogInfoDao是我封装的用来和数据库交互的类,没啥内容这里就不再贴了。

结语

我数据目前是半公开状态,可以让大家看,https://xindoo.xyz/ 然后用github登陆后就可以看到数据了,有兴趣可以体验下。之前有人建议开源,不过这个源码是放在一个我个人项目中的,里面很多东西不适合公开,所以暂时不考虑了。

查看原文

赞 0 收藏 0 评论 0

认证与成就

  • 获得 52 次点赞
  • 获得 3 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 3 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

注册于 2019-07-31
个人主页被 1.7k 人浏览