一致性哈希初探

原始论文:一致性哈希

本来不打算放的。。被批评说太不严谨orz..

说说自己的理解好了。。

大概就是。。。hash的时候。。一开始有n个桶。。你设计的函数是y=x%n…看起来美滋滋。。。

然后这时候突然一个桶不见了。。。如果按照之前设计的hash函数。。就变成了x%(n-[……]

Read more

hash学习笔记

前言:

hash这种东西人人都会用的东西还有必要说?

起因是…本问了hash中的一个细节…然后…我知道怎么做… 结果描述的不够清楚?如果知道那个做法的名字也许就不用费劲描述了呢。。。所以来复习一下吧2333

hash函数_维基百科

 

说起来其实哈[……]

Read more

poj 3274 Gold Balanced Lineup (抽屉原理?错题?)

poj 3274 题目链接

题意:给出n个数和k,每个数不超过k位二进制。现在问最长的一段区间,满足该区间中所有数相加,k个位置上的数相等。

思路:k个位置上的数都相等的话。。。那这个和应该是(k<<1)-1的整数倍。。。

于是抽屉原理搞了一发。。一直wa..

正[……]

Read more

poj 3349 Snowflake Snow Snowflakes (利用hash分组)

题意:有n个雪花,每个雪花有6瓣,给出每一瓣的长度,问是否有两个雪花相同。(雪花相同的条件是:存在某个顺序使得两个雪花的每一瓣长度对应相等)

思路:一开始想到的是先最小表示法。。。然后hash。。。存set。。看set的大小。。。但是因为我是顺时针,逆时针都存了一次,那么如果有一个雪花顺时针和[……]

Read more

poj 1200 Crazy Search (字符串哈希)

题目链接

题意:一个字符串,其仅由nc种字符组成,问其所有长度为n的字串里,共用多少种不同的。

思路:一开始木有懂nc种字符有什么用…

然后写了hash,发现会TLE。。。因为用到了map,被卡了个log..

nc的作用是,可以把字符串看成一个nc进制的数,这样做的好处是[……]

Read more

hdu 1800 Flying to the Mars (字符串hash)

题目链接

题意:n个人,每个人有一个level值,用一个最长30位的,可能带前缀0的数字串表示,如果i的level大于j的level,那么i可以教j飞行,每个人只能有一个老师,每个人也只能收一个徒弟。师生可以共用一把扫帚飞行。现在问最少需要多少扫帚。

思路:分析发现,影响扫帚多少的是相等[……]

Read more

codeforces 4C. Registration system (字符串hash)

题目链接

题意:网站的注册系统..处理用户要注册的用户名,如果数据库中没有重名输出OK,否则输出要注册的用户名的字符串+num,num的大小为之前一共有多少个用户试图用该用户名。

思路:hash一下。。。

 [……]

Read more

poj 2503 Babelfish (字符串hash +sscanf读入技巧)

题目链接

题意:给定一个两种语言的对照关系表…给出后一种语言中的单词,问对应的前一种语言的单词是什么。。。

思路:hash一下然后map存一下即可。。。。读入方式由于单词表和查询是根据空行分开的。。那么读入不能用scanf(因为会跳过空行),要用gets。。。然后再sscanf一下。[……]

Read more

hdu 1880 魔咒词典 (字符串hash)

题目链接

题意:给你一部魔咒词典。当哈利听到一个魔咒时,你的程序必须告诉他那个魔咒的功能;当哈利需要某个功能但不知道该用什么魔咒时,你的程序要替他找到相应的魔咒。如果他要的魔咒不在词典中,就输出“what?”

思路:hash裸题。。。然而怎么感觉是第一次写hash呢。。。。
[cray[……]

Read more

hdoj4391 Paint The Wall

http://acm.hdu.edu.cn/showproblem.php?pid=4391
题意:有 n 个点,每个点有一种颜色(可能相同),两种操作:1、将区间 [a,b] 染成颜色 c ; 2、询问区间 [a,b] 中颜色为 c 的点有多少个。
思路:因为颜色种类很多。。。没办法通过建很多[……]

Read more