1.2.2. Caching and Hash Tables 高速緩存和哈希表

1.2.2. Caching and Hash Tables

It is pretty common to use a cache to increase performance. In the networking code, there are caches for L3-to-L2 mappings (such as the ARP cache used by IPv4), for the routing table cache, etc.

我們經常會用緩存來提高處理速率。在網絡程式設計中，L3-to-L2 對應，路由表等都用到了緩存。

Cache lookup routines often take an input parameter that says whether a cache miss should or should not create a new element and add it to the cache. Other lookup routines simply add missing elements all the time.

高速緩存查找例程經常使用一個輸入參數來訓示，當高速緩存中沒有所要查找的元素時，是建立該元素并添加到高速緩存還是什麼都不做。其他的一些查找例程總是簡單的添加不存在的元素。

Caches are often implemented with hash tables . The kernel provides a set of data types, such as one-way and bidirectional lists, that can be used as building blocks for simple hash tables.

高速緩存一般用HASH表來管理，核心提供了多種資料結構來建立哈希表，例如單連結清單和雙連結清單。

The standard way to handle inputs that hash to the same value is to put them in a list. Traversing this list takes substantially longer than using the hash key to do a lookup. Therefore, it is always important to minimize the number of inputs that hash to the same value.

處理hash到同一個元素的标準方法是将他們放進一個連結清單。周遊一個連結清單比使用hash關鍵字的查找要費時的多，是以減少hash到同一進制素的輸入數是非常重要的。

When the lookup time on a hash table (whether it uses a cache or not) is a critical parameter for the owner subsystem, it may implement a mechanism to increase the size of the hash table so that the average length of the collision lists goes down and the average lookup time improves. See the section "Dynamic resizing of per-netmask hash tables" in Chapter 34 for an example.

當hash表的查詢時間在所屬子系統中是一個嚴格限制時，應該采取某種機制增加hash表的長度，這樣沖突連結清單的平均長度将會減小而平均查詢時間将得到改善。參閱第三十四章中“per－netmask hash表動态變化尺寸”一節。

You may also find subsystems, such as the neighboring layer, that add a random component (regularly changed) to the key used to distribute elements in the cache's buckets. This is used to reduce the damage of Denial of Service (DoS) attacks aimed at concentrating the elements of a hash table into a single bucket. See the section "Caching" in Chapter 27 for an example.

在子系統中，如臨層，經常會在配置設定元素的關鍵字中增加一個随機數。這是用來減少那些試圖将大量元素hash入相同VAlue值的Dos（拒絕服務攻擊）攻擊的危害。