B*******1
发帖数: 2454 | 1 Consistent hashing.
★ 发自iPhone App: ChineseWeb 7.8 |
|
s****A
发帖数: 80 | 2 而且书上还说，如果来search字符串的话,最好这样计算hash function
( char[0] x s^n + char[1] x s^(n-1)+...+char[n] )% M
这里如果s和M不互质的话，就会导致得到的index分布不uniform
我没想明白为什么，我怎么觉得不管是否互质，只要输入分布uniform得到的index还是
在0到M-1之间uniform分布的啊
谁能给举个例子说明一下s和M不互质的情况下会出什么问题？
最好是例子，一看就明白
谢谢！ |
|
f*******n
发帖数: 12623 | 3 目的是要字符串的每一部分都用到。譬如s=M，
( char[0] x s^n + char[1] x s^(n-1)+...+char[n] )% M
就等于char[n]了。其他的字符都没有用到。
因为实际上，放在hash table的东西很多时候是有一部分相同的。如果你刚刚没有用到
它们不同那部分，那就会把它们全放在同一个bucket了。 |
|
d**********x
发帖数: 4083 | 4 为啥要每个function村一个table。。。
它只是每次换个不同的hash function算吧。。 |
|
d**********x
发帖数: 4083 | 5 减少collision啊。
只用一个hash function的话，如果数据有天然的bias或者人造的bias，很容易导致
collision的 |
|
d*s
发帖数: 699 | 6 恶意攻击要有效的话需要知道你用的具体参数，如果没有universal hashing，就靠实
现时候对参数的保密，显然不靠谱。有了之后就算公开源代码一般也没办法进行攻击，
因为根本不知道具象化之后的database用的p, q, m是多少，我认为需要换函数的情况
是十分罕见的
function |
|
r**h
发帖数: 1288 | 7 突然想到了这个问题，求教一下各位
虽然trie专门用来处理字符串，但是我觉得对于hashset，如果hash函数设计得好，效
率也不会输呀。 |
|
g***j
发帖数: 1275 | 8 我看很多code用的是map，类似这样
但是map.find，是logN的时间复杂度啊
请问如果用C/C++如何使用hash来表示呢？
谢谢了！ |
|
|
R******1
发帖数: 58 | 10 刚好之前上过这课。是Homework6.1吗？ hash table完全可以做呀。LZ卡在哪里呀？ |
|
|
R******1
发帖数: 58 | 12 我之前做的时候是【2500， 4000】，所以很快， 7s左右
刚试了试这个新的range，本来以为是线性增加，时间应该也不不大；
但是，很多target无法满足，就要遍历hash table一次。
【2500， 4000】 用时 7s 命中率1477/1500 绝大多数都很快break了
【0， 1000】 用时 1m56s 命中率445/1000 多于一半要遍历完
建议楼主试试先sort（O（NlogN)), 然后binary search （O（logN)).
2sum.txt ～4MB 所以建设1M个ints
range是【-10000， 10000】， 20000
用hashtable worst case 20000*1M
用sort然后binary search， worst case 1M*log（1M） + 20000*log（1M） ～ 20*1M |
|
b****g
发帖数: 192 | 13 有1万个正整数，范围是0 ~ 2^32-1。
怎么hash？要求用到%
我只能想到：
（1）用%质数
（2）用bit operation算每个digit的和，这样就相当于%32 |
|
H*****l
发帖数: 1257 | 14 我用类似3 sum的方法，是O（n^3)的复杂度，但是过不了large judge，超时；
看到帖子说可以用hash table做到O（n^2）的复杂度，能不能具体说下算法？
题目如下：
Given an array S of n integers, are there elements a, b, c, and d in S such
that a + b + c + d = target? Find all unique quadruplets in the array which
gives the sum of target.
Note:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ?
b ? c ? d)
The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
A soluti... 阅读全帖 |
|
|
h*d
发帖数: 19309 | 16 sort string then hash?
word |
|
A*********t
发帖数: 64 | 17 有hash function不sort也行么？ |
|
a**********0
发帖数: 422 | 18 这个问题我自己解决了
LSH的某个scheme就是minhash的形式:
对集合S进行排列 每个元素将会有一个index 取一个S的子集 设为A 则A中每个元素皆
有一个permutated index 定义哈希函数为依照此permutation的最小的index 完全符合
minhash的定义 如何产生若干hash function？ 多取几个permutation就是了 |
|
l**********i
发帖数: 12 | 19 说个hash真不知道是什么意思
首先弄清楚
1. 要不要支持自定义的shorten url
2. 任何人都可以生成shorten url呢还是只有登录的用户才可以
3. 一样的full url要不要给一样的shorten url
然后最基本的
1. shorten url是什么形式，多长，为什么，encode id to base 62?
2. 如何维护shorten url -> full url的mapping，id => full url?
3. 如何生成id? 会不会有collision, 如何解决
再说几点吧
1. 如何防止生成的url被scan，比如我知道某id=abc是合法的，然后试id-1 和id+1 不
应该被猜中
2. 如果要求随机猜N个url都未命中的概率大于99.99%，如何做到
3. 如果有人随机猜url 对你的系统有什么影响，如果你是persistant storage+cache
的架构 会有什么问题
4. 如何distribute到多机器 service和storage 都谈谈
5. 如何要限制单个用户的rps，用什么策略，如何实现
欢迎补充 |
|
l*****a
发帖数: 14598 | 20 这个题常见解法不是hash
直接把URL插入数据库，用DB中index生成tiny URL |
|
a******0
发帖数: 67 | 21 请问，如果用Hash，有collision怎么办？
谢谢啊。 |
|
a******0
发帖数: 67 | 22 谢谢啊；再帮个忙，能推荐几个link或paper吗？我想再细细消化您上面所说的hash方
法。
非常感谢！ |
|
g*****g
发帖数: 34805 | 23 公开资源还要防止被 scan就是搞笑，真要安全，应该是所有 url产生的 shorten url
互相独立，加密码。也不用算什么 hash. |
|
g*****g
发帖数: 34805 | 24 如果你不懂得C*怎么存数据的，想象一下这相当于一个hash后面带了一整个bucket，自
然不会冲突。你把UUID值存在这里，再建个UUID->url的索引就行了。把UUID拿出来做
Shorten URL。
建立新URL查第一个表，访问shorten URL查第二个表。
一个HashMap是个人都懂，差别在于C*这样的数据库能提供分布式存取。 |
|
h*******e
发帖数: 1377 | 25 rt
给定平面上n点，求在同一直线上最多点问题～～大家用double /float 类型作hash
key么？
判断两个double /float 类型相等～～～ 靠谱么 |
|
h*******e
发帖数: 1377 | 26 如果是pair作为 key 的话自定义的hash 函数一般怎么写
在 c++ unordered_set, int> 大牛给讲一下哦。 |
|
h*******e
发帖数: 1377 | 27 光是这个过不了leetcode的编译器阿，需要自定义hash 函数，和比较函数的似乎。 |
|
h*******e
发帖数: 1377 | 28 namespace std {
template <>
struct hash >
{
typedef std::size_t result_type;
result_type operator()(const pair & t) const
{ return ((long)t.first * 1000003 + t.second )& (((long)1<<32 ) - 1);
}
};
}
class Solution {
public:
// suppose no two points are the same
int gcd(int a, int b)
{ return !b? a: gcd(b, a %b); }
pair getK(vector & points, int pointI, int pointJ)
{
int x1 = points[pointI].x, y1 =... 阅读全帖 |
|
h*******e
发帖数: 1377 | 29 rt
给定平面上n点，求在同一直线上最多点问题～～大家用double /float 类型作hash
key么？
判断两个double /float 类型相等～～～ 靠谱么 |
|
h*******e
发帖数: 1377 | 30 如果是pair作为 key 的话自定义的hash 函数一般怎么写
在 c++ unordered_set, int> 大牛给讲一下哦。 |
|
h*******e
发帖数: 1377 | 31 光是这个过不了leetcode的编译器阿，需要自定义hash 函数，和比较函数的似乎。 |
|
h*******e
发帖数: 1377 | 32 namespace std {
template <>
struct hash >
{
typedef std::size_t result_type;
result_type operator()(const pair & t) const
{ return ((long)t.first * 1000003 + t.second )& (((long)1<<32 ) - 1);
}
};
}
class Solution {
public:
// suppose no two points are the same
int gcd(int a, int b)
{ return !b? a: gcd(b, a %b); }
pair getK(vector & points, int pointI, int pointJ)
{
int x1 = points[pointI].x, y1 =... 阅读全帖 |
|
|
l********e
发帖数: 103 | 34 这里没有数据库
就是 让我写个 用于多线程的hash table |
|
l********e
发帖数: 103 | 35 你说的lock striping是在hash table 的每个slot加个read write lock吗？
我就是这样说的 然后
面试官 要求更好的performance
然后他就提到get不用任何lock... |
|
l********e
发帖数: 103 | 36 就是实现一个thread safe的hash table...
提供像标准库函数一样的api
没别的了 |
|
g*********e
发帖数: 14401 | 37 1 reader thread reads the object o0
2 writer creates another object o1
3 writer makes that hash bucket point to o1 (atomic, no need lock)
4 reader is still reading o0
5 future reader reads o1 |
|
r*******g
发帖数: 1335 | 38 hash table read的话确实可以做到不用lock。
就好比A->B->C
你现在新加入一个D进来，那么先D->C，然后内存sig_atomic或者database atomic操作
让B的next指向D，只要这个操作不影响read，那read就无需lock了，重点是先放好data
然后再链接起来。 |
|
l********e
发帖数: 103 | 39 就是实现一个类似于标准library里的thread safe hash table,
也是单机上的
没别的了。。。 |
|
发帖数: 1 | 40 这就是一个单机版的题目，凡是提到数据库的都会被fail掉。
我给你几个面试的哥们会追问的常规hash table问题吧：
1. 如果有大量的写入新value，如何保证concurrency和efficiency
2. 如果有大量的写入新key
3. 如果有大量的写new key/删除new key
4. 如果有大量的读和少量的写
千万不要提copy-on-write。必废。
看看concurrenthashmap，这是提问的人想要你回答的方向。不要看Collections.
synchronousXXX，必废，几乎没有人敢在production用这个。 |
|
c*******a
发帖数: 1879 | 41 【 以下文字转载自 Military 讨论区 】
发信人: centralla (central LA), 信区: Military
标 题: 码工搞的密码MD5 hash形同虚设 真是脱裤子放屁
发信站: BBS 未名空间站 (Thu Oct 11 13:08:29 2018, 美东)
尼玛还说什么是单向加密 不可逆
结果你到谷歌上随便一搜 就是被人破解的案例
码工搞的东西都是滥竽充数 只知其一 不知其二的烂东西
要不然怎么几大credit 机构的数据库都被人破解了
操 |
|
|
s*****o
发帖数: 1540 | 43 One hash function:
f(x) = x+1;
it is revertable. but it is meaningless.
in
教 |
|
x****e
发帖数: 55 | 44 我的数据格式是这样的
1，2，3，4
21，21.2,9,11
...
数据量很大，几百万条
想要快速检索，请问有什么HASH算法能解决这个问题？
多谢！ |
|
x****e
发帖数: 55 | 45 不好意思，我没说清楚
我的数据一行不是就4个数字，而是30个
所以用TREE的方式，可能TREE的底层会变的非常庞大，存储效率不高
所以如何有比较好的HASH算法那最好了 |
|
|
x****o
发帖数: 29677 | 47 请问什么情况下不能用hash table来储存数据 |
|
w****a
发帖数: 155 | 48 Hash table 和 bloom filter 有什莫区别。
是不是bloom filter更space efficient一些。 |
|
s****y
发帖数: 25 | 49 请问当前主要的数据库技术中
主要是用什么样的hash function 来
实现快速提取数据的.谢谢指教! |
|
y********o
发帖数: 2565 | 50 I have a users table in SQL Server 2005. It has the following fields:
userid (the primary key)
user_first_name nvarchar(20)
user_last_name nvarchar(20)
user_password varbinary(50)
I don't wanna store user_password as plain text. How do I encrypt or hash it
when I insert a record? I know in MySQL, we can do something like
INSERT INTO USERS VALUE ('johndoe', 'John', 'Doe', password('sikulito'));
Thanks. |
|
