原文地址:https://ruby-china.org/topics/38223

散列表(也叫Hash表)是一种应用较为广泛的数据结构,几乎所有的高级编程语言都内置了散列表这种数据结构。然而散列表在不同的编程语言中称呼不一样,在JavaScript中被称为对象,在Ruby中被称为哈希,而在Python中被称为字典。即便称呼不同,语法不同,它们的原理基本相通。

原理解析

在现代的编程语言中,几乎都会有散列表的身影,故而难以忽视它为程序员所带来的种种便利性。散列跟数组是很相似的,较大的区别在于,数组直接通过特定的索引来访问特定位置的数据,而散列表则是先通过散列函数来获取对应的索引,然后再定位到对应的存储位置。这是比较底层的知识了,一般的散列表,在底层都是通过数组来进行存储,利用数组作为底层存储的数据结构最大的好处在于它的随机访问特性,不管数组有多长,访问该数组的时间复杂度都是O(1)。

当然要设计一个能用的散列表,在底层仅仅用普通的数组是不够的,毕竟我们需要存储的不仅仅是数值类型,还可能会存储字符串为键,字符串为值,或者以字符串为键,某个函数的指针为值 (JavaScript就很多这种情况)的键值对。在这类情况中,我们需要对底层的结点进行精心设计,才能够让散列表存储更多元化的数据。

无论以何种数据类型为键,我们始终都需要有把键转换成底层数组任意位置索引的能力,通过散列函数可以做到这一点。散列函数是个很考究的东西,设计得不好可能会导致频繁出现多个不同的键映射到同一个索引值的现象,这种现象称之为冲突,文章的后半部分会看到常用的一些解决冲突的方式。除此之外,每次为散列表所分配的空间是有限的,随着元素的插入,散列表会越来越满,这时,冲突的几率就越高。故而,我们需要定期对散列表进行扩张,并把已有的键值对重新映射到新的空间中去,让散列表中的键值对更加分散,降低冲突的几率。这个过程被称为Resize。这个过程能够在一定程度上降低散列表的冲突几率,提高查找效率。

接下来会从散列函数,冲突解决,散列查找以及散列表Resize这几个方面来详细谈谈散列表的基本概念。

为何不用链表来存储键值对?

散列表本质上就是用来存储键值对的,其实完全可以用一个链表来实现键值对存储的功能,这样就不会产生冲突了。举个简单的例子

typedef struct Node {
  char * key;
  char * value;
  struct Node * next;
} Node;

以上的结点能够存储以字符串为键,字符串为值的键值对。假设完全用链表来实现键值对存储机制,那么每次插入元素,我们都得遍历整个链表,对比每个结点中的键。如果键已经存在的话则替换掉原来的值,如果遍历到最后都不能找到相关的结点则创建新的结点并插入到散列的末端。查找的方式其实也类似,同样是遍历整个链表,查找到对应键值对则返回相关的值,当遍历到散列最后都不能找到相关值的话则提示找不到对应结点。删除操作跟插入操作类似,都需要遍历链表,寻找待删除的键值对。

这种实现方式虽然操作起来较为简便,也不会有冲突产生,不过最大的问题在于效率。无论是插入,查找还是删除都需要遍历整个链表,最坏情况下时间复杂度都是O(n)。假设我们有一个相当庞大的键值对集合,这样的时间成本是难以让人接受的。为此在存储键值对的时候都会采用数组来作为底层的数据结构,得益于它随机访问的特征,无论最终的键值对集合多有庞大,访问任意位置的时间复杂度始终为O(1)。即便这种方式会有产生冲突的可能,但只要散列函数设计得当,Resize的时机合适,散列表访问的时间复杂度都会保持在O(1)左右。

散列函数

散列函数在维基百科上的解释是

散列函数(英语:Hash function)又称散列算法、哈希函数,是一种从任何一种数据中创建小的数字“指纹”的方法。

在散列表中所谓的“指纹”其实就是我们所分配的数组空间的索引值,不同类型的键需要设计不同的散列函数,它将会得到一个数值不是太大的索引值。假设我们用C语言来设计一个以字符串为键,字符串为值的散列表,那么这个散列表的结点可以被设计成

typedef struct Hash {
  char * key; // 指向散列的键
  char * value; // 指向散列的值
  char isNull; // 标识这个散列是否为空
} Hash;

以这个结点为基础可以简单地创建一个长度为7的散列表

Hash hash[7]

接下来就要设计对应的散列函数了,这个函数的目的是把字符串转换成整型数值。字符串和整型最直接的关联无非就是字符串的长度了,那么我们可以设计一个最简单的字符串散列函数

#include <string.h>

unsigned long simpleHashString(char * str) {
  return strlen(str);
}

不过这个散列函数有两个比较大的问题

对同样长度的字符串,它的散列值都是相同的。放在数组的角度上来看就是,它们所对应的数组索引值是一样的,这种情况会引发冲突。
以字符串为键,当它的长度大于7的时候,它所对应的索引值会造成数组越界。
针对第一种情况,可以简单描述为,这个散列函数还不够“散”。可以进一步优化,把字符串中的每个字节所对应的编码值进行累加如何?

#include <string.h>

unsigned long sum(char * str) {
  unsigned long sum = 0;
  for (unsigned long i = 0; i < strlen(str); i++) {
    sum += str[i];
  }
  return sum;
}

unsigned long simpleHashString(char * str) {
  return strlen(str) + sum(str);
}

这样似乎就可以得到一个更“散”的地址了。接下来还需要考虑第二种情况,索引值太大所造成的越界的问题。要解决越界的问题,最粗暴的方式就是对数组进行扩展。不过依照我前面写的这个不太合格的散列函数,散列函数的值几乎是随着字符串的增长而线性增长。举个例子

int main() {
  printf("%lu", simpleHashString("Hello World"));
}

打印结果是1063,这是一个相当大的值了。如果要按这个数值来分配内存的话那么所需要的内存空间是sizeof(Hash) * 1063 => 25512个字节,大概是25KB,这显然不太符合情理。故而需要换个思路去解决问题。为了让散列函数的值坐落在某个范围内,采用模运算就可以很容易做到这一点

unsigned long simpleHashStringWithMod(char * str) {
  return (strlen(str) + sum(str)) % 7;
}

这里除数是7,故而散列函数simpleHashStringWithMod所生成索引值的取值范围是0 <= hvalue < 7,恰好落在长度为7的数组索引范围内。如果要借助这个散列函数来存储键值对{'Ruby' => 'Matz', 'Java' => 'James'},那么示意图为

169741e0d7c92142.png

冲突

前面我们所设计的散列函数十分简单,然而所分配的空间却最多只能够存储7个键值对,这种情况下很快就会产生冲突。所谓冲突就是不同的键,经过散列函数处理之后得到相同的散列值。也就是说这个时候,它们都指向了数组的同一个位置。我们需要寻求一些手段来处理这种冲突,如今用途比较广泛的就有开放地址法以及链地址法,且容我一一道来。

1. 开放地址法

开放地址法实现起来还算比较简单,只不过是当冲突产生的时候通过某种探测手段来在原有的数组上寻找下一个存放键值对位置。如果下个位置也存有东西了则再用相同的探测算法去寻找下下个位置,直到能够找到合适的存储位置为止。目前常用的探测方法有

线性探测法

平方探测法

伪随机探测法

无论哪种探测方法,其实都需要能够保证对于同一个地址输入,第n次探测到的位置总是相同的。

线性探测法很容易理解,简单来讲就是下一个索引位置,计算公式为hashNext = (hash(key) + i) mod size。举个直观点的例子,目前散列表中索引为5的位置已经有数据了。当下一个键值对也想在这个位置存放数据的时候,冲突产生了。我们可以通过线性探测算法来计算下一个存储的位置,也就是(5 + 1) % 7 = 6。如果这个地方也已经有数据了,则再次运用公式(5 + 2) % 7 = 0,如果还有冲突,则继续(5 + 3) % 7 = 1以此类推,直到找到对应的存储位置为止。很明显的一个问题就是当数组越满的时候,冲突的几率越高,越难找到合适的位置。用C语言来实现线性探测函数linearProbing结果如下

int linearProbing(Hash * hash, int address, int size) {
  int orgAddress = address;

  for (int i = 1; !hash[address].isNull; i++) {
    address = (orgAddress + i) % size; // 线性探测
  }
  return address;
}

只要散列表还没全满,它总会找到合适的位置的。平方探测法与线性探测法其实是类似的,区别在于它每次所探测的位置不再是原有的位置加上i,而是i的平方。平方探测函数quadraticProbing大概如下

int quadraticProbing(Hash * hash, int address, int size) {
  for (int i = 1; !hash[address].isNull; i++) {
    address = (address + i * i) % size; // 平方探测
  }
  return address;
}

上面两个算法最大的特点在于,对于相同的地址输入,总会按照一个固定的路线去寻找合适的位置,这样以后要再从散列表中查找对应的键值对就有迹可循了。其实伪随机数也有这种特性,只要随机的种子数据是相同的,那么每次得到的随机序列都是一定的。可以利用下面的程序观察伪随机数的行为

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int seed = 100;
    srand(seed);
    int value = 0;
    int i=0;
    for (i=0; i< 5; i++)
    {
        value =rand();
        printf("value is %d\n", value);
    }
}

伪随机种子是seed = 100,这个程序无论运行多少次打印的结果总是一致的,在我的计算机上会打印以下数值
value is 1680700
value is 330237489
value is 1203733775
value is 1857601685
value is 594259709
利用这个特性,我们就能够以伪随机的机制来实现伪随机探测函数randomProbing

int randomProbing(Hash *hash, int address, int size) {
  srand(address);
  while (!hash[address].isNull) {
    address = rand() % size;
  }
  return address;
}

无论采用哪种方式,只要有相同的address输入,都会得到相同的查找路线。总体而言,用开放地址法来解决地址冲突问题,在不考虑哈希表Resize的情况下,实现起来还是比较简单的。不过不难想到,它较大问题在于当散列表满到一定程度的时候,冲突的几率会比较大,这种情况下为了找到合适的位置必须要进行多次计算。另外还有个问题,就是删除键值对的时候,我们不能把键值对的数据简单地“删除”掉,并把当前位置设置成空。因为如果直接删除并设置为空的话会出现查找链中断的情况,任何依赖于当前位置所做的搜索都会作废,可以考虑另外维护一个状态来标识当前位置是“空闲”的,表明它曾经有过数据,现在也接受新数据的插入。

PS: 在这个例子中,我们可以只利用isNull字段来标识不同状态。用数值0来标识当前结点已经有数据了,用1来标识当前结点是空的,采用2来标识当前结点曾经有过数据,目前处于空闲状态,并且接受新数据的插入。这样就不会出现查找链中断的情况了。不过需要对上面的探测函数稍微做一些调整,这里不展开说。

2. 链地址法

链地址法跟开放地址法的线性探测十分相似,最大的不同在于线性探测法中的下一个节点是在当前的数组上去寻找,而链地址法则是通过链表的方式去追加结点。实际上所分配数组的每一个位置都可以称之为桶,总的来说,开放地址法产生冲突的时候,会去寻找一个新的桶来存放键值对,而链地址法则是依然使用当前的桶,但是会追加新结点增加桶的深度。示意图大概如下

169741ec2a0a377a.png

可见它的结点结构是

typedef struct Hash {
  char * key; // 指向散列的键
  char * value; // 指向散列的值
  char isNull; // 标识这个散列是否为空
  struct Hash * next; // 指向下一个结点
} Hash;

除了原来的数据字段之外,还需要维护一个指向下一个冲突结点的指针,实际上就是最开始谈到的链表的方式。这种处理方式有个好处就是,产生冲突的时候,不再需要为了寻找合适的位置而进行大量的探测,只要通过散列函数找到对应桶的位置,然后遍历桶中的链表即可。此外,利用这种方式删除节点也是比较容易的。即便是采用了链地址法,到了一定时候还是要对散列表进行Resize的,不然等桶太深的时候,依旧不利于查找。

3. 汇总

总体而言,采用开放地址法所需要的内存空间比较少,实现起来也相对简单一些,当冲突产生的时候它是通过探测函数来查找下一个存放的位置。但是删除结点的时候需要另外维护一个状态,才不至于查找链的中断。链地址法则是通过链表来存储冲突数据,这为数据操作带来不少便利性。然而,无论采用哪种方式,都需要在恰当的时候进行Resize,才能够让时间复杂度保持在O(1)左右。

查找

了解如何插入,那么查找也就不成问题了。对开放地址法而言,插入算法大概如下

1.通过散列函数计算出键所对应的散列值。

2,.根据散列值从数组中找到相对应的索引位置。

3.如果这个位置是“空闲”的,则插入数据。如果该键值对已经存在了,则替换掉原来的数据。

4.如果这个位置已经有别的数据了,表明冲突已经产生。

5.通过特定的探测法,计算下一个可以存放的位置。

返回第三步。

而查找算法是类似的

1.通过散列函数计算出键所对应的散列值。

2.根据散列值从数组中找到相对应的索引位置。

3.如果这个位置为空的话则直接返回说找不到数据。

4.如果这个位置能够匹配当前查找的键,则返回需要查找的数据。

5.如果这个位置已经有别的数据,或者状态显示曾经有过别的数据,表明有冲突产生。

6.通过特定的探测法,计算下一个位置。

7.返回第三步。

链地址法其实也类似,区别在于插入键值对的时候如果识别到冲突,链地址法并不会通过一定的探测法来查找下一个存放数据的位置,而是顺着链表往下搜索,增添新的结点,或者更新已有的结点。查找的时候则是沿着链表往下查找,找到目标数据则直接把结果返回。假设穷尽链表都无法找到对应的数据,表明数据不存在。

重组(Resize)

Resize是专业术语,直接翻译过来是重新设置大小,不过有些书籍会把它翻译成重组,我觉得这个翻译更为贴切。当原有的散列表快满的时候,其实我们不仅需要对原有的空间进行扩张,还需要用新的散列函数来重新映射键值对,让键值对可以更加分散地存储。

不过不同的实现方式进行重组的时机不太一样,对于开放地址法而言,每个桶都只能存放一个键值对,需要通过特定的探测法把冲突数据存放到相关的位置中。当散列表越满的时候冲突的几率就越大,要找到可以存放数据的地方将会越艰难,这将不利于后续的插入和查找。为此需要找到一个恰当的时机对散列表进行Resize。业界通过载荷因子来评估散列表的负载,载荷因子越大,冲突的可能性就越高。

载荷因子 = 填入表中的元素个数 / 散列表的长度
采用开放地址法来实现的散列表,当载荷因子超过某个阀值的时候就应当对散列表进行Resize了,不过阀值的大小则由设计者自行把控了。据维基百科上的描述,Java的系统库把载荷因子的阀值设置为0.75左右,超过这个值则Resize散列表。

而采用链地址法实现散列的时候,利用链表的特性,每个桶都能够存放多个结点,因此在链地址法中通过桶的深度来评估一个散列是否需要Resize更有意义。你可以当桶的最大深度超过某个值的时候对原有的散列进行Resize。

无论采用哪种实现方式,Resize的时机还需要设计者自行把控,不同的应用场景Resize的时机也可能会有所不同。Resize操作可以让我们原有的键值对数据更加分散,让散列表插入和查找的时间复杂度保持在O(1)左右。然而Resize毕竟是耗时操作,时间复杂度随着键值对数据的增长而增长,因此不宜操作得过于频繁。

本篇为Docker的入门级别的简单使用。

在做毕业设计相关的东西时候,需要安装环境特别苛刻的库。所以我直接使用了作者README中推荐的Docker的方式。

Web部分如何调用它呢:

方法一:

sudo docker exec

使用docker exec命令,执行某个命令然后输出。这种方式缺点是sudo需要输入密码,而且调用的方式太死板。不够灵活。

方法二:以提供的Docker镜像为基础,定制自己的Docker镜像。

1.拉取基础镜像

sudo docker pull aaa/bbb

图1

图中简单展示了这个镜像的的环境以及功能

2.以命令交互式进入该镜像

sudo docker run -it aaa/bbb

3.做一些修改,然后退出 exit

4.查看刚刚的修改

sudo docker ps -l 

图2

5.sudo docker commit [image id] [name]

提交修改,name 就是自己新的镜像名称。

图3

6.Run起来

我的应用是一个Rails应用,代码放在本地,在Docker环境中跑起来。

-d 后台运行

-v 目录1:目录2 将本地目录1映射到容器中的目录2

-w 执行命令目录

-e 环境变量

-p 端口映射 示例是将容器的3000端口映射到本机的3000端口

其中有些设计模式可能在实际中没用用到过,有些用到了可能自己也不知道。O(∩_∩)O

单例模式

一个类仅有一个实例。
var S = function(){
    this._instance = null;
}

S.prototype.getInstance = function(){
    if (!this._instance) return new S();
    return this._instance;
}

场景:一个登录框、一个数据库连接实例

策略模式

定义一系列的算法,把它们一个个封装起来,并且使它们可以相互替换。
var S = function( salary ){
  return salary * 4;
};
var A = function( salary ){
  return salary * 3;
};
var B = function( salary ){
  return salary * 2;
};
var calculateBonus = function( func, salary ){
  return func( salary );
};
calculateBonus( S, 10000 ); // 输出:40000

场景:实现不同的动画(如仅仅因为动画计算方法不同)、表单提交验证(有很多条验证的规则)。

简单地说就是把【算法】部分提取出来。

代理模式

为其他对象提供一种代理以控制对这个对象的访问。

分为两种代理:1.保护代理;对被代理的对象进行一些过滤等操作。2.虚拟代理。虚拟代理把一些开销很大的对象,延迟到真正需要它的时候才去创建。

形象的描述一下,书上的例子:

A在追求C,请求C的好朋友B去送东西。

保护代理:B如果在收到A的东西里面发现只有鲜花一类没用的东西,就不送给C了。如果B发现A送的是宝马车,那么就把东西转交给C。

虚拟代理:B在收到A的东西后,不着急转交给C。在C的心情好的时候交给他,这样A追求成功的机率会大一些。

体现了单一职责原则;当然可以把B的功能写在A里面,但是这样在修改的时候可能会感到困难。

场景:请求代理、图片懒加载

// 请求代理,在不同环境下请求不同的host。保护代理
var proxyRequest = function(url){
  if (environment === 'development'){
    url = 'http://localhost' + url;
  }
  if (environment === 'production'){
    url = 'http://www.xxx.com' + url;
  }
  return fetch(url);
}
proxyRequest('/api/')

// 图片懒加载。虚拟代理
var myImage = (function(){
var imgNode = document.createElement( 'img' );
document.body.appendChild( imgNode );
  return {
  setSrc: function( src ){
    imgNode.src = src;
    }
  }
})();

var proxyImage = (function(){
  var img = new Image;
    img.onload = function(){
      myImage.setSrc( this.src );
    }
    return {
      setSrc: function( src ){
      myImage.setSrc( 'file:///C:/Users/svenzeng/Desktop/loading.gif' );
      img.src = src;
    }
  }
})();

proxyImage.setSrc( 'http://imgcache.qq.com/music/photo/k/000GGDys0yA0Nk.jpg' );

发布-订阅模式

发布-订阅模式又叫观察者模式,它定义对象间的一种一对多的依赖关系,当一个对象的状态发生改变时,所有依赖于它的对象都将得到通知。

在JS中非常常见:Ajax回调、事件监听...

组合模式

组合模式将对象组合成树形结构,以表示“部分-整体”的层次结构。

实例:文件扫描器

/******************************* Folder ******************************/
var Folder = function( name ){
  this.name = name;
  this.files = [];
};
Folder.prototype.add = function( file ){
  this.files.push( file );
};
Folder.prototype.scan = function(){
  console.log( '开始扫描文件夹: ' + this.name );
  for ( var i = 0, file, files = this.files; file = files[ i++ ]; ){
    file.scan();
  }
};
/******************************* File ******************************/
var File = function( name ){
  this.name = name;
};
File.prototype.add = function(){
  throw new Error( '文件下面不能再添加文件' );
};
File.prototype.scan = function(){
  console.log( '开始扫描文件: ' + this.name );
};

var folder = new Folder( '学习资料' );
var folder1 = new Folder( 'JavaScript' );
var folder2 = new Folder ( 'jQuery' );
var file1 = new File( 'JavaScript 设计模式与开发实践' );
var file2 = new File( '精通 jQuery' );
var file3 = new File( '重构与模式' )
folder1.add( file1 );
folder2.add( file2 );
folder.add( folder1 );
folder.add( folder2 );
folder.add( file3 );
folder.sacn()

享元模式

享元模式的核心是运用共享技术来有效支持大量细粒度的对象。

享元模式要求将对象的属性划分为内部状态与外部状态(状态在这里通常指属性)。

  • 内部状态储存于对象内部。
  • 内部状态可以被一些对象共享。
  • 内部状态独立于具体的场景,通常不会改变。
  • 外部状态取决于具体的场景,并根据场景而变化,外部状态不能被共享。

通俗讲就是把需要大量的实例的共同点(内部状态)提取出来,只实例化一个,其他属性(外部状态)由管理器去操作、管理。

书中的例子是有一个上传2000个文件的操作,有些是通过Flash上传,有些通过表单上传。new了2000个Upload实例。但是他们唯一不同的是其中uploadType不同,所以可以只new 2个Upload实例就行了,分别代表用Flash上传和表单上传,其他属性,也可以说是外部状态(文件名、文件大小等)由外部的管理器去修改、操作。

适配器模式

适配器模式的作用是解决两个软件实体间的接口不兼容的问题。使用适配器模式之后,原本由于接口不兼容而不能工作的两个软件实体可以一起工作。

常见的场景如一些ORM框架,只需要填写简单的配置,在不同的环境下使用不同的数据库。Session的配置,模板引擎的配置等。

ThinkJS框架的Adapter文档中有写到

前端方面我觉得pollyfill应该也算是适配器模式吧。

function AnimationAdapter(){
  if (!window.requestAnimationFrame){
    return function(fn){
      return setTimeout(fn, 17);
    }
  }
  return window.requestAnimationFrame;
}
let fn = AnimationAdapter()

装饰器模式

装饰者模式能够在不改变对象自身的基础上,在程序运行期间给对象动态地添加职责。

装饰器在Python、ES6中都有,其本质就是一个函数。只是通过一个语法糖简化了传递函数的过程。可以将装饰器就看作一个函数A,参入的参数是函数B,对传入的函数B进行修改后返回一个新的函数C。

但是在JS中装饰器不能用于一个函数。

@decorator
class A {}
// 等同于
class A {}
A = decorator(A) || A;

和适配器模式的区别:装饰器模式一般给函数、对象增加功能,可能增加很多个功能。而适配器通常只包装一次。

一般用于AOP

中介者模式

中介者模式的作用就是解除对象与对象之间的紧耦合关系。增加一个中介者对象后,所有的相关对象都通过中介者对象来通信,而不是互相引用,所以当一个对象发生改变时,只需要通知中介者对象即可。

最少知识原则,减少对象之间的联系。

发现只有在写博客的时候,才会认真地去学习。总结一下我在学习、写前后端项目中的一些有关身份验证的心得体会。

因为HTTP是无状态的,如何保证用户和用户之间的操作隔离开来,如何保证有些接口、页面只有某些用户才能访问。一般通过下面的方式实现:

1.cookie方案

原理

这种方式依赖没用禁用cookie浏览器环境。

step1:客户端请求登陆接口,服务端返回200状态码同时把cookie给客户端。

step2:客户端在需要身份验证的接口上带上cookie。

step3:服务端把cookie取出、解析后就可以知道身份了。

那session(会话)又是什么?session不是一个实体,而是基于cookie来维持会话状态的一种技术。有些敏感信息存储在客户端导致不安全,所以服务端在创建session的时候生成一个session_id通过cookie传给客户端。而服务端维持一个 session_id -> session 类似的哈希结构。

一般来说session是在内存中的,但是通常会把这个哈希结构用KV(键值对)数据库来存储,这样做的好处是方便管理,而且在分布式的环境下也可以。

服务端大致实现思路:

const http = require('http')
const server = http.createServer((req, res) => {
  if (req.url === '/login'){
    // 从数据库中验证账号密码正确(略)

    // 保存下面这个SESSION_ID(略)

    // 设置响应头
    res.writeHead(200, {
      'Content-Type': 'application/json',
      'Set-Cookie': 'SESSION_ID=abcdefg; HttpOnly;' 
    })
    // 返回响应
    res.write(JSON.stringify({
      code: 200,
      msg: 'OK'
    }))
    res.end()
    
  }
  // 匹配其他路由
  else {
    if (req.headers.cookie && isValid(req.headers.cookie)){
      // 解析cookie并验证,验证通过做一些事情
      // 验证失败则返回code 401
      res.write('OK')
      res.end()
    }
  }
})
server.listen(3000)

前端需要注意:使用fetch时默认不携带cookie,需要手动设置。在XMLHttpRequest中也是。

// Fetch
fetch({
  //cookie既可以同域发送,也可以跨域发送
  credentials: 'include'  
})

// XMLHttpRequest
xhr.withCredentials = true

安全

首先,没用绝对的安全。只能通过一些手段来提高安全性。

1.在set-cookie的时候使用HttpOnly。这样可以防止客户端通过JS来获取cookie,在一些XSS攻击中可能会导致cookie泄漏。

2.HTTPS。在传输过程中cookie不会以明文的方式传递,就算被第三方截取,也是加密过的。

3.服务端的session过期机制。

Token方案

在一些非浏览器环境下(当然浏览器环境也可以使用该方案),如微信小程序、APP中等前端如何和后端通信。其实原理和上面说的是一样的。

原理

step1:客户端请求登陆接口,服务端返回Token,且客户端手动将Token保存。

step2:客户端发起请求的时候将Token带上。

step3:服务端解析Token。

不同就在于需要手动去存储这个凭证。

安全

1.Token设置过期时间,增加刷新机制。

2.HTTPS。

再说下JWT

再说一下JWT(JSON Web Token),我过去对JWT的理解是错误的。
参考:请停止使用 JWT 认证。JWT适合用于一次性登陆的场景。
优点是服务端消耗更少的资源(不用去保存状态)。
至于很多文章说的安全,无法认同。难道服务端用SCRET KEY加密后就是安全的了吗?一般jwt保存在localStorage里面,泄漏了jwt同样会导致身份被盗用。可以通过在payload里面设置过期时间来避免泄漏后造成的风险。所以“更安全”我认为是不成立的。

2018年秋招面试记录。所记录的内容并非完整,部分是印象比较深的部分。

offer = 实力 + 运气。运气包括了公司的HC,部门匹配度,面试官等因素。自身的实力当然是最重要的。其实在面试的过程学到了很多东西:

一、知识的查漏补缺;每一场面试下来一定要有所收获。

二、表达能力;特别是在电话面试的时候,能够清晰地把想表达的意思表达出去非常重要!

三、谦虚;每一个面试官应该都有很多值得学习的地方,有机会向面试官寻求一些建议或询问不足的地方。

ThoughtWorks

岗位:软件开发

Homework:一个生成迷宫的程序,使用工厂模式、格式化输入、输入验证、写单元测试等。

写完Homework后,在此基础上加两个功能。写完后对问代码有什么可以优化的地方,引申出了一些问题。如:if else 如果嵌套过多该如何处理。问的其他问题和简历相关度很大。以下是不完整记录:

1.React数据流的理解

2.前端工程化

3.Django和Tornado的区别

4.如何实现单例模式

基本没有问算法相关,个人感觉主要是对对工程、编码能力的要求。

腾讯云

晚上十点来的电话,把我问得一脸懵逼。首先是自我介绍,讲项目。

1.Python的异常处理

2.Python执行Linux命令

3.Python多进程和多线程

4.Tornado协程

5.Django项目的结构

6.OSI七层模型以及功能

7.ping用的什么协议

8.TCP三次握手

9.Celery Broker

10.Redis常用的数据结构类型

11.Websocket

12.Bootstrap和Jquery相关的问题

13.设计一个后台跑任务前端实时输出日志的功能

其他主要是一些Linux、网络相关的知识,没有任何准备,也没复习,比较凉。

腾讯SNG

由于问的问题太多太杂,差不多问了一个小时,完全是知识点轰炸,所以记录几个答得不好的问题。

1.闭包是什么,如何产生,为什么会产生(底层原理)

2.浏览器针对重绘和重排做了哪些优化

3.Diff算法的策略(tree diff, component diff, element diff)

4.XSS防御的方法,前端方面我说了escape过滤,对特殊字符进行转义,插入HTML片段innerHTML->innerText,(面试官好像不满意,感觉没有答到点子上)

5.CORS跨域(withCredentials、简单请求、非简单请求的预检请求)

6.Webpack、gulp、grunt的区别

7.协商缓存的请求头和响应头(当时If-None-Match和Last-Modified记混了,凉)

猿辅导

听说开的薪资十分高,但是要求也很严格。一开始问了几个简历相关的问题后,如React的setState、VirtualDOM、Redux、跨域以后便开始通过石墨文档在线同步手撕代码。

1.写一个函数toPromise将一个获取数据函数fn转化为Promise

2.Promise.all相关

已知:loadImage(src).then().catch()

实现:loadImageList(srcList).then().catch()

扩展1:自己实现Promise.all且保证结果顺序与srcList一致

扩展2:加一个limit参数限制最大同时请求数量

function map(arr, fn, concurrency) {
    concurrency = concurrency || 1;
    return new Promise(function(resolve, reject) {
  
      var completed = 0;
      var started = 0;
      var running = 0;
      var results = new Array(arr.length);
  
      (function replenish() {
        if (completed >= arr.length) {
          return resolve(results);
        };
  
        while (running < concurrency && started < arr.length) {
          running++;
          started++;
  
          var index = started - 1;
          fn.call(arr[index], arr[index], index) // item,index
            .then(function(result) {
              // console.log('done');
              running--;
              completed++;
              results[index] = result;
  
              replenish();
            })
            .catch(reject);
        }
      })();
    });
}
3.Flatten

List: [1, 2, [3, 4], [5, 6, [7, 8], 9], 10, 11]

depth = 1: [1, 2, 3, 4, 5, 6, [7, 8], 9, 10, 11]

depth = 2: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
function flatten(list, depth){
    let result = []
    if (depth == 0) return list
    for(let i = 0; i < list.length; i++){
        if (!Array.isArray(list[i])){
            result.push(list[i])
        }else{
            result = result.concat(flatten(list[i], depth - 1))
        }
    }
    return result
}

二面(现场面试):一上来就是三道手撕代码,然后结束面试。

1.类似[孤岛问题](https://leetcode.com/problems/number-of-islands/description/)

由于做过类似的,很快就说出了思路,面试官说那我们换道题(我的内心是崩溃的)

2.一个数组实现两个栈

a.奇数、偶数坐标分别代表两个栈,b.中间作为两个栈的底部,分别向左和向右扩展。都说到了思路,不知道面试官好像不太满意。

3.求一颗二叉树的最大宽度(哪一层节点数最多)

勉强写出来了,但是代码可能不太好看。

360 搜索

一面:面试官比较随意,上来先是自我介绍以及谈谈对前端的理解。感觉是让你自己自由发挥,看看能说出多少。这一部分自由发挥得很一般,不知道该说点啥,胡扯一通。问了一些有关HTML5、CSS相关的话题,甚至PSD切图。JS问了闭包、ES6/Promise、Webpack、Nodejs了解程度以及Vue的双向绑定实现等等,都是些常规问题。

列出几个答得不好得问题

1.如果浏览器不支持JSON.parse怎么办

用eval

2.Meta标签有哪些

这个的确平时用到的比较少,就回答了viewport, charset, keywords等,其实还有很多有用的。
<meta http-equiv="参数" content="具体的描述">
* http-equiv属性(相当于http的文件头作用)
* content-Type
* X-UA-Compatible(浏览器采取何种版本渲染当前页面)
* cache-control(指定请求和响应遵循的缓存机制)
* expires(网页到期时间)
* refresh(自动刷新并指向某页面)
* Set-Cookie(cookie设定)

3.页面性能优化

没说到preload predns prefetch等。
<link rel="dns-prefetch" href="//example.com">

二面:考察JS相关的多一点,记录几个印象比较深刻的问题。

1.parseInt(0.000000008)

答案8,这个考parseInt的隐式转换,0.000000008 -> 8e-9 -> 8

2.(() => {}).length 

答案0,function的length属性,形参数量

3.1 in [1]

答案false,[1] == { 0: 1 },in操作符取key比较 1 != 0

4.伪类::nth-child(an+b) 干什么n从多少开始算

答案:选取第a的倍数+b个子元素,n从1开始计算

5.visibility: hidden 如何不能点击

答案:CSS3中的pointer-event

英语流利说

一面:

1.两栏布局、position相关问题(fixed,absolute)、垂直居中、Flex(flex自己用的很少,答得不好)

2.斐波拉契数列、数组去重、数组中包含对象的去重

3.TCP、UDP的区别与HTTP的关系、HTTP、HTTPS、HTTPS原理以及什么加密算法

4.动画setTimeout为什么是16ms(项目中写的一个polyfill)

5.React生命周期;Redux的思想以及在白板上画出数据流图

6.项目中为什么要用Redis

7.滚动不用JS如何实现?(CSS的一个新特性)

8.点击ABCD选项将某选项通过动画移动到某个位置的实现思路

9.讲讲C语言中的malloc以及如何释放(free) -> 引申出JS相关垃圾回收机制

10.捕获和冒泡的过程

二面:面非常广,从技术->生活->学习各方面都问

1.HTTP状态码能说多少说多少(1XX,200,301,302,304,403,404,405,500,502,504),着重讲了下304

2.CDN以及前端部署

3.实习项目中难点如何解决

4.学校做项目和公司最大的不同

5.实习中有哪些收获,学到了什么 -> 流程化开发、ABTest(如何实现的,达到什么目的)

6.平时的学习方法,最近看什么书,什么爱好

百度 流量质量控制部

一面:

1.HTML5新特性

2.输入url到浏览器展示的过程(一个数据包的传输过程,从IP讲到DNS,交换机、路由器、Nginx、WebApplication、浏览器渲染等多个角度去讲)

3.CSS相关:BFC(比如解决塌陷的原理是什么)、清除浮动还有什么方法、垂直水平居中

4.JS相关:prototype原型链;方法、属性继承实现;原型链继承后为什么要改constructor指向;闭包的应用;

5.快排过程,复杂度是多少,最坏情况是怎么样的,如何优化(每次排序随机选择pivot)

5.同步、异步、阻塞、非阻塞的区别。这个答得不好,但是面试官非常耐心地给我讲了CPU的调度方式、中断等等,起码讲了有15分钟吧,学到了不少的知识,也知道了自己的薄弱点。中途还问了进程的3个状态,以及这三个状态是如何转换的。“就绪”和“阻塞”态有什么不同。

6.锁,死锁是什么,如何产生,MySQL的锁

二面:

1.讲一个印象比较深的项目

2.为什么使用Redis;Redis常用的数据结构;这种情况为什么不用MySQL;

3.JQuery和前端MV*框架相比优点、缺点,适用的场景

4.对前端、后端开发的理解

还有些问题记不住了,聊的东西总体来说是大方向上的,没有去讲很细节的东西。

三面:

经理面。聊人生、聊职业规划、聊部门

网易考拉

一面:序号前端1组,面试体验非常好,问的东西也是基础,而且说话和善。

1.垂直居中:尽量多写,flex属性以及各个属性的意思。position absolute,relative

2.BFC、清除浮动

3.原型链、继承实现

4.闭包,写一个节流函数

5.const a = {}; a.b = 1; 可以吗

6.讲下Promise大致原理

7.String实例有哪些方法,Array实例有哪些方法(当时给自己挖了坑,valueOf和toString没说好)

8.学习JS过程中看了哪些书

9.常见的HTTP请求头、响应头

二面:面试官很严肃,全程看电脑

1.写一个数组去重,讲下思路

2.写一个发布订阅模式

3.webpack自己配置过吗,大致说一下,以及优化点(Tree shaking和增量更新等)。

4.React生命周期;shouldComponentUpdate具体是干什么的(扯出了virtualDOM、Diff等)

5.实习过程中学到了什么

6.React高阶组件以及举例子,场景有哪些

7.React组件有哪些形式(一:类,函数。二:受控,不受控,无状态)

8.讲一下Redux的三大原则,这样设计的好处

9.React Router如何实现的;HTML5的history和hash的区别;BrowerHistory后端需要如何配合

爱奇艺

凉凉的一面,走之前面试官小哥还说:“我送一下你吧”:

1.主线程和子线程,谁操作内存

2.进程间共享内存吗

3."abc" 占多少字节

4.MySQL 中 int(x) x是指位数还是2^x字节

5.MySQL范式;MySQL索引,建多了会怎么样,哪种情况下建,

6.MySQL中的锁,行锁还是表锁,哪个效率高点,什么场景下会出现

7.Redis中常用的数据结构

8.网络几层模型;tcp、udp的区别以及和socket的关系

9.鸭子类型

10.迭代器和生成器哪个效率高,为什么

11.Python2 检查str还是unicode

感觉基础知识答得太烂,总结:我菜

猎豹移动

一面:

1.自我介绍

2.CSS垂直居中、position的各个值以及使用

3.闭包以及作用;节流和防抖的应用场景;

4.React生命周期;Ajax请求应该在哪个周期发起

5.function component 和 class component

6.数组去重(很好奇为什么十次有八次都要考这个)

7.box-sizing属性;盒子模型

二面:

1.统计数组中出现'1'的次数,['abc123', 1234, '761saz', 5610']

2.TOP K问题以及优化;讲一个排序算法

3.输入URL到浏览器展示的过程;onload和onready区别

4.跨域;(详细说了下CORS、JSONP过程)

5.GET和POST区别

还有些常规JS问题,实在是忘了。还聊了一下部门主要的业务

贝壳

一面:

1.闭包理解;应用:实现increse()增加,get()获取

2.双飞翼布局;如何解决浮动问题

3.作用域链的理解和原理

4.var a = 5; function b(){ function c(){ console.log(a); var a = 10;  }; c() } 输出什么

5.Session

6.对React的理解

二面:体验较差

1.介绍项目说难点

2.硬币找零问题(我用的动态规划,面试官一直强调这是组合问题不是排列问题,说这个方法不行。我表示很懵逼,没办法最后就写了一个暴力破解)

最后二面挂了,有点不解。

度小满

一面:

1.React生命周期

2.作用域和作用域链

3.Promise

4.call bind apply,apply实现bind

5.es6继承

6.首屏白屏优化

7.http传输的安全

8.web Storage和cookie

9.双飞翼布局

二面:

1.CPU的GHz代表什么意思

2.写代码:设计一个验证(Valid)类

3.Hybird中H5与原生通信的注意点(线程、性能、通信格式等)

4.Tree Shaking 原理;你来写如何实现;

5.写代码,二叉树中序遍历

6.写代码,merge两个有序链表

今日头条

一面:其他都是基础知识,印象不太深刻,10分钟就结束了。

1.自适应屏幕宽度一半的正方形

2.选择排序;swap的不用变量的交换

第四范式

一面:基础知识(HTML,CSS,JS) + 手撕代码(1.类似Vue的模板语法解析、2.getAttr(obj, 'user.name')获取属性值)

二面:基础知识 + 大方向上的问题。其中有一个问题没答上来,如何保证cookie安全,让JS不能操作cookie:http-only

三面:聊人生,聊职业规划,聊部门

京东 京东云

一面:

1.React理解

2.React-Router的两种模式的实现和异同

3.后端渲染和前端渲染的区别

4.自己一个React项目结构是怎么样的

5.项目中用到了哪些设计模式;用ES6实现一个单例模式

6.跨域;讲一下代理;Nginx

7.闭包;作用域链

8.Webpack的使用

二面:

1.React开发的感受以及大致的实现(Diff、VirtualDOM);缺点是什么(个人觉得从应用场景去讲)

2.JSX转码后输出的是什么

3.父子组件、子子组件中的通信

4.介绍一下Redux,以及Redux和React结合使用

5.介绍一下Vue和React的不同;双向绑定的实现

6.CSS3特性;动画:一个正方形放大到2倍;

7.Flex布局

8.事件模型;为什么会有冒泡和捕获两种;事件委托,好处是什么

9.跨域;重点讲CORS

10.前端性能优化

11.HTTP2和HTTP1.1和HTTP1.0区别;HTTP缓存;HTTP长连接

12.TCP三次握手

13.重排和重绘

14.Promise

美团 新到店

一面:

输入URL到展示的过程

页面加载是单进程还是多进程

TCP三次握手过程

TCP包一次最大传输数据多大

localStorage存储量

HTTP缓存

跨域如何解决

两道布局题

线上CDN挂了如何处理、容错方案

Nginx负载均衡如何与Node进程通信;通信的原理是什么;这种架构名称

如果保证负载均衡后面的服务可用

hello world级别的node进程复制一个进程大约需要申请多少内存

关注过QPS等数据吗

node一般启动最大进程数与什么有关;关系式

二面:

1.讲一下链表、二叉树、栈、队列

2.链表和数组的区别

3.用过图吗

4.查找一般使用哪些结构

5.排序算法;哪些稳定

6.写一个快排

7.HTTP/TCP/UDP的区别和联系

8.HTTP头有哪些,如何使用

9.HTTP状态码有哪些,什么意思

10.CDN和DNS是什么

11.谈谈用NodeJS、Python、Ruby等的感受(因为他问我博客用什么写的,Ruby on Rails。中心突出语言不重要)

三面:主要聊了一些架构、前端理解等大方向的问题,谈谈项目设计的结构,用到的设计模式等等。生活、为人、遇到困难的解决办法、学习的方法等等。最后面试官还给我提出了一些建议:1.看看《代码大全》这本书,基础不错,但是需要加强设计这方面的知识。2.佛系地与人相处可能并不是一个特别好的点,争执有时可能会更好的促进人际关系。

拼多多

一面:

1.前端渲染和后端渲染的区别、优缺点

2.React生命周期

3.React用的什么版本,最新的生命周期有了解吗

4.讲一下Redux的作用

5.闭包是什么

6.继承的实现

7.new 操作符做了哪些事情

8.垂直水平居中

9.position的值以及使用

10.CSS一个div实现圆环

11.排序算法哪些稳定

12.讲一下快排,时间复杂度多少

13.1-100 无序,求缺少的数

阿里

早听说没用HC了,走一个流程。

简历面:

1.聊项目

2.谈下React

3.一个CSS题

4.一道编程题

5.TOP K问题

6.cookie和session

腾讯

一面:在酒店的一个房间,进去先做一张卷子。一些基础题+2道编程题(1.实现类、私有属性、方法 2.高精度加法)

1.304说一下,完整过程(还给我埋坑:last-modified只能精确的秒吗)

2.同源策略、跨域(具体说一下iframe的跨域)

3.小程序和H5的区别

4.React中Key的作用

5.React中PureComponent和Component区别

6.UI组件和容器组件

7.正则匹配QQ号

8.5:15 两个指针的夹角

9.实习的公司对你的评价

10.职业规划

面试官每个问题都想了好多秒才问的。有点迷

新浪微博

一面:

1.JS基本数据类型

2.JS引用数据类型

3.快排

4.深拷贝、浅拷贝

5.Python中常用的数据类型

6.JS的异步是怎么样的

7.回调函数的场景有哪些

二面:

1.Hybird原理

2.小程序原理

3.React JSX语法本质是什么

4.setState干了什么

5.如果自己设计React大致思路(其实就是React的思路)

6.Webpack配置

7.CORS跨域

8.移动端适配

9.rem和px以及flexiable.js原理

10.正则表达式解析URL query参数

11.node 内存泄漏排除问题

12.node 事件循环机制

13.koa或者express是如何处理post提交的数据

14.最大连续子数组和以及坐标

15.随机生成16位a-zA-Z0-9字符串

====================================

感谢之前实习的公司携程,实习过程中学到了很多东西,而且部门老大也非常好。

但行好事,莫问前程。

2018.9.29