hashing 的一些变形和应用

最近看的 blog / code 多少都涉及到 hashing,于是就写一个杂谈吧。

首先是 ELF 动态库 的载入过程。程序载入动态库的时候需要在库的动态符号表中查找需要的符号并进行重定位。不难想象查找的过程使用了 hash 表以提高效率。几年前 GNU ELF 对原有的实现作了增强,其中之一就是在 hash 表的查找之前加了一个 Bloom 过滤器。Bloom 过滤器是一个用一组独立的 Hash 函数实现的用来测试元素是否属于某集合的随机数据结构,存在第二类错误(元素不属于集合,但测试表示属于),不存在第一类错误。因为在动态载入过程中,一般只有一个库会拥有给定符号,所以 Bloom 过滤器往往能直接过滤掉大多数库中不存在的符号,跳过更昂贵的查找动态符号表的过程。GNU Hash ELF Sections 这篇 blog 给了更详尽的介绍和实现细节。

另一种是在常在分布式系统中使用的 一致 hashing(consisitent hashing)。简单而言,就是给 hash 值空间加上距离的测度,同时将各分布式的服务器(随机的)映射到值空间上的数个点,最后按照值到服务器的距离将数据存放到对应的服务器。Consistent Hashing 这篇 blog 有非常直观的介绍。一个应用是分布式 hash 表。

memcached 使用的是 Bob Jenkins 的 hash 函数和实现。他有一篇相当详细的 hash 函数的实现的比较的 blog The Hash

Advertisements
This entry was posted in Computer and Internet, Programming and Algorithm, Science and tagged , . Bookmark the permalink.

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