您现在的位置:首页 --> 查看专题: Hash
对于海量数据处理业务,我们通常需要一个索引数据结构,用来帮助查询,快速判断数据记录是否存在,这种数据结构通常又叫过滤器(filter)。考虑这样一个场景,上网的时候需要在浏览器上输入URL,这时浏览器需要去判断这是否一个恶意的网站,它将对本地缓存的成千上万的URL索引进行过滤,如果不存在,就放行,如果(可能)存在,则向远程服务端发起验证请求,并回馈客户端给出警告。
索引的存储又分为有序和无序,前者使用关联式容器,比如B树,后者使用哈希算法。这两类算法各有优劣:比如,关联式容器时间复杂度稳定O(logN),且支持范围查询;又比如哈希算法的查询、增删都比较快O(1),但这是在理想状态下的情形,遇到碰撞严重的情况,哈希算法的时间复杂度会退化到O(n)。因此,选择一个好的哈希算法是很重要的。
在Ubuntu 下有一个问题经常会困扰大家,就是运行 apt-get update 是出现 Hash校验和不符的提示。
HashMap主要有插入、删除、查找以及ReHash四种基本操作。一个典型的HashMap实现,会用到一个数组,数组的每项元素为一个节点的链表。对于此链表,我们可以利用文中提到的操作方法,执行插入、删除以及查找操作,但对于ReHash操作则比较困难。
MinHash首先它是一种基于 Jaccard Index 相似度的算法,也是一种LSH的降维的方法,应用于大数据集的相似度检索、推荐系统。下边按我的理解介绍下MinHash。 举例A,B 两个集合: A = {s1, s3, s6, s8, s9} B = {s3, s4, s7, s8, s10} 根据Jaccard Index公式,A,B的相似度 S(A,B) = |A∩B|/|A∪B| = 2/8 = 0.25, 用图表示如下: 当然直接计算两个集合的交集与并集,是很耗计算资源的,特别是在海量数据场景下不可行。 假如,我们随机从两个集合中各挑选一个元素s(A)、s(B),刚好这两个无素相同的概率是多少呢?
LVS 有个 connection hash table ,默认的 size 为 4096,可以通过以下命令得到:# ipvsadm -lnIP Virtual Server version 1.0.12 (size=4096)简单地说,这个hash table 用于记录每个进来的连接及路由去向的信息。面对庞大的连接时,这个4096是远远不够的,这时就会产生冲突,然后hash table 就不断置换table 中的数据,系统的负荷就这样上来了。所以,很多调优文章都说,要把这个值调大。至于如何调大呢,好像必须重编译内核了。。。
背景介绍 站点新功能或者是站内新策略开发完毕之后,在全流量上线之前要评估新功能或者新策略的优劣,常用的评估方法是A-B测试,做法是在全量中抽样出两份小流量,分别走新策略分支和旧策略分支,通过对比这两份流量下的各指标的差异,我们可以评估出新策略的优劣,进而决定新策略是否全流量。 上文中提到的抽样是指按照某种确定的随机化方法,对线上流量进行划分。抽样可以指这种划分的方法,也可以指划分得到的一个流量子集。抽样是一种特殊的小流量,要求对流量的划分必须保证均匀性和随机性,并且可以根据需求过滤掉不符合规范的部分,我们把抽样的过程分为流量切分和流量筛选两个步骤,流量切分是指把全流量进行均匀的打散,提取出其中固定的流量比例,流量筛选是对流量切分的辅助,筛选过程就是从切分好的流量中过滤掉不符合规范的部分,本文主要涉及的是流量切分的实现。
consistent hashing 算法早在 1997 年就在论文 Consistent hashing and random trees 中被提出,目前在 cache 系统中应用越来越广泛; 1 基本场景 比如你有 N 个 cache 服务器(后面简称 cache ),那么如何将一个对象 object 映射到 N 个 cache 上呢,你很可能会采用类似下面的通用方法计算 object 的 hash 值,然后均匀的映射到到 N 个 cache ; hash(object)%N 一切都运行正常,再考虑如下的两种情况;
这事可能都过气了,不过还是贴出我使用的方式吧,用的着的可以参考. 上段时间的各语言hash绝对印象深刻吧,做网站的几乎都在此类,不论你是用的是php,python还是ruby都不同程度受到影响, PHP尤其明显,因为PHP用的人也多嘛,攻击方式简直简单到不行,有兴趣的可以找我索取此测试脚本,一个终端随便搞挂一台有次漏洞的PHP站点. 我们http请求都是通过nginx反向代理,所以优势是可以在nginx这一层对请求做很多逻辑,此次防hash dos就是这个架构.
微博发了一道安全常识题,从反馈看,搞不太清楚的人还是蛮多的。有意思的是,搞不清楚的人多数认为是我搞错了。微博就144个字,也说不开,挪这里详细说说。很多网站都有用户系统,有用户系统就有密码存放,通常,密码都是加密传输的,为了安全,通常是单向散列加密,或者说,不可逆加密,一个简单的判断是,你通过密码找回功能操作,如果让你重设密码的,基本上是不可逆加密的,直接给你密码的,都是明文或可逆加密的,这种...
最近关于hash的攻击很火,这个问题存在的时间很久了。有几点想法,写出来和大家分享一下。 hash的好处是查找速度快,但是通过特殊的输入,会造成冲突链过长,查找会退化成一个链表遍历操作。对于hash来说,有几个重要的参数 1)hash table size,也就是hash的映射空间,很显然,hash表越大,映射的冲突几率就越小。 2)hash function,冲突取决于几个因素,一是输入源,二是hash function。好的hash function可以把非随机的输入源映...
hashtable的实现有很多,redis的dict.c 是其中之一。 dict 包含了2个dictht hashtable ht[0], ht[1]。 client版本的dict是没有dictht的概念。加入dictht的概念存在2个ht的目的是为了在rehash的时候可以平滑的迁移bucket里的数据,而不像client的dict要把老的hash table里的一次性的全部数据迁移到新的hash table,这在造成一个密集型的操作,在业务高峰期不可取。 ht是hashtable的简称,实际上是一个指针数组,数组的个数由dictht-...
这是一种开放地址HASH,主要目的是为了提高查询速度。提高查询速度常用的思路是在插入的时候对数据作调整,让数据更紧凑。常用的方法在HASH表比较满的情况下,复杂度都很难保证。这个方法的特点是,它可以保证最坏情况下,查询的复杂度也是个常数。元素X算HASH后,应该存在I节点,则允许它存在【I,I+H)之间第一个空闲的节点,H一般去32,一是H比较小,用一个INT作BITMAP就可以表示它后面哪些元素是HASH到这里的。二是,H太...
hash join是oracle里面一个非常强悍的功能,当做hash join时,oracle会选择一个表作为驱动表,先根据过滤条件排除不必要的数据,然后将结果集做成hash表,放入进程的hash area,接着扫描第二张表,将行的键值做hash运算,到内存的hash表里面去探测,如果探测成功,就返回数据,否则这行就丢弃掉这个是最基本的解释,实际情况中,考虑到单个进程PGA的大小,oracle不会让进程任意的消耗OS内存,hash area是有一定限制的,所以在oracl...
HMAC-SHA1、HMAC-MD5等算法,在PHP5.1.X之后,可直接使用如下形式来计算 echo hash_hmac(\'sha1\',$data,$key); 如果加载了MHASH扩展,也可直接使用mhash来进行运算 echo bin2hex(mhash(MHASH_SHA1, $data, $key)); 如果PHP版本低于5.1.X或者没有加载Mhash、或HMAC扩展,可使用如下的通用方法来进行相应运算下载:
nginx 做 url 的 hash 时,做动态和静态的 hash 时需要多多注意。因为动态和静态的文件表现出来的不一样。 静态文件 Nginx 的 Hash 处理 静态的文件的源网站的,特点文件静态,大小基本是几种类型...
[ 共25篇文章 ][ 第1页/共2页 ][ 1 ][ 2 ]
近3天十大热文
- [67] Go Reflect 性能
- [67] Oracle MTS模式下 进程地址与会话信
- [67] 如何拿下简短的域名
- [61] IOS安全–浅谈关于IOS加固的几种方法
- [60] 图书馆的世界纪录
- [59] 【社会化设计】自我(self)部分――欢迎区
- [58] android 开发入门
- [56] 视觉调整-设计师 vs. 逻辑
- [49] 给自己的字体课(一)——英文字体基础
- [47] 界面设计速成
赞助商广告