hogwarts sorting hat_huge squares

hogwarts sorting hat_huge squares1.概述murmurhash是AustinAppleby于2008年创立的一种非加密hash算法,适用于基于hash进行查找的场景。murmurhash最新版本是MurMurHash3,支持32位、64位及128位值的产生。murmurhash标准使用c++实现,但是…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

1. 概述

murmurhash是 Austin Appleby于2008年创立的一种
非加密hash算法,适用于基于hash进行查找的场景。murmurhash最新版本是MurMurHash3,支持
32位、64位及128位值的产生。

murmurhash标准使用c++实现,但是也有其他主流语言的支持版本,包括:perl、c#、ruby、python、java等。murmurhash在多个开源项目中得到应用,包括libstdc、libmemcached
、nginx、hadoop等。

CityHash是Google发布的字符串散列算法,和murmurhash一样,属于非加密型hash算法。CityHash算法的开发是受到了 MurmurHash的启发。其主要优点是大部分步骤包含了至少两步独立的数学运算。现代 CPU 通常能从这种代码获得最佳性能。

CityHash 也有其缺点:代码较同类流行算法复杂。
Google 希望为速度而不是为了简单而优化,因此没有照顾较短输入的特例


Google 号称CityHash64 在速度方面至少能提高 30%(这个,肯定不是和murmurhash比咯),并有望提高多达两倍。此外,这些算法的统计特性也很完备。

目前CityHash支持
64、128、256

2.使用:

1)Murmurhash直接添加源码:

//----------------------------------------------------------------------------- // MurmurHash2, 64-bit versions, by Austin Appleby // The same caveats as 32-bit MurmurHash2 apply here - beware of alignment // and endian-ness issues if used across multiple platforms. typedef unsigned long int uint64_t; // 64-bit hash for 64-bit platforms uint64_t MurmurHash64A ( const void * key, int len, unsigned int seed ) { const uint64_t m = 0xc6a4a7935bd1e995; const int r = 47; uint64_t h = seed ^ (len * m); const uint64_t * data = (const uint64_t *)key; const uint64_t * end = data + (len/8); while(data != end) { uint64_t k = *data++; k *= m; k ^= k >> r; k *= m; h ^= k; h *= m; } const unsigned char * data2 = (const unsigned char*)data; switch(len & 7) { case 7: h ^= uint64_t(data2[6]) << 48; case 6: h ^= uint64_t(data2[5]) << 40; case 5: h ^= uint64_t(data2[4]) << 32; case 4: h ^= uint64_t(data2[3]) << 24; case 3: h ^= uint64_t(data2[2]) << 16; case 2: h ^= uint64_t(data2[1]) << 8; case 1: h ^= uint64_t(data2[0]); h *= m; }; h ^= h >> r; h *= m; h ^= h >> r; return h; } // 64-bit hash for 32-bit platforms uint64_t MurmurHash64B ( const void * key, int len, unsigned int seed ) { const unsigned int m = 0x5bd1e995; const int r = 24; unsigned int h1 = seed ^ len; unsigned int h2 = 0; const unsigned int * data = (const unsigned int *)key; while(len >= 8) { unsigned int k1 = *data++; k1 *= m; k1 ^= k1 >> r; k1 *= m; h1 *= m; h1 ^= k1; len -= 4; unsigned int k2 = *data++; k2 *= m; k2 ^= k2 >> r; k2 *= m; h2 *= m; h2 ^= k2; len -= 4; } if(len >= 4) { unsigned int k1 = *data++; k1 *= m; k1 ^= k1 >> r; k1 *= m; h1 *= m; h1 ^= k1; len -= 4; } switch(len) { case 3: h2 ^= ((unsigned char*)data)[2] << 16; case 2: h2 ^= ((unsigned char*)data)[1] << 8; case 1: h2 ^= ((unsigned char*)data)[0]; h2 *= m; }; h1 ^= h2 >> 18; h1 *= m; h2 ^= h1 >> 22; h2 *= m; h1 ^= h2 >> 17; h1 *= m; h2 ^= h1 >> 19; h2 *= m; uint64_t h = h1; h = (h << 32) | h2; return h; }

2)cityhash需要下载、配置、编译后才能使用

3.测试代码:

#include <iostream> #include <string> #include <time.h> #include "city.h" using namespace std; uint64_t MurmurHash64A ( const void * key, int len, unsigned int seed ); int main(int argc, char** argv) {         char buf[1024];         time_t t1, t2;         FILE* file = fopen(argv[1], "r");         int pattern = atoi(argv[2]);         t1 = time(NULL);         while(fgets(buf, 1024, file) != NULL)         {                 if(1 == pattern)                 {                         MurmurHash64A(buf, strlen(buf), 16);                 }                 else                 {                         CityHash64WithSeed(buf, strlen(buf), 16);                 }         }         t2 = time(NULL);         cout << (t2-t1) << endl;         return 0; }

生成随机字符串bash脚本:

#!/bin/sh #sh make_random_strings 16 10000 #make 10000 strings, the string length:16 for((j=0; j<$2; j++)) { str= for((i=0; i<$1; i++)) { one=`cat /dev/urandom |strings -n 1 | cut -c-1| head -1` str=${str}${one} } echo $str }

测试长度16的字符串hash速度

测试数据:

735,529,084行 长度16的随机字符串


murmurhash平均耗时:94s
cityhash平均耗时:86s


测试长度
32的字符串hash速度

测试数据:

262,017,242行 长度32的随机字符串


murmurhash平均耗时:33

cityhash平均耗时:33

测试长度
256的字符串hash速度

测试数据:

60,000,000行 长度256的随机字符串


murmurhash平均耗时:32

cityhash平均耗时:30



4.总结:


速度: cityhash和murmurhash相比,速度略快

使用复杂度:都非常简单

语言支持:murmurhash主流语言基本都支持;cityhash 2010才发布算法,2011年发布实现,目前只有c++的支持。

hash值位数:murmurhash支持32、64、128bit, cityhash支持64、128、256bit


reference:

http://code.google.com/p/cityhash/

wiki:http://en.wikipedia.org/wiki/CityHash

wiki:http://en.wikipedia.org/wiki/Murmurhash

转载于:https://my.oschina.net/zipu888/blog/549639

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。

发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/183754.html原文链接:https://javaforall.net

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • 免费.NET代码生成器KevinCodeBuilder「建议收藏」

    .NET代码生成器KevinCodeBuilder>>>免费下载:百度云CSDN>>>点击学习:视频教程+完整源码自己在做.NET开发的时候,简单的三层架构会有很多重复的代码,如果手敲会比较浪费时间。前段时间在互联网找了下.net的代码生成器,发现要么太复杂甚至生成的代码会报错,要么要收费而且效果不是自己想要的。所以,干脆…

    2022年4月14日
    105
  • ftp常用命令详解_ospf生成路由表的过程

    ftp常用命令详解_ospf生成路由表的过程在window下按window+r可打开DOS命令窗口,然后就可以输入FTP命令了。1.登录FTP服务器方法一:直接输入ftp加ip地址ftp192.168.10.xxx方法二:直接输入ftp,进入ftp服务后输入open加ip地址open192.168.10.xxx当连接成功后会让你进行身份验证,在输入密码时屏幕上没有任何显示,不用管,直接…

    2022年9月21日
    1
  • vb四环棋的实现,平面四子棋

    vb四环棋的实现,平面四子棋

    2021年3月12日
    235
  • SpringBoot框架_skynet框架详解

    SpringBoot框架_skynet框架详解SpringBoot框架详解1.SpringBoot概述1.1springboot简介1.2SpringBoot特点1.3Spring官网解读2.SpringBoot入门2.1系统要求2.2创建项目2.3引入依赖2.4创建测试2.5测试验证3.SpringBoot配置原理3.1SpringBoot特点3.2容器功能3.3自动配置原理入门3.4开发小技巧1.SpringBoot概述1.1springboot简介springboot之所以能使用广泛也基于微服务分布式的的崛

    2022年8月21日
    11
  • vue删除数组中某一元素_数组索引超出范围

    vue删除数组中某一元素_数组索引超出范围在前端开发中,我们经常需要对数组进行操作,增删改是经常的事情,那我们js中该如何删除指定的下标元素呢????我们用splice来操作1.定义和用法splice()方法用于添加或删除数组中的元素。注意:这种方法会改变原始数组。数组中添加新元素:varfruits=[“Banana”,”Orange”,”Apple”,”Mango”];fruits.splice(2,0,”Lemon”,”Kiwi”);fruits输出结果:Banana,Orange,Le.

    2022年8月10日
    76
  • 500G 史上最全的JAVA全套视频教程网盘[通俗易懂]

    500GJAVA视频网盘分享(JEECG开源社区)[涵盖从java入门到深入架构,Linux、云计算、分布式、大数据Hadoop、ios、Android、互联网技术应有尽有]JEECG开源社区秉承开源宗旨,分享社区Java架构视频,更多资料点击:www.jeecg.orgJAVA快速开发平台源码下载:https://gitee.com/jeecg/jeecgJEE…

    2022年4月10日
    54

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号