hash算法分表

Ⅰ 大数据量最近的存储分表常见算法

大数据量最近的存储分表常见算法
当一个应用的数据量大的时候，我们用单表和单库来存储会严重影响操作速度，如mysql的myisam存储，我们经过测试，200w以下的时候，mysql的访问速度都很快，但是如果超过200w以上的数据，他的访问速度会急剧下降，影响到我们webapp的访问速度，而且数据量太大的话，如果用单表存储，就会使得系统相当的不稳定，mysql服务很容易挂掉。所以当数据量超过200w的时候，建议系统工程师还是考虑分表.
以下是几种常见的分表算法。
1.按自然时间来分表/分库;
如一个应用的数据在一年后数据量会达到200w左右，那么我们就可以考虑用一年的数据来做为一个表或者库来存储，例如，表名为app，那么2010年的数据就是app_2010，app_2011;如果数据量在一个月就达到了200w左右，那么我们就可以用月份来分，app_2010_01，app_2010_02.
2.按数字类型hash分表/分库;
如果我们要存储用户的信息，我们应用的注册量很大，我们用单表是不能满足存储需求的，那么我们就可以用用户的编号来进行hash，常见的是用取余操作，如果我们要分30张表来存储用户的信息，那么用户编号为1的用户1%30=1，那么我们就存在user_01表里，如用户的编号为500，那么500%30=20，那么我们就将此用户的信息存储在user_20的表里.
3.按md5值来分表/分库;
我们假设要存储用户上传的文件，如果上传量大的话，也会带来系统的瓶颈问题，我们做过试验，在一个文件夹下如果超过200个文件的话，文件的浏览效率会降低，当然，这个不属于我们本文讨论的范围，这块也要做散列操作.我们可以用文件的用户名来md5或者用文件的md5校验值来做，我们就可以用md5的前5位来做hash，这样最多我们就可以得到5^5=3125个表，每次在存储文件的时候，就可以用文件名的md5值的前5位来确定这个文件该存那张表.
4.实例:某微博的url加密算法和存储策略的猜想.
现在好多微博都用这样的url来访问，如果他们的域名为www.example.com，那么如果你发微博的时候，你会发现你所发的url都变成了http://t.cn/Mx4ja1，这样的形式，他们是怎么进行这样的转换呢?我猜想就是用到了我们上面讲的md5的存储和查找规则，用你发的url来进行md5，得到md5值之后，如我们例子来说，就会用前6位来进行分表.
5.分表所带来的问题.
分表也会带来一系列的问题，如分页的实现，统计的实现，如果我们要做一个所有数据的分页，那么我们得每张表都得遍历一遍，这样访问效率会很低下.之前我尝试过用mysql的代理来实现，最终用tcsql来实现了.
6.分表算法的选择.
首先，分表适合于没有大的列表的应用来使用，要不然，会为这部分做好多额外的工作，如果你的应用数据量不是特别大的话，最好别用分表。7.针对每秒插入数据500+的设想为什么要这个呢，因为很多数据库在数据上千万级别后，每秒插入数据的数度不是很快了，所以500/秒的速度够呛，解决方案设想：建立数据总表及两个缓冲表，结构完全相同，将数据先插入其中一个缓冲表中，等到一定时间(插入效率降低之前)，转向插入另一个缓冲表，同时启动一个后台进程将第
一个缓冲表的的数据转入总表，转入总表后删除第一个缓冲表中的数据; 再等到一定时间(还是插入效率降低之前)，转向插入第一个缓冲表，这时启动一个后台进程将第
二个缓冲表的的数据转入总表，转入总表后删除第二个缓冲表中的数据; 如此循环往复...

如果后台进程处理的时间超过两个缓冲表的循环周期的话，甚至可以考虑建立三个乃至四个缓冲表。

这仅仅是解决插入效率，查询什么的问题也大。

Ⅱ 哈希值计算方法耗电量

摘要 哈希算法（Hash 算法，Hash 算式，散列算法，消息摘要算法）将任意长度的二进制值映射为较短的固定长度的二进制值，这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母，随后的哈希都将产生不同的值。

Ⅲ mysql水平分表的几种方法

1.按时间分表

这种分表方式有一定的局限性，当数据有较强的实效性，如微博发送记录、微信消息记录等，这种数据很少有用户会查询几个月前的数据，如就可以按月分表。

2.按区间范围分表

一般在有严格的自增id需求上，如按照user_id水平分表：
table_1 user_id从1~100w
table_2 user_id从101~200w
table_3 user_id从201~300w
...

3.hash分表

通过一个原始目标的ID或者名称通过一定的hash算法计算出数据存储表的表名，然后访问相应的表。
按如下分10张表：

• functionget_hash_table($table,$userid)

• {

• $str=crc32($userid);

• if($str<0){

• $hash="0".substr(abs($str),0,1);

• }else{

• $hash=substr($str,0,2);

• }

• return$table."_".$hash;

• }

• echo get_hash_table('message','user18991');//结果为message_10

• echo get_hash_table('message','user34523');//结果为message_13

Ⅳ 什么是哈希算法

就是空间映射函数，例如，全体的长整数的取值作为一个取值空间，映射到全部的字节整数的取值的空间，这个映射函数就是HASH函数。通常这种映射函数是从一个非常大的取值空间映射到一个非常小的取值空间，由于不是一对一的映射，HASH函数转换后不可逆，即不可能通过逆操作和HASH值还原出原始的值，受到计算能力限制（注意，不是逻辑上不可能，前面的不可能是逻辑上的）而且也无法还原出所有可能的全部原始值。HASH函数运用在字典表等需要快速查找的数据结构中，他的计算复杂度几乎是O(1)，不会随着数据量增加而增加。另外一种用途就是文件签名，文件内容很多，将文件内容通过HASH函数处理后得到一个HASH值，验证这个文件是否被修改过，只需要把文件内容用同样的HASH函数处理后得到HASH值再比对和文件一起传送的HASH值即可，如不公开HASH算法，那么信道是无法篡改文件内容的时候篡改文件HASH值，一般应用的时候，HASH算法是公开的，这时候会用一个非对称加密算法加密一下这个HASH值，这样即便能够计算HASH值，但没有加密密钥依然无法篡改加密后HASH值。这种算法用途很广泛，用在电子签名中。HASH算法也可进行破解，这种破解不是传统意义上的解密，而是按照已有的HASH值构造出能够计算出相同HASH值的其他原文，从而妨碍原文的不可篡改性的验证，俗称找碰撞。这种碰撞对现有的电子签名危害并不严重，主要是要能够构造出有意义的原文才有价值，否则就是构造了一个完全不可识别的原文罢了，接收系统要么无法处理报错，要么人工处理的时候发现完全不可读。理论上我们终于找到了在可计算时间内发现碰撞的算法，推算了HASH算法的逆操作的时间复杂度大概的范围。HASH算法的另外一个很广泛的用途，就是很多程序员都会使用的在数据库中保存用户密码的算法，通常不会直接保存用户密码（这样DBA就能看到用户密码啦，好危险啊），而是保存密码的HASH值，验证的时候，用相同的HASH函数计算用户输入的密码得到计算HASH值然后比对数据库中存储的HASH值是否一致，从而完成验证。由于用户的密码的一样的可能性是很高的，防止DBA猜测用户密码，我们还会用一种俗称“撒盐”的过程，就是计算密码的HASH值之前，把密码和另外一个会比较发散的数据拼接，通常我们会用用户创建时间的毫秒部分。这样计算的HASH值不大会都是一样的，会很发散。最后，作为一个老程序员，我会把用户的HASH值保存好，然后把我自己密码的HASH值保存到数据库里面，然后用我自己的密码和其他用户的用户名去登录，然后再改回来解决我看不到用户密码而又要“偷窥”用户的需要。最大的好处是，数据库泄露后，得到用户数据库的黑客看着一大堆HASH值会翻白眼。

Ⅳ 大家mysql 分表的哈希算法是怎样的

当一张的数据达到几百万时，你查询一次所花的时间会变多，如果有联合查询的话，我想有可能会死在那儿了。分表的目的就在于此，减小数据库的负担，缩短查询时间。
根据个人经验，mysql执行一个sql的过程如下：
1,接收到sql;2,把sql放到排队队列中 ;3,执行sql;4,返回执行结果。在这个执行过程中最花时间在什么地方呢？第一，是排队等待的时间，第二，sql的执行时间。其实这二个是一回事，等待的同时，肯定有sql在执行。所以我们要缩短sql的执行时间。

Ⅵ Hash表及其应用

散列表，也叫做哈希表。

它基于数组的随机访问的特性，来拓展延伸，从而实现了散列表，为什么这样说呢，我们举一个例子来看看。

假设学校举行运动会，对100个进行编号，我们现在希望实现通过编号来快速找到某一个学生，该怎么实现呢，我们可以维护一个数组，将每一个学生的编号放到同样的数组下标内，比如1号放到数组下标为1的位置，接下来额以此类推，这样就能够实现快速随机访问，在O(1)的时间复杂度内就找到这个学生。

也许这样你看不出用到了散列思想，但这确实就是使用了散列的思想，将数组下标和学生编号进行了映射，只不过映射规则非常简单，就是f(n) = n。

但是现实时不会这么简单的，现在要求编号要复杂一点，用 6 位数字来表示。比如 051167，其中，前两位 05 表示年级，中间两位 11 表示班级，最后两位还是原来的编号 1 到 89。这个时候我们该如何存储选手信息，才能够支持通过编号来快速查找选手信息呢？

依然时通过散列的思想，我们可以截取编号的后两位作为数组下标，存储选手信息，当我们要查询时，也截取后两位作为数组下标，到数组内去查询，这样就能够实现快速查询。

其中，参赛选手的编号我们叫作键（key）或者关键字。我们用它来标识一个选手。我们把参赛编号转化为数组下标的映射方法就叫作散列函数（或“Hash 函数”“哈希函数”），而散列函数计算得到的值就叫作散列值（或“Hash 值”“哈希值”）。拿上面那个来说，关键字是051167，我们通过hash函数，即截取后两位，计算得到hash值67。

可以看到的是，hash函数是一个非常重要的东西，如何构造一个好的hash函数也是非常重要的，通过学习，我目前知道的是3点：

1：hash值是一个非负整数

2：如果key1==key2 hash(key1) == hash(key2)

3：如果key1!=key2 hash(key1) != hash(key2)

第一点很好理解，因为我们要维护成数组的下标，那么负数和非整数都是不行的；第二点也好理解，如果两个key相同，那么经过同一个hash函数计算，他们得到的值也必须要一样。第三点要好好理解一下，不同的key得到的hash值不一样，也就是这一点，引出了hash冲突这样一个概念。

因为即使最好的hash算法，也无法保证两个不一样的key得到的hash值一定不一样。

计既然无法解决，那么就要找其他的方法了。

经典的方法有链表法和开放寻址法。

开放寻址法：

这个比较好理解，就是如果计算得到的hash值在数组内已经有数据了，那我们就在紧接下一个寻找，如果没有数据，就插入到这个位置，这种方法不是非常好。

为了保证散列表的性能，我们会维护一个 装载因子 的概念。

装载因子： 填入表中的元素个数 / 散列表的长度

装载因子越小，发生散列冲突的概率就越小，性能就越好，如果装载因子越大，那么性能就会迅速下降，不过装载因子越小，那么需要消耗的内存就越大，如果不考虑性能，装载因子可以超越1.

链表法：

链表法比较常用

介绍了散列表的基本概念和一些散列冲突的解决方法，拿我们来看看究竟怎么样，才能设计一个优秀的企业级的散列表呢？

设计散列表，最关键的就是散列函数的设计，一个好的散列函数，既能够快速计算，也能够让散列冲突的概率较为小。既然要计算快速，那么这个散列函数就必然不能够太复杂，不然计算时间就较为耗时，其次也要保证计算出来的hash值要平均分布，否则一个槽出现的概率非常大，那么散列冲突的概率就大大提升。

我们之前说过，hash函数是有一个装载因子的概念的，对于动态的散列表，我们不断进行插入操作，它的装载因子势必会扩大，当装载因子过大时，hash表的性能就会下降，这个时候，就需要对hash表进行扩容，这样装载因子就会下降，对于数组的扩容，我们都可以很好的实现，不过对于散列表的扩容，就不是简单的移动数据这么简单了。

可以看到，当我们新建了一个数组后，原来hash表中的内容就要重新计算hash值，然后存放到新的哈市、表中，并不是简单的移动就能解决的。

不过，这样扩容，如果数据量很大，那么效率就必然很低下，怎么解决呢，我们可以不立刻拷贝数据到新的hash表里面，可以每新插入一个数据就将老的表里面的数据拿一个到新的表里面，这样就可以不一次性拷贝数据，效率就会得到提升。

接下啦看如何选择合适的hash冲突解决法：

当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 Java 中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。

基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。

    this.hash = var1;

  }

  return var1;

}

Ⅶ PHP mysql 实现hash分区的问题

当分片索引不是纯整型的字符串时，只接受整型的内置 hash 算法是无法使用的。为此，stringhash 按照用户定义的起点和终点去截取分片索引字段中的部分字符，根据当中每个字符的二进制 unicode 值换算出一个长整型数值，然后就直接调用内置 hash 算法求解分片路由：先求模得到逻辑分片号，再根据逻辑分片号直接映射到物理分片。

• 用户需要在 rule.xml 中定义 partitionLength[] 和 partitionCount[] 两个数组和 hashSlice 二元组。

• 在 DBLE 的启动阶段，点乘两个数组得到模数，也是逻辑分片的数量

• 并且根据两个数组的叉乘，得到各个逻辑分片到物理分片的映射表（物理分片数量由 partitionCount[] 数组的元素值之和）

• 此外根据 hashSlice 二元组，约定把分片索引值中的第 4 字符到第 5 字符（字符串以 0 开始编号，编号 3 到编号 4 等于第 4 字符到第 5 字符）字符串用于 “字符串->整型”的转换

• 在 DBLE 的运行过程中，用户访问使用这个算法的表时，WHERE 子句中的分片索引值会被提取出来，取当中的第 4 个字符到第 5 字符，送入下一步

• 设置一个初始值为 0 的累计值，逐个取字符，把累计值乘以 31，再把这个字符的 unicode 值当成长整型加入到累计值中，如此类推直至处理完截取出来的所有字符，此时的累计值就能够代表用户的分片索引值，完成了 “字符串->整型” 的转换

• 对上一步的累计值进行求模，得到逻辑分片号

• 再根据逻辑分片号，查映射表，直接得到物理分片号

与MyCat的类似分片算法对比

两种算法在string转化为int之后，和 hash 分区算法相同，区别也继承了 hash 算法的区别。

开发注意点

【分片索引】1. 必须是字符串

【分片索引】2. 最大物理分片配置方法是，让 partitionCount[] 数组和等于 2880

例如：

• <property name="partitionLength">1</property><property name="partitionCount">2880</property>



或

• <property name="partitionLength">1,1</property><property name="partitionCount">1440,1440</property>



【分片索引】3. 最小物理分片配置方法是，让 partitionCount[] 数组和等于 1

例如

• <property name="partitionLength">2880</property><property name="partitionCount">1</property>



【分片索引】4. partitionLength 和 partitionCount 被当做两个逗号分隔的一维数组，它们之间的点乘必须在 [1, 2880] 范围内

【分片索引】5. partitionLength 和 partitionCount 的配置对顺序敏感

• <property name="partitionLength">512,256</property><property name="partitionCount">1,2</property>



和

• <property name="partitionLength">256,512</property><property name="partitionCount">2,1</property>



是不同的分片结果

【分片索引】6. 分片索引字段长度小于用户指定的截取长度时，截取长度会安全减少到符合分片索引字段长度

【数据分布】1. 分片索引字段截取越长则越有利于数据均匀分布

【数据分布】2. 分片索引字段的内容重复率越低则越有利于数据均匀分布

运维注意点

【扩容】1. 预先过量分片，并且不改变 partitionCount 和 partitionLength 点乘结果，也不改变截取设置 hashSlice 时，可以避免数据再平衡，只需进行涉及数据的迁移

【扩容】2. 若需要改变 partitionCount 和 partitionLength 点乘结果或改变截取设置 hashSlice 时，需要数据再平衡

【缩容】1. 预先过量分片，并且不改变 partitionCount 和 partitionLength 点乘结果，也不改变截取设置 hashSlice 时，可以避免数据再平衡，只需进行涉及数据的迁移

【缩容】2. 若需要改变 partitionCount 和 partitionLength 点乘结果或改变截取设置 hashSlice 时，需要数据再平衡

配置注意点

【配置项】1. 在 rule.xml 中，可配置项为<property name="partitionLength"> 、<property name="partitionCount"> 和 <property name="hashSlice">

【配置项】2.在 rule.xml 中配置 <property name="partitionLength">标签

内容形式为：<物理分片持有的虚拟分片数>[,<物理分片持有的虚拟分片数>,...<物理分片持有的虚拟分片数>]

物理分片持有的虚拟分片数必须是整型，物理分片持有的虚拟分片数从左到右与同顺序的物理分片数对应，partitionLength 和partitionCount 的点乘结果必须在 [1, 2880] 范围内

【配置项】3. 在 rule.xml 中配置 <property name="partitionCount">标签
内容形式为：<物理分片数>[,<物理分片数>,...<物理分片数>]

其中物理分片数必须是整型，物理分片数按从左到右的顺序与同顺序的物理分片持有的虚拟分片数对应，物理分片的编号从左到右连续递进，partitionLength 和 partitionCount 的点乘结果必须在 [1, 2880] 范围内

【配置项】4. partitionLength 和 partitionCount 的语义是：持有partitionLength[i] 个虚拟分片的物理分片有 partitionCount[i] 个

例如

• <property name="partitionLength">512,256</property><property name="partitionCount">1,2</property>



语义是持有 512 个逻辑分片的物理分片有 1 个，紧随其后，持有 256 个逻辑分片的物理分片有 2 个

【配置项】5.partitionLength 和 partitionCount 都对书写顺序敏感，

例如

• <property name="partitionLength">512,256</property><property name="partitionCount">1,2</property>



分片结果是第一个物理分片持有头512个逻辑分片，第二个物理分片持有紧接着的256个逻辑分片，第三个物理分片持有最后256个逻辑分片，相对的

• <property name="partitionLength">256,512</property><property name="partitionCount">2,1</property>



分片结果则是第一个物理分片持有头 256 个逻辑分片，第二个物理分片持有紧接着的 256 个逻辑分片，第三个物理分片持有最后 512 个逻辑分片

【配置项】6.partitionLength[] 的元素全部为 1 时，这时候partitionCount 数组和等于 partitionLength 和 partitionCount 的点乘，物理分片和逻辑分片就会一一对应，该分片算法等效于直接取余

【配置项】7.在 rule.xml 中配置标签，从分片索引字段的第几个字符开始截取到第几个字符：

• 若希望从首字符开始截取 k 个字符（ k 为正整数），配置的内容形式可以为“ 0 : k ”、“ k ”或“ : k ”；

• 若希望从末字符开始截取 k 个字符（ k 为正整数），则配置的内容形式可以为“ -k : 0 ”、“ -k ”或“ -k : ”；

• 若希望从头第 m 个字符起算截取 n 个字符（ m 和 n 都是正整数），则先计算出 i = m - 1 和 j = i + n - 1，配置的内容形式为“ i : j ”；

• 若希望从尾第 m 个字符起算截取从尾算起的 n 个字符（ m 和 n 都是正整数），则先计算出 i = -m + n - 1，配置的内容形式可以为“ -m : i ”；

• 若希望不截取，则配置的内容形式可以为“ 0 : 0 ”、“ 0 : ”、“ : 0 ”或 “ : ”