2018-02

博客分类: 江河计划-月总结
JavaScript (120) 总结 (15)

2018-02

JavaScript (120) 总结 (15)

算法

字典

class Dictionary{
    private items: any = {};
    private length: number = 0;
    set(key:string, value:any):boolean{
        if(!this.has(key)){
            this.items[key] = value;
            ++this.length;
            return true;
        }
        return false;
    }
    remove(key:string):boolean{
        if(this.has(key)){
            delete this.items[key];
            --this.length;
            return true;
        }
        return false;
    }
    has(key:string):boolean{
        return this.items.hasOwnProperty(key)
    }
    get(key:string):any{
        if(this.has(key)){
            return this.items[key]
        }
        return undefined;
    }
    clear(){
        this.items = {};
        this.length = 0;
    }
    size():number{
        return this.length;
    }
    keys():string[]{
        return Object.keys(this.items);
    }
    values():any[]{
        return Object.keys(this.items).map(item => {
            return this.items[item];
        });
    }
}
var dictionary = new Dictionary();
dictionary.set('aaa', 111);
console.log(dictionary.values());
dictionary.set('bbb', 222);
console.log(dictionary.values());
dictionary.set('ccc', 333);
console.log(dictionary.values());
console.log(dictionary.has('aaa'));
console.log(dictionary.get('aaa'));
console.log(dictionary.size());
console.log(dictionary.keys());
dictionary.remove('aaa');
console.log(dictionary.values());
dictionary.remove('ccc');
console.log(dictionary.values());

散列表

class HashTable{
    private items:{} = {};
    private length:number = 0;
    private loseloseHashCode(key:string):number{
        var hash = 0;
        for(var i=0; i<key.length; i++){
            hash += key.charCodeAt(i);
        }
        return hash % 37;
    }
    put(key:string, value:any){
        var pos = this.loseloseHashCode(key);
        this.items[pos] = value;
    }
    remove(key:string){
        var pos = this.loseloseHashCode(key);
        delete this.items[pos];
    }
    get(key:string){
        var pos = this.loseloseHashCode(key);
        return this.items[pos];
    }
}

由于 key 经过 hash 算法之后可能产生重复，这种现象称之为冲突，面对这个问题一般有两种解决方案，一种是分离链接，一种是线性探测。

分离链接

采用链表的方式存储，比如 ae、ea 通过 hash 算法，当计算得到 hash 值之后，在存储这个 hash key 对应的数据时采用链表的方式去存储。下面是大致伪代码的实现

put(key, value){
    var pos = this.loseloseHashCode(key);
    if(this.items[pos] === undefined){
        this.items[pos] = new LinkList();
    }
    this.items[pos].append(key + '-' + value)
}

get(key){
    var pos = this.loseloseHashCode(key);
    if(this.items[pos] !== undefined){
        return this.item[pos].find(key + '-' + value);
    }
    return false;
}

线性探测

当前的 hash key 已经被占用时，对当前的 hash key 进行自增，直到找到空的 key 时，将这个值存起来。下面是大致伪代码的实现

put(key, value){
    var pos = this.loseloseHashCode(key);
    if(this.items[pos] === undefined){
        this.items[pos] = key + '-' + value;
    }else{
        var index = ++ pos;
        while(this.items[index]){
            index++;
        }
        this.items[index] = key + '-' + value;
    }
}

get(key){
    var pos = this.loseloseHashCode(key);
    
    if(this.items[pos] !== undefined){
        while(this.items[pos].replace(/\-.*/g, '') === key){
            pos++;
        }
        return this.items[pos]
    }
    return false;
}

二叉树

interface Node {
    key: number,
    left: any,
    right: any
}

class Tree {
    private root:any = null;
    private getNode(key:number):Node{
        return {
            key,
            left: null,
            right: null
        }
    }
    private inserNode(oldNode:Node, newNode:Node){
        if(oldNode.key > newNode.key){
            if(oldNode.left === null){
                oldNode.left = newNode;
            }else{
                this.inserNode(oldNode.left, newNode);
            }
        }else{
            if(oldNode.right === null){
                oldNode.right = newNode;
            }else{
                this.inserNode(oldNode.right, newNode);
            }
        }
    }
    public insert(key:number){
        var node = this.getNode(key);
        if(!this.root){
            this.root = node;
        }else{
            this.inserNode(this.root, node);
        }
    }
    public search(key:number, searchNode?:Node){
        var node = searchNode || this.root;
        while(node !== null && node.key !== key){
            if(node.key > key){
                node = node.left;
            }else{
                node = node.right;
            }
        }
        if(node === null){
            return false;
        }
        return node;
    }
    public min(_node?:Node){
        var node = _node || this.root;
        if(this.root === null){
            return false;
        }
        while(node.left !== null){
            node = node.left;
        }
        return node.key;
    }
    public max(_node?:Node){
        var node = _node || this.root;
        if(this.root === null){
            return false;
        }
        while(node.right !== null){
            node = node.right;
        }
        return node.key;
    }
    public remove(key:number, removeNode?:Node){
        var node = removeNode || this.root;
        if(node.key > key){
            node.left = this.remove(key, node.left);
        }else if(node.key < key){
            node.right = this.remove(key, node.right);
        }else{
            if( node.left === null && node.right === null){
                node = null;
            }else if(node.left && node.right === null){
                node = node.left;
            }else if(node.right && node.left === null){
                node = node.right;
            }else{
                var minKey = this.min(node.right);
                node.key = minKey;
                node.right = this.remove(minKey, node.right);
            }
        }
        return node
    }
    public inOrderTraverse(_node?:Node){
        if(_node === null){
            return
        }
        var node = _node || this.root;
        this.inOrderTraverse(node.left);
        console.log(node.key)
        this.inOrderTraverse(node.right);
    }
    public preOrderTraverse(_node?:Node){
        if(_node === null){
            return
        }
        var node = _node || this.root;
        console.log(node.key)
        this.preOrderTraverse(node.left);
        this.preOrderTraverse(node.right);
    }
    public postOrderTraverse(_node?:Node){
        if(_node === null){
            return
        }
        var node = _node || this.root;
        this.postOrderTraverse(node.left);
        this.postOrderTraverse(node.right);
        console.log(node.key)
    }
}

var tree = new Tree();
tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);
tree.insert(6);
console.log(tree)
console.log(tree.search(6))
console.log(tree.min())
console.log(tree.max())
console.log(tree.inOrderTraverse())
console.log(tree.preOrderTraverse())
console.log(tree.postOrderTraverse())
console.log(tree.remove(15))

知识整理

错误处理

try-catch

在 js 中报错之后就会停止执行后续代码，使用 try-catch 一方面能捕获到错误，另一方面能使后面的代码继续执行。

try{
    // 可能会出错的代码
}catch(error){
    // error 错误对象
    // 错误处理信息
}finally{
    // 不管错误还是正确都会执行
}

错误类型

可以判断错误属于上述哪个错误的实例。也可以通过抛出错误来对代码进行监控。 (throw new 上述错误类型)

捕获全局错误

通过全局捕获错误，可以对错误进行上报，帮助面对前端的系统的稳定性，让自己的代码没有 error，是一个工程师对前端的最低要求。

window.onerror = function(message, url, line){
    // 通过此方法来捕获错误
}

单纯的记录错误是没用的，需要将导致错误的用户行为连贯起来，能复原用户的报错行为路径，将错误复现并解决。通过对请求的统一记录来标识请求行为，重写 console.log 对记录日志进行上传，将这些行为维护到堆栈中，出现报错时统一上传。

Ajax 和 Comet

XMLHttpRequest 对象

用于发送请求的对象，更早一些的版本会有 ActiveXObject()，现代浏览器都支持 XMLHttpRequest 对象，更新的浏览器支持的 fetch API。（监控错误日志，想要获取到错误的网络请求行为可以通过重写 fetch API 和 XMLHttpRequest 对象获取）

// 获取 XML 对象
var xhr = new XMLHttpRequest();
// 对请求的状态进行监听
xhr.onreadystatuschange = function(){
    // 0：未初始化，尚未调用 open 方法
    // 1：启动，已经调用 open 方法，并未调用 send 方法
    // 2：发送，已经调用 send 方法，但尚未接收到响应
    // 3：接收，已经接收到部分响应数据，数据接收中
    // 4：完成，已经接收到全部响应数据
    if(xhr.readystate == 4){
        if(xhr.status === 200){
            // 请求结果
            xhr.responseText;
        }else{
            // 请求出错
        }
    }
}
// 设置超时时间
xhr.timeout = 10000;
// 设置超时的回调函数
xhr.ontimeout = function(){}
// 准备发送请求的参数
xhr.open('method', 'url', 是否异步发送请求);
// 发送请求
xhr.send(data);
// 请求提前结束
xhr.abort();

send方法中的data，只有在post的方法中才会进行传递，如果content-type：application/json，数据需要用json的数据格式来表示。如果content-type:x-www-form-urlencoded，数据则需要用表单的格式，new FormData()通过表单的数据格式进行发送。

xhr 进度事件
  • loadstart：在接受到响应数据的第一个字节时触发
  • progress：在接收响应期间持续不断地触发
  • error：在请求发生错误时错发
  • abort：在因为调用 abort 方法而终止连接时触发
  • load：在接收到完整的响应数据时触发
  • loadend：在通信完成或者触发 error，abort 或 load 事件后触发
xhr.onprogress = function(event){
    if(event.lengthComputable){
        console.log(`已接收到 ${event.position}，一共请求大小 ${event.totalSize} bytes`)
    }
}

跨域 传送门

comet

指的是让信息近乎实时的推送到页面。实现方式大致有以下几种：

  • 短轮询：通过 setInterval 这样的方式不断的发出请求，来保持和服务器同步，延迟时间就是请求间隔时间，无用的请求会比较多
  • 长轮询：服务器接收到请求后，将请求 hold 住，等到有数据时返回，没有延迟时间，但是服务器会建立非常多连接，性能会是一种考验。
  • SSE，通过 EventSource 对象发起与服务器建的连接，服务器返回的 MIME 类型必须是 text/event-stream，基于事件流的处理。
  • websocket：是 HTTP 之上的连接方式，但是不是属于 HTTP 协议，通过 new WebSocket 得到实例。只能发送字符串，当然也可以发送 json。
websocket
var socket = new WebSocket('ws://xxx.xxx.xxx');
socket.onopen = function(){}
socket.onerror = function(){}
socket.onclose = function(){}
socket.onmessage = function(event){
    var data = event.data;
}

web workers

相当于子进程进行计算，处理复杂计算，加载另一个 js 来加载代码。比较简单，看一个实际的例子。

// main.js
var worker = new Worker('js/worker.js');
var workerCallback = {};
var timer = +new Date();
workerCallback['ready'] = () => {
    worker.postMessage({
        type: 'start'
    });
    setTimeout(() => {
        worker.terminate();
    }, 300)
}
workerCallback['end'] = (e) => {
    console.log(+new Date() - timer);
}
worker.onmessage = (e) => {
    workerCallback[e.data.type](e);
}
worker.onerror = (e) => {
    console.log(`ERROR:${e.filename}+(e.lineno):e.message`)
}
// 也可以通过事件监听
worker.addEventListener('message', () => {
    workerCallback[e.data.type](e);
})

-----------------
// worker.js
var worker = this;
worker.postMessage({
    type: 'ready'
})
var workerInfo = {};
workerInfo['start'] = function() {
    var a = 1;
    for (var i = 0; i < 1000000000; i++) {
        a += i;
    }
    worker.postMessage({
        type: 'end',
        data: {
            result: a
        }
    });
}
worker.onmessage = function(e) {
    workerInfo[e.data.type](e);
}

数据传递 早期数据传递只能传字符串，会带来 from-string 和 to-string 的损耗，并且内存会是两份，后来有了结构化克隆算法，省去了字符串转化的性能，但是内存依旧会有两份。

message 传输的过程中可以传输对象，web worker 中的运行环境相当于一个没有 UI 的内核环境，所以很多方法也可以使用，比如setTimeout 等。

也可以通过子进程加载其他的脚本文件，如：import.scripts(‘路径名’)