Editing Hash table (section)

==== Caching and locality of reference ====
The linked list of separate chaining implementation may not be [[Cache-oblivious algorithm|cache-conscious]] due to [[spatial locality]]—[[locality of reference]]—when the nodes of the linked list are scattered across memory, thus the list traversal during insert and search may entail [[CPU cache]] inefficiencies.<ref name="nick05">{{cite book |doi=10.1007/11575832_1 |chapter=Enhanced Byte Codes with Restricted Prefix Properties |title=String Processing and Information Retrieval |series=Lecture Notes in Computer Science |date=2005 |last1=Culpepper |first1=J. Shane |last2=Moffat |first2=Alistair |volume=3772 |pages=1–12 |isbn=978-3-540-29740-6 }}</ref>{{rp|p=91}}

In [[cache-oblivious algorithm|cache-conscious variants]] of collision resolution through separate chaining, a [[dynamic array]] found to be more [[CPU cache|cache-friendly]] is used in the place where a linked list or self-balancing binary search trees is usually deployed, since the [[Memory management (operating systems)#Single contiguous allocation|contiguous allocation]] pattern of  the array could be exploited by [[Cache prefetching|hardware-cache prefetchers]]—such as [[translation lookaside buffer]]—resulting in reduced access time and memory consumption.<ref>{{cite journal |last1=Askitis |first1=Nikolas |last2=Sinha |first2=Ranjan |title=Engineering scalable, cache and space efficient tries for strings |journal=The VLDB Journal |date=October 2010 |volume=19 |issue=5 |pages=633–660 |doi=10.1007/s00778-010-0183-9 }}</ref><ref>{{Cite conference | title=Cache-conscious Collision Resolution in String Hash Tables | first1=Nikolas | last1=Askitis | first2=Justin | last2=Zobel |date=October 2005 | isbn=978-3-540-29740-6 | pages=91–102 | book-title=Proceedings of the 12th International Conference, String Processing and Information Retrieval (SPIRE 2005) | doi=10.1007/11575832_11 | volume=3772/2005}}</ref><ref>{{Cite conference |title       = Fast and Compact Hash Tables for Integer Keys |first1      = Nikolas |last1       = Askitis |year        = 2009 |isbn        = 978-1-920682-72-9 |url         = http://crpit.com/confpapers/CRPITV91Askitis.pdf |pages       = 113–122 |book-title     = Proceedings of the 32nd Australasian Computer Science Conference (ACSC 2009) |volume      = 91 |url-status  = dead |archive-url  = https://web.archive.org/web/20110216180225/http://crpit.com/confpapers/CRPITV91Askitis.pdf |archive-date = February 16, 2011 |df          = mdy-all |access-date = June 13, 2010 }}</ref>