2019-06-15

散列表

散列算法的作用是尽可能快地在数据结构中找到一个值。散列函数的作用是给定一个键值，然后返回值在表中的地址

基本实现

class HashTable {
    constructor() {
        this.table = [];
    }
    put(key, value) {
        const position = this.loseloseHashCode(key);
        this.table[position] = value;
    }
    get(key) {
        return this.table[loseloseHashCode(key)];
    }
    remove(key) {
        this.table[loseloseHashCode(key)] = undefined;
    }
    loseloseHashCode(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i);
        }
        // 为了得到比较小的数值，我们会使用hash值和一个任意数做除法的余数
        return hash % 37;
    }
}

碰撞处理

分离链接法

分离链接法包括为散列表的每一个位置创建一个链表并将元素存储在里面。它是解决冲突的最简单的方法，但是它在HashTable实例之外还需要额外的存储空间

class HashTable {
    constructor() {
        this.table = [];
    }
    put(key, value) {
        const LList = this.table[this.loseloseHashCode(key)];
        const valuePair = { key, value };
        if (LList === undefined) {
            LList = new LinkedList();
        }
        table[position].append(valuePair);
    }
    get(key) {
        const LList = this.table[this.loseloseHashCode(key)];
        if (LList !== undefined) {
            let curNode = LList.head;
            while(curNode.next) {
                if (curNode.next.key === key) {
                    return curNode.next.item.value;
                }
                curNode = curNode.next;
            }
        }
        return undefined;
    }
    remove(key) {
        const LList = this.table[this.loseloseHashCode(key)];
        if (LList !== undefined) {
            let curNode = LList.head;
            while(curNode.next) {
                if (curNode.next.key === key) {
                    LList.remove(key);
                    return true;
                }
            }
        }
        return false;
    }
    loseloseHashCode(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i);
        }
        // 为了得到比较小的数值，我们会使用hash值和一个任意数做除法的余数
        return hash % 37;
    }
}

线性探测法

另一种解决冲突的方法是线性探查。当想向表中某个位置加入一个新元素的时候，如果索引为index的位置已经被占据了，就尝试index+1的位置。如果index+1的位置也被占据了，就尝试index+2的位置，以此类推

创建更好的散列函数

function djb2HashCode (key) {
    var hash = 5381; // 初始化一个hash变量并赋值为一个质数（大多数实现都使用5381）
    for (var i = 0; i < key.length; i++) { 
    // 将hash与33相乘（用来当作一个魔力数），并和当前迭代到的字符的ASCII码值相加
        hash = hash * 33 + key.charCodeAt(i); //{3}
    }
   // 最后将使用相加的和与另一个随机质数（比我们认为的散列表的大小要大， 比如1000）相除的余数
    return hash % 1013; 
};

2019-06-15

字典

字典是一种以键 - 值对形式存储数据的数据结构

语法

new Map([iterable])
map.set(key, value) // 根据键（key）存储值（value），返回该Map对象
map.get(key) // 根据键返回值，如果 map 中该键不存在，返回 undefined
map.has(key) // 如果键存在，返回 true，否则返回 false
map.delete(key) // 移除该键的值
map.clear() // 清空 map
map.size // 返回当前元素个数

// 迭代 Map
map.keys() – 返回键的迭代器，
map.values() – 返回值的迭代器，
map.entries() – 返回 [key, value] 迭代器入口，for..of 循环会默认使用它

Object 和 Map 对比

一个Object的键只能是字符串或者Symbols，但一个 Map 的键可以是任意值，包括函数、对象、基本类型
Map 中的键值是有序的，而添加到对象中的键则不是。因此，当对它进行遍历时，Map 对象是按插入的顺序返回键值
- 可以通过 size 属性直接获取一个 Map 的键值对个数，而 Object 的键值对个数只能手动计算
Map 可直接进行迭代，而 Object 的迭代需要先获取它的键数组，然后再进行迭代
Map 在涉及频繁增删键值对的场景下会有些性能优势

2019-06-15

集合

集合是由一组无序且不重复的元素组成的

语法

new Set([iterable]); // 如果传递一个[可迭代对象]，它的所有元素将不重复地被添加到新的 Set 中。
set.add(value)  // 添加值，返回 set 自身
set.delete(value)  // 删除值，如果该 value 在调用方法的时候存在则返回 true ，否则返回 false
set.has(value)  // 如果 set 中存在该值则返回 true ，否则返回 false
set.clear() // 清空 set
set.size  // 元素个数

set.keys()  // 返回 set 中值的迭代对象
set.values() // 和 set.keys 一样
set.entries() // 返回形如 [value, value] 的迭代对象，为了兼容 Map 而存在。

Set迭代

可以使用 for..of 或者 forEach 来循环查看 set

for (let value of set) alert(value);

set.forEach((value, valueAgain, set) => {
  alert(value);
});

应用

数组去重

// Use to remove duplicate elements from the array 
const numbers = [2,3,4,4,2,3,3,4,4,5,5,6,6,7,5,32,3,4,5]
console.log([...new Set(numbers)]) 
// [2, 3, 4, 5, 6, 7, 32]

2019-06-15

链表

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成

为什么使用链表

数组的大小是固定的，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素。链表的一个好处在于，添加或移除元素的时候不需要移动其他元素，因此插入一个元素的效率很高。
数组的另一个细节是可以直接访问任何位置的任何元素，而要想访问链表中间的一个元素，需要从起点（表头）开始迭代列表直到找到所需的元素。

实现

class Node {
    constructor(item) {
        this.item = item;
        this.next = null;
    }
 }
 
 class LinkedList {
     constructor() {
         this.head = new Node("head");
     }
     find(item) {
         let curNode = this.head;
         while(curNode.item !== item) {
             curNode = curNode.next;
         }
         return curNode
     }
     insert(newItem, item) {
         const newNode = new Node(newItem);
         const curNode  = this.find(item);
         newNode.next = curNode.next;
         curNode.next = newNode;
     }
     append(item) {
         const curNode = this.head;
         while(curNode.next) {
             curNode = curNode.next;
         }
         curNode.next = item;
     }
     findPrevious(item) {
         let prevNode = this.head;
         while(prevNode.next && prevNode.next.item !== item) {
             prevNode = prevNode.next;
         }
         return prevNode;
     }
     remove(item) {
         const prevNode = this.findPrevious(item);
         prevNode.next = prevNode.next.next;
     }
     display() {
         let curNode = this.head.next;
         while(curNode !== null) {
             console.log(curNode.item);
             curNode = curNode.next;
         }
     }
 }

2019-06-15

队列

队列是遵循FIFO（First In First Out，先进先出）原则的一组有序的线性结构

实现

class Queue {
    constructor() {
        this.queue = [];
    }
    enQueue(item) {
        this.queue.push(item);
    }
    deQueue() {
        this.queue.shift();
    }
}

优先队列

优先队列中元素的添加和移除是基于优先级的。一个现实的例子就是机场登机的顺序。头等舱和商务舱乘客的优先级要高于经济舱乘客

class PriorityQueue {
    constructor() {
        this.queue = [];
    }
    enQueue(item, priority) {
        let queueItem = { item, priority };
        let added = false;
        for (let i = 0; i < this.queue.length; i++) {
            if (priority < this.queue[i].priority) {
                this.queue.splice(i, 0, queueItem);
                added = true;
                break;
            }
        }
        if (!added) {
            this.queue.push(queueItem);
        }
    }
    deQueue() {
        this.queue.shift();
    }
}

循环队列

循环队列的一个例子就是击鼓传花游戏（HotPotato）。在这个游戏中，孩子们围成一个圆圈，把花尽快地传递给旁边的人。某一时刻传花停止，这个时候花在谁手里，谁就退出圆圈结束游戏。重复这个过程，直到只剩一个孩子（胜者）

function hotPotato(nameList, num) {
    let queue = new queue();
    for (let i = 0; i < nameList.length; i++) {
        queue.enQueue(nameList[i]);
    }
    while(queue.size() > 1) {
        for (let i = 0; i < num; i++) {
            queue.enQueue(queue.deQueue());
        }
        queue.deQueue(); // 被淘汰
    }
    return queue.deQueue();
}

javascript任务队列

当我们在浏览器中打开新标签时，就会创建一个任务队列。这是因为每个标签都是单线程处理所有的任务，它被称为事件循环。浏览器要负责多个任务，如渲染HTML，执行JavaScript代码，处理用户交互（用户输入、鼠标点击等），执行和处理异步请求。

2019-06-15

栈

栈是一种后入先出（LIFO，last-in-ﬁrst-out）的数据结构
栈使用两种基本操作：推入（压栈，push）和弹出（弹栈，pop）
在javascript中，栈可以看成是数组的子集

1、实现

class Stack{
    constructor() {
        this.stack= [];
    }
    push(item) {
        this.stack.push(item);
    }
    pop() {
        this.stack.pop();
    }
}

2、应用

数制间的相互转换

可以利用栈将一个数字从一种数制转换成另一种数制。假设想将数字 n 转换为以 b 为基数的数字，实现转换的算法如下:

最高位为 n % b，将此位压入栈
使用 n/b 代替 n
重复步骤 1 和 2，直到 n 等于 0，且没有余数

持续将栈内元素弹出，直到栈为空，依次将这些元素排列，就得到转换后数字的字符串形式

function mulBase(num, base) {    
    const s = new Stack();
    do {
        s.push(num % base);    
        num = Math.floor(num /= base);
    } while (num > 0);
    let converted = "";
    while (s.length() > 0) {
        converted += s.pop();
    }    
    return converted;
}

括号匹配

/**
 * @param {string} s
 * @return {boolean}
 */
function isValid(s) {
    const stack = [];
    const mapping = {
        ')': '(',
        '}': '{',
        ']': '['
    };
    for (v of s) {
        if (v in mapping) {
            let top_el = stack.pop();
            if (top_el !== mapping[v]) {
                return false;
            }
        } else {
            stack.push(v)
        }
    }
    return stack.length === 0;
};

2019-06-15

数组

1、数组的定义

一个存储元素的线性集合（collection），元素可以通过索引来任意存取，索引通常是数字，用来计算元素之间存储位置的偏移量。

JavaScript 中的数组是一种特殊的对象，用来表示偏移量的索引是该对象的属性，索引可能是整数。然而，这些数字索引在内部被转换为字符串类型，这是因为 JavaScript 对象中的属性名必须是字符串。数组在 JavaScript 中只是一种特殊的对象，所以效率上不如其他语言中的数组高。

2、使用数组

创建数组

1
2
3

// 通过 [] 操作符声明一个数组变量
var numbers = [];
var numbers = [1,2,3,4,5];

// 调用 Array 的构造函数创建数组
var numbers = new Array(); 
var numbers = new Array(1,2,3,4,5);  //可以为构造函数传入一组元素作为数组的初始值
var numbers = new Array(10);  //可以只传入一个参数，用来指定数组的长度

由字符串生成数组

调用字符串对象的 split() 方法也可以生成数组。该方法通过一些常见的分隔符，比如分隔单词的空格，将一个字符串分成几部分，并将每部分作为一个元素保存于一个新建的数组中

1 2	var sentence = "the quick brown fox jumped over the lazy dog"; var words = sentence.split(" ");

Array.from()

从类数组对象或者可迭代对象中创建一个新的数组实例

1	Array.from('foo'); // Array ["f", "o", "o"]

判断是否数组类型

可以调用 Array.isArray() 来判断一个对象是否是数组

3、数组访问函数

JavaScript 提供了一组用来访问数组元素的函数，这些函数返回目标数组的某种表现

查找元素

indexOf() 和 lastIndexOf()函数是最常用的存取函数之一，用来查找传进来的参数在目标数组中是否存在。如果目标数组包含该参数，就返回该元素在数组中的索引；如果不包含，就返回 -1。如果数组中包含多个相同的元素，indexOf() 函数总是返回第一个与参数相同的元素的索引

1 2	var names = ["David", "Cynthia", "Raymond", "Clayton", "Jennifer"]; names.indexOf("Cynthia") // 1

find() 方法返回数组中满足提供的测试函数的第一个元素的值。否则返回undefined

1	arr.find(callback[, thisArg])

数组的字符串表示

有两个方法可以将数组转化为字符串：join() 和 toString()

1	arr.join([separator])

由已有数组创建新数组

concat 方法可以合并多个数组创建一个新数组，slice() 方法截取一个数组的子集创建一个新数组

1 2	array.concat(value1[, value2[, ...[, valueN]]]) array.slice(begin, end);

4、可变函数

JavaScript 拥有一组可变函数，使用它们，可以不必引用数组中的某个元素，就能改变数组内容

为数组添加元素

有两个方法可以为数组添加元素：push() 和 unshift()。

从数组中删除元素

使用 pop() 方法可以删除数组末尾的元素，shift() 方法可以删除数组的第一个元素

从数组中间位置添加和删除元素

使用 splice() 方法

1	array.splice(start[, deleteCount[, item1[, item2[, ...]]]])

为数组排序

reverse() 方法将数组中元素的位置颠倒,并返回该数组。该方法会改变原数组
sort()方法用原地算法对数组的元素进行排序，并返回数组

1	arr.sort([compareFunction])

5、迭代器方法

迭代器方法方法对数组中的每个元素应用一个函数，可以返回一个值、一组值或者一个新数组

不生成新数组的迭代器方法

forEach()方法接受一个函数作为参数，对数组中的每个元素使用该函数

1	arr.forEach(callback[, thisArg]);

every() 方法测试数组的所有元素是否都通过了指定函数的测试

1	arr.every(callback[, thisArg])

some() 方法测试是否至少有一个元素通过由提供的函数实现的测试

1	arr.some(callback(element[, index[, array]])[, thisArg])

reduce() 方法对数组中的每个元素执行一个由您提供的reducer函数(升序执行)，将其结果汇总为单个返回值。reduceRight则反方向执行

1	arr.reduce(callback[, initialValue])

生成新数组的迭代器方法

map() 方法创建一个新数组，其结果是该数组中的每个元素都调用一个提供的函数后返回的结果

1
2
3

var new_array = arr.map(function callback(currentValue[, index[, array]]) {
 // Return element for new_array }[, 
thisArg])

filter() 方法创建一个新数组, 其包含通过所提供函数实现的测试的所有元素

1	var newArray = arr.filter(callback(element[, index[, array]])[, thisArg])

2018-06-25

Docker学习笔记

Docker镜像

获取镜像

1 2	docker pull NAME[:TAG] e.g. docker pull ubuntu:latest

查看镜像信息

docker images

# 详细
docker inspect ID

添加镜像标签
1
docker tag TGNAME NAME
搜寻镜像
1
docker search NAME
删除镜像
1
docker rmi NAME|ID

创建镜像

1
2
3

# 基于已有的容器创建 -m --author, -a --author, 
docker commit [OPTIONS] CONTAINER [REPOSITORY[:TAG]]
e.g. docker commit -m "Added a new file" -a "jim.fun" 0f99624 test

上传镜像
1
docker push NAME:[TAG]

Docker容器

启动容器

1
2
3

docker run NAME
e.g. docker run -t -i ubuntu /bin/bash
-t 分配一个伪终端并绑定到标准输入，-i 让容器的标准输入保持打开, -d Daemonized 守护态运行

终止容器
1
docker stop ID
重启容器
1
docker restart ID

进入容器

1
2
3

    docker exec [OPTIONS] ID

* 删除容器

docker rm [OPTIONS] CONTAINER

导出和导入容器

windows env get some problems

Docker仓库

Docker HUb

2018-06-19

Javascript Full Stack - concentrate

Javascript Basic

The modern Javascript Tutorial
You-Dont-Know-JS
ECMAScript 6 — New Features
mdn javascript
《professional javascript for web developers》

node.js Basic

Node.js API Docs
《深入浅出node.js》
《node.js in pratice》

Css & Html

React - A JavaScript library for building user interfaces

React Router
UI Framework
- Ant Design

Koa.js - next generation web framework for node.js

Desktop

electron

Mobile

React Native - Build native mobile apps using JavaScript and React

Project Tools

webpack - bundle
babel - Babel is a JavaScript compiler
Code Style
- EditorConconfig

有趣的开源项目

Command Line Tools

httpie - Modern command line HTTP clients
mycli - A Terminal Client for MySQL with AutoCompletion and Syntax Highlighting

Http

httpbin.org - HTTP Request & Response Service, written in Python + Flask.

File Managers

Cloud Commander(website) - Orthodox web file manager with console and editor.

video

sickbeard_mp4_automator - Automatically convert video files to a standardized mp4 format with proper metadata tagging to create a beautiful and uniform media library
videoconverter.js - Convert videos in your browser

developer

meteor - Meteor is an open source platform for web, mobile, and desktop.
mongo-express - Web-based MongoDB admin interface, written with Node.js and express
json-server - Get a full fake REST API with zero coding in less than 30 seconds (seriously)
hotel - A simple process manager for developers. Start apps from your browser and access them using local domains
brew - The missing package manager for macOS
swagger - Swagger module for node.js

oprating system

NodeOS - Lightweight operating system using Node.js as userspace

Restful API

Node-restful - Create awesome APIs using express

Crawer

Scrapy - An open source and collaborative framework for extracting the data you need from websites

AI

tensorflow - Computation using data flow graphs for scalable machine learning

Chrome extensions

image-downloader - A Google Chrome browser extension that displays all images on a web page and allows the user to choose which ones to download.

基本实现

碰撞处理

分离链接法

线性探测法

创建更好的散列函数

语法

Object 和 Map 对比

语法

Set迭代

应用

数组去重

为什么使用链表

实现

实现

优先队列

循环队列

javascript任务队列

1、实现

2、应用

数制间的相互转换

1、数组的定义

2、使用数组

创建数组

由字符串生成数组

Array.from()

判断是否数组类型

3、数组访问函数

查找元素

数组的字符串表示

由已有数组创建新数组

4、可变函数

为数组添加元素

从数组中删除元素

从数组中间位置添加和删除元素

为数组排序

5、迭代器方法

不生成新数组的迭代器方法

生成新数组的迭代器方法

Docker镜像

Docker容器

Docker仓库

Javascript Basic

node.js Basic

Css & Html

React - A JavaScript library for building user interfaces

Koa.js - next generation web framework for node.js

Desktop

Mobile

Project Tools

Version Control

Database

Dev Tools

Command Line Tools

Http

File Managers

video

developer

oprating system

Restful API

Crawer

AI

Chrome extensions