c*********t
发帖数: 2921 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: cookiesweet (apple), 信区: JobHunting
标 题: 弱弱的问问跟hash有关的问题
发信站: BBS 未名空间站 (Mon Aug 1 01:51:41 2011, 美东)
在这个板上，看到很多的时候大家解决问题都用hash。
本人很弱，感觉hash很高深的。
问几个简单的问题，请回答，有包子送。
1. hash, hash table, hash_set, hash_map, map, linked hashmap,这些有什么关系
和区别？
2. 在上面提到的数据结构中，哪些是排序的，哪些不是？
3. 在上面提到的数据结构中，哪些插入，搜索，和删除是 O(1),哪些是O(n)
4. 他们所占的空间是O(n)吗？
5. C++ STL里支持上面的这些数据结构吗？哪些不支持？
6. 面试的时候，如果用到hash的方法，你是假设已经有很好的hash fuction,已经有了
hash table, 重点放在如何用hash解决问题，还是你要自己from scratch 设计hash
functi... 阅读全帖 |
|
c*********t
发帖数: 2921 | 2 在这个板上，看到很多的时候大家解决问题都用hash。
本人很弱，感觉hash很高深的。
问几个简单的问题，请回答，有包子送。
1. hash, hash table, hash_set, hash_map, map, linked hashmap,这些有什么关系
和区别？
2. 在上面提到的数据结构中，哪些是排序的，哪些不是？
3. 在上面提到的数据结构中，哪些插入，搜索，和删除是 O(1),哪些是O(n)
4. 他们所占的空间是O(n)吗？
5. C++ STL里支持上面的这些数据结构吗？哪些不支持？
6. 面试的时候，如果用到hash的方法，你是假设已经有很好的hash fuction,已经有了
hash table, 重点放在如何用hash解决问题，还是你要自己from scratch 设计hash
function,创建hash table?
7. 什么时候(什么样的应用，什么样的场合)，该用上面提到的哪种数据结构？
下面的这个帖子里，有人用map替代hash map.
http://www.mitbbs.com/article_t/JobHunting/31911013.ht... 阅读全帖 |
|
l******9
发帖数: 579 | 3 【 以下文字转载自 Statistics 讨论区 】
发信人: light009 (light009), 信区: Statistics
标 题: a hash embedded with another hash in R
发信站: BBS 未名空间站 (Fri Apr 11 15:56:40 2014, 美东)
This question is related to my previous question.
I need to design a hash that is embedded with another hash in R in Rstudio
on Win 7.
library(hash)
myf <- function()
{
h1 <- hash()
if (!has.key("first", h1))
{
list1 <- list()
h1.son<- hash()
h1.son["first_son"] <- list1
h1["first"] <- h1.son
}
# second check
if(!has.key("first_son... 阅读全帖 |
|
l******9
发帖数: 579 | 4 【 以下文字转载自 Statistics 讨论区 】
发信人: light009 (light009), 信区: Statistics
标 题: a hash embedded with another hash in R
发信站: BBS 未名空间站 (Fri Apr 11 15:56:40 2014, 美东)
This question is related to my previous question.
I need to design a hash that is embedded with another hash in R in Rstudio
on Win 7.
library(hash)
myf <- function()
{
h1 <- hash()
if (!has.key("first", h1))
{
list1 <- list()
h1.son<- hash()
h1.son["first_son"] <- list1
h1["first"] <- h1.son
}
# second check
if(!has.key("first_son... 阅读全帖 |
|
l******9
发帖数: 579 | 5 【 以下文字转载自 Statistics 讨论区 】
发信人: light009 (light009), 信区: Statistics
标 题: a hash embedded with another hash in R
发信站: BBS 未名空间站 (Fri Apr 11 15:56:40 2014, 美东)
This question is related to my previous question.
I need to design a hash that is embedded with another hash in R in Rstudio
on Win 7.
library(hash)
myf <- function()
{
h1 <- hash()
if (!has.key("first", h1))
{
list1 <- list()
h1.son<- hash()
h1.son["first_son"] <- list1
h1["first"] <- h1.son
}
# second check
if(!has.key("first_son... 阅读全帖 |
|
c**y
发帖数: 172 | 6 I also had the same question before. After carefully studying the related
documents, I found my previous understanding is not correct. The universal
hashing is used in the following way.
Assume that we are given a bunch of keys to process. At the very beginning,
we randomly choose a hash function from a family of hash functions. Then
during execution, we apply this hash function to all the keys. A key
observation here is that the hash function doesn't change from key to key.
Will does universal ... 阅读全帖 |
|
d****n
发帖数: 1637 | 7 先扫进第二个文件，以col 1 为 key ,然后push 每个value 到 key
push @{$hash{'06'}}, 100
push @{$hash{'06'}}, 200
你就有了 hash of array, like 06 =>[100, 200,50]
再扫第一个文件，当你用到
$VAR{$key1}{$key2}{$key3} 时候，
你就 assignment reference to
$VAR{'P5'}{'E'}{'06'}= \@{$hash{'06'}} ;
第二个文件 用 hash of array
第一个文件用 hash of hash of hash of reference
大致是这个样子，可能有语法问题。
顺便说下，你的结构够混乱的
太乱了。
我早就不用perl， 用python吧。 |
|
c*******o
发帖数: 27734 | 8 【 以下文字转载自 Joke 讨论区 】
发信人: crashinfo (跨世因佛§梦幻泡影), 信区: Joke
标 题: [合集] 这个hash估计就是uid的hash
发信站: BBS 未名空间站 (Sat Mar 27 06:29:02 2010, 美东)
☆─────────────────────────────────────☆
zhanglaosan (张老三) 于 (Fri Mar 26 21:00:13 2010, 美东) 提到:
你去google那些hash值，每个人的值在互联网上都无数结果。一般各种hash算法不同的
字符hash值肯定不撞车，说明原始值肯定是很普通的东西
这么说来，我估计就是每个人注册id后的uid数字的简单hash
☆─────────────────────────────────────☆
crashinfo (跨世因佛§梦幻泡影) 于 (Fri Mar 26 21:02:55 2010, 美东) 提到:
你找个MD hash generator试一下？
☆────────────────────────────── |
|
B*****7
发帖数: 137 | 9 我最近在学clrs，觉得universal hashing这节挺dry的，看的比较困惑，想跟大家请教
一些问题。
在实际应用中，the size of the set of hashing functions大概有多大？几百？几千
？对每个hashing function，是不是都在内存中存一份hash table? If so, is it
fair to say that universal hashing is a trade off between memory and CPU
time?
另外，以数据库为例，如果库的数据更新了，比如插入或删除了一个纪录，那更新所有
的hash tables的时间复杂度是不是O(n), where n is the number of hash tables?
先谢谢啦～ |
|
h******3
发帖数: 351 | 10 hash function is important in implementing hash table. I know that in java
Object has its hash code, which might be generated from weak hash function.
Following is one snippet that is "supplement hash function"
static int hash(Object x) {
int h = x.hashCode();
h += ~(h << 9);
h ^= (h >>> 14);
h += (h << 4);
h ^= (h >>> 10);
return h;
}
Can anybody help to explain what is the fundamental idea of a hash algorithm
? to generate non-duplicate |
|
l******9
发帖数: 579 | 11 This question is related to my previous question.
I need to design a hash that is embedded with another hash in R in Rstudio
on Win 7.
library(hash)
myf <- function()
{
h1 <- hash()
if (!has.key("first", h1))
{
list1 <- list()
h1.son<- hash()
h1.son["first_son"] <- list1
h1["first"] <- h1.son
}
# second check
if(!has.key("first_son", h1["first"]))
{
list1 <- list()
h1.son<- hash()
h1.son["first_son"] <- list1
h1["first"] <- h1.son
}
}
myf()
Why in "second check ", h1["first"] st... 阅读全帖 |
|
B*****7
发帖数: 137 | 12 这个我理解，但我不理解的是如何用多个hashing function却只用一个hash table。
举个例子吧。key1 and key2 are mapped to m1 by hashing function h1, and to m2
by hashing function h2. Apparently, the addresses of elements with key1 and
key2, respectively, are stored in slot m1 by h1. When the hashing function
is changed to h2, how do their addresses magically appear in slot m2 without
storing another hash table with their keys already mapped to m2?
困惑中～～ |
|
c*********u
发帖数: 361 | 13 基本概念，不过问得比较细，觉得比较有参考价值。(这里语言用的是Java)
1. What is a hash table?
2. What does Java do when it creates a hash table?(details, size, load facto
r, etc)
3. How is the hash table implemented to ensure constant lookup time?
4. How is each element of the hash table implemented?
4. Say you have a hash table of size 10 and load factor of 0.5, what ha
ppens when you insert a 6th element? Why? |
|
K******g
发帖数: 1870 | 14 经常有人说用hash，比如对一些1 million个字符串，有人建议建立一个hash table，
那请问怎么选择hash function？能给几个常见的吗？
还有，有1 million个file，有人说可以根据file的内容建立hash，请问用什么hash
function好？能举出几个例子吗？多谢 |
|
P*******b
发帖数: 1001 | 15 不会java。wiki上这么说的：
In computer science, a hash table or hash map is a data structure that uses
a hash function to map identifying values, known as keys, (e.g., a person's
name) to their associated values (e.g., their telephone number). The hash fu
nction is used to transform the key into the index (the hash) of an array el
ement (the slot or bucket) where the corresponding value is to be sought. |
|
g*********s
发帖数: 1782 | 16 hartime123 once posted the doubt and it seems not answered yet.
we all know universal hash is a hash function family H that has the
similar hash property.
for the insert op, we randomly select h from H and apply h to the input
key k and put it to h(k)
but what if now we need to query if k is in the hash table? we don't know
which hash function h is used to insert k. iterating H one by one
looks too naive. |
|
t******r
发帖数: 209 | 17 就是前几天有人贴的这个题吧：
Userid PageID
A 1
A 2
A 3
B 2
B 3
C 1
B 4
A 4
找出最常用的length-3访问序列：对于用户A：1-2-3， 2-3-4 用户B：2-3-4
2-3-4 是最常见的
两个hash，一个user hash，每一项存userid和对应的三连击中的前两个值；一个三连
击hash，存三连击string和count。
对于logfile中的每一行，在这两个hash中查找并更新。如果认为每次hash的复杂度为O
(1),则总的时间复杂度为O(n)。空间复杂度为O(m+k)，m为userid的个数，k为不同的三
连击的个数。 |
|
B*****7
发帖数: 137 | 18 这也是我比较困惑的地方。如果不换hash table, 换hashing function的意义在哪里呢
？因为hashing function最终要map到hash table去找地址，如果不换hash table, n个
key占一个slot的情况永远都不会变啊，如果有的话。 |
|
h*******e
发帖数: 1377 | 19 要自己加hash function的，我写了一个总算过了编译了
namespace std {
template <>
struct hash >
{
typedef std::size_t result_type;
result_type operator()(const pair & t) const
{
return t.first * 1000003 + t.second;
}
};
}
备注 (不过似乎不太好~~ 似乎 hash值 溢出了~~~ )但是也过了oj了。
有没有人写过这个hash, 这个似乎是c++ 0x/11新标准 ~~这个hash函数该怎么写才能
写得简单少冲突而又 不越界呢~~
gcd非常少的代码的。就是辗转相除一行代码就行。 |
|
h*******e
发帖数: 1377 | 20 要自己加hash function的，我写了一个总算过了编译了
namespace std {
template <>
struct hash >
{
typedef std::size_t result_type;
result_type operator()(const pair & t) const
{
return t.first * 1000003 + t.second;
}
};
}
备注 (不过似乎不太好~~ 似乎 hash值 溢出了~~~ )但是也过了oj了。
有没有人写过这个hash, 这个似乎是c++ 0x/11新标准 ~~这个hash函数该怎么写才能
写得简单少冲突而又 不越界呢~~
gcd非常少的代码的。就是辗转相除一行代码就行。 |
|
n*******e
发帖数: 55 | 21 电面的时候被问到，自己对hash table不太熟，感觉回答的不是太好，麻烦大家给看一下
要你不用C/C++原有的hash类，自己design一个hash table的class，用伪代码写一个给
这个table赋值和取值的函数，而且已经给了你一个hash function
unsigned int hash(char *), 假设没有任何collision
结果我就卡在怎么样来存储这些index上了，为了实现O（1）的search time，很自然我
会想用数组来做，但是你有不可能浪费这么多内存生成一个2^32（4GB，unsigned int
的range)size的数组。
抱歉本人不是CS的背景，麻烦知道的高手给解释一下？谢谢了 |
|
b*********n
发帖数: 464 | 22 写过几年程序，从未用过hash table, technical电面之前两次提到hash table. c/c++
有标准的hash table实现吗？感觉hash function得自己选啊 |
|
g*****k
发帖数: 623 | 23 我理解的是每一个hash table建立之后hash function h就已经绑定了。
只是建立hash table之前你随机选择H中的一个h而已。
不是每次都要随机选择h来compute hash key |
|
d****o
发帖数: 1055 | 24 hash table里面存储key本身吗？比如说有5billion个超长的URL,我用md5 转换之后的
值作为hash table的key,然后把所有的URL存进hash table, 那么这个hash table 有多
大？多谢。能放进一个4GB内存的机器吗？
理论上面说，一个5billion个URL 被md5后有 5G*16B = 80GB。 |
|
j******2
发帖数: 362 | 25 在那道"找两个超大文件里共同的url"的题里，要把每个url算hash再模10，存到小文件
里，不知道怎么算string的hash，找到一个
#include
void main()
{
string s=...
locale loc;
const collate& coll = use_facet >(loc);
long hash = coll.hash(s.data(),s.data()+s.size());
}
不知道是不是常规的算法？对locale, collate, use_facet都很陌生。 |
|
e****9
发帖数: 316 | 26 有n个很长的字符串，比如
abcd....
bacd....
cabd....
........
有没有一个hash算法，使第一个字串的生成的hash值小于第二个，第二个hash值小于第
三个？
就是hash之后，不改变原来的排序。 |
|
g*****g
发帖数: 34805 | 27 我老提供个思路吧。从尾部截取一个固定长度，比如最长1K，以md5做hash，以hash值
为key放入Cassandra DB，原始url为column name，column name是排序好的. 产生一个
UUID来作为tinyurl的索引。Quorum Read/Write
也就是说用hash粗比较，用原始url在相同hash里面做两分比较。这是个分布式数据库
，整个架构可以linear scaleout。
另外，既然是公开的服务，被猜到索引并不是问题，也不会是要求。 |
|
x*j
发帖数: 271 | 28 Hash Table---the Bucket World of an Object
一个对象的桶世界
In computer science, a hash table is a data structure that map keys to
objects using a hash function. In an ideal world, each key is assigned to a
unique bucket, resulting a single object in each bucket. When two or more
objects are in the same bucket, this is called a collision. If the hash
table has too many collisions, rehashing is needed.
迷迷糊糊醒来的时候，桶世界依旧没有什么变化，只有胸前变了的钥匙... 阅读全帖 |
|
i********g
发帖数: 41 | 29 ft, 不过听起来好像workable，但是正确性没有保证啊，自己review不太可能吧，数据
量太大了。
我还是想知道如果hash的话该怎么弄。
我刚才已经在网上找到了hash的code，可以把每个B的值都hash成char(32)了，但是有
什么办法把每个a对应的那些hash(b)的值aggregate成一个呢？好像sql也不支持bit
wise xor阿。想把char(32) convert 或者 cast到 numeric之类的也总是报错。
review |
|
y****r
发帖数: 17 | 30 hash of hash means the value is another hash table.
//I am using mysql |
|
c****r
发帖数: 185 | 31 hash of hash is weird.
Why don't you use (key of hash1,key of hash2) as a new key.
Then you have only one hash. |
|
w****o
发帖数: 2260 | 32 【 以下文字转载自 JobHunting 讨论区 】
发信人: winhao (勇敢的人), 信区: JobHunting
标 题: 弱弱的问问hash, hashtable?
发信站: BBS 未名空间站 (Wed Mar 7 22:13:29 2012, 美东)
大概知道hash, hashtable的概念，主要是为了快速的lookup。
可是如果面试的时候被问到hash, hashtable,通常他们要考核的是什么？是要实现一个
好的hash fuction呢？还是要实现一个hashtable的class?
平时自己写代码的时候如果要用到一个hashtable,是不是可以用C++ STL tr1/
hashtable来当做一个hashtable?
看了下面的链接，说是C++新的标准定义了四类hashtable,分别叫 unordered_set,
unordered_map, unordered_multiset, unordered_multimap.这些是通常意义上的
hashtale吗？
http://en.wikipedia.org/wiki/C%2B%2B0x
这个... 阅读全帖 |
|
h*****u
发帖数: 109 | 33 主要目的想节省cpu。好的hash functions要减少collision, 加上自身efficient.
缺省的用std::hash, 似乎是基于murmur32
试过city hash, xxhash, 都是比较推荐的。但都比不上std::hash。
各位高手请指教 :) |
|
S******r
发帖数: 4421 | 34 MD5, like other cryptographic hashing, is indeed a one-way function
Despite the attacks shown by Wang in 2004, its resilience to reverse
operations is still safe.
Those hackings of database are mostly related to SQL injection attacks, and
have no f*king business with the security of cryptographic functions.
The only thing relevant is that once the password hash is obtained, an
attacker can use brute-force or dictionary attacks to guess the password.
But few decent companies use MD5 to generate p... 阅读全帖 |
|
m*********w
发帖数: 6004 | 35 【 以下文字转载自 board 讨论区 】
发信人: milkswallow (失业失学失恋☆我的名字依然叫牛奶燕), 信区: board
标 题: 科苑台版後乃燕時代開啟時刻的若干回想 作者：hash
发信站: BBS 未名空间站 (Sat Dec 27 04:07:12 2008)
發信人: hash (hashing), 信區: Taiwan
標 題: 科苑台版後乃燕時代開啟時刻的若干回想
發信站: BBS 科苑星空站 (Wed Dec 1 14:33:15 2004), 站內
乃燕為了學習的緣故辭斑主而去,科苑台版創版以來的第一個時代結束了。
順之而起的，應該是被叫做後乃燕時代的。
在這個上下傳承的時期，回味一下乃燕時代，展望一下未來，似乎是件很自然的事。
在此，絕不品評乃燕，因為不需要，老友們都知道她，都瞭解她。
其實，台版的乃燕時代是由一群熱心朋友來支撐和澆灌的。
在那個時期，大家也少不了唇槍舌箭，也有很多情緒化的相互指稱，
因為在台海這樣一個背景下，雙方不同思想和理念的碰撞是一個必然。
但是，揮之不去的溫馨友愛氣息卻是乃燕時代的主流風格。
這種氛圍的根源是相互的尊重、理 |
|
r****o
发帖数: 1950 | 36 如果想把一个整数对(x,y)hash到另一个整数z，假设有很多这样的整数对，
那么这个hash function怎么设计比较好才不会导致collison很多？ |
|
a*****k
发帖数: 704 | 37 How to scale this up or down in this case?
Say my hash function calculate the hash code by dividing the size of the
vector,
and when number of the items accumulate/decrease to some critical value,
what should I do? I can put some slots in the vector, but then do I have to
go through the whole collection, recalculate their hash values, and put
them in the right places? |
|
a*d
发帖数: 47 | 38 The complexity of computing hash function is also a key factor, because it
is very common for hash function to be called inside a loop.
MD5 is good in terms of collision rate, but it is expensive to compute.
There is no cure-all hash functions for all applications. Many factors need
to be considered for real application.
上有 |
|
s*********e
发帖数: 36 | 39 求教各位牛人：
如果一个search engine系统从网上crawling很多的URL，为了保存不重复的URL，我们
用hash
table解决。这是个distributed hash table，分别保存在一个network里的各个节点上
。请问，
有什么比较好的hash function把一个URL map到一个节点上？
多谢！ |
|
q****x
发帖数: 7404 | 40 anyone know the answer of the following?
CLRS v3:
As Exercise 11.3-3 asks you to show, choosing m = 2^p - 1 when k is a
character string interpreted in radix 2p may be a poor choice, because
permuting the characters of k does not change its hash value.
11.3-3
Consider a version of the division method in which h(k) = k mod m, where
m = 2^p - 1 and k is a character string interpreted in radix 2^p. Show
that if we can derive string x from string y by permuting its characters,
then x and y hash to... 阅读全帖 |
|
P**********c
发帖数: 3417 | 41 假设是用C/C++, 不会Java. C/C++没有很方便的hash table可用，怎么办呢？比如说要
hash一堆浮点数或者一堆string, 是不是还要自己想一个hash function呢。但是自己
想的function肯定又有collision问题和有一些空间空着的问题，感觉white board很不
好写啊。
C++的map是BST, runtime完全不对啊。大家怎么解决这个问题的。 |
|
s*****n
发帖数: 5488 | 42 面bb? 放狗吧。 简单的如下。还可以看看top coder里面关于stl的讨论。
hash set : just key.
hash_map: key value pair
map : is bst
hash table : is hash table.
linked hashmap: not sure what it is.
系: 和区别？ |
|
w****o
发帖数: 2260 | 43 大概知道hash, hashtable的概念，主要是为了快速的lookup。
可是如果面试的时候被问到hash, hashtable,通常他们要考核的是什么？是要实现一个
好的hash fuction呢？还是要实现一个hashtable的class?
平时自己写代码的时候如果要用到一个hashtable,是不是可以用C++ STL tr1/
hashtable来当做一个hashtable?
看了下面的链接，说是C++新的标准定义了四类hashtable,分别叫 unordered_set,
unordered_map, unordered_multiset, unordered_multimap.这些是通常意义上的
hashtale吗？
http://en.wikipedia.org/wiki/C%2B%2B0x
这个链接还说hashtables 是 unordered associative containers。我觉得
associative containers都是 (key, value)这样的。可是通常的简单的hashtable，也
就只有key,没有value, 不是ass... 阅读全帖 |
|
e****9
发帖数: 316 | 44 用hash的目的是缩减所需要的存储
比如下面的字串长度可能是1000生成long的hash只要8 bytes.
abcd....
但是同时还要用这些字串来排序，hash之后排序完全没有了。
现在就想要没有一个算法，既可对原来的字串做某种压缩，并且压缩之后的不改变原来
的排序顺序。 |
|
d*s
发帖数: 699 | 45 universal hashing，按我的理解，是在每次create instance的时候用随机的hash
function, 一旦instantiated之后就不变了，也就是说你的table只要存在就用同样的
hash function访问，但你想攻击我的系统，我只要做一个新的table出来，然后把原来
的数据全部copy过来就行了。这个cost amortized之后就忽略不计了 |
|
A***o
发帖数: 358 | 46 Linear hashing, extensible hashing
如果有1M个数，每个数大概是100,0000,0000这样的整数，是不是hash table的size也
要很大啊，比如说等于数组中的最大数。最近做coursera上的algor........ |
|
A*********t
发帖数: 64 | 47 存在这样的hash么？如hash("hello world") = hash("world hello")。就是里面word
的order是irrelevant的。求大虾指点。 |
|
a**********0
发帖数: 422 | 48 需要一个family of hash functions 具体大家都选用什么hash function呢？
另外wiki上写minhash是LSH的特例 我自己也觉得minhash也需要k个hash functions
但是大多数的document processing都把minhash和LSH算作独立的两个stage。。。 |
|
h*******e
发帖数: 1377 | 49 请问第一和 第二个附加问题防止被猜中有什么方法么，在hash 出来的id 后面 随机
pigback 一个 rand(10000)的数么。。可是这样又怎么能防止两次产生不同的数呢。。
。或者 可以pigback 一个数根据前面的hash 计算出来的一个 0 10000之间分布均匀的
数。是这样子么。
请问多个机器应该怎样呢。。是不是hash 时候 加lock呢。分布系统我不是特别熟悉的
。 |
|
l********e
发帖数: 103 | 50 面试时候
被问到 写个 多线程的hash table
hash table我用linked list解决collision 问题
加lock的时候 我说 要用read write lock
hash table insert 时候用write lock
get的时候用read lock
然后 面试官跟我说
get的时候 不用加任何lock
大不了 get的值是旧的
（我当时 没说话 心想 只要 让我过 你说什么都好）
不过 我不明白为什么get不用加任何lock
如果 一个现在正在更改 一个值 改着一半的时候
正好另一个线程过来读 这时候 岂不是 读出来的值 一般旧一半新
请问各位大侠 我哪里对多线程理解错了？
请指点
谢谢 |
|
