精华内容
下载资源
问答
  • 在学习PHP数组底层实现原理的时候,发现就是通过hash表的方法实现。其实好多查询搜索的底层都是利用hash实现最快O(1)时间复杂度。hash的概念课本上,网上有甚多。其中,hash函数实现方法是让我最觉得好奇的。 hash...

            在学习PHP数组底层实现原理的时候,发现就是通过hash表的方法实现。其实好多查询搜索的底层都是利用hash实现最快O(1)时间复杂度。hash的概念课本上,网上有甚多。其中,hash函数实现方法是让我最觉得好奇的。

            hash函数:直接寻址法,直接定址法是以数据元素关键字k本身或它的线性函数作为它的哈希地址,    实际生活中,关键字的元素很少是连续的。用该方法产生的哈希表会造成空间大量的浪费,因此这种方法适应性并不强

    数字分析法、数字分析法是取数据元素关键字中某些取值较均匀的数字位作为哈希地址的方法。即当关键字的位数很多时,可以通过对关键字的各位进行分析,丢掉分布不均匀的位,作为哈希值它只适合于所有关键字值已知的情况。通过分析分布情况把关键字取值区间转化为一个较小的关键字取值区间。

    平方取中法,

    这是一种常用的哈希函数构造方法。这个方法是先取关键字的平方,然后根据可使用空间的大小,选取平方数是中间几位为哈希地址。

    哈希函数 H(key)=“key2的中间几位”因为这种方法的原理是通过取平方扩大差别,平方值的中间几位和这个数的每一位都相关,则对不同的关键字得到的哈希函数值不易产生冲突,由此产生的哈希地址也较为均匀。

    折叠法,所谓折叠法是将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位),这方法称为折叠法。

    随机数法,

    除留余数法取关键字被某个不大于散列表   表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。对p的选择很重要,一般取,素数,质数,或m,若p选的不好,容易产生同义词  摘自:哈希表

    那么对p 的选择,关键字不仅可以通过直接对取模,还可以在上述数字分析,平方取中,折叠之后,在进行取模。这样使得关键字在通过hash函数映射到内存单元的任意地址是均匀的,减少冲突。

    在取模的过程中对P为什么要使用质数或素数呢?

    因为质数是只有1和他本身的因子。而合数除了1和他本身外还有其他因子。这样在取模的时候,就会出现相同的hash地址,进而增加冲突。  b = ak +n   n为取余之后的值,那么当a为合数的时候,同样是n,k的取值或b的取值是密集,增加冲突。可以参考博客:为什么求模运算要用素数(质数)—— 哈希表设计

    关于hash函数的其他方法介绍,可以学习:哈希函数的构造方法

    展开全文
  • 本篇笔记记录了PHP使用Memcached扩展,采用取模hash和一致性hash算法操作Memcached分布式集群的实现对比 相关笔记: CentOS6.9源码编译安装memcached CentOS6.9源码编译安装php-memcached扩展 1.开启4个Memcached...

    本篇笔记记录了PHP使用Memcached扩展,采用取模hash和一致性hash算法操作Memcached分布式集群的实现对比

    相关笔记:
    CentOS6.9源码编译安装memcached
    CentOS6.9源码编译安装php-memcached扩展

    1.开启4个Memcached服务模拟集群

    /usr/local/memcached/bin/memcached -d -p 11211 -u memcached -vv >> /var/log/memcached.11211.log 2>&1
    /usr/local/memcached/bin/memcached -d -p 11212 -u memcached -vv >> /var/log/memcached.11212.log 2>&1
    /usr/local/memcached/bin/memcached -d -p 11213 -u memcached -vv >> /var/log/memcached.11213.log 2>&1
    /usr/local/memcached/bin/memcached -d -p 11214 -u memcached -vv >> /var/log/memcached.11214.log 2>&1
    

    2.取模hash算法

    php代码

    <?php
    /**
     * Created by PhpStorm.
     * User: jmsite.cn
     * Date: 2019/1/28
     * Time: 11:38
     */
    $memcached = new Memcached();
    //设置算法为取模hash
    $memcached->setOptions(
        array(
            Memcached::OPT_DISTRIBUTION         => Memcached::DISTRIBUTION_MODULA,
            //Memcached::OPT_LIBKETAMA_COMPATIBLE => true,
            Memcached::OPT_REMOVE_FAILED_SERVERS=> true,
        )
    );
    //添加服务器
    $memcached->addServer('192.168.75.132', '11211');
    $memcached->addServer('192.168.75.132', '11212');
    $memcached->addServer('192.168.75.132', '11213');
    $memcached->addServer('192.168.75.132', '11214');
    //写入12个key
    for ($i =1;$i <= 12;$i++){
        $memcached->set('key_'.$i, 'value_'.$i);
    }
    

    执行上述代码,查看log

    #memcached.11211.log
    <28 new auto-negotiating client connection
    28: Client using the ascii protocol
    <28 set key_2 0 0 7
    >28 STORED
    <28 set key_3 0 0 7
    >28 STORED
    <28 set key_4 0 0 7
    >28 STORED
    <28 set key_10 0 0 8
    >28 STORED
    <28 quit
    <28 connection closed.
    #memcached.11212.log
    <28 new auto-negotiating client connection
    28: Client using the ascii protocol
    <28 set key_1 0 0 7
    >28 STORED
    <28 set key_6 0 0 7
    >28 STORED
    <28 set key_9 0 0 7
    >28 STORED
    <28 set key_12 0 0 8
    >28 STORED
    <28 quit
    <28 connection closed.
    #memcached.11213.log
    <28 new auto-negotiating client connection
    28: Client using the ascii protocol
    <28 set key_7 0 0 7
    >28 STORED
    <28 set key_8 0 0 7
    >28 STORED
    <28 quit
    <28 connection closed.
    #memcached.11214.log
    <28 new auto-negotiating client connection
    28: Client using the ascii protocol
    <28 set key_5 0 0 7
    >28 STORED
    <28 set key_11 0 0 8
    >28 STORED
    <28 quit
    <28 connection closed.
    
    

    查看key的分布

    服务器键名
    11211key_2,key_3,key_4,key_10
    11212key_1,key_6,key_9, key_12
    11213key_7,key_8
    11214key_5, key_11

    注释掉php代码中的11214//$memcached->addServer('192.168.75.132', '11214');
    再次执行php代码
    查看key的分布

    服务器键名
    11211key_1, key_2, key_6, key_7, key_8, key_9, key_10, key_11, key_12
    11212
    11213key_3, key_4, key_5

    对比两次key的分布:
    key_2和key_10命中没有变动,始终在11211中,其他10个key因为服务器的减少命中发生变化

    3.一致性hash算法

    php代码

    <?php
    /**
     * Created by PhpStorm.
     * User: jmsite.cn
     * Date: 2019/1/28
     * Time: 11:38
     */
    $memcached = new Memcached();
    //设置算法为一致性hash
    $memcached->setOptions(
        array(
            Memcached::OPT_DISTRIBUTION         => Memcached::DISTRIBUTION_CONSISTENT,
            Memcached::OPT_LIBKETAMA_COMPATIBLE => true,
            Memcached::OPT_REMOVE_FAILED_SERVERS=> true,
        )
    );
    //添加服务器
    $memcached->addServer('192.168.75.132', '11211');
    $memcached->addServer('192.168.75.132', '11212');
    $memcached->addServer('192.168.75.132', '11213');
    $memcached->addServer('192.168.75.132', '11214');
    //写入12个key
    for ($i =1;$i <= 12;$i++){
        $ret = $memcached->set('key_'.$i, 'value_'.$i);
    }
    

    执行上述代码,查看log
    查看key的分布

    服务器键名
    11211key_1, key_6, key_11
    11212key_7, key_10
    11213key_2, key_3, key_5, key_8, key_9
    11214key_4, key_12

    注释掉php代码中的11214//$memcached->addServer('192.168.75.132', '11214');
    再次执行php代码
    查看key的分布

    服务器键名
    11211key_1, key_4, key_6, key_11
    11212key_7, key_10
    11213key_2, key_3, key_5, key_8, key_9, key_12

    对比两次key的分布:
    11211原有的key命中没有发生变化,新增了key_4
    11212原有的key命中没有发生变化
    11213原有的key命中没有发生变化,新增了key_12
    有2个key因为服务器的减少命中发生变化

    4.对比

    取模hash算法减少一台服务器有10个key命中发生了变化。
    一致性hash算法减少一台服务器2个key命中发生了变化。
    这里只测试了12个key,模拟的数据量太小导致key分布不均匀,但服务器减少导致key命中发生变化和模拟数据量大小无关,而是和hash算法有关,这些测试体现了一致性hash算法的优势,取模hash因为服务器的减少导致大量key的取模结果发生变化,命中的服务器也发生了变化;而一致性hash算法key是固定在一个有2^32-1个节点的hash环上,服务器减少key在hash环上的位置不会发生变化,仅仅影响减少的那台服务器上key的命中,增加服务器也仅仅影响hash环上下一个位置服务器的部分key而已
    原文地址:https://www.jmsite.cn/blog-624.html

    展开全文
  • /// <summary> /// 获取一个key的Md5 Hash值 /// </summary> /// <param name="key"></param> /// <returns></returns> public in...
            /// <summary>
            /// 获取一个key的Md5 Hash值
            /// </summary>
            /// <param name="key"></param>
            /// <returns></returns>
            public int HashCode(string key)
            {
                int HashCode;
                byte[] Md5Bype;
                if (Md5Cache.ContainsKey(key))
                {
                    return Md5Cache[key];
                }
                else
                {
                    using (var md5 = new MD5CryptoServiceProvider())
                    {
                        Md5Bype = md5.ComputeHash(Encoding.UTF8.GetBytes(key));
                    }
                    HashCode = BitConverter.ToInt32(Md5Bype, 0);
                    if (HashCode < 0)
                    {
                        HashCode = int.MaxValue + HashCode;
                    }
    
                    HashCode = Math.Abs(HashCode);
                    Md5Cache[key] = HashCode;
                }
                return HashCode;
            }
    
    
    
            /// <summary>
            /// 是否是当前节点
            /// </summary>
            public int BeloneNode(string key)
            {
                return HashCode(key) % NodeCount;
            }

     

    展开全文
  • 一点php分享关于redis分布式架构理念的一些总结并不涉及实际部署方式以及代码,无论是redis还是其他软件所有的架构理念是一样的,个人认为理念更为重要,代码是死的理念是活的,没有一种架构可以解决一切问题,只有...

    一点php分享关于redis分布式架构理念的一些总结并不涉及实际部署方式以及代码,无论是redis还是其他软件所有的架构理念是一样的,个人认为理念更为重要,代码是死的理念是活的,没有一种架构可以解决一切问题,只有遇到不同的问题采用不同的架构根据实际场景调整架构方案。

    分布式算法无非是运维开发者手动实现或者是软件自身支持某种算法实现。搭建分布式的目的就在于将不同的请求压力以及读写io分散开,关键在于如何分散请求以及后续如何可以精确的命中请求。

    一致性hash算法:

    redis存储采用一致性hash方式命中节点,将所有缓存以及节点都放入hash空间中,数据进来后 通过hash计算得出自己的位置然后顺时针寻找就近节点,如果节点宕机则寻找下一个。如果分布不均匀,导致某一节点压力过大,可以采用虚拟节点。

    hash取模方式:

    数据进来后通过hash取模的方式算出节点位置,从而进行读写操作,这种算法实现简单也有一定的作用,但是server总数不能轻易变化。因为如果增加/减少server的数量,对原先存储的所有key的后续查询都将定位到别的server上,导致所有的cache都不能被命中而失效。

    区别:

    为了解决这个问题,需要采用一致性hash算法

    相对于取模的算法,一致性hash算法除了计算key的hash值外,还会计算每个server对应的hash值,然后将这些hash值映射到一个有限的值域上(比如0~2^32)。通过寻找hash值大于hash(key)的最小server作为存储该key数据的目标server。如果找不到,则直接把具有最小hash值的server作为目标server。

    在redis3.0版本之后推出redis自身的实现方式:

    生产通过hash槽将0~16383范围分片给不同节点存储数据,最少6台redis才能将这个架构跑起来,3台master以及3台slave分别为主各自的主从,并且将16383个hash槽位置分散在3台master节点中。好处是显而易见的主挂从上,同时主从数据基本同步当然也不是强一致性的,并不能100%的认为数据一致。当master数量少于一定程度或者某个节点的主从同时宕机,这个集群将停止工作。

    77b0d6f72250115d0b60bd2dd3b70f42.gif

    总结:

    以上只是博主分享的一部分关于redis的架构理念,只是让大家有个概念,具体细节一篇文章也讲不完。同时并不是说只有这些方式,例如某些大厂中会有自身的一套算法,还有redis中也有哨兵算法等,本文主要作为抛砖引玉的作用。

    一点php一点技术分享

    展开全文
  • MurmurHash3PHP实现 有关这些算法的更多信息,请参见: 由Gary Court创建的MurmurHash3 JavaScript版本的移植( ) 安装 使用: composer require lastguest/murmurhash 用法 您可以通过Murmur类的hash3静态方法...
  • php class Moder { protected $nodes = []; protected $cnt = 0; public function _hash($str) { return sprintf('%u', crc32($str)); } public function _lookup($key) { return $this->nodes[$this...
  • 最近在看一些分布式方面的文章,所以就用php实现一致性hash来练练手,以前一般用的是最原始的hash取模做 分布式,当生产过程中添加或删除一台memcache都会造成数据的全部失效,一致性hash就是为了解决这个问题,把...
  • 普通Hash分布简介普通Hash分布比较简单,Hash函数大致如下:function mHash($key){ $md5 = substr(md5($key),0,8); $seed = 31; $hash = 0; for($i = 0; $i ; $i++){ $hash = $hash*$seed + ord(md5($i));
  • php hash 拉链法

    2017-05-27 11:33:14
    php 模拟hash 拉链法 :)<?php /** * FILE_NAME:hash.php * AUTHOR: ChenShuai * Date: 2017/5/27 * DESC: */class myhash{ public $bucket = []; /** * @param $key * @return int * @a
  • 本文实例讲述了PHP实现的一致性Hash算法。分享给大家供大家参考,具体如下: 一致性哈希算法是分布式系统中常用的算法,为什么要用这个算法? 比如:一个分布式存储系统,要将数据存储到具体的节点(服务器)上, 在...
  • 为什么不直接使用hash取模的方式,主要原因是:hash取模在容错性和扩展性上较差,如果新增一个节点,或者删除一个节点,那么所有的几点都要重新计算一遍。显然不符合实际实际生产环境。 什么是一致性hash? 通过...
  •  最近在看一些分布式方面的文章,所以就用php实现一致性hash来练练手,以前一般用的是最原始的hash取模做 分布式,当生产过程中添加或删除一台memcache都会造成数据的全部失效,一致性hash就是为了解决这个问题,把...
  • PHP实现一致性hash

    万次阅读 2015-10-23 14:27:57
    随着memcache、redis以及其它一些内存K/V数据库的流行,一致性哈希也越来越被开发者所了解。因为这些内存K/V数据库大多不提供分布式支持(本文以redis为例),所以如果要提供多台redis server来...取模算法   取...
  • 摘要:PHP数组的定义,本质上是一种键-值映射的关系,算是一...PHPHash采用的是目前最为普遍的DJBX33A (Daniel J. Bernstein, Times 33 with Addition), 这个算法被广泛运用与多个软件项目,Apache, Perl和Berkeley D
  • mysql 取模分表

    千次阅读 2017-11-09 14:40:00
    取模分表,根据时间维度进行分表自定义的Hash 分表实现原理:利用sqlparser解析sql参数,根据参数修改相关的表名为实际表名。 分表后的数据复制,一般采用insert select语句将原有表的数据导入新的分表,或者直接...
  • PHP一致性hash的实现

    2015-01-08 19:22:26
    一致性hash大多用于缓存集群中,为了使在缓存中由于一台或多台服务器宕机,导致后端数据库压力过大而崩溃,他对添加和减少缓存服务器迁移的数据量最小化,相对于取模来说 对于一致性hash的原理和介绍,网上有很多,...
  • PHP一致性Hash

    2017-06-16 15:45:29
    随着memcache、Redis以及其它一些内存K/V数据库的流行,一致性哈希也越来越被开发者所了解。因为这些内存K/V数据库大多不提供分布式支持(本文以redis为例),所以如果要提供多台redis ...取模算法
  • 哈希表最关键的几个方面有: ...一般来说对于整形索引进行哈希我们很容易想到的是取模运算,比如array(1=>'a', 2=>'b', 3=>'c'),这类我们可以使用index%3来哈希,不过PHP数组的下标还有更...
  • php hash分表的方法(个人收藏)

    千次阅读 2015-01-30 17:20:25
    //分库分表算法 ...function calc_hash_db($u, $s = 10){  $h = sprintf("%u", crc32($u));  $h1 = intval(fmod($h, $s));  return $h1; } for($i = 10000034; $i ; $i++){  $table = calc_hash
  • PHP一致性hash实现

    2018-05-29 16:55:13
    PHP 一致性hash实现 &lt;?php /** * 分布式缓存部署方案 * 当有1台cache服务器不能满足我们的需求,我们需要布置多台来做分布式服务器,但是 * 有个问题,怎么确定一个数据应该保存到哪台服务器上呢? * 有...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,486
精华内容 994
关键字:

hashphp取模