1.2.2 缓存和Hash表

icedragon

1.2.2. 缓存和Hash表
通常使用一个缓存来提高性能。在网络代码中, 有缓存用于 L3层-到-L2层 映射 (像 IPv4 的用于 ARP 缓存 ),用于路由表缓存, 等等

缓存查询的常规方式通常是输入一个叁数到缓存，来判断缓存是否错过这个参数，如果失败就应该新建一个新的元素而且把它加入到缓存中。 其他的查询方式只是始终添加丢失的元素。

缓存经常通过Hash表来执行。内核提供一组数据类型, 像是单行道和双向性目录，他们能用来做为构造阻塞通过简易的Hash表

对相同的值处理的标准方法是操作 Hash 把他们放入一个列表中。通过这个表可以充分持久的使用 Hash key 来做查询。 因此, 最重要的是输入 Hash 表对于同样的值尽可能的少。

当查询时间在一张 Hash 表 (是否它使用一个缓存) 上是一个临界的叁数对于子系统的拥有者, 它可能实现一个机制去增加 Hash 表的大小以便降低列表内容碰撞的平均长度和改善平均的查询时间。一个例子在第 34 章中 " 由子网掩码动态恢复的Hash表" 。

你也可能找像邻近层这样的子系统,用来增加一个任意的成份(经常变化的)作为关键(Key)用来分配元素在缓存的桶 。 这用来减少针对集中Hash表的元素进入一个桶子中的拒绝式服务类攻击 (Dos)的损害。 参考 在第 27 章中 " 缓存 " 的例子
/*看不懂这段话意思的朋友 可以参考下HASH的桶概念
散列文件的存储单位称为桶（BUCKET）。假如一个桶能存放m个记录，当桶中已经有m个同义词（散列函数值相同）的记录时，存放第m+1个同义词会发生“溢出”。此时需要将第m+1个同义词存放到另一个“溢出桶”的桶中。相对的，称存放 前m个同义词的桶称为基桶。溢出处桶和基桶大小相同，用指针链接。查找指定元素记录时，首先在基桶中查找。若找到，则成功返回，否则沿指针到益处桶中查找。为了简化起见，散列文件的存储单位以内存单元表示------译者注*/


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/1880/showart_71269.html