一致性哈希算法php

1. 如何理解c/c++和php语言的区别

一、编程语言

1.根据熟悉的语言，谈谈两种语言的区别？

主要浅谈下C/C++和PHP语言的区别:

1)PHP弱类型语言，一种脚本语言，对数据的类型不要求过多，较多的应用于Web应用开发，现在好多互联网开发公司的主流web后台开发语言，主要框架为mvc模型，如smarty,yaf，升级的PHP7速度较快，对服务器的压力要小很多，在新浪微博已经有应用，对比很明显。

2)C/C++开发语言，C语言更偏向硬件底层开发，C++语言是目前为止我认为语法内容最多的一种语言。C/C++在执行速度上要快很多，毕竟其他类型的语言大都是C开发的，更多应用于网络编程和嵌入式编程。

2.volatile是干啥用的，（必须将cpu的寄存器缓存机制回答得很透彻），使用实例有哪些？（重点）

1） 访问寄存器比访问内存单元要快,编译器会优化减少内存的读取，可能会读脏数据。声明变量为volatile，编译器不再对访问该变量的代码优化，仍然从内存读取，使访问稳定。

总结：volatile关键词影响编译器编译的结果，用volatile声明的变量表示该变量随时可能发生变化，与该变量有关的运算，不再编译优化，以免出错。

2）使用实例如下( 区分C程序员和嵌入式系统程序员的最基本的问题。 )：

并行设备的硬件寄存器（如：状态寄存器）
一个中断服务子程序中会访问到的非自动变量(Non-automatic variables)
多线程应用中被几个任务共享的变量
3)一个参数既可以是const还可以是volatile吗？解释为什么。

可以。一个例子是只读的状态寄存器。它是volatile因为它可能被意想不到地改变。它是const因为程序不应该试图去修改它。
4）一个指针可以是volatile 吗？解释为什么。
可以。尽管这并不是很常见。一个例子当中断服务子程序修改一个指向一个buffer的指针时。

下面的函数有什么错误：
int square(volatile int *ptr) {
return *ptr * *ptr;
}
下面是答案：
这段代码有点变态。这段代码的目的是用来返指针*ptr指向值的平方，但是，由于*ptr指向一个volatile型参数，编译器将产生类似下面的代码：
int square(volatile int *ptr){
int a,b;
a = *ptr;
b = *ptr;
return a * b;
}
由于*ptr的值可能被意想不到地改变，因此a和b可能是不同的。结果，这段代码可能并不是你所期望的平方值！正确的代码如下：
long square(volatile int *ptr){
int a;
a = *ptr;
return a * a;
}

更多linux内核视频教程文本资料免费获取后台私信【 内核 】。

3.static const等等的用法，（能说出越多越好）（重点）

² 首先说说const的用法（绝对不能说是常数）

1）在定义的时候必须进行初始化

2）指针可以是const 指针，也可以是指向const对象的指针

3）定义为const的形参，即在函数内部是不能被修改的

4）类的成员函数可以被声明为正常成员函数，不能修改类的成员变量

5）类的成员函数可以返回的是常对象，即被const声明的对象

6）类的成员变量是指成员变量不能在声明时初始化，必须在构造函数的列表里进行初始化

（注：千万不要说const是个常数，会被认为是外行人的！！！！哪怕说个只读也行）

下面的声明都是什么意思？
const int a; a是一个正常整型数
int const a; a是一个正常整型数
const int *a; a是一个指向常整型数的指针，整型数是不可修改的，但指针可以
int * const a; a为指向整型数的常指针，指针指向的整型数可以修改，但指针是不可修改的
int const * a const; a是一个指向常整型数的常指针，指针指向的整型数是不可修改的，同时指针也是不可修改的
通过给优化器一些附加的信息，使用关键字const也许能产生更紧凑的代码。合理地使用关键字const可以使编译器很自然地保护那些不希望被改变的参数，防止其被无意的代码修改。简而言之，这样可以减少bug的出现。

Const如何做到只读？

这些在编译期间完成，对于内置类型，如int， 编译器可能使用常数直接替换掉对此变量的引用。而对于结构体不一定。

² 再说说static的用法（三个明显的作用一定要答出来）

1）在函数体内，一个被声明为静态的变量在这一函数被调用过程中维持其值不变。
2）在模块内（但在函数体外），一个被声明为静态的变量可以被模块内所用函数访问，但不能被模块外其它函数访问。它是一个本地的全局变量。
3）在模块内，一个被声明为静态的函数只可被这一模块内的其它函数调用。那就是，这个函数被限制在声明它的模块的本地范围内使用

4）类内的static成员变量属于整个类所拥有，不能在类内进行定义，只能在类的作用域内进行定义

5）类内的static成员函数属于整个类所拥有，不能包含this指针，只能调用static成员函数

static全局变量与普通的全局变量有什么区别?static局部变量和普通局部变量有什么区别?static函数与普通函数有什么区别?

static全局变量与普通的全局变量有什么区别：static全局变量只初始化一次，防止在其他文件单元中被引用;
static局部变量和普通局部变量有什么区别：static局部变量只被初始化一次，下一次依据上一次结果值；
static函数与普通函数有什么区别：static函数在内存中只有一份，普通函数在每个被调用中维持一份拷贝

4.extern c 作用

告诉编译器该段代码以C语言进行编译。

5.指针和引用的区别

1）引用是直接访问，指针是间接访问。

2）引用是变量的别名，本身不单独分配自己的内存空间，而指针有自己的内存空间

3）引用绑定内存空间（必须赋初值），是一个变量别名不能更改绑定，可以改变对象的值。

总的来说：引用既具有指针的效率，又具有变量使用的方便性和直观性

6. 关于静态内存分配和动态内存分配的区别及过程

1) 静态内存分配是在编译时完成的，不占用CPU资源；动态分配内存运行时完成，分配与释放需要占用CPU资源；

2)静态内存分配是在栈上分配的，动态内存是堆上分配的；

3)动态内存分配需要指针或引用数据类型的支持，而静态内存分配不需要；

4)静态内存分配是按计划分配，在编译前确定内存块的大小，动态内存分配运行时按需分配。

5)静态分配内存是把内存的控制权交给了编译器，动态内存把内存的控制权交给了程序员；

6)静态分配内存的运行效率要比动态分配内存的效率要高，因为动态内存分配与释放需要额外的开销；动态内存管理水平严重依赖于程序员的水平，处理不当容易造成内存泄漏。

7. 头文件中的 ifndef/define/endif 干什么用 ？

预处理，防止头文件被重复使用，包括pragma once都是这样的

8. 宏定义求两个元素的最小值

#define MIN(A,B) （（A） next;

}

else

{

return NULL;

}

}

Node* pFind = pHead;

while (pCurrent) {

pFind = pFind->next;

pCurrent = pCurrent->next;

}

return pFind;

}

2. 给定一个单向链表（长度未知），请遍历一次就找到中间的指针，假设该链表存储在只读存储器，不能被修改

设置两个指针，一个每次移动两个位置，一个每次移动一个位置，当第一个指针到达尾节点时，第二个指针就达到了中间节点的位置

处理链表问题时，”快行指针“是一种很常见的技巧，快行指针指的是同时用两个指针来迭代访问链表，只不过其中一个比另一个超前一些。快指针往往先行几步，或与慢指针相差固定的步数。

node *create() {

node *p1, *p2, *head;

int cycle = 1, x;

head = (node*)malloc(sizeof(node));

p1 = head;

while (cycle)

{

cout > x;

if (x != 0)

{

p2 = (node*)malloc(sizeof(node));

p2->data = x;

p1->next = p2;

p1 = p2;

}

else

{

cycle = 0;

}

}

head = head->next;

p1->next = NULL;

return head;

}

void findmid(node* head) {

node *p1, *p2, *mid;

p1 = head;

p2 = head;

while (p1->next->next != NULL)

{

p1 = p1->next->next;

p2 = p2->next;

mid = p2;

}

}

3. 将一个数组生成二叉排序树

排序，选数组中间的一个元素作为根节点，左边的元素构造左子树，右边的节点构造有子树。

4. 查找数组中第k大的数字？

因为快排每次将数组划分为两组加一个枢纽元素，每一趟划分你只需要将k与枢纽元素的下标进行比较，如果比枢纽元素下标大就从右边的子数组中找，如果比枢纽元素下标小从左边的子数组中找，如果一样则就是枢纽元素，找到，如果需要从左边或者右边的子数组中再查找的话，只需要递归一边查找即可，无需像快排一样两边都需要递归，所以复杂度必然降低。

最差情况如下：假设快排每次都平均划分，但是都不在枢纽元素上找到第k大第一趟快排没找到，时间复杂度为O(n)，第二趟也没找到，时间复杂度为O(n/2)，第k趟找到，时间复杂度为O(n/2k)，所以总的时间复杂度为O(n(1+1/2+....+1/2k))=O(n)，明显比冒泡快，虽然递归深度是一样的，但是每一趟时间复杂度降低。

5. 红黑树的定义和解释？B树的基本性质？

红黑树：

性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3. 每个叶子结点都带有两个空的黑色结点（被称为黑哨兵），如果一个结点n的只有一个左孩子，那么n的右孩子是一个黑哨兵；如果结点n只有一个右孩子，那么n的左孩子是一个黑哨兵。
性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

B树：

1.所有非叶子结点至多拥有两个儿子（Left和Right）；

2.所有结点存储一个关键字；

3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；

6. 常见的加密算法？

对称式加密就是加密和解密使用同一个密钥。
非对称式加密就是加密和解密所使用的不是同一个密钥，通常有两个密钥，称为“公钥”和“私钥”，它们两个必需配对使用。
DES：对称算法，数据加密标准，速度较快，适用于加密大量数据的场合；
MD5的典型应用是对一段Message产生fingerprint(指纹)，以防止被“篡改”。
RSA是第一个既能用于数据加密也能用于数字签名的算法。

7. https?

HTTP下加入SSL层，HTTPS的安全基础是SSL。

8.有一个IP库，给你一个IP,如何能够快速的从中查找到对应的IP段？不用数据库如何实现？要求省空间
9.简述一致性hash算法。

1）首先求memcached服务器（节点）的哈希值，并将其配置到0 232的圆（continuum）。

2）然后采用同样的方法求出存储数据的键的哈希值，并映射到相同的圆上。

3）然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上。如果超过232仍然找不到服务器，就会保存到第一台memcached服务器上。
11.描述一种hash table的实现方法

1） 除法散列法: p ，令 h(k ) = k mod p ，这里， p 如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。最直观的一种，上图使用的就是这种散列法，公式： index = value % 16，求模数其实是通过一个除法运算得到的。

2） 平方散列法 :求index频繁的操作，而乘法的运算要比除法来得省时。公式： index = (value * value) >> 28 （右移，除以2^28。记法：左移变大，是乘。右移变小，是除）

3） 数字选择法:如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。

4） 斐波那契（Fibonacci）散列法:平方散列法的缺点是显而易见的，通过找到一个理想的乘数index = (value * 2654435769) >> 28

冲突处理：令数组元素个数为 S ，则当 h(k) 已经存储了元素的时候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。

12、各类树结构的实现和应用

13、hash，任何一个技术面试官必问（例如为什么一般hashtable的桶数会取一个素数？如何有效避免hash结果值的碰撞）

不选素数的话可能会造成hash出值的范围和原定义的不一致

14.什么是平衡二叉树?

左右子树都是平衡二叉树，而且左右子树的深度差值的约对值不大于1。

15．数组和链表的优缺点

数组，在内存上给出了连续的空间。链表，内存地址上可以是不连续的，每个链表的节点包括原来的内存和下一个节点的信息(单向的一个，双向链表的话，会有两个)。

数组优于链表的:

A. 内存空间占用的少。

B. 数组内的数据可随机访问，但链表不具备随机访问性。

C. 查找速度快

链表优于数组的:

A. 插入与删除的操作方便。

B. 内存地址的利用率方面链表好。

C. 方便内存地址扩展。

17.最小堆插入，删除编程实现

18. 4G的long型整数中找到一个最大的，如何做？

每次从磁盘上尽量多读一些数到内存区，然后处理完之后再读入一批。减少IO次数，自然能够提高效率。分批读入选取最大数，再对缓存的最大数进行快排。

19. 有千万个string在内存怎么高速查找，插入和删除？

对千万个string做hash，可以实现高速查找，找到了，插入和删除就很方便了。关键是如何做hash，对string做hash，要减少碰撞频率。

在内存中维护一个大小为10000的最小堆，每次从文件读一个数，与最小堆的堆顶元素比较，若比堆顶元素大，则替换掉堆顶元素，然后调整堆。最后剩下的堆内元素即为最大的1万个数，算法复杂度为O(NlogN)

（1）全局洗牌法

a）首先生成一个数组，大小为54，初始化为1~54

b）按照索引1到54，逐步对每一张索引牌进行洗牌，首先生成一个余数 value = rand %54，那么我们的索引牌就和这个余数牌进行交换处理

c）等多索引到54结束后，一副牌就洗好了

（2）局部洗牌法：索引牌从1开始，到54结束。这一次索引牌只和剩下还没有洗的牌进行交换， value = index + rand（） %（54 - index）

算法复杂度是O(n)

22．请分别用递归和非递归方法，先序遍历二叉树

24.其他各种排序方法

25.哈希表冲突解决方法？

常见的hash算法如下：

解决冲突的方法：

也叫散列法，主要思想是当出现冲突的时候，以关键字的结果值作为key值输入，再进行处理，依次直到冲突解决

线性地址再散列法

当冲突发生时，找到一个空的单元或者全表

二次探测再散列

冲突发生时，在表的左右两侧做跳跃式的探测

伪随机探测再散列

同时构造不同的哈希函数

将同样的哈希地址构造成一个同义词的链表

建立一个基本表和溢出区，凡是和基本元素发生冲突都填入溢出区

六、系统架构

1.设计一个服务，提供递增的SessionID服务，要求保证服务的高可靠性，有哪些方案？集中式/非集中式/分布式

2.多台服务器要执行计划任务，但只有拿到锁的任务才能执行，有一个中心服务器来负责分配锁，但要保证服务的高可靠性。

3.如何有效的判断服务器是否存活？服务器是否踢出集群的决策如何产生？

4.两个服务器如何在同一时刻获取同一数据的时候保证只有一个服务器能访问到数据？

可以采用队列进行处理，写一个队列接口保证同一时间只有一个进程能够访问到数据，或者对于存取数据库的来说，数据库也是可以加锁处理的

5. 编写高效服务器程序，需要考虑的因素

性能对服务器程序来说是至关重要的了，毕竟每个客户都期望自己的请求能够快速的得到响应并处理。那么影响服务器性能的首要因素应该是：

（1）系统的硬件资源，比如说CPU个数，速度，内存大小等。不过由于硬件技术的飞速发展，现代服务器都不缺乏硬件资源。因此，需要考虑的主要问题是如何从“软环境”来提升服务器的性能。

服务器的”软环境“

（2）一方面是指系统的软件资源，比如操作系统允许用户打开的最大文件描述符数量

（3）另一方面指的就是服务器程序本身，即如何从编程的角度来确保服务器的性能。

主要就要考虑大量并发的处理这涉及到使用进程池或线程池实现高效的并发模式（半同步/半异步和领导者/追随者模式），以及高效的逻辑处理方式--有限状态机内存的规划使用比如使用内存池，以空间换时间，被事先创建好，避免动态分配，减少了服务器对内核的访问频率，数据的复制，服务器程序还应该避免不必要的数据复制，尤其是当数据复制发生在用户空间和内核空间之间时。如果内核可以直接处理从socket或者文件读入的数据，则应用程序就没必要将这些数据从内核缓冲区拷贝到应用程序缓冲区中。这里所谓的“直接处理”，是指应用程序不关心这些数据的具体内容是什么，不需要对它们作任何分析。比如说ftp服务器，当客户请求一个文件时，服务器只需要检测目标文件是否存在，以及是否有权限读取就可以了，不需要知道这个文件的具体内容，这样的话ftp服务器就不需要把目标文件读入应用程序缓冲区然后调用send函数来发送，而是直接使用“零拷贝”函数sendfile直接将其发送给客户端。另外，用户代码空间的数据赋值也应该尽可能的避免复制。当两个工作进程之间需要传递大量的数据时，我们就应该考虑使用共享内存来在他们直接直接共享这些数据，而不是使用管道或者消息队列来传递。上下文切换和锁：并发程序必须考虑上下文的切换问题，即进程切换或线程切换所导致的系统开销。即时I/O密集型服务器也不应该使用过多的工作线程（或工作进程），否则进程间切换将占用大量的CPU时间，服务器真正处理业务逻辑的CPU时间比重就下降了。因此为每个客户连接都创建一个工作线程是不可取的。应该使用某种高效的并发模式。（半同步半异步或者说领导者追随者模式）另一个问题就是共享资源的加锁保护。锁通常被认为是导致服务器效率低下的一个因素，因为由他引入的代码不仅不处理业务逻辑，而且需要访问内核资源，因此如果服务器有更好的解决方案，应该尽量避免使用锁。或者说服务器一定非要使用锁的话，尽量使用细粒度的锁，比如读写锁，当工作线程都只读一块内存区域时，读写锁不会增加系统开销，而只有当需要写时才真正需要锁住这块内存区域。对于高峰和低峰的伸缩处理，适度的缓存。

6. QQ飞车新用户注册时，如何判断新注册名字是否已存在？（数量级：几亿)

可以试下先将用户名通过编码方式转换，如转换64位整型。然后设置N个区间，每个区间为2^64/N的大小。对于新的用户名，先通过2分寻找该用户名属于哪个区间，然后在在这个区间，做一个hash。对于不同的时间复杂度和内存要求可以设置不同N的大小~

加一些基础的技术面试之外的职业素养的面试问题

1.你在工作中犯了个错误，有同事打你小报告，你如何处理？

a.同事之间应该培养和形成良好的同事关系，就是要互相支持而不是互相拆台，互相学习，互相帮助，共同进步。

b.如果小报告里边的事情都是事实也就是说确实是本人做的不好不对的方面，那么自己应该有则改之，提高自己。如果小报告里边的事

情全部不是事实，就是说确实诬陷，那么应该首先坚持日久见人心的态度，持之以恒的把本职工作做好，然后在必要的时候通过适当的

方式和领导沟通，相信领导会知道的。

2.你和同事合作完成一个任务，结果任务错过了截止日期，你如何处理？

3.职业规划？

4.离职原因？

5. 项目中遇到的难题，你是如何解决的?

A．时间 b要求 c.方法

2. 算法简述：一致性hash环，与redis 槽道原理

1.哈希算法 对服务器个数进行模余存储，

（下图）

传统新增节点 （下图）

2、哈希环，应用于数据的分布式存储，在增删节点之间，能够尽可能少的迁移数据，保证多数数据的一致性。（下图）每个节点代表一个数据存储服务器。服务器在通过哈希算法过后，得到一个固定长度数值a, 由a/65535 模余 得0~65535之间正整数，散列分布在hash环上（下图）

蓝色代表数据，绿色代表数据存储库，每个数据存储库 管理顺时针 ，上个节点之间的区域。（下图）图中数字 因该是对65536取余数

在新增节点4  后，只有数据a需要迁移（下图）

3，槽道原理，综上所述 ，哈希环减少了 数据在存储节点增删 过程中对数据产生的影响。redis 提出的hash槽道，则让数据迁移变得更为灵活

3. php的memcached分布式hash算法,如何解决分布不均crc32这个算法没办法把key值均匀的分布出去

memcached的总结和分布式一致性hash
当前很多大型的web系统为了减轻数据库服务器负载，会采用memchached作为缓存系统以提高响应速度。
目录： （http://hounwang.com/lesson.html）
memchached简介
hash
取模
一致性hash
虚拟节点
源码解析
参考资料
1. memchached简介
memcached是一个开源的高性能分布式内存对象缓存系统。
其实思想还是比较简单的，实现包括server端（memcached开源项目一般只单指server端）和client端两部分:
server端本质是一个in-memory key-value store，通过在内存中维护一个大的hashmap用来存储小块的任意数据，对外通过统一的简单接口（memcached protocol）来提供操作。
client端是一个library，负责处理memcached protocol的网络通信细节，与memcached server通信，针对各种语言的不同实现分装了易用的API实现了与不同语言平台的集成。
web系统则通过client库来使用memcached进行对象缓存。
2. hash
memcached的分布式主要体现在client端，对于server端，仅仅是部署多个memcached server组成集群，每个server独自维护自己的数据（互相之间没有任何通信），通过daemon监听端口等待client端的请求。
而在client端，通过一致的hash算法，将要存储的数据分布到某个特定的server上进行存储，后续读取查询使用同样的hash算法即可定位。
client端可以采用各种hash算法来定位server：
取模
最简单的hash算法
targetServer = serverList[hash(key) % serverList.size]
直接用key的hash值（计算key的hash值的方法可以自由选择，比如算法CRC32、MD5,甚至本地hash系统，如java的hashcode）模上server总数来定位目标server。这种算法不仅简单，而且具有不错的随机分布特性。
但是问题也很明显，server总数不能轻易变化。因为如果增加/减少memcached server的数量，对原先存储的所有key的后续查询都将定位到别的server上，导致所有的cache都不能被命中而失效。
一致性hash
为了解决这个问题，需要采用一致性hash算法（consistent hash）
相对于取模的算法，一致性hash算法除了计算key的hash值外，还会计算每个server对应的hash值，然后将这些hash值映射到一个有限的值域上（比如0~2^32）。通过寻找hash值大于hash(key)的最小server作为存储该key数据的目标server。如果找不到，则直接把具有最小hash值的server作为目标server。
为了方便理解，可以把这个有限值域理解成一个环，值顺时针递增。
如上图所示，集群中一共有5个memcached server，已通过server的hash值分布到环中。
如果现在有一个写入cache的请求，首先计算x=hash(key)，映射到环中，然后从x顺时针查找，把找到的第一个server作为目标server来存储cache，如果超过了2^32仍然找不到，则命中第一个server。比如x的值介于A~B之间，那么命中的server节点应该是B节点
可以看到，通过这种算法，对于同一个key，存储和后续的查询都会定位到同一个memcached server上。
那么它是怎么解决增/删server导致的cache不能命中的问题呢？
假设，现在增加一个server F，如下图
此时，cache不能命中的问题仍然存在，但是只存在于B~F之间的位置（由C变成了F），其他位置（包括F~C）的cache的命中不受影响（删除server的情况类似）。尽管仍然有cache不能命中的存在，但是相对于取模的方式已经大幅减少了不能命中的cache数量。
虚拟节点
但是，这种算法相对于取模方式也有一个缺陷：当server数量很少时，很可能他们在环中的分布不是特别均匀，进而导致cache不能均匀分布到所有的server上。
如图，一共有3台server – 1，2，4。命中4的几率远远高于1和2。
为解决这个问题，需要使用虚拟节点的思想：为每个物理节点（server）在环上分配100～200个点，这样环上的节点较多，就能抑制分布不均匀。
当为cache定位目标server时，如果定位到虚拟节点上，就表示cache真正的存储位置是在该虚拟节点代表的实际物理server上。
另外，如果每个实际server的负载能力不同，可以赋予不同的权重，根据权重分配不同数量的虚拟节点。
// 采用有序map来模拟环
this.consistentBuckets = new TreeMap();
MessageDigest md5 = MD5.get();//用MD5来计算key和server的hash值
// 计算总权重
if ( this.totalWeight for ( int i = 0; i < this.weights.length; i++ )
this.totalWeight += ( this.weights[i] == null ) ? 1 : this.weights[i];
} else if ( this.weights == null ) {
this.totalWeight = this.servers.length;
}
// 为每个server分配虚拟节点
for ( int i = 0; i < servers.length; i++ ) {
// 计算当前server的权重
int thisWeight = 1;
if ( this.weights != null && this.weights[i] != null )
thisWeight = this.weights[i];
// factor用来控制每个server分配的虚拟节点数量
// 权重都相同时，factor=40
// 权重不同时，factor=40*server总数*该server权重所占的百分比
// 总的来说，权重越大，factor越大，可以分配越多的虚拟节点
double factor = Math.floor( ((double)(40 * this.servers.length * thisWeight)) / (double)this.totalWeight );
for ( long j = 0; j < factor; j++ ) {
// 每个server有factor个hash值
// 使用server的域名或IP加上编号来计算hash值
// 比如server - "172.45.155.25:11111"就有factor个数据用来生成hash值：
// 172.45.155.25:11111-1, 172.45.155.25:11111-2, ..., 172.45.155.25:11111-factor
byte[] d = md5.digest( ( servers[i] + "-" + j ).getBytes() );
// 每个hash值生成4个虚拟节点
for ( int h = 0 ; h < 4; h++ ) {
Long k =
((long)(d[3+h*4]&0xFF) << 24)
| ((long)(d[2+h*4]&0xFF) << 16)
| ((long)(d[1+h*4]&0xFF) << 8 )
| ((long)(d[0+h*4]&0xFF));
// 在环上保存节点
consistentBuckets.put( k, servers[i] );
}
}
// 每个server一共分配4*factor个虚拟节点
}
// 采用有序map来模拟环
this.consistentBuckets = new TreeMap();
MessageDigest md5 = MD5.get();//用MD5来计算key和server的hash值
// 计算总权重
if ( this.totalWeight for ( int i = 0; i < this.weights.length; i++ )
this.totalWeight += ( this.weights[i] == null ) ? 1 : this.weights[i];
} else if ( this.weights == null ) {
this.totalWeight = this.servers.length;
}
// 为每个server分配虚拟节点
for ( int i = 0; i < servers.length; i++ ) {
// 计算当前server的权重
int thisWeight = 1;
if ( this.weights != null && this.weights[i] != null )
thisWeight = this.weights[i];
// factor用来控制每个server分配的虚拟节点数量
// 权重都相同时，factor=40
// 权重不同时，factor=40*server总数*该server权重所占的百分比
// 总的来说，权重越大，factor越大，可以分配越多的虚拟节点
double factor = Math.floor( ((double)(40 * this.servers.length * thisWeight)) / (double)this.totalWeight );
for ( long j = 0; j < factor; j++ ) {
// 每个server有factor个hash值
// 使用server的域名或IP加上编号来计算hash值
// 比如server - "172.45.155.25:11111"就有factor个数据用来生成hash值：
// 172.45.155.25:11111-1, 172.45.155.25:11111-2, ..., 172.45.155.25:11111-factor
byte[] d = md5.digest( ( servers[i] + "-" + j ).getBytes() );
// 每个hash值生成4个虚拟节点
for ( int h = 0 ; h < 4; h++ ) {
Long k =
((long)(d[3+h*4]&0xFF) << 24)
| ((long)(d[2+h*4]&0xFF) << 16)
| ((long)(d[1+h*4]&0xFF) << 8 )
| ((long)(d[0+h*4]&0xFF));
// 在环上保存节点
consistentBuckets.put( k, servers[i] );
}
}
// 每个server一共分配4*factor个虚拟节点
}
// 用MD5来计算key的hash值
MessageDigest md5 = MD5.get();
md5.reset();
md5.update( key.getBytes() );
byte[] bKey = md5.digest();

// 取MD5值的低32位作为key的hash值
long hv = ((long)(bKey[3]&0xFF) << 24) | ((long)(bKey[2]&0xFF) << 16) | ((long)(bKey[1]&0xFF) << 8 ) | (long)(bKey[0]&0xFF);

// hv的tailMap的第一个虚拟节点对应的即是目标server
SortedMap tmap = this.consistentBuckets.tailMap( hv );
return ( tmap.isEmpty() ) ? this.consistentBuckets.firstKey() : tmap.firstKey();
更多问题到问题求助专区（http://bbs.hounwang.com/）

4. 一致性哈希算法怎么保证数据的一致性

环割法（一致性 hash）环割法的原理如下：

1. 初始化的时候生成分片数量 X × 环割数量 N 的固定方式编号的字符串，例如 SHARD-1-NODE-1，并计算所有 X×N 个字符串的所有 hash 值。

2. 将所有计算出来的 hash 值放到一个排序的 Map 中，并将其中的所有元素进行排序。

3. 输入字符串的时候计算输入字符串的 hash 值，查看 hash 值介于哪两个元素之间，取小于 hash 值的那个元素对应的分片为数据的分片。

数据比较

下面将通过测试对环割法和跳跃法的性能及均衡性进行对比，说明 DBLE 为何使用跳跃法代替了环割法。

• 数据源：现场数据 350595 条

• 测试经过：

  1. 通过各自的测试方法执行对于测试数据的分片任务。

  2. 测试方法：记录分片结果的方差；记录从开始分片至分片结束的时间；记录分片结果与平均数的最大差值。

  3. 由于在求模法 PartitionByString 的方法中要求分片的数量是 1024 的因数，所以测试过程只能使用 2 的指数形式进行测试，并在 PartitionByString 方法进行测试的时候不对于 MAC 地址进行截断，取全量长度进行测试。

5. 一致性hash算法是什么

一致性哈希算法是在1997年由麻省理工学院提出的一种分布式哈希（DHT）算法。其设计目标是为了解决因特网中的热点（Hot spot)问题，初衷和CARP十分类似。

一致性Hash是一种特殊的Hash算法，由于其均衡性、持久性的映射特点，被广泛的应用于负载均衡领域，如nginx和memcached都采用了一致性Hash来作为集群负载均衡的方案。

一致性哈希算法的目标是，当K个请求key发起请求时。后台增减节点，只会引起K/N的key发生重新映射。即一致性哈希算法，在后台节点稳定时，同一key的每次请求映射到的节点是一样的。而当后台节点增减时，该算法尽量将K个key映射到与之前相同的节点上。

构成哈希算法的条件：

从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）。

对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同。

散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小。

哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。

6. 哈希表、哈希算法、一致性哈希表

    散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。它通过把关键码映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数（哈希函数），存放记录的数组叫做散列表。

  优点：

        哈希表可以提供快速的操作。

缺点：

        哈希表通常是基于数组的，数组创建后难于扩展。

        也没有一种简便的方法可以以任何一种顺序〔例如从小到大）遍历表中的数据项 。

    综上， 如果不需要有序遍历数据，井且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

        1. 使用哈希函数将被查找的键转换为数组的索引。

        2. 处理哈希碰撞冲突。

    若关键字为 k ，则其值存放在 f(k) 的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系 f 为散列函数，按这个思想建立的表为散列表。

    若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为 均匀散列函数 (Uniform Hash function)，这就是使关键字经过散列函数得到一个"随机的地址"，从而减少碰撞。

散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。

一个好的散列函数一般应该考虑下列因素 ：

    1.计算简单，以便提高转换速度。

    2.关键词对应的地址空间分布均匀，以尽量减少冲突。

1.   直接寻址法

    取关键字或者关键字的某个线性函数值作为哈希地址,即H(Key)=Key或者H(Key)=a*Key+b(a,b为整数),这种散列函数也叫做自身函数.如果H(Key)的哈希地址上已经有值了,那么就往下一个位置找,直到找到H(Key)的位置没有值了就把元素放进去。

2.   数字分析法

    数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。

3.   平方取中法

    取关键字平方后的中间几位作为散列地址。这种方法的原理是通过取平方扩大差别，平方值的中间几位和这个数的每一位都相关，则对不同的关键字得到的哈希函数值不易产生冲突，由此产生的哈希地址也较为均匀。该方法适用于关键字中的每一位都有某些数字重复出现频度很高的现象。

4.   折叠法

    折叠法是将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加和(注意:叠加和时去除进位)作为散列地址。

    数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐,然后相加;间界叠加是从一端向另一端沿分割界来回折叠,然后对齐相加。

    该方法适用于关键字特别多的情况。

5.   随机数法

    选择一个随机数,作为散列地址,通常用于关键字长度不同的场合。

6.   除留余数法

    取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址.即H(Key)=Key MOD p,p<=m.不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选得不好，则很容易产生冲突。

    对不同的关键字可能得到同一散列地址，即 k1≠k2 ，而 f(k1)=f(k2) ，这种现象称为碰撞(英语:Collision)。具有相同函数值的关键字对该散列函数来说称做同义词。

    通过构造性能良好的散列函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是哈希法的另一个关键问题。 创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应该一致。

下面以创建哈希表为例，说明解决冲突的方法。

1.开放寻址法

    这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H(key)出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：Hi=(H(key)+di)%m   i=1，2，…，m-1,其中H（key）为哈希函数，m 为表长，di称为增量序列，i为碰撞次数。增量序列的取值方式不同，相应的再散列方式也不同。增量序列主要有以下几种：

    (1) 线性探测再散列

        di=1，2，3，…，m-1

        这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。

    (2)二次探测再散列

        di=12，-12，22，-22，…，k2，-k2( k<=m/2 )

        这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。

    (3)伪随机探测再散列

        di=伪随机数序列。

    线性探测再散列的 优点 是：只要哈希表不满，就一定能找到一个不冲突的哈希地址，而二次探测再散列和伪随机探测再散列则不一定。线性探测再散列容易产生“二次聚集”，即在处理同义词的冲突时又导致非同义词的冲突。

    其实除了上面的几种方法，开放寻址法还有很多变种，不过都是对di有不同的表示方法。（如双散列探测法：di=i*h2(k)）

2.再哈希法

    这种方法是同时构造多个不同的哈希函数：Hi=RHi（key），i=1，2,3，…,n。

    当哈希地址H1=RH1（key）发生冲突时，再计算H2=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

 3.链地址法(拉链法)

    这种方法的基本思想是将所有哈希地址相同的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表（数组）中，因而查找、插入和删除主要在同义词链中进行。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。链地址法适用于经常进行插入和删除的情况。

     拉链法的优点

        与开放寻址法相比，拉链法有如下几个优点：

            (1)拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；

            (2)由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；

            (3)开放寻址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中理论上可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；（散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度）

注：HashMap默认装填因子是0.75。

            (4)在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放寻址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填入散列表的同义词结点的查找路径。这是因为各种开放寻址法中，空地址单元都被理解没有查找到元素。 因此在用开放寻址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

     拉链法的缺点

        拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放寻址法较为节省空间，此时将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放寻址法中的冲突，从而提高平均查找速度。

4、建立公共溢出区

    这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表(在这个方法里面是把元素分开两个表来存储)。

    散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。

    查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。

影响产生冲突多少有以下三个因素:

    1. 散列函数是否均匀;

    2. 处理冲突的方法;

    3. 散列表的装填因子。

     散列表的装填因子

        定义为:α= 填入表中的元素个数 / 散列表的长度

        α是散列表装满程度的标志因子。由于表长是定值，α与"填入表中的元素个数"成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大;α越小，填入表中的元素较少，产生冲突的可能性就越小。

        实际上，散列表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。

    这个HASH算法不是大学里数据结构课里那个HASH表的算法。这里的HASH算法是密码学的基础，了解了hash基本定义，就不能不提到一些着名的hash算法，MD5 和 SHA-1 可以说是目前应用最广泛的Hash算法，而它们都是以 MD4 为基础设计的。

Hash算法在信息安全方面的应用主要体现在以下的3个方面:

     ⑴  文件校验

        我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗 数据篡改 的能力，它们一定程度上能检测出数据传输中的信道误码，但却不能防止对数据的恶意破坏。

        MD5 Hash算法的"数字指纹"特性，使它成为目前应用最广泛的一种文件完整性 校验和 (Checksum)算法，不少Unix系统有提供计算md5 checksum的命令。

     ⑵  数字签名

        Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在 数字签名 协议中，单向散列函数扮演了一个重要的角色。对 Hash 值，又称"数字摘要"进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。

     ⑶ 鉴权协议

        如下的鉴权协议又被称作挑战--认证模式:在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。

    一致性哈希表简称DHT，主要应用于分布式缓存中，可以用来解决分布式存储结构下动态增加和删除节点所带来的问题。比如，一个分布式的存储系统，要将数据存储到具体的节点上，如果采用普通的hash方法，将数据映射到具体的节点上，如key%N（key是数据的key，N是机器节点数），如果有一个机器加入或退出这个集群，则所有的数据映射都无效了，如果是持久化存储则要做数据迁移，如果是分布式缓存，则其他缓存就失效了。

判定哈希算法好坏的四个定义 ：

    1、平衡性(Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。

    2、单调性(Monotonicity)：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。

    3、分散性(Spread)：在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。 分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。

    4、负载(Load)：负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的， 因此好的哈希算法应能够尽量降低缓冲的负荷。

    在分布式集群中，对机器的添加删除，或者机器故障后自动脱离集群这些操作是分布式集群管理最基本的功能。如果采用常用的hash取模算法，那么在有机器添加或者删除后，很多原有的数据就无法找到了，这样严重的违反了单调性原则。接下来主要说明一下一致性哈希算法是如何设计的。

以SpyMemcached的ketama算法来说，思路是这样的：

把数据用hash函数，映射到一个很大的空间里，如图所示。数据的存储时，先得到一个hash值，对应到这个环中的每个位置，如k1对应到了图中所示的位置，然后沿顺时针找到一个机器节点B，将k1存储到B这个节点中。

如果B节点宕机了，则B上的数据就会落到C节点上，如下图所示：

这样，只会影响C节点，对其他的节点A，D的数据不会造成影响。然而，这又会造成一个“雪崩”的情况，即C节点由于承担了B节点的数据，所以C节点的负载会变高，C节点很容易也宕机，这样依次下去，这样造成整个集群都挂了。

为此，引入了“虚拟节点”的概念：即把想象在这个环上有很多“虚拟节点”，数据的存储是沿着环的顺时针方向找一个虚拟节点，每个虚拟节点都会关联到一个真实节点，如下图所使用：

图中的A1、A2、B1、B2、C1、C2、D1、D2都是虚拟节点，机器A负载存储A1、A2的数据，机器B负载存储B1、B2的数据，机器C负载存储C1、C2的数据。由于这些虚拟节点数量很多，均匀分布，因此不会造成“雪崩”现象。