{"id":451,"date":"2020-08-18T19:23:47","date_gmt":"2020-08-18T20:23:47","guid":{"rendered":"http:\/\/www.linux-tutorial.info\/?page_id=77"},"modified":"2020-08-22T19:26:01","modified_gmt":"2020-08-22T20:26:01","slug":"this-is-the-page-title-toplevel-284","status":"publish","type":"page","link":"http:\/\/www.linux-tutorial.info\/?page_id=451","title":{"rendered":"Hash Tables"},"content":{"rendered":"\n<title>Hash Tables<\/title>\n<p>\nLinked lists are handy ways of tying data structures together, but navigating\n<glossary>linked list<\/glossary>s can be inefficient.\nIf you were searching for a particular element, you might easily have to look at the whole\nlist before you find the one that you need.\nLinux uses another technique, <em>hashing<\/em>, to get around this restriction.\nA <em>hash table<\/em> is an <em>array<\/em> or <em>vector<\/em> of pointers.\nAn array, or vector, is simply a set of things coming one after another in memory.\nA bookshelf could be said to be an array of books.\nArrays are accessed by an <em>index<\/em>, which is an offset into the array&#8217;s associated\narea in memory.\nTaking the bookshelf analogy a little further, you could describe each book by its position\non the shelf; you might ask for the 5th book.\n<p>\nA hash table is an array of pointers to data structures and its index is derived from information\nin those data structures.\nIf you had data structures describing the population of a village then you could use a person&#8217;s\nage as an index.\nTo find a particular person&#8217;s data you could use their age as an index into the population hash\ntable and then follow the pointer to the data structure containing the person&#8217;s details.\nUnfortunately many people in the village are likely to have the same age and so the hash\ntable pointer becomes a pointer to a chain or list of data structures each describing people\nof the same age.\nHowever, searching these shorter chains is still faster than searching all of the data\nstructures.\n<p>\nAs a hash table speeds up access to commonly used data structures, Linux often uses hash tables\nto implement <em>caches<\/em>.\nCaches are handy information that needs to be accessed quickly and are usually a subset\nof the full set of information available.\nData structures are put into a cache and kept there because the kernel often\naccesses them.\nThe drawback to caches is that they are more complex to use and maintain than simple\nlinked lists or hash tables.\nIf the data structure can be found in the cache (this is known as a <em>cache hit<\/em>),\nthen all well and good.\nIf it cannot then all of the relevant data structures must be searched and, if the\ndata structure exists at all, it must be added into the cache.\nIn adding new data structures into the cache an old cache entry may need discarding.\nLinux must decide which one to discard, the danger being that the discarded data structure\nmay be the next one that Linux needs.\n","protected":false},"excerpt":{"rendered":"<p>Hash Tables Linked lists are handy ways of tying data structures together, but navigating linked lists can be inefficient. If you were searching for a particular element, you might easily have to look at the whole list before you find &hellip; <a href=\"http:\/\/www.linux-tutorial.info\/?page_id=451\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-451","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"http:\/\/www.linux-tutorial.info\/index.php?rest_route=\/wp\/v2\/pages\/451","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.linux-tutorial.info\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"http:\/\/www.linux-tutorial.info\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"http:\/\/www.linux-tutorial.info\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.linux-tutorial.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=451"}],"version-history":[{"count":1,"href":"http:\/\/www.linux-tutorial.info\/index.php?rest_route=\/wp\/v2\/pages\/451\/revisions"}],"predecessor-version":[{"id":575,"href":"http:\/\/www.linux-tutorial.info\/index.php?rest_route=\/wp\/v2\/pages\/451\/revisions\/575"}],"wp:attachment":[{"href":"http:\/\/www.linux-tutorial.info\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=451"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}