hash 订阅
Hash,一般翻译做散列、杂凑,或音译为哈希,是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。 展开全文
Hash,一般翻译做散列、杂凑,或音译为哈希,是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
信息
外文名
Hash
音    译
哈希
特    点
很难找到逆向规律
释    义
把任意长度的输入通过散列算法变换成固定长度的输出
中文名
散列、杂凑
属    性
压缩映射
Hash简介
Hash算法可以将一个数据转换为一个标志,这个标志和源数据的每一个字节都有十分紧密的关系。Hash算法还具有一个特点,就是很难找到逆向规律。Hash算法是一个广义的算法,也可以认为是一种思想,使用Hash算法可以提高存储空间的利用率,可以提高数据的查询效率,也可以做数字签名来保障数据传递的安全性。所以Hash算法被广泛地应用在互联网应用中。 [1]  Hash算法也被称为散列算法,Hash算法虽然被称为算法,但实际上它更像是一种思想。Hash算法没有一个固定的公式,只要符合散列思想的算法都可以被称为是Hash算法。 [2] 
收起全文
精华内容
下载资源
问答
  • 2021-10-19 15:43:24

    一、哈希表定义

    • 哈希表(hash table,也叫散列表),是根据键(key)直接访问访问在内存储存位置的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度,这个映射函数叫做散列函数,存放记录的数组叫做散列表。
    • 给定表 M,存在函数 f(key),对任意给定的关键字值 key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表 M 为哈希(Hash)表,函数f(key)为哈希(Hash)函数。
    • 若关键字为 k,则其值存放在 f(k) 的存储位置上,由此不需比较便可直接取得所查记录,称这个对应关系 f 为散列函数,按这个思想建立的表为散列表。
    • 对不同的关键字可能得到同一散列地址,即 k1≠k2,而 f(k1)=f(k2),这种现象称为冲突(英译:Collision)。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述,根据散列函数f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这种表便称为散列表,这一映射过程称为散列造表或散列,所得的存储位置称散列地址。
    • 若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数(Uniform Hash function),这就是使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。
    • 哈希表本质是一个数组,数组中的每一个元素成为一个箱子,箱子中存放的是键值对,根据下标 index 从数组中取 value。关键是如何获取 index,这就需要一个固定的函数(哈希函数),将 key 转换成 index。
    • 不论哈希函数设计的如何完美,都可能出现不同的 key 经过 hash 处理后得到相同的 hash 值,这时候就需要处理哈希冲突。

    二、哈希表优缺点

    • 优点:哈希表可以提供快速的操作。
    • 缺点:
      • 哈希表通常是基于数组的,数组创建后难于扩展;
      • 没有一种简便的方法可以以任何一种顺序〔例如从小到大)遍历表中的数据项。
    • 综上,如果不需要有序遍历数据,井且可以提前预测数据量的大小,那么哈希表在速度和易用性方面是无与伦比的。

    三、哈希查找步骤

    • 使用哈希函数将被查找的键映射(转换)为数组的索引,理想情况下(hash 函数设计合理)不同的键映射的数组下标也不同,所有的查找时间复杂度为 O(1)。但是实际情况下不是这样的,所以哈希查找的第二步就是处理哈希冲突。
    • 处理哈希碰撞冲突,方法有很多,比如拉链法、线性探测法。

    四、哈希表存储过程

    • 使用 hash 函数根据 key 得到哈希值 h;
    • 如果箱子的个数为 n,那么值应该存放在底(h%n)个箱子中,h%n 的值范围为 [0, n-1];
    • 如果该箱子非空(已经存放了一个值)即不同的 key 得到了相同的h产生了哈希冲突,此时需要使用拉链法或者开放定址线性探测法解决冲突。

    五、常用哈希函数

    • 哈希查找第一步就是使用哈希函数将键映射成索引,这种映射函数就是哈希函数。
    • 如果有一个保存 0 ~ M 数组,那么就需要一个能够将任意键转换为该数组范围内的索引(0 ~ M-1)的哈希函数,哈希函数需要易于计算并且能够均匀分布所有键。
    • 举个简单的例子,使用手机号码后三位就比前三位作为 key 更好,因为前三位手机号码的重复率很高;再比如使用身份证号码出生年月位数要比使用前几位数要更好。
    • 在实际中,我们的键并不都是数字,有可能是字符串,还有可能是几个值的组合等,所以需要实现自己的哈希函数:
      • 直接寻址法;
      • 数字分析法;
      • 平方取中法;
      • 折叠法;
      • 随机数法;
      • 除留余数法。
    • 要想设计一个优秀的哈希算法并不容易,根据经验,总结了需要满足的几点要求:
      • 从哈希值不能反向推导出原始数据(所以哈希算法也叫单向哈希算法);
      • 对输入数据非常敏感,哪怕原始数据只修改了一个 Bit,最后得到的哈希值也大不相同;
      • 散列冲突的概率要很小,对于不同的原始数据,哈希值相同的概率非常小;
      • 哈希算法的执行效率要尽量高效,针对较长的文本,也能快速地计算出哈希值。

    六、负载因子

    • 负载因子 = 总键值对数/数组的个数。
    • 负载因子是哈希表的一个重要属性,用来衡量哈希表的空/满程度,一定程度也可以提现查询的效率。负载因子越大,意味着哈希表越满,越容易导致冲突,性能也就越低。所以当负载因子大于某个常数(一般是0.75)时,哈希表将自动扩容。
    • 哈希表扩容时,一般会创建两倍于原来的数组长度,因此即使 key 的哈希值没有变化,对数组个数取余的结果会随着数组个数的扩容发生变化,因此键值对的位置都有可能发生变化,这个过程也成为重哈希(rehash)。

    七、哈希表扩容

    • 在数组比较多的时候,需要重新哈希并移动数据,性能影响较大。
    • 虽然能够使负载因子降低,但并不总是能有效提高哈希表的查询性能。
    • 比如哈希函数设计的不合理,导致所有的 key 计算出的哈希值都相同,那么即使扩容他们的位置还是在同一条链表上,变成了线性表,性能极低,查询的时候时间复杂度就变成了 O(n)。

    八、哈希冲突的解决方法

    ① 拉链法

    • 简单来说就是数组 + 链表,将键通过 hash 函数映射为大小为 M 的数组的下标索引,数组的每一个元素指向一个链表,链表中的每一个结点存储着 hash 出来的索引值为结点下标的键值对。
    • Java 8 解决哈希冲突采用的就是拉链法,在处理哈希函数设计不合理导致链表很长时(链表长度超过 8 切换为红黑树,小于 6 重新退化为链表),将链表切换为红黑树能够保证插入和查找的效率,缺点是当哈希表比较大时,哈希表扩容会导致瞬时效率降低。
    • Redis 解决哈希冲突采用的也是拉链法,通过增量式扩容解决了 Java 8 中的瞬时扩容导致的瞬时效率降低的缺点,同时拉链法的实现方式(新插入的键值对放在链表头部)带来了两个好处:
      • 头插法可以节省插入耗时,如果插到尾部,则需要时间复杂度为 O(n) 的操作找到链表尾部,或者需要额外的内存地址来保存尾部链表的位置;
      • 头插法可以节省查找耗时,对于一个数据系统来说,最新插入的数据往往可能频繁的被查询。
    • 与开放定址线性探测发相比,拉链法有如下几个优点:
      • 拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;
      • 由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;
      • 开放定址线性探测法为减少冲突,要求装填因子 α 较小,故当结点规模较大时会浪费很多空间。而拉链法中可取 α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;
      • 在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放定址线性探测发构造的散列表,删除结点不能简单地将被删结 点的空间置为空,否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放定址线性探测发中,空地址单元(即开放地址)都是查找失败的条件。因此在用开放定址线性探测发处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点。
    • 拉链法的缺点:指针需要额外的空间,故当结点规模较小时,开放定址线性探测发较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址线性探测发中的冲突,从而提高平均查找速度。

    ② 开放定址线性探测法

    • 使用两个大小为 N 的数组(一个存放 keys,另一个存放 values),使用数组中的空位解决碰撞,当碰撞发生时(即一个键的 hash 值对应数组的下标被两外一个键占用)直接将下标索引加一(index += 1),这样会出现三种结果:
      • 未命中(数组下标中的值为空,没有占用):keys[index] = key,values[index] = value;
      • 命中(数组下标中的值不为空,占用):keys[index] == key,values[index] == value;
      • 命中(数组下标中的值不为空,占用):keys[index] != key,继续 index += 1,直到遇到结果 1 或 2 停止。
    • 开放定址线性探测法缺点
      • 容易产生堆积问题;
      • 不适于大规模的数据存储;
      • 散列函数的设计对冲突会有很大的影响;
      • 插入时可能会出现多次冲突的现象,删除的元素是多个冲突元素中的一个,需要对后面的元素作处理,实现较复杂;
      • 结点规模很大时会浪费很多空间。

    ③ 再散列法

    • Hi=RHi(key),i=1,2,…,k RHi 均是不同的散列函数,即在同义词产生地址冲突时计算另一个散列函数地址,直到冲突不再发生,这种方法不易产生“聚集”,但增加了计算时间;

    ④ 建立一个公共溢出区

    九、Hash 表的平均查找长度

    • Hash 表的平均查找长度包括查找成功时的平均查找长度和查找失败时的平均查找长度:
      • 查找成功时的平均查找长度=表中每个元素查找成功时的比较次数之和/表中元素个数;
      • 查找不成功时的平均查找长度相当于在表中查找元素不成功时的平均比较次数,可以理解为向表中插入某个元素,该元素在每个位置都有可能,然后计算出在每个位置能够插入时需要比较的次数,再除以表长即为查找不成功时的平均查找长度。
    • 给定一组数据 {32,14,23,01,42,20,45,27,55,24,10,53},假设散列表的长度为 13(最接近 n 的质数),散列函数为 H(k) = k,分别画出用“线性探测法”和“拉链法”解决冲突时构造的哈希表,并求出在等概率下情况,这两种方法查找成功和查找不成功的平均查找长度。
      • 拉链法:
        • 查找成功时的平均查找长度:ASL = (16 + 24 + 31 + 41)/12 = 7/4;
        • 查找不成功时的平均查找长度:ASL = (4 + 2 + 2 + 1 + 2 + 1)/13。

    在这里插入图片描述

      • 线性探测法:
        • 查找成功时查找次数 = 插入元素时的比较次数,查找成功的平均查找长度:ASL = (1 + 2 + 1 + 4 + 3 + 1 + 1 + 1 + 3 + 9 + 1 + 1 + 3)/12 = 2.5;
        • 查找不成功时的查找次数 = 第 n 个位置不成功时的比较次数为,第 n 个位置到第 1 个没有数据位置的距离:如第 0 个位置取值为 1,第 1个位置取值为 2。查找不成功时的平均查找长度:ASL = ( 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12/13 = 91/13。

    十、Apple 方案选择

    • 解决哈希冲突的拉链法和开放定址线性探测法,Apple 都在使用,具体使用哪一种是根据存储数据的生命周期和特性决定的:
      • @synchronized 使用的是拉链法,拉链法多用于存储的数据是通用类型,能够被反复利用,就像@synchronized 存储的是锁是一种无关业务的实现结构,程序运行时多个对象使用同一个锁的概率相当高,有效的节省了内存。
      • weak 对象 associatedObject 采用的是开放定址线性探测法,开放定址线性探测法用于存储的数据是临时的,用完尽快释放,就像 associatedObject,weak。

    十一、字符串的 hash 方法

    • [NSString hash] 出现同样的 hash 值问题:
    At least there are special circumstances for which this unreliability kicks in.
    
    Comparing [a hash] and [b hash] of two different NSString is safe when:
    
    the strings' length is shorter or equal to 96 characters.
    [a length] is different to [b length].
    the concatinated first, middle, and last 32 characters of a differ to the concatinated components of b.
    Otherwise every difference between the first and the middle 32 chars, as well as every difference between the middle and the last 32 characters, are not used while producing the [NSString hash] value.
    
    • [NSString hash] 这个方法对 <=96 个字符的字符串是安全的,如果比 96 个字符长,会大大增加碰撞的概率:
    #define HashEverythingLimit 96
    
    #define HashNextFourUniChars(accessStart, accessEnd, pointer) \
        {result = result * 67503105 + (accessStart 0 accessEnd) * 16974593  + (accessStart 1 accessEnd) * 66049  + (accessStart 2 accessEnd) * 257 + (accessStart 3 accessEnd); pointer += 4;}
    
    #define HashNextUniChar(accessStart, accessEnd, pointer) \
        {result = result * 257 + (accessStart 0 accessEnd); pointer++;}
    
    
    CF_INLINE CFHashCode __CFStrHashCharacters(const UniChar *uContents, CFIndex len, CFIndex actualLen) {
        CFHashCode result = actualLen;
        // ****X 这里HashEverythingLimit = 96
        if (len <= HashEverythingLimit) {
            // ****X 若字符串长度在96以内,对所有的字符做hash运算得到一个结果
            
            const UniChar *end4 = uContents + (len & ~3);
            const UniChar *end = uContents + len;
            while (uContents < end4) HashNextFourUniChars(uContents[, ], uContents);    // First count in fours
            while (uContents < end) HashNextUniChar(uContents[, ], uContents);      // Then for the last <4 chars, count in ones...
        } else {
            // ****X 若字符串长度超过96
            
            const UniChar *contents, *end;
            // ****X 取前32个字符做hash运算
        contents = uContents;
            end = contents + 32;
            while (contents < end) HashNextFourUniChars(contents[, ], contents);
            // ****X 取中间32个字符做hash运算
        contents = uContents + (len >> 1) - 16;
            end = contents + 32;
            while (contents < end) HashNextFourUniChars(contents[, ], contents);
            // ****X 取最后32个字符做hash运算
        end = uContents + len;
            contents = end - 32;
            while (contents < end) HashNextFourUniChars(contents[, ], contents);
        }
        return result + (result << (actualLen & 31));
    }
    
    • 如果长度大于 96,只有前、中、后 32 个字符做了哈希运算,也就是说在这些字符相同的情况下,其他任意位置的字符发生改变,Hash 值都不会变。
    • 在工程中使用字符串的 hash 方法作为数据是否发生改变的依据,发现方法返回的 hash 值为一个很大的负数,这是因为数值大小超出了数据类型能够表达的范围。可以使用 md5 算法代替系统的 hash 算法。

    十二、Hash 在 iOS 中的应用分析

    ① 关联对象 AssociatedObject 的底层实现采用的数据存储结构(Hash 表 + Hash 表)

    • 关联对象采用的是 HashMap 嵌套 HashMap 的结构存储数据的,简单来说就是根据对象从第一个 HashMap 中取出存储对象所有关联对象的第二个 HashMap,然后根据属性名从第二个 HashMap 中取出属性对应的值和策略。
    • 设计关联对象的初衷:通过传入对象 + 属性名字,就可以找到属性值,方案设计实现好后,查找一个对象的关联对象的基本步骤:
      • 已知条件一:对象,因此引出第一个 HashMap(AssociationsHashMap),用一个能唯一代表对象的值作为 key,用存储对象的所有关联对象的结构(名字:值+策略)作为 value;
      • 已知条件二:属性名字,因此引出第二个 HashMap(ObjectAssociationMap),用属性名字作为key,用属性名字对应的结构体(值+策略)作为 value。

    ② weak 底层实现采用的数据存储结构(Hash 表 + 数组)

    • weak 采用的是一个全局的 HashMap 嵌套数组的结构存储数据的,销毁对象(weak 指针指向的对象)的时候,根据对象从 HashMap 中找到存放所有指向该对象的 weak 指针的数组,然后将数组中的所有元素都置为 nil。
    • weak 的最大特点就是在对象销毁时,自动置 nil,减少访问野指针的风险,这也是设计 weak 的初衷。
    • 方案设计实现好后,weak 指针置 nil 的基本步骤:
      • 对象 dealloc 的时候,从全局的 HashMap 中,根据一个唯一代表对象的值作为 key,找到存储所有指向该对象的 weak 指针的数组;
      • 将数组中的所有元素都置为 nil。
    • 深入了解请参考:iOS之深入解析weak关键字的底层原理

    ③ KVO 底层实现采用的数据存储结构(Hash 表 + 数组)

    ④ iOS App 签名的原理(MD5 + 哈希表 + 非对称加密 RSA)

    • 一致性哈希算法 + 非对称加解密算法:
      • 数字签名:传递数据时会将原始的数据和数字签名一起发送,对方拿到数据后,通过同样的 Hash 算法得到原始数据的 Hash 的值,然后通过非对称加密,将数字签名中的校验 Hash 值解密出来,最后对比两个 Hash 值是否一致。
      • 代码签名:代码签名就是对可执行文件或脚本进行数字签名,用来确认软件在签名后未被修改或损坏的措施。它的原理和数字签名类似,只不过把签名的不是数据,而是代码。
    • 深入了解请参考:iOS逆向之深入解析App签名的双向验证机制和原理

    ⑤ 对象的引用计数存储的位置(Hash 表)

    if 对象支持TaggedPointer {
        return 直接将对象的指针值作为引用计数返回
    } 
    else if 设备是64位环境 && Objective-C2.0 {
        return 对象isa指针的一部分空间(bits_extra_rc)
    }
    else {
        return hash表
    }
    

    ⑥ NSDictionary 的实现原理(Hash 表)

    • NSMapTable 实现:
      • NSDictionary 是使用 NSMapTable 实现的,采用拉链法解决哈希冲突:
    typedef struct {
       NSMapTable *table;
       NSInteger i;
       struct _NSMapNode *j;
    } NSMapEnumerator;
    
      • 上述结构体描述了遍历一个 NSMapTable 时的一个指针对象,其中包含 table 对象自身的指针,计数值和节点指针:
    typedef struct {
       NSUInteger (*hash)(NSMapTable *table,const void *);
       BOOL (*isEqual)(NSMapTable *table,const void *,const void *);
       void (*retain)(NSMapTable *table,const void *);
       void (*release)(NSMapTable *table,void *);
       NSString  *(*describe)(NSMapTable *table,const void *);
       const void *notAKeyMarker;
    } NSMapTableKeyCallBacks;
    
      • 上述结构体中存放的是几个函数指针,用于计算 key 的 hash 值,判断 key 是否相等,retain,release 操作:
    typedef struct {
       void (*retain)(NSMapTable *table,const void *);
       void (*release)(NSMapTable *table,void *);
       NSString *(*describe)(NSMapTable *table, const void *);
    } NSMapTableValueCallBacks;
    
      • 上述存放的三个函数指针,定义在对 NSMapTable 插入一对 key、value 时,对 value 对象的操作:
    @interface NSMapTable : NSObject {
       NSMapTableKeyCallBacks *keyCallBacks;
       NSMapTableValueCallBacks *valueCallBacks;
       NSUInteger count;
       NSUInteger nBuckets;
       struct _NSMapNode **buckets;
    }
    
      • 从上面的结构真的能看出 NSMapTable 是一个“哈希表 + 链表”的数据结构吗?在 NSMapTbale 中插入或者删除一个对象的寻找时间 = O(1) + O(m) ,m 为最坏时可能为 n:
        • O(1):对 key 进行 hash 得到 bucket 的位置;
        • O(m):不同的 key 得到相同的 hash 值的 value 存放到链表中,遍历链表的时间。
      • 上面的结论和对应的解释似乎很合理?下面我们继续分析。
    • _CFDictionary 封装:
      – NSDictionary 是对 _CFDictionary 的封装,解决哈希冲突使用的是开放定址线性探测法:
    struct __CFDictionary {
        CFRuntimeBase _base;
        CFIndex _count;
        CFIndex _capacity;
        CFIndex _bucketsNum;
        uintptr_t _marker;
        void *_context;
        CFIndex _deletes;
        CFOptionFlags _xflags;
        const void **_keys;
        const void **_values;
    };
    
      • 从上面的数据结构可以看出 NSDictionary 内部使用了两个指针数组分别保存 keys 和 values,采用的是连续方式存储键值对。拉链法会将 key 和 value 包装成一个结果存储(链表结点),而 Dictionary 的结构拥有 keys 和 values 两个数组(开放寻址线性探测法解决哈希冲突的用的就是两个数组),说明两个数据是被分开存储的,不像是拉链法。
      • NSDictionary 使用开放定址线性探测法解决哈希冲突的原理:NSDictionary 设置的 key 和 value,key 值会根据特定的 hash 函数算出建立的空桶数组,keys 和 values 同样多,然后存储数据的时候,根据 hash 函数算出来的值,找到对应的 index 下标,如果下标已有数据,开放定址法后移动插入,如果空桶数组到达数据阀值,这个时候就会把空桶数组扩容,然后重新哈希插入。
      • 这样一来,把一些不连续的 key-value 值插入到了能建立起关系的 hash 表中,当查找的时候,key 根据哈希算法算出来索引,然后根据索引,直接 index 访问 hash 表 keys 和 hash 表 values,这样查询速度就可以和连续线性存储的数据一样接近 O(1),只是占用空间有点大,性能就很强悍。
      • 如果删除的时候,也会根据 _maker 标记逻辑上的删除,除非 NSDictionary(NSDictionary 本体的hash 值就是 count)内存被移除。
      • NSDictionary 之所以采用这种设计:
        • 出于查询性能的考虑;
        • NSDictionary 在使用过程中总是会很快的被释放,不会长期占用内存。
    • NSDictionary 的存储过程:
      • 通过方法 - (void)setObject:(id)anObject forKey:(id)aKey; 可以看出 key 必须遵循 NSCopy 协议,也就是说 NSDictionary 的 key 是 copy 一份新的,而 value 是浅拷贝的(如果想深拷贝可以使用 NSMapTable)。
      • key 还必须要继承 NSObject,并且重写 -(NSUInteger)hash; 和 -(BOOL)isEqual:(id)object; 两个方法:
        • 第一个函数用于计算 hash 值;
        • 第二个函数用来判断当哈希值相同的时候 value 是否相同(解决哈希冲突)。

    ⑦ Runloop 与线程的存储关系

    • 线程和 Runloop 之间是一一(子线程可以没有)对应的,其关系是保存在一个全局的 Dictionary 里。
    • 线程刚创建时并没有 Runloop,如果你不主动获取,那它一直都不会有。
    • Runloop 的创建是发生在第一次获取时,Runloop 的销毁是发生在线程结束时,只能在一个线程的内部获取其 Runloop(主线程除外)。
    • Runloop 保存在一个全局的可变字典中,key 是 pthread_t,value 是 cfrunloopref,即 Hash 表。
    • 深入了解请参考:iOS之深入解析Runloop的底层原理
    更多相关内容
  • 真正搞懂hashCode和hash算法

    万次阅读 多人点赞 2021-01-28 19:29:08
    自从搞懂hash,妈妈再也不担心我找不到工作啦

    本人当初刚接触java的时候一说到hash算法或者hashCode也是蛋蛋疼,两只都疼
    在这里插入图片描述

    后来花了整整一天时间来研究hash,搞懂后发现其实也不难理解,时隔一年突然想起来,写篇博客记录下;

    以前我莫得选择,现在我想搞懂hash,搞懂算法,做大做强,再创辉煌!

    本文会围绕以下几个点来讲:

    什么是hashCode?
    hashCode和equals的关系
    剖析hashMap的hash算法(重点)

    为什么会有hashCode
    先抛一个结论

    hashCode的设计初衷是提高哈希容器的性能

    抛开hashCode,现在让你对比两个对象是否相等,你会怎么做?

    thisObj == thatObj
    thisObj.equals(thatObj)

    我想不出第三种了,而且这两种其实没啥大的区别,object的equals()方法底层也是==,jdk1.8 Object类的第148行;

        public boolean equals(Object obj) {
            return (this == obj);
        }
    

    为什么有了equals还要有hashCode?上面说了,hashCode的设计初衷是提高哈希容器的性能,equals的效率是没有hashCode高的,不信的可以自己去试一下;

    像我们常用的HashMap、HashTable等,某些场景理论上讲是可以不要hashCode的,但是会牺牲很多性能,这肯定不是我们想看到的;

    什么是hashCode
    知道hashCode存在的意义后,我们来研究下hashCode,看下长什么样

    对象调用hashCode方法后,会返回一串int类型的数字码

    Car car = new Car();
    log.info("对象的hashcode:{}", car.hashCode());
    log.info("1433223的hashcode:{}", "1433223".hashCode());
    log.info("郭德纲的hashcode:{}", "郭德纲".hashCode());
    log.info("小郭德纲的hashcode:{}", "小郭德纲".hashCode());
    log.info("彭于晏的hashcode:{}", "彭于晏".hashCode());
    log.info("唱跳rap篮球的hashcode:{}", "唱跳rap篮球".hashCode());
    

    运行结果

    对象的hashcode:357642
    1433223的hashcode:2075391824
    郭德纲的hashcode:36446088
    小郭德纲的hashcode:738530585
    彭于晏的hashcode:24125870
    唱跳rap篮球的hashcode:-767899628      ##因为返回值是int类型,有负数很正常

    可以看出,对象的hashcode值跟对象本身的值没啥联系,比如郭德纲和小郭德纲,虽然只差一个字,它们的hashCode值没半毛钱关系~

    hashCode和equals的关系

    java规定:

    如果两个对象的hashCode()相等,那么他们的equals()不一定相等。
    如果两个对象的equals()相等,那么他们的hashCode()必定相等。

    还有一点,重写equals()方法时候一定要重写hashCode()方法,不要问为什么,无脑写就行了,会省很多事

    hash算法

    前面都是铺垫,这才是今天的主题

    我们以HashMap的hash算法来看,个人认为这是很值得搞懂的hash算法,设计超级超级巧妙

        static final int hash(Object key) {
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }
    

    这是hashMap的hash算法,我们一步一步来看

    (h = key.hashCode()) ^ (h >>> 16)
    

    hashCode就hashCode嘛,为啥还要>>>16,这个 ^ 又是啥,不着急一个一个来说

    hashMap我们知道默认初始容量是16,也就是有16个桶,那hashmap是通过什么来计算出put对象的时候该放到哪个桶呢

        final Node<K,V> getNode(int hash, Object key) {
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
                if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;
                if ((e = first.next) != null) {
                    if (first instanceof TreeNode)
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }
            }
            return null;
        }
    

    上面是hashmap的getNode方法,对hashmap源码有兴趣的同学自行研究,我们今天主要看这一句:(n - 1) & hash

    也就是说hashmap是通过数组长度-1&key的hash值来计算出数组下标的,这里的hash值就是上面(h = key.hashCode()) ^ (h >>> 16)计算出来的值

    不要慌不要慌不要慌,看不懂没关系,我们现在总结下目前的疑问

    为什么数组长度要 - 1,直接数组长度&key.hashCode不行吗
    为什么要length-1 & key.hashCode计算下标,而不是用key.hashCode % length
    为什么要^运算
    为什么要>>>16

    先说结论

    数组长度-1、^运算、>>>16,这三个操作都是为了让key在hashmap的桶中尽可能分散
    用&而不用%是为了提高计算性能

    我们先看下如果数组长度不-1和不进行>>>16运算造成的结果,知道了结果我们后面才来说为什么,这样子更好理解

    log.info("数组长度不-1:{}", 16 & "郭德纲".hashCode());
    log.info("数组长度不-1:{}", 16 & "彭于晏".hashCode());
    log.info("数组长度不-1:{}", 16 & "李小龙".hashCode());
    log.info("数组长度不-1:{}", 16 & "蔡徐鸡".hashCode());
    log.info("数组长度不-1:{}", 16 & "唱跳rap篮球鸡叫".hashCode());
    
    log.info("数组长度-1但是不进行异或和>>>16运算:{}", 15 & "郭德纲".hashCode());
    log.info("数组长度-1但是不进行异或和>>>16运算:{}", 15 & "彭于晏".hashCode());
    log.info("数组长度-1但是不进行异或和>>>16运算:{}", 15 & "李小龙".hashCode());
    log.info("数组长度-1但是不进行异或和>>>16运算:{}", 15 & "蔡徐鸡".hashCode());
    log.info("数组长度-1但是不进行异或和>>>16运算:{}", 15 & "唱跳rap篮球鸡叫".hashCode());
    
    log.info("数组长度-1并且进行异或和>>>16运算:{}", 15 & ("郭德纲".hashCode()^("郭德纲".hashCode()>>>16)));
    log.info("数组长度-1并且进行异或和>>>16运算:{}", 15 & ("彭于晏".hashCode()^("彭于晏".hashCode()>>>16)));
    log.info("数组长度-1并且进行异或和>>>16运算:{}", 15 & ("李小龙".hashCode()^("李小龙".hashCode()>>>16)));
    log.info("数组长度-1并且进行异或和>>>16运算:{}", 15 & ("蔡徐鸡".hashCode()^("蔡徐鸡".hashCode()>>>16)));
    log.info("数组长度-1并且进行异或和>>>16运算:{}", 15 & ("唱跳rap篮球鸡叫".hashCode()^("唱跳rap篮球鸡叫".hashCode()>>>16)));
    

    数组长度不-1:0
    数组长度不-1:0
    数组长度不-1:16
    数组长度不-1:16
    数组长度不-1:16
    数组长度-1但是不进行异或和>>>16运算:8
    数组长度-1但是不进行异或和>>>16运算:14
    数组长度-1但是不进行异或和>>>16运算:8
    数组长度-1但是不进行异或和>>>16运算:2
    数组长度-1但是不进行异或和>>>16运算:14
    数组长度-1并且进行异或和>>>16运算:4
    数组长度-1并且进行异或和>>>16运算:14
    数组长度-1并且进行异或和>>>16运算:7
    数组长度-1并且进行异或和>>>16运算:13
    数组长度-1并且进行异或和>>>16运算:2

    一下就看出区别了哇,第一组返回的下标就只有0和16,第二组也只有2、8、14,第三组的下标就很分散,这才是我们想要的

    这结合hashMap来看,前两组造成的影响就是key几乎全部怼到同一个桶里,及其不分散,用行话讲就是有太多的hash冲突,这对hashMap的性能有很大影响,hash冲突造成的链表红黑树转换那些具体的原因这里就不展开说了
    而且!!
    而且!!
    而且!!
    如果数组长度不 - 1,刚上面也看到了,会返回16这个下标,数组总共长度才16,下标最大才15,16越界了呀

    原理

    知道了结果,现在说说其中的玄学

    1、为什么数组长度要 - 1,直接数组长度&key.hashCode不行吗?

    我们先不考虑数组下标越界的问题,hashMap默认长度是16,看看16的二进制码是多少

    log.info("16的二进制码:{}",Integer.toBinaryString(16));  
    //16的二进制码:10000,
    

    再看看key.hashCode()的二进制码是多少,以郭德纲为例

    log.info("key的二进制码:{}",Integer.toBinaryString("郭德纲".hashCode()));
    //key的二进制码:10001011000001111110001000
    
    length & key.hashCode()  => 10000 & 10001011000001111110001000
    位数不够,高位补0,即
    
    0000 0000 0000 0000 0000 0001 0000 
                    & 
    0010 0010 1100 0001 1111 1000 1000
    
    &运算规则是第一个操作数的的第n位于第二个操作数的第n位都为1才为1,否则为0
    所以结果为0000 0000 0000 0000 0000 0000 0000,即 0
    

    在这里插入图片描述

    冷静分析,问题就出在16的二进制码上,它码是10000,只有遇到hash值二进制码倒数第五位为1的key他们&运算的结果才不等于0,这句话好好理解下,看不懂就别强制看,去摸会儿鱼再回来看

    再来看16-1的二进制码,它码是1111,同样用郭德纲这个key来举例

    (length-1) & key.hashCode()  => 1111 & 10001011000001111110001000
    位数不够,高位补0,即
    
    0000 0000 0000 0000 0000 0000 1111 
                    & 
    0010 0010 1100 0001 1111 1000 1000
    
    &运算规则是第一个操作数的的第n位于第二个操作数的第n位都为1才为1,否则为0
    所以结果为0000 0000 0000 0000 0000 0000 1000,即 8
    

    如果还看不出这其中的玄机,你就多搞几个key来试试,总之记住,限制它们&运算的结果就会有很多种可能性了,不再受到hash值二进制码倒数第五位为1才能为1的限制

    2、为什么要length-1&key.hashCode计算下标,而不是用key.hashCode%length?

    这个其实衍生出三个知识点

    1、其实(length-1)&key.hashCode计算出来的值和key.hashCode%length是一样的

    log.info("(length-1)&key.hashCode:{}",15&"郭德纲".hashCode());
    log.info("key.hashCode%length:{}","郭德纲".hashCode()%16);
    
    //  (length-1)&key.hashCode:8
    //  key.hashCode%length:8
    

    那你可能更蒙逼了,都一样的为啥不用%,这就要说到第二个知识点

    2、只有当length为2的n次方时,(length-1)&key.hashCode才等于key.hashCode%length,比如当length为15时

    log.info("(length-1)&key的hash值:{}",14&"郭德纲".hashCode());
    log.info("key的hash值%length:{}","郭德纲".hashCode()%15);
    
    //  (length-1)&key.hashCode:8
    //  key.hashCode%length:3
    

    可能又有小朋友会思考,我不管那我就想用%运算,要用魔法打败魔法,请看第三点

    3、用&而不用%是为了提高计算性能,对于处理器来讲,&运算的效率是高于%运算的,就这么简单,除此之外,除法的效率也没&高

    3、为什么要进行^运算,|运算、&运算不行吗?

    这是异或运算符,第一个操作数的的第n位于第二个操作数的第n位相反才为1,否则为0
    我们多算几个key的值出来对比

    //不进行异或运算返回的数组下标
    log.info("郭德纲:{}", Integer.toBinaryString("郭德纲".hashCode()));            
    log.info("彭于晏:{}", Integer.toBinaryString("彭于晏".hashCode()));            
    log.info("李小龙:{}", Integer.toBinaryString("李小龙".hashCode()));            
    log.info("蔡徐鸡:{}", Integer.toBinaryString("蔡徐鸡".hashCode()));            
    log.info("唱跳rap篮球鸡叫:{}", Integer.toBinaryString("唱跳rap篮球鸡叫".hashCode()));
    
    00001000101100000111111000 1000
    00000101110000001000011010 1110
    00000110001111100100010011 1000
    00000111111111111100010111 0010
    10111010111100100011001111 1110
    
    进行&运算,看下它们返回的数组下标,length为16的话,只看后四位即可
    8
    14
    8
    2
    14
    
    
    //进行异或运算返回的数组下标
    log.info("郭德纲:{}", Integer.toBinaryString("郭德纲".hashCode()^("郭德纲".hashCode()>>>16)));                  
    log.info("彭于晏:{}", Integer.toBinaryString("彭于晏".hashCode()^("彭于晏".hashCode()>>>16)));                  
    log.info("李小龙:{}", Integer.toBinaryString("李小龙".hashCode()^("李小龙".hashCode()>>>16)));                  
    log.info("蔡徐鸡:{}", Integer.toBinaryString("蔡徐鸡".hashCode()^("蔡徐鸡".hashCode()>>>16)));                  
    log.info("唱跳rap篮球鸡叫:{}", Integer.toBinaryString("唱跳rap篮球鸡叫".hashCode()^("唱跳rap篮球鸡叫".hashCode()>>>16)));
    
    0000001000101100000111011010 0100
    0000000101110000001000001101 1110
    0000000110001111100100001011 0111
    0000000111111111111100001000 1101
    0010111010111100101000100100 0010
    
    进行&运算,看下它们返回的数组下标,length为16的话,只看后四位即可
    4
    14
    7
    13
    2
    
    

    很明显,做了^运算的数组下标更分散

    如果还不死心,再来看几个例子

    看下 ^、|、&这三个位运算的结果就知道了

    log.info("^ 运算:{}", 15 & ("郭德纲".hashCode() ^ ("郭德纲".hashCode() >>> 16)));  
    log.info("^ 运算:{}", 15 & ("彭于晏".hashCode() ^ ("彭于晏".hashCode() >>> 16)));  
    log.info("^ 运算:{}", 15 & ("李小龙".hashCode() ^ ("李小龙".hashCode() >>> 16)));  
    log.info("^ 运算:{}", 15 & ("蔡徐鸡".hashCode() ^ ("蔡徐鸡".hashCode() >>> 16)));  
    //^ 运算:4      
    //^ 运算:14     
    //^ 运算:7      
    //^ 运算:13      
                                                                                   
    log.info("| 运算:{}", 15 & ("郭德纲".hashCode() | ("郭德纲".hashCode() >>> 16)));  
    log.info("| 运算:{}", 15 & ("彭于晏".hashCode() | ("彭于晏".hashCode() >>> 16)));  
    log.info("| 运算:{}", 15 & ("李小龙".hashCode() | ("李小龙".hashCode() >>> 16)));  
    log.info("| 运算:{}", 15 & ("蔡徐鸡".hashCode() | ("蔡徐鸡".hashCode() >>> 16)));  
    //| 运算:12     
    //| 运算:14     
    //| 运算:15     
    //| 运算:15  
                                                                                               
    log.info("& 运算:{}", 15 & ("郭德纲".hashCode() & ("郭德纲".hashCode() >>> 16)));  
    log.info("& 运算:{}", 15 & ("彭于晏".hashCode() & ("彭于晏".hashCode() >>> 16)));  
    log.info("& 运算:{}", 15 & ("李小龙".hashCode() & ("李小龙".hashCode() >>> 16)));  
    log.info("& 运算:{}", 15 & ("蔡徐鸡".hashCode() & ("蔡徐鸡".hashCode() >>> 16))); 
    //& 运算:8      
    //& 运算:0      
    //& 运算:8      
    //& 运算:2   
    

    现在看出来了吧,^ 运算的下标分散,具体原理在下文会说

    4、为什么要>>>16,>>>15不行吗?

    这是无符号右移16位,位数不够,高位补0

    现在来说进行 ^ 运算中的玄学,其实>>>16和 ^ 运算是相辅相成的关系,这一套操作是为了保留hash值高16位和低16位的特征,因为数组长度(按默认的16来算)减1后的二进制码低16位永远是1111,我们肯定要尽可能的让1111和hash值产生联系,但是很显然,如果只是1111&hash值的话,1111只会与hash值的低四位产生联系,也就是说这种算法出来的值只保留了hash值低四位的特征,前面还有28位的特征全部丢失了;

    因为&运算是都为1才为1,1111我们肯定是改变不了的,只有从hash值入手,所以hashMap作者采用了 key.hashCode() ^ (key.hashCode() >>> 16) 这个巧妙的扰动算法,key的hash值经过无符号右移16位,再与key原来的hash值进行 ^ 运算,就能很好的保留hash值的所有特征,这种离散效果才是我们最想要的。

    上面这两段话就是理解>>>16和 ^ 运算的精髓所在,如果没看懂,建议你休息一会儿再回来看,总之记住,目的都是为了让数组下标更分散

    再补充一点点,其实并不是非得右移16位,如下面得测试,右移8位右移12位都能起到很好的扰动效果,但是hash值的二进制码是32位,所以最理想的肯定是折半咯,雨露均沾

    log.info(">>>16运算:{}", 15 & ("郭德纲".hashCode() ^ ("郭德纲".hashCode() >>> 16)));
    log.info(">>>16运算:{}", 15 & ("彭于晏".hashCode() ^ ("彭于晏".hashCode() >>> 16)));
    log.info(">>>16运算:{}", 15 & ("李小龙".hashCode() ^ ("李小龙".hashCode() >>> 16)));
    log.info(">>>16运算:{}", 15 & ("蔡徐鸡".hashCode() ^ ("蔡徐鸡".hashCode() >>> 16)));
    //>>>16运算:4  
    //>>>16运算:14 
    //>>>16运算:7  
    //>>>16运算:13
       
    log.info(">>>16运算:{}", 15 & ("郭德纲".hashCode() ^ ("郭德纲".hashCode() >>> 8))); 
    log.info(">>>16运算:{}", 15 & ("彭于晏".hashCode() ^ ("彭于晏".hashCode() >>> 8))); 
    log.info(">>>16运算:{}", 15 & ("李小龙".hashCode() ^ ("李小龙".hashCode() >>> 8))); 
    log.info(">>>16运算:{}", 15 & ("蔡徐鸡".hashCode() ^ ("蔡徐鸡".hashCode() >>> 8))); 
    //>>>8运算:7
    //>>>8运算:1
    //>>>8运算:9
    //>>>8运算:3 
    
    log.info(">>>16运算:{}", 15 & ("郭德纲".hashCode() ^ ("郭德纲".hashCode() >>> 12)));
    log.info(">>>16运算:{}", 15 & ("彭于晏".hashCode() ^ ("彭于晏".hashCode() >>> 12)));
    log.info(">>>16运算:{}", 15 & ("李小龙".hashCode() ^ ("李小龙".hashCode() >>> 12)));
    log.info(">>>16运算:{}", 15 & ("蔡徐鸡".hashCode() ^ ("蔡徐鸡".hashCode() >>> 12)));
    //>>>12运算:9 
    //>>>12运算:12
    //>>>12运算:1 
    //>>>12运算:13
    

    搞java你是避不开hash家族的,与其逃避不如花点心思彻底搞懂!

    嘤嘤嘤~ 写了整整一天终于我写完了

    嘤嘤嘤~ 好害羞

    嘤嘤嘤~ 好紧张

    展开全文
  • Geohash算法

    千次阅读 2022-01-27 14:08:38
    如果把某个区域或整个地图上的地理位置都按照Geohash编码,则会得到一个网格,编码递归粒度越细,网格的矩形区域越小,geohash编码的长度越大,则Geohash编码越精确。 不同的编码长度,生成的网格与实际地理的精度...

    用户附近位置计算

    经纬度与物理距离介绍

    经纬度是经度与纬度的合称组成一个坐标系统,称为地理坐标系统,它是一种利用三度空间的球面来定义地球上的空间的球面坐标系统,能够标示地球上的任何一个位置

    img

    在一定误差范围内,通常情况下,经纬线和米的换算为:经度或者纬度0.00001度,约等于1米。以下表格列出更细致的换算关系:

    在纬度相等的情况下在经度相等的情况下
    经度每隔0.00001度,距离相差约1米;每隔0.0001度,距离相差约10米;每隔0.001度,距离相差约100米;每隔0.01度,距离相差约1000米;每隔0.1度,距离相差约10000米。纬度每隔0.00001度,距离相差约1.1米;每隔0.0001度,距离相差约11米;每隔0.001度,距离相差约111米;每隔0.01度,距离相差约1113米;每隔0.1度,距离相差约11132米。

    地图坐标系

    WGS84坐标系地球坐标系,国际通用坐标系
    GCJ02坐标系火星坐标系,WGS84坐标系加密后的坐标系;Google国内地图、高德、QQ地图 使用
    BD09坐标系百度坐标系,GCJ02坐标系加密后的坐标系

    注:如果使用GCJ-02坐标系,Geohash函数和距离计算函数理论上都应在WGS84坐标系下使用,在火星坐标系下会存在一定的偏差,主要是火星坐标系的加偏处理带来的,经过查阅资料及抽样测试,认为该误差在可接受范围内。

    Geohash算法介绍

    GeoHash是空间索引的一种方式,其基本原理是将地球理解为一个二维平面,通过把二维的空间经纬度数据编码为一个字符串,可以把平面递归分解成更小的子块,每个子块在一定经纬度范围内拥有相同的编码。

    以GeoHash方式建立空间索引,可以提高对空间poi数据进行经纬度检索的效率。

    编码规则为:先将纬度范围(-90, 90)平分成两个区间(-90, 0)和(0, 90),如果目标维度位于前一个区间,则编码为0,否则编码为1,然后根据目标纬度所落的区间再平均分成两个区间进行编码,以此类推,直到精度满足要求,经度也用同样的算法,对(-180, 180)依次细分,然后合并经度和纬度的编码,奇数位放纬度,偶数位放经度,组成一串新的二进制编码,按照Base32进行编码。

    示例

    以当前所在办公区【两江国际】的位置坐标为例, 经纬度为(104.059684,30.559545)

    第一步:将经纬度转换为二进制

    序号纬度范围划分区间0划分区间130.559545所属区间
    1(-90, 90)(-90, 0.0)(0.0, 90)1
    2(0.0, 90)(0.0, 45.0)(45.0, 90)0
    3(0.0, 45.0)(0.0, 22.5)(22.5, 45.0)1
    4(22.5, 45.0)(22.5, 33.75)(33.75, 45.0)0
    5(22.5, 33.75)(22.5, 28.125)(28.125, 33.75)1
    6(28.125, 33.75)(28.125, 30.9375)(30.9375, 33.75)0
    7(28.125, 30.9375)(28.125, 29.53125)(29.53125, 30.9375)1
    8(29.53125, 30.9375)(29.53125, 30.234375)(30.234375, 30.9375)1
    9(30.234375, 30.9375)(30.234375, 30.5859375)(30.5859375, 30.9375)0
    10(30.234375, 30.5859375)(30.234375, 30.41015625)(30.41015625, 30.5859375)1
    11(30.41015625, 30.5859375)(30.41015625, 30.498046875)(30.498046875, 30.5859375)1
    12(30.498046875, 30.5859375)(30.498046875, 30.541992188)(30.541992188, 30.5859375)1
    13(30.541992188, 30.5859375)(30.541992188, 30.563964844)(30.563964844, 30.5859375)0
    14(30.541992188, 30.563964844)(30.541992188, 30.552978516)(30.552978516, 30.563964844)1
    15(30.552978516, 30.563964844)(30.552978516, 30.55847168)(30.55847168, 30.563964844)1

    最后得到维度的二进制编码为:101010110111011, 用同样的方式可以得到精度(104.059684)的二进制编码:110010011111111

    第二步:将经纬度的二进制编码合并

    从偶数0开始,经度占偶数位,纬度占奇数位。

    序号01234567891011121314151617181920212223242526272829
    编码111001001100011110111111101111

    第三步:将合并后的二进制数做Base32编码

    按照每5位一组,分成6组,每组计算其对应的十进制数值,按照Base32进行编码。

    Base32编码表的其中一种如下,是用0-9、b-z(去掉a, i, l, o)这32个字母进行编码.

    img

    11100 10011 00011 11011 11111 01111
    28(w) 19(m) 3(3)  27(v) 31(z) 15(g)
    

    最终得到的经纬度编码为:wm3vzg

    如上文二进制编码的计算过程,如果递归的次数越大,则生成的二进制编码越长,因此生成的geohash编码越长,位置越精确。目前Geohash使用的精度说明如下:

    img

    GeoHash用一个字符串表示经度和纬度两个坐标, 比直接用经纬度的高效很多,而且使用者可以发布地址编码,既能表明自己位于某位置附近,又不至于暴露自己的精确坐标,有助于隐私保护。

    编码过程中,通过二分范围匹配的方式来决定某个经纬坐标是编码为1还是0,因此某些邻近坐标的编码是相同的,因此GeoHash表示的并不是一个点,而是一个矩形区域。 GeoHash编码的前缀可以表示更大的区域。例如wm3vzg,它的前缀wm3vz表示包含编码wm3vzg在内的更大范围。 这个特性可以用于附近地点搜索。

    如果把某个区域或整个地图上的地理位置都按照Geohash编码,则会得到一个网格,编码递归粒度越细,网格的矩形区域越小,geohash编码的长度越大,则Geohash编码越精确。 不同的编码长度,生成的网格与实际地理的精度如下(Geohash字符串编码长度对应网格大小)

    字符串长度网格宽度网格高度
    15000Km5000Km
    21250Km625Km
    3156Km156Km
    439.1Km19.5Km
    54.89Km4.89Km
    61.22Km0.61Km
    7153m153m
    838.2m19.1m
    94.77m4.77m
    101.19m0.596m

    Geohash编码与网格

    当前选取的编码长度为6,因此一个网格实际的地理差异在1.2公里与0.6公里,示例中两江国际对应的网格大致效果如图:

    img

    邻近网格位置推算

    结论

    根据Geohash的编码规则将经纬度分解到二进制,结合地理常识,中心网格在南北(上下)方向上体现为纬度的变化,往北则维度的二进制加1,往南则维度的二进制减1,在东西(左右)方向上体现为经度的变化,往东则经度的二进制加1,往西则减1,可以计算出上下左右四个网格经纬度的二进制编码,再将加减得出的经纬度两两组合,计算出左上、左下、右上和右下四个网格的经纬度二进制编码,从而就可以根据Geohash的编码规则计算出周围八个网格的字符串。

    正向推导

    以Geohash编码长度为6为基础,网格的宽高与实际距离换算为:1.2Km*0.6Km.

    参考上文提到的,在经度相同情况下,每隔0.001度,距离相差约111米。0.6Km换算为纬度为:0.005405405。

    当前两江国际粗粒度的wgs84坐标(104.05503,30.562251), 纬度二进制编码:101010110111011,经度二进制编码:110010011111111, Geohash值为:wm3vzg

    正北方向近邻的网格维度为增加一个网格的高度,即纬度增加0.005405405,为:30.562251 + 0.005405405 = 30.567656405, 转换为二进制编码后为(可用工具快速转换):101010110111100

    正好是原纬度的二进制编码101010110111011 加1后的结果(101010110111011 + 000000000000001 = 101010110111100)

    反向推导

    当前两江国际粗粒度的wgs84坐标(104.05503,30.562251), 纬度二进制编码:101010110111011,经度二进制编码:110010011111111, Geohash值为:wm3vzg

    基于当前坐标的网格,正北方向近邻的网格N,其纬度二进制加1后为:101010110111100,经度不变,其Geohash值为:wm3vzu

    通过http://geohash.co/ 反向转换其经纬坐标为:(104.0570068359375,30.56671142578125)

    通过https://www.box3.cn/tools/lbs.html 查询2个坐标的实际位置,误差在531m(符合精度范围)

    img

    邻近8个网格位置计算

    **Geohash编码:**wm3vzs纬度二进制编码:101010110111100经度二进制编码:110010011111110公式:(Lat_bin + 1, Lon_bin - 1)**Geohash编码:**wm3vzu纬度二进制编码:101010110111100经度二进制编码:110100101101010公式:(Lat_bin + 1, Lon_bin)**Geohash编码:**wm6jbh纬度二进制编码:101010110111100经度二进制编码:110010100000000公式:(Lat_bin + 1, Lon_bin + 1)
    **Geohash编码:**wm3vze纬度二进制编码:101010110111011经度二进制编码:110010011111110公式:(Lat_bin, Lon_bin - 1)**Geohash编码:**wm3vzg纬度二进制编码:101010110111011经度二进制编码:110010011111111公式:(Lat_bin, Lon_bin)**Geohash编码:**wm6jb5纬度二进制编码:101010110111011经度二进制编码:110010100000000公式:(Lat_bin, Lon_bin + 1)
    **Geohash编码:**wm3vzd纬度二进制编码:101010110111010经度二进制编码:110010011111110公式:(Lat_bin - 1, Lon_bin - 1)**Geohash编码:**wm3vzf纬度二进制编码:101010110111010经度二进制编码:110010011111111公式:(Lat_bin - 1, Lon_bin)**Geohash编码:**wm6jb4纬度二进制编码:101010110111010经度二进制编码:110010100000000公式:(Lat_bin - 1, Lon_bin + 1)

    附近3公里网格模型

    img

    青色代表:用户位置的网格编码,红色代表:附近附近3公里的网格编码

    展开全文
  • 弄明白HASH,你就弄明白区块链的一大半

    万次阅读 多人点赞 2021-06-14 00:46:43
    依此方法,上面16个HASH输出也就是(省略号代表省略了后面的位): HASH01 c7………:11000111…………………… HASH02 9a………:10011010…………………… HASH03 b1………:10110001…………………… HASH04 24...

    “人类历史上第一次,全世界各地的人,花费巨额的成本,争前恐后地寻找美学意义上的数学运算结果。”

    —卫sir

    Beeple加密艺术作品《区块链》

    说起区块链,似乎大家都懂一点,再往细里一问,似乎又都不懂了。

    比如,你问一个人:为什么要挖矿,挖的到底是啥。

    怕是没几个明白人。

    本文就是要给你讲明白!

    前言

    人们一说起区块链,就常常说防篡改防篡改,那么,这个防篡改是怎么做到的呢。

    主要靠HASH。

    人们所常说的挖矿,其实是在挖HASH。

    挖一个长得很好看的HASH。

    但,什么是HASH?

    外行人是说不清的,内行人,似乎也很少能给外行人讲明白。

    很多人喜欢用比喻的方式给外行人讲HASH,其实,你就是弄100个比喻(什么麻将、扑克、骰子啥的),不懂HASH的人还不懂。

    他们中比较傻白甜的,甚至会想,挖矿是在挖麻将吗?

    真正想弄明白HASH,就让他看看HASH长什么样子呗!!

    HASH到底是个啥

    HASH是一个算法,你给它一串数,它给你一串数。

    你给它的叫输入,它给你的叫输出。

    也就是说,将数据输入给HASH函数,HASH函数输出一串数。

    HASH( 输入 )= 输出

    这就好比你把一头猪输入给一个香肠机,香肠机给你输出一段香肠。

    看个例子吧,我们以最常见的HASH算法MD5为例。(当然,有很多种HASH算法,MD5是其中最知名的一个。)

    MD5 ("weijianfan") = c49262b1117b9fd1d6ebd74aaa016f3e

    上面这个例子中,“weijianfan”是输入,后面那串数是输出。

    再如:

    MD5 ("weiyuerenhua") = a799c7c504a1a80f95ebe69a86c42637

    注意,HASH函数有个重要的特点,不管输入多长,输出都是固定长度的。

    当然,和一般的算法一样,只要输入不变,输出是不变的。

    比如MD5,输入是不限制长度的,输出就是128位的二进制,也就是16个字节的十六进制。像上面第一个例子里,c4就是一个字节,代表了8位的二进制,即11000100,最后那个3e也是一个字节,也即00111110

    我们把输入搞长点:

    MD5 ("In Math We Trust.") = 767fa54f12bab6b71fb411f265814bb7

    把汉字作为输入:

    MD5 ("博鳌亚洲论坛2021年年会数字支付与数字货币分论坛4月18日晚举行。") = 36b5e89c797d22d14ccefe4ec79f56c2

    再搞长点:

    MD5 ("Andreas M. Antonopoulos is a noted technologist and serial entrepreneur who has become one of the most well-known and well-respected figures in bitcoin. An engaging public speaker, teacher, and writer, Andreas makes complex subjects accessible and easy to understand. Andreas advises multiple technology startups and speaks regularly at conferences and community events around the world.") = 5ac503b01e213d4794d92134096ad313

    长一点的汉字:

    MD5 ( "Andreas M. Antonopoulos 是⼀位著名的技术学家和连续创业企业家,⽐特币界最著名和倍受尊敬的⼈物之⼀。⾝为⼀名迷 ⼈的公共演说家、教师和作家,他善于把复杂的问题变得简单⽽易于理解。作为⼀名顾问,他则帮助初创者认知、评估并指 引减⼩安全和业务风险。") = 90f039293e0b3da5516e251b93434795

    HASH还有一个特点,只要输入有一点点的变化,输出都会完全不同,就好像输入是完全不同的。

    比如把上面这段文字中“一位”里的“一”字删掉,再做HASH:

    MD5 ("Andreas M. Antonopoulos 是位著名的技术学家和连续创业企业家,⽐特币界最著名和倍受尊敬的⼈物之⼀。⾝为⼀名迷 ⼈的公共演说家、教师和作家,他善于把复杂的问题变得简单⽽易于理解。作为⼀名顾问,他则帮助初创者认知、评估并指 引减⼩安全和业务⻛险。") = 159c9d192e45fbd2eaa0c3f068a78508

    看到了吧,输入有微小的变化,输出会完全不同。

    HSAH对输入是不挑的,不管是字符串,还是文件,不管是文本、图像、视频,只要是数字的,都当作二进制输入就是了。

    比如,把下面这幅图像给MD5,可以得到:

    MD5 (Emily Blunt.jpg) = b818d284ef28f733c701f7bc1ee5f669

    图|艾米莉布朗特,英国最受欢迎的女演员

    如果你的电脑上有md5工具,你就可以试试自己做HASH,比如在mac电脑里,在“终端”中输入md5 -s "xxx",或者md5 1.txt就可以对字符串或者文件进行md5。

    若干G的视频文件也没问题:

    MD5 (伟大的转折-01.mp4) = 9093c85d13f79609978f52c48e19aa65

    图|38集革命历史剧《伟大的转折》,遵义会议会址

    你哪怕是改动了这个视频中任何一帧的任何一个像素,MD5算出来的结果都截然不同。

    所以,判断一个文件是不是被人改动过,算一下HASH就行,HASH只要没变,文件就没有被动过。(前提是这个HASH算法还不错!)

    现在你对HASH大概有点印象了吧,反正只要是数字的输入,都能给你整出一段固定长度的输出,而且个个都不一样。

    啥是好看的HASH

    答:好看的HASH就是前面有很多位0的HASH。—卫sir

    HASH输出是比较均匀分布的,基本上,你对任意16个不同的输入做HASH,第1位是0的概率是1/2(大概有8个),前两位是0的概率是1/4,前3位是0的概率是1/8,前4位都是0的概率为1/16。

    我们做个实验看看对不对,以下的输入都是随意给的:

    1、MD5 ("ionnoouyd") = c78a3b60314d11fc9e739aef407989f5
    2、MD5 ("njjiuhbh") = 9aee0690f6002392b2c6fc0d2224adb2
    3、MD5 ("88990933") = b19bf0928fc649d99b1cdf02748ae88e
    4、MD5 ("-sr&&fvbgt") = 24cc429a2636ac1b9092cf3f681bba09
    5、MD5 ("区块链技术") = 649e6048a32c09299e1c952347ccac7e
    6、MD5 ("hashcash is very good") = 8015b497b3a9bd6ca7ba1213a731b1a1
    7、MD5 ("CC0-MIT") = cd08de7f0f219d8e13437c65974f9773
    8、MD5 ("beihaimuchang") = 7cd9a24efce05bbceb01c9020d904294
    9、MD5 ("wqqwrr2") = 1cb1797fb57add01523fbd6e86ca2b73
    10、MD5 ("1123ed") = ae49266f10e08922780afeb664fd61dc
    11、MD5 ("hello world") = 5eb63bbbe01eeed093cb22bb8f5acdc3
    12、MD5 ("niahoa...") = 5d3e60365ff999e68a932da4619a129b
    13、MD5 ("blockchain") = 5510a843bc1b7acb9507a5f71de51b98
    14、MD5 ("随机发均出版后我给") = 18eb95457ec90f1c33fa5914579730d7
    15、MD5 ("93002712") = 0abf0bd1dbb35366c56b26d157686f0f
    16、MD5 ("13811031123") = 940ca3847eec1e99e716975bc7096c8d

    前面说过,MD5输出是128位的,上面是用16进制展示的,比如第一个输出的第1字节是“c7”,第二个输出的第1字节是“9a”,用2进制表示就是“11000111”、“10011010”。依此方法,上面16个HASH输出也就是(省略号代表省略了后面的位):

    HASH01  c7………:11000111……………………
    HASH02  9a………:10011010……………………
    HASH03  b1………:10110001……………………
    HASH04  24………:00100100……………………
    HASH05  64………:01100100……………………
    HASH06  80………:10000000……………………
    HASH07  cd………:11001101……………………
    HASH08  7c………:01111100……………………
    HASH09  1c………:00011100……………………
    HASH10  ae………:10101110……………………
    HASH11  5e………:01011110……………………
    HASH12  5d………:01011101……………………
    HASH13  55………:01010101……………………
    HASH14  18………:00011000……………………
    HASH15  0a………:00001010……………………
    HASH16  94………:10010100……………………

    你们可以数数,前1位、前2位、前3位、前4位是0的HASH个数,是不是和上面说的概率差不多?

    当然,我最喜欢的是那个前4位都是0的,HASH15,它在这16位里面是长得最好看的。

    它出现的概率大概就是每16个HASH里面出一个。也就是2^4次出一个。

    那么,多少次才会出来一个前20位都是0的HASH呢。

    2^20次。

    2^20就是2的20次方,就是1,048,576这么多啦!一百万还多啦!所以想在你的电脑上找到它,得算一会呢~

    前20位是0,就是16进制前5个数为0,大概就是下面这个样子

    00000fc7f1d91e9053995f707a90971d

    是不是很好看?

    至少比前面出现过的都好看。

    当然还不是最最好看的,全宇宙举世无双好看的那个HASH,是全0。

    这个全0的HASH,应该还从来没有被算出来过,不知道人类灭亡前能否靠运气找出来。

    总之,我说的好看,就是前面有很多个0。

    0越多,越好看。

    好的HASH算法有什么特点?

    注意HASH算法有很多,比如MD5、SHA-1、SHA-2等,再如BTC用的SHA-256和RIPEMD-160等。

    至少有这么两个特点:

    1、对于任意两个不同的输入,应该产生不同的输出。(这叫抗碰撞)

    2、正向计算很容易,反过来从输出倒推输入,就非常难,只能靠暴力猜。(这叫不可逆)

    先看第一个特点:抗碰撞

    一个好的HASH算法,对于任意两个不同的输入,应该产生不同的输出。

    事实证明,MD5、SHA-1不能算很好的HASH算法,因为王小云院士等人,已经可以找到两个不同的输入,产生相同的HASH输出。具体可以看看相关文章12

    如何形象理解这个特点呢?

    首先,这个HASH算法的输出必须要有一定的长度,如果长度不够,肯定会有重复的。比如假设一个HASH算法,输出只有1位,输出不是0就是1,那是不是运行两、三次,就能找到了不同输入相同输出了呢!如果输出只有两位,这个HASH的输出就只有4种可能,00、01、10、11,那是不是运行四、五次,就能找到不同输入相同输出了呢!

    所以MD5有128位这么长,SHA-256有256位这么长!

    其次,要保障HASH值是非常随机、非常均匀地落在整个输出空间上。而且输入有一点点的不同,输出都会全然的不同。

    这样,就有了一种ID的效果,HASH就像是每个输入各异的“指纹”。比如,你把1000万份不同的文件都做了HASH,每份文件都获得一个独一无二的HASH值,就可以把这个当作是一个文件的ID。每个ID都指代了一个独一无二的文件,如果再遇到ID相同的,就表明遇到相同的文件了。

    再次,要能理解,输出的空间是非常大的。

    对于像RSA-256这样的算法,其输出位数为256位,那么可能的值就会有10^78个(也即2^256个),这是多么大的一个数呢?

    全地球沙子的数量(不只是海滩上的,而是所有),有人估算过,大致是7*10^21个,还不到10^22个。

    全宇宙星球的数量,也大致不过7*10^22个,还不到10^23个。

    你给它两个不同的输入,它产生相同输出的概率,比下面这个例子中的概率还要小得多:

    你随便在一个星球上选了一粒沙子,另外一个人,在完全不受你影响的情况下,也随机在某个星球上随机选了一粒沙子,结果你俩选择了同一粒沙子!然后你俩还不约而同地选择了这个沙子中的同一个原子!

    现在看第二个特点:不可逆

    一个好的HASH算法,要求正向计算很快,但反向几乎不可能。

    比如,我现在有一个BTC私钥,形如:

    5HvrDrdQ9EpJTcJHXuctU9vUjydzuZ1????????????????DCHa

    为了保密,我把其中16个字符用?代替。

    计算出这个私钥的MD5值为:630a0cec43d49095027b224ea0f2b317

    那么,请问,全世界的黑客,有没有能力通过破解MD5,得到我这个私钥呢?

    答案是:按照现在的能力,不能。

    黑客的做法,只能是,不断尝试这16个?号可能的组合,计算其MD5值,以期有一天能算出相同的MD5值。

    但这种暴力猜解需要很长时间。(大致毛估一下,以目前的技术,如果全世界黑客联合起来,拥有类比全球BTC挖矿那么大的算力,那也至少要算5年。)

    那么,挖矿是在干什么

    2021年6月13日18:09:30,BTC矿工们挖出一个HASH:

    00000000000000000009813c8a3b95e3a75d878419547b7fe4dd71f9dc71da72

    看看这个HASH多么漂亮!它的前面有多少个0!

    上面是用16进制表示的,所以,每个0其实是二进制的0000,所以上面那个HASH,前面是19*4=76个二进制的0!

    这个HASH是一个区块的HASH(严格的说,是这个区块头部的HASH)。

    最近每10分钟就出一个这么漂亮的。

    矿工们做了多少次HASH才做出这么漂亮个HASH呢?

    不知道,反正平均2^76次才会出现一个这样的,你说做了多少次呢。

    他们这么费劲挖这个,图啥呢?

    图这个区块奖励的BTC。

    挖出这个区块的矿工(可能是很多人一起挖的),得到了6.54164549个BTC,其中6.25个是系统奖励的,剩下的是赚的手续费。

    哦,我大致明白HASH了,区块又是什么?

    现在给大家讲讲区块链的老祖宗—BTC—的工作原理。

    如果一遍看不懂,就看两遍,两遍看不懂,就大声读第三遍。

    一般都能读懂。

    1、互联网中若干个节点(节点就是计算机啦!)同时运行BTC软件。这些软件是开源的,谁都可以下载了来运行(本文说的节点是指全功能节点,全球目前大约有1000个左右)。

    2、人们如果要发起BTC转账(也即交易),就让某个节点在互联网广播转账信息,此交易很快传遍全网每个节点。每个节点都会检查它所收到的交易是否符合逻辑(比如有没有那么多钱来转账),如果不对,就会把这个交易抛弃掉。

    转账就是:张三给李四发送1个BTC,王五给赵六发送0.1个BTC,诸如此类。差不多就是这个意思,每一笔转账也叫一个交易。

    3、平均每隔一段时间(平均10分钟),网内某个节点就会率先打包出一个区块,区块里面含有这段时间的所有交易数据,这个区块会广播到全网,每个节点都会收到该区块(大小在1M左右)。

    3a:打包是有条件的,这个区块的头部的HASH值必须很好看。
    
    3b:平均10分钟才出一个,这是由挖矿难度导致的。难度是动态调整的,每两周调整一次,调整使得全网平均每10分钟才能挖出一个区块。
    
    在一个完全去中心化的网络中,难度调整是如何做到的呢?方法是:每过2016个区块,所有节点都会自发地调整难度(写在代码里了)。新的难度是由最近2016个区块的花费时长与20160分钟(两周)比较后调整得出的。如果花费时间短于20160分钟,就将难度调大一些,反之亦然则调小一些。难度可以简单地理解为要求HASH值前面有多少个0。
    
    3c:每个10分钟内,世界上都会发生很多笔交易,这些交易都等着打包(最终只有打包在区块里的交易才被人们承认)。每个试图打包的矿工,把自己收到的、尚未打包的交易,放在区块里(由于区块大小的限制,平均一个区块能装大约2000多个交易),然后通过填充区块中的随机数区域,计算HASH,以期找到一个好看的HASH(符合难度就叫好看),找到了就叫打包成功(也就是挖矿成功),赶紧广播出去。
    
    3d:每次收到广播来的区块,各节点检验该区块是否符合对区块的要求(至少HASH要好看嘛!),如果符合,就把此块保存下来,然后开始试图出下一个块(也即继续挖矿),把已经收到但尚未打包的交易打包进入下一个要出的块。

    4、所有节点都在抢着打包,因为谁能正确打包谁就能得到BTC奖励。

    4a:每成功出一个区块,打包者将会被奖励若干个BTC。最早一开始是奖励50个,每210000个区块(大约4年)奖励减半,所以后来是25个、12.5个、现在是6.25个,到2140年就会无币可挖。
    
    4b:事实上,矿工们除了可以得到系统的奖励,还能得到区块中的手续费。

    5、每个节点收到区块后,如果验证无误,就接受该区块,将其附加到自己保存的区块链上。

    5a:由于每个节点都和其他节点不断同步,所以每个节点(全功能节点)都保存着从第一个区块到现在这个区块的数据(目前已经产生将近70万个区块)。
    
    5b:一个区块的头部,会含有本区块体内全部交易的merkle根(其实也是一种HASH计算啦),如果区块体内的某个交易被篡改,可以通过计算merkle根,和头部的merkle根比较,从而发现篡改。
    
    5c:一个区块的头部,还会含有上个区块头部的HASH值(可以简称为区块的HASH)。这就可以校验上个区块是否完整、正确(因为任何数据差错,都做不出好看的HASH了)。你可以从最新的区块,一直追溯到创世区块(第一个区块),确保没有任何数据被改动过。

    5d:整个区块链上,如果其中任何一个区块,有任何一点点的篡改,都会导致这个区块的HASH值不再是一个好看的HASH,也会导致其后区块的HASH都不再好看,任何明眼人,都会知道数据不对了。而每个好看的HASH,都是全球若干矿工,使用若干矿机,花着若干电费,辛辛苦苦挖出来的。一个试图篡改区块的人或组织,没有这么强大的能力。

    结语

    现在,你是不是了解了HASH,了解了挖矿,了解了区块链为什么这么能防篡改了呢!

    我简单总结一下:

    HASH很容易计算,但反过来倒推就不容易;输入有一点改变,输出就会大变;对于一个好的HASH算法,不同的输入,肯定会是不同的输出,不用担心碰撞;HASH值可以当作ID来看待;通过对比HASH,可以判断输入是否被人改了。

    挖矿是为了给一个区块找一个好看的HASH,也即前面若干位是0的HASH;不管有多少节点在挖矿,都能够自动、简单地调整难度,使得保证大约10分钟才能找到一个好看的HASH;每个区块都将自己那个好看的HASH,放在下一个区块的头部;每个全节点都记录着所有区块的数据,而且可以很方便的验证所有区块没有被人改动过;如果有人想改历史区块里的数据,那要费老鼻子劲了!

    不过这只是一大半,还有一些东西你是不了解的,也不是本文所想描述的。

    你如果对其他的东西感兴趣,请留言。

    文|卫剑钒


    1. https://www.zhihu.com/question/19743262/answer/289095984 

    2. https://www.zhihu.com/question/56234281/answer/148349930

    展开全文
  • uthash简介

    千次阅读 2020-07-10 00:39:11
    文章目录C语言hash总结一、 uthash的使用Key类型为int时使用注意事项总结二、 完整的例子2.1 key为int2.2 key为字符数组2.3 key为字符 C语言hash总结 本文内容基本来自对官网的翻译,若有不准确的地方,望指正。 ​...
  • c开源hash项目 uthash的用法总结

    万次阅读 多人点赞 2019-07-14 21:22:48
    uthash 是C的比较优秀的开源代码,它实现了常见的hash操作函数,例如查找、插入、删除等待。该套开源代码采用宏的方式实现hash函数的相关功能,支持C语言的任意数据结构最为key值,甚至可以采用多个值作为key,无论...
  • Hashcat从入门到入土(一)

    千次阅读 2022-03-21 10:03:59
    Hashcat的官方是这么介绍自己的: Hashcat is a password recovery tool. It had a proprietary code base until 2015, but was then released as open source software. Versions are available for Linux, OS X, ...
  • hash破解-hashcat

    千次阅读 2020-04-29 10:30:14
    hashcat破解hash值自己搭建实验环境:1.了解hashcat2.了解JohnTheRipper3.了解zip试验步骤: 今天分享一个称之为世界上最快的密码破解工具hashcat 在渗透测试中我们经常会碰到一些加密处理的一串hash,有的在线的...
  • 开源库uthash第一弹uthash.h

    万次阅读 多人点赞 2019-04-05 17:14:28
    uthash是C的比较优秀的开源代码,它实现了常见的hash操作函数,例如查找、插入、删除等待。该套开源代码采用宏的方式实现hash函数的相关功能,支持C语言的任意数据结构最为key值,甚至可以采用多个值作为key,无论是...
  • //创建hashHASH **create_hash() { HASH **h = (HASH **)malloc(N * ADDR_SIZE); int i = 0; for (i = 0; i ; i++) { h[i] = (struct node *)malloc(sizeof(struct node)); h[i]->next = NULL; } return h; } //...
  • C语言哈希表uthash的使用方法详解(附下载链接)

    千次阅读 多人点赞 2020-08-08 09:13:16
    工科生一枚,热衷于底层技术开发,有强烈的好奇心,感兴趣内容包括单片机,嵌入式Linux,Uboot等,欢迎学习交流! 爱好跑步,打篮球,睡觉。...我们需要做的就是将头文件复制到您的项目中,然后:#include “uthash..
  • std::cout << "corned beef hash is " <<hash_str (food) ; 这里生成了一个函数对象,它用和前面章节中示例相同的方式来哈希 string 对象。本次测试的输出结果如下: corned beef hash is 3803755380 这里...
  • hashhash

    千次阅读 2019-08-31 17:10:23
    hash 桶 哈希桶就是为了解决哈希冲突 哈希桶算法其实就是链地址解决冲突的方 https://www.cnblogs.com/xqn2017/p/7997666.html https://blog.csdn.net/tanggao1314/article/details/51457585 ...
  • C开源hash代码uthash的用法总结

    千次阅读 2019-08-16 00:08:13
    uthash 是C的比较优秀的开源代码,它实现了常见的hash操作函数,例如查找、插入、删除等待。该套开源代码采用宏的方式实现hash函数的相关功能,支持C语言的任意数据结构最为key值,甚至可以采用多个值作为key,无论...
  • 一致性hash和redis中hash槽的区别

    千次阅读 多人点赞 2020-08-15 16:31:11
    一致性hash主要用于分布式系统中,用于解决数据选择节点存储、选择节点访问、增删节点后数据的迁移和重分布问题。redis集群并没有使用一致性hash,而是使用了hash槽来解决数据分配的问题。 一致性hash: 它是一个0...
  • 一致性hash算法

    千次阅读 2020-09-04 11:51:14
    一致性hash算法为什么会出现一致性hash传统hash算法的弊端顺序分区哈希分区节点取余分区一致性hash算法算法演示如何让key和缓存节点对应起来呢?增加节点有哪些key会受到影响呢?删除节点有哪些key会受到影响呢?...
  • Hash冲突以及如何解决Hash冲突

    千次阅读 2021-11-21 20:07:13
    一、哈希冲突 Hash冲突指的是在向Hash表中存数据时,首先要用Hash函数计算出该数据要存放的地址。但是在这个地址中已经有值存在,所以这个时候就发生了Hash冲突,
  • 一致性hash和普通hash区别?

    千次阅读 2020-07-29 15:31:22
    普通hash 定义 Hash函数:一般翻译做散列、杂凑,或音译为哈希,是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出,该输出就是散列值。 碰撞(冲突):如果两个关键字通过hash函数得到...
  • 如何找到周围8个区域的GeoHash编码

    热门讨论 2014-11-28 09:32:03
    如何找到周围8个区域的GeoHash编码, java版本的。
  • javascript hash的使用

    千次阅读 2022-03-24 14:44:27
    在javascript中,hash指的是哈希表,是一种根据关键字直接访问内存存储位置的数据结构;通过哈希表,数据元素的存放位置和数据元素的关键字之间建立起某种对应关系,建立这种对应关系的函数称为哈希函数。 hash就是...
  • hash主要操作函数

    千次阅读 2021-01-26 21:40:20
    hash主要操作函数 hash是一些列key value(field value)的映射表。常常用其存储一些对象实例。相对于把一个对象的各个字段存储为string,存储为hash会占用更少的内存。为什么会更省内存呢?需要搞清楚两个配置(hash-...
  • MySQL 开发组于 2019 年 10 月 14 日 正式发布了 MySQL 8.0.18 GA 版本,带来了一些新特性和增强功能。其中最引人注目的莫过于多表连接查询支持 hash join 方式了。
  • hashcat使用教程

    千次阅读 2020-03-20 16:25:32
    本文转载于:... hashcat官网:https://hashcat.net/hashcat/ GitHub项目:https://github.com/hashcat/hashcat 使用语法: ...hashcat.exe [选项] <哈希> <密码字典> ...
  • 其他文章: 安全系列之——手写JAVA加密、解密 安全系列之——数据传输的完整性、私密性、源认证、不可否认性 安全系列之——主流Hash散列算法介绍和使用 安全系列之——RSA的公钥私钥有多少人能分的清楚?...
  • sha1+'\n\nsha224值:'+hash_value_224+'\n\nsha256值:'+hash_value+'\n\nsha384值:'+hash_value_384+'\n\nsha512值:'+hash_value_512) ScrolledText_file.insert("end", '\n\nblake2b值:' + hash_value_blake2b...
  • RFID系统面临很大的安全问题,在逻辑方法上,可以通过hash锁,随机hash锁,hash链来解决。 一.hash锁: 1.抵制标签未授权访问的安全隐私技术,采用hash散列函数给标签加锁,成本较低。 2.散列冲突:由于散列算法将...
  • 一文详解密码学中的Hash算法

    千次阅读 2020-05-21 23:43:14
    上一篇文章里面,我们介绍了随机数以及随机数中的应用,可以看到密码学中到处都有随机数的身影,这种作为大部分密码学算法的基本组成被称之为 “加密基元“。今天我们一起来看一下另外一个加密基元 - 密码学Hash算法
  • Hash算法的讲解

    千次阅读 2020-02-15 17:31:59
    散列表,又叫哈希表,它是基于快速存取的角度设计的,也是一种典型的“空间换时间”的做法。顾名思义,该数据结构可以理解为一个线性表,但是其中的... 散列表(Hash table,也叫哈希表),是根据关键码值(Key value...
  • Murmurhash 哈希算法 介绍与实现

    万次阅读 2019-10-31 15:38:18
    最近在项目代码中看到了一种hash算法,以前没有遇见过,在此记录下来。   一、介绍   MurmurHash 是一种非加密型哈希函数,适用于一般的哈希检索操作。 由Austin Appleby在2008年发明, 并出现了多个变种,都...
  • Hash详解

    万次阅读 多人点赞 2018-07-23 10:00:22
    Hash(哈希) Hash :散列,通过关于键值(key)的函数,将数据映射到内存存储中一个位置来访问。这个过程叫做Hash,这个映射函数称做散列函数,存放记录的数组称做散列表(Hash Table),又叫哈希表。JAVA函数hashCode()...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,148,839
精华内容 459,535
关键字:

hash