以图明志

数据结构

Hash魔法:哈希表的工作原理与常用操作

一种高效的数据结构
哈希表(Hash Table)的应用近两年才在NOI中出现,作为一种高效的数据结构,它正在竞赛中发挥着越来越重要的作用。 哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下,用空间换时间的做法是值得的。另外,编码比较容易也是它的特点之一。

数据结构

Hash魔法:分布式哈希算法

降低了数据全部被损坏的风险
哈希表把所有的东西都存储在一台机器上,当这台机器坏掉了之后,所存储的东西就全部消失了。分布式哈希表可以把一整张哈希表分成若干个不同的部分,分别存储在不同的机器上,这样就降低了数据全部被损坏的风险。分布式哈希表通常采用一致性哈希函数来对机器和数据进行统一运算。这里先不用深究一致性哈希究竟是什么。

数据结构

Hash魔法:一致性 hash 算法

consistent hashing
consistent hashing 一致性 hash 算法早在 1997 年就在论文 Consistent hashing and random trees 中被提出,目前在 cache 系统中应用越来越广泛。比如你有 N 个 cache 服务器(后面简称 cache ),那么如何将一个对象 object 映射到 N 个 cache 上呢,你很可能会采用类似下面的通用方法计算 object 的 hash 值,然后均匀的映射到到 N 个 cache。

数据结构

Hash魔法:哈希表的原理与实现

用C实现一个Hash表
一列键值对数据,存储在一个table中,如何通过数据的关键字快速查找相应值呢?不要告诉我一个个拿出来比较key啊,呵呵。 大家都知道,在所有的线性数据结构中,数组的定位速度最快,因为它可通过数组下标直接定位到相应的数组空间,就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的结构解决以上的问题的。
1 / 1 首页 < Prev 1 Next > 尾页 页码: