分析levelDB源码的时候遇到的...发现是一个广泛应用的hash算法，而且是纯c写的，于是找来了源码看。 **MurmurHash** 是一种非[加密](https://zh.wikipedia.org/wiki/)型[哈希函数](https://zh.wikipedia.org/wiki/)，适用于一般的哈希检索操 …

原始论文：一致性哈希 本来不打算放的。。被批评说太不严谨orz.. 说说自己的理解好了。。 大概就是。。。hash的时候。。一开始有n个桶。。你设计的函数是y=x%n...看起来美滋滋。。。 然后这时候突然一个桶不见了。。。如果按照之前设计的hash函数。。就变成了x%(n-1)... 这可能会造成大量的数据改变自己之前所在的桶。。。这是不可接受的。。。 或者是。。。当前的桶不够用了。。要增加一个桶。。。变成了x%(n+1)。。。也会出现类似情况。。。 我们的目的就是设计一种算法。。。使得当减少一个桶或者增加一个桶的时候。。。。变化尽可能小。。。 并且希望以后新放入的数据尽可能到新的桶中（？ 桶是简化的模型。。。实际应用上。。。一致 …

前言： hash这种东西人人都会用的东西还有必要说？ 起因是...本问了hash中的一个细节...然后...我知道怎么做... 结果描述的不够清楚？如果知道那个做法的名字也许就不用费劲描述了呢。。。所以来复习一下吧2333 hash函数_维基百科 说起来其实哈希只有两个东西比较重要吧。。。 一个是哈希函数的构造： 构造散列函数 散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快定位。 1. [直接定址法](https://zh.wikipedia.org/w/index.php?title=&action=edit&redlink=1)：取关键字或关键字的某个线性函数值为散列 …

poj 3274 题目链接 题意：给出n个数和k，每个数不超过k位二进制。现在问最长的一段区间，满足该区间中所有数相加，k个位置上的数相等。 思路：k个位置上的数都相等的话。。。那这个和应该是(k<<1)-1的整数倍。。。 于是抽屉原理搞了一发。。一直wa.. 正解是数字hash。。。 不过我拍了一下。。。如果不是我理解错了题意的话。。。我是把一份ac代码　hack掉了。。。。。 用来对拍的ac代码： #include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> using …

题意：有n个雪花，每个雪花有６瓣，给出每一瓣的长度，问是否有两个雪花相同。（雪花相同的条件是：存在某个顺序使得两个雪花的每一瓣长度对应相等） 思路：一开始想到的是先最小表示法。。。然后hash。。。存set。。看set的大小。。。但是因为我是顺时针，逆时针都存了一次，那么如果有一个雪花顺时针和逆时针相同，就会出现错误的结果（虽然这个我应该判掉了。。。但是还是WA　orz） 归根结底我是没有搞定当hash相同的时候，如何判定这两个不是一组orz。 看了很多题解。。。（为什么大家这道题的代码都写得这么丑啊。。。。？ 思路有：hash或者最小表示法，或者最小表示法＋hash 思路是，把六瓣的长度求和，作为hash的key值。。。 然 …

题目链接 题意：一个字符串，其仅由nc种字符组成，问其所有长度为n的字串里，共用多少种不同的。 思路：一开始木有懂nc种字符有什么用... 然后写了hash，发现会TLE。。。因为用到了map，被卡了个log.. nc的作用是，可以把字符串看成一个nc进制的数，这样做的好处是，得到的hash值可以尽可能的小而且保证了不同的字符串对应了不同的hash值。 然后就可以不用map而是一个数组，就变成了O(1)赋值和判断了。。。 （然而没有数据范围其实还是有点耍流氓的嫌疑。。 #include <iostream> #include <cstring> #include <stdio.h> using …

题目链接 题意：n个人，每个人有一个level值，用一个最长30位的，可能带前缀0的数字串表示，如果i的level大于j的level，那么i可以教j飞行，每个人只能有一个老师，每个人也只能收一个徒弟。师生可以共用一把扫帚飞行。现在问最少需要多少扫帚。 思路：分析发现，影响扫帚多少的是相等的数有多少，因为只要不相等，就肯定可以构成师生关系.... 更确切得说，是所有数出现次数的最大值。 有一个trick点，就是带前缀0和不带前缀0的两个level被认为是相等的，hash的时候要处理前缀0. /* *********************************************** Author :111qqz Created …

题目链接 题意：网站的注册系统..处理用户要注册的用户名，如果数据库中没有重名输出OK，否则输出要注册的用户名的字符串+num,num的大小为之前一共有多少个用户试图用该用户名。 思路：hash一下。。。 /* *********************************************** Author :111qqz Created Time :2016年11月22日 星期二 19时00分58秒 File Name :code/cf/problem/4C.cpp ************************************************ */ #include <cstdio> …

题目链接 题意：给定一个两种语言的对照关系表...给出后一种语言中的单词，问对应的前一种语言的单词是什么。。。 思路：hash一下然后map存一下即可。。。。读入方式由于单词表和查询是根据空行分开的。。那么读入不能用scanf(因为会跳过空行），要用gets。。。然后再sscanf一下。。。 /* *********************************************** Author :111qqz Created Time :2016年11月20日 星期日 11时13分29秒 File Name :code/poj/2503.cpp …

题目链接 题意：给你一部魔咒词典。当哈利听到一个魔咒时，你的程序必须告诉他那个魔咒的功能；当哈利需要某个功能但不知道该用什么魔咒时，你的程序要替他找到相应的魔咒。如果他要的魔咒不在词典中，就输出“what?” 思路：hash裸题。。。然而怎么感觉是第一次写hash呢。。。。 /* *********************************************** Author :111qqz Created Time :2016年11月20日 星期日 10时27分05秒 File Name :code/hdu/1880.cpp …