Hashing 的技术

Basic c++/java string hasing algorithm and rational behind it:

In Java, the hash code for a String object is computed as

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

https://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

using int arithmetic, where s[i] is the ith character of the string, n is the length of the string, and ^ indicates exponentiation. Why is 31 used as a multiplier? So why not 29, or 37, or even 97?

Consistent hashing: 在分布系统中,通过hashing请求打到不同的server上, 不同的server自然就各自cache了一部分数据。 这里可能出现的一个问题就是如果一个server down了。 理论上需要每个server的cache数据都需要作废,因为hash function发生了改变。 Consistent hashing 就是为了解决这个问题。 具体做法如下, 假设hash function的目的是产生N个桶, 我们在 [0, 1] 的区间内产生  为没个桶产生L 个随机数。 这样[0,1]上面就会有L*N个随机数。当每一个请求来后,我们随机生成一个[0,1]的随机数,看一下这个数落在了哪两个随机数之间。 取前面那个随机数对应的桶好就好了。

这个做法的好处是,当一个机器故障时, 等同于我们只是在 [0,1]上面这 L*N 点中,均匀的移除了L个点, 对应大多数的请求, hash对应的桶号并没有改变。

Extended linear hashing

Advertisements
Hashing 的技术

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s