ในวิทยาการคอมพิวเตอร์ตารางแฮชเป็นโครงสร้างข้อมูลที่ใช้การจัดเรียง^แบบเชื่อมโยงหรือเรียกอีกอย่างว่าพจนานุกรมหรือแผนที่การจัดเรียงแบบเชื่อมโยงเป็นชนิดข้อมูลนามธรรมที่แมปคีย์กับค่า[ 3 ^{] ตาราง}แฮชใช้ฟังก์ชันแฮชเพื่อคำนวณดัชนีหรือเรียกอีกอย่างว่ารหัสแฮชลงในอาร์เรย์ของบัคเก็ตหรือสล็อตซึ่งสามารถค้นหาค่าที่ต้องการได้ ในระหว่างการค้นหา คีย์จะถูกแฮช และแฮชที่ได้จะระบุว่าค่าที่สอดคล้องกันถูกจัดเก็บไว้ที่ใด แผนที่ที่ใช้โดยตารางแฮชเรียกว่าแผนที่แฮช

การออกแบบตารางแฮชส่วนใหญ่ใช้ฟังก์ชันแฮชที่ไม่สมบูรณ์ การชนกันของแฮชซึ่งฟังก์ชันแฮชสร้างดัชนีเดียวกันสำหรับคีย์มากกว่าหนึ่งคีย์ จึงมักจะต้องได้รับการจัดการด้วยวิธีใดวิธีหนึ่ง กลยุทธ์ทั่วไปในการจัดการการชนกันของแฮช ได้แก่ การเชื่อมโยง ซึ่งจัดเก็บองค์ประกอบหลายรายการในช่องเดียวกันโดยใช้รายการที่เชื่อมโยง และการกำหนดแอดเดรสแบบเปิด ซึ่งค้นหาช่องว่างที่ว่างถัดไปตามลำดับการตรวจสอบ^{[ 4 ]}

ในตารางแฮชที่มีขนาดเหมาะสม ความซับซ้อนของเวลาเฉลี่ยสำหรับการค้นหาแต่ละครั้งจะไม่ขึ้นอยู่กับจำนวนองค์ประกอบที่จัดเก็บในตาราง การออกแบบตารางแฮชจำนวนมากยังอนุญาตให้มีการแทรกและการลบคู่คีย์-ค่าตามอำเภอใจโดยมีต้นทุนเฉลี่ยคงที่ต่อการดำเนินการ^{[ 5 ] [ 4 ] : 513–558 [ 6 ]}

การแฮชเป็นตัวอย่างของการแลกเปลี่ยนระหว่างพื้นที่และเวลาหากหน่วยความจำมีไม่จำกัด คีย์ทั้งหมดสามารถใช้เป็นดัชนีโดยตรงเพื่อค้นหาค่าด้วยการเข้าถึงหน่วยความจำเพียงครั้งเดียว ในทางกลับกัน หากมีเวลาไม่จำกัด ค่าต่างๆ สามารถจัดเก็บได้โดยไม่ต้องคำนึงถึงคีย์ และ สามารถใช้ การค้นหาแบบไบนารีหรือการค้นหาเชิงเส้นเพื่อดึงองค์ประกอบ^{[ 7 ] : 458}

ในหลายสถานการณ์ ตารางแฮชโดยเฉลี่ยแล้วมีประสิทธิภาพมากกว่าต้นไม้ค้นหา หรือโครงสร้างการค้นหา ตารางอื่นๆด้วยเหตุนี้จึงมีการใช้งานอย่างแพร่หลายในซอฟต์แวร์ คอมพิวเตอร์หลายประเภท โดยเฉพาะอย่างยิ่งสำหรับอาร์เรย์แบบเชื่อมโยงการจัดทำดัชนีฐานข้อมูลแคชและเซต[ ^{8 ] ภาษา}โปรแกรมหลายภาษามีโครงสร้างตารางแฮชในตัว เช่นพจนานุกรมของ Python , HashMap ของ Java , unordered_map ของ C++ , แผนที่ของ Goซึ่งช่วยลดความซับซ้อนของการแฮชจากโปรแกรมเมอร์^{[ 9 ]}

แนวคิดเรื่องการแฮชเกิดขึ้นอย่างอิสระในสถานที่ต่างๆ ในเดือนมกราคม พ.ศ. 2496 Hans Peter Luhnได้เขียนบันทึกภายในของ IBMที่ใช้การแฮชร่วมกับการเชื่อมโยง ตัวอย่างแรกของการกำหนดแอดเดรสแบบเปิดได้รับการเสนอโดย AD Linh โดยต่อยอดจากบันทึกของ Luhn ^{[ 4 ] : 547} ในช่วงเวลาเดียวกันGene Amdahl , Elaine M. McGraw , Nathaniel RochesterและArthur SamuelจากIBM Researchได้นำการแฮชมาใช้กับแอสเซมเบลอร์ IBM 701 ^{[ 10 ] : 124} การกำหนดแอดเดรสแบบเปิดด้วยการตรวจสอบเชิงเส้นได้รับการยกย่องให้เป็นผลงานของ Amdahl แม้ว่าAndrey Ershovจะมีแนวคิดเดียวกันนี้โดยอิสระก็ตาม^{[ 10 ] : 124–125} คำว่า "การกำหนดแอดเดรสแบบเปิด" ถูกบัญญัติขึ้นโดยW. Wesley Petersonในบทความของเขาซึ่งกล่าวถึงปัญหาการค้นหาในไฟล์ขนาดใหญ่^{[ 11 ] : 15}

งานตีพิมพ์ชิ้นแรกเกี่ยวกับการแฮชด้วยการเชื่อมโยงได้รับการยกย่องให้แก่Arnold Dumeyซึ่งได้กล่าวถึงแนวคิดของการใช้เศษเหลือโมดูลัสจำนวนเฉพาะเป็นฟังก์ชันแฮช^{[ 11 ] : 15} คำว่า "แฮชชิ่ง" ได้รับการตีพิมพ์ครั้งแรกในบทความโดย Robert Morris ^{[ 10 ] : 126} การวิเคราะห์เชิงทฤษฎีของการตรวจสอบเชิงเส้นได้รับการเสนอครั้งแรกโดย Konheim และ Weiss ^{[ 11 ] : 15}

อาร์เรย์แบบเชื่อมโยงจะเก็บชุดของคู่ (คีย์, ค่า) และอนุญาตให้แทรก ลบ และค้นหา โดยมีข้อจำกัดของคีย์ที่ไม่ซ้ำกันในการใช้งานตารางแฮชของอาร์เรย์แบบเชื่อมโยง อาร์เรย์ที่มีความยาวจะถูกเติมด้วยองค์ประกอบบางส่วน โดยที่คีย์จะถูกแฮชโดยใช้ฟังก์ชันแฮชเพื่อคำนวณตำแหน่งดัชนีในตารางแฮช โดยที่ประสิทธิภาพของตารางแฮชขึ้นอยู่กับปัจจัยการโหลด ซึ่งกำหนดเป็นอัตราส่วนของจำนวนองค์ประกอบที่จัดเก็บต่อจำนวนช่องว่างที่มีอยู่ โดยทั่วไปแล้วปัจจัยการโหลดที่ต่ำกว่าจะทำให้การทำงานเร็วขึ้น^{[ 12 ]}ที่ดัชนีนี้ ทั้งคีย์และค่าที่เกี่ยวข้องจะถูกจัดเก็บ การจัดเก็บคีย์ควบคู่ไปกับค่าทำให้มั่นใจได้ว่าการค้นหาสามารถตรวจสอบคีย์ที่ดัชนีเพื่อดึงค่าที่ถูกต้องได้ แม้จะมีการชนกันก็ตาม ภายใต้สมมติฐานที่สมเหตุสมผล ตารางแฮชมี ขอบเขต ความซับซ้อนของเวลา ที่ดีกว่า สำหรับการค้นหา การลบ และการแทรก เมื่อเทียบกับ ต้นไม้ ค้นหาไบนารีแบบปรับสมดุลด้วยตนเอง^{[ 11 ] : 1} ${\displaystyle A}$${\displaystyle m}$${\displaystyle n}$${\displaystyle m\geq n}$${\displaystyle x}$${\displaystyle h}$${\displaystyle A[h(x)]}$${\displaystyle h(x)<m}$

ตารางแฮชยังนิยมใช้ในการสร้างเซต โดยไม่ต้องเก็บค่าสำหรับแต่ละคีย์ และเพียงแค่ติดตามว่าคีย์นั้นมีอยู่หรือไม่^{[ 11 ] : 1}

ปัจจัยการโหลด เป็นสถิติที่สำคัญของตารางแฮช และกำหนดไว้ดังนี้: ^{[ 2 ]} โดยที่ ${\displaystyle \alpha }$$${\displaystyle {\text{ตัวประกอบภาระ}}\ (\alpha )={\frac {n}{m}},}$$

• ${\displaystyle n}$คือจำนวนรายการที่ถูกใช้งานในตารางแฮช
• ${\displaystyle m}$คือจำนวนถัง

ประสิทธิภาพของตารางแฮชจะเสื่อมลงตามปัจจัยโหลด[ ^{11 ] : 2} ในกรณีที่มีขนาดใหญ่และแต่ละบัคเก็ตจะมีการกระจายแบบปัวซง ทางสถิติ โดยคาดหวังฟังก์ชันแฮช แบบสุ่ม ใน อุดมคติ${\displaystyle \alpha }$${\displaystyle m}$${\displaystyle n}$${\displaystyle \lambda =\alpha }$

โดยทั่วไปซอฟต์แวร์จะตรวจสอบให้แน่ใจว่าปัจจัยโหลดยังคงต่ำกว่าค่าคงที่ที่กำหนดไว้ซึ่งจะช่วยรักษาประสิทธิภาพที่ดี ดังนั้นวิธีการทั่วไปคือการปรับขนาดหรือ "สร้างแฮชใหม่" ตารางแฮชเมื่อใดก็ตามที่ปัจจัยโหลดถึงค่าที่กำหนดไว้ในทำนองเดียวกัน ตารางอาจถูกปรับขนาดหากปัจจัยโหลดลดลงต่ำกว่าค่าที่กำหนดไว้^{[ 13 ]}${\displaystyle \alpha }$${\displaystyle \alpha _{\max }}$${\displaystyle \alpha }$${\displaystyle \alpha _{\max }}$${\displaystyle \alpha _{\max }/4}$

ด้วยตารางแฮชแบบเชื่อมโยงแยกกัน ช่องแต่ละช่องของอาร์เรย์บัคเก็ตจะเก็บตัวชี้ไปยังรายการหรืออาร์เรย์ของข้อมูล^{[ 14 ]}

ตารางแฮชแบบแยกโซ่จะมีประสิทธิภาพลดลงเรื่อยๆ เมื่อปัจจัยโหลดเพิ่มขึ้น และไม่มีจุดคงที่ใดๆ ที่จำเป็นต้องปรับขนาดอย่างแน่นอน^{[ 13 ]}

ด้วยการเชื่อมโยงแบบแยกกัน ค่าที่ให้ประสิทธิภาพที่ดีที่สุดมักจะอยู่ระหว่าง 1 ถึง 3 ^{[ 13 ]}${\displaystyle \alpha _{\max }}$

ด้วยการกำหนดแอดเดรสแบบเปิด ช่องแต่ละช่องของอาร์เรย์บัคเก็ตจะเก็บรายการได้เพียงรายการเดียว ดังนั้นตารางแฮชแอดเดรสแบบเปิดจึงไม่สามารถมีปัจจัยการโหลดมากกว่า 1 ได้^{[ 14 ]}

ประสิทธิภาพของการกำหนดแอดเดรสแบบเปิดจะแย่ลงมากเมื่อปัจจัยโหลดเข้าใกล้ 1 ^{[ 13 ]}

ดังนั้นตารางแฮชที่ใช้การกำหนดแอดเดรสแบบเปิดจะต้องได้รับการปรับขนาดหรือสร้างแฮชใหม่หากปัจจัยโหลดเข้าใกล้ 1 ^{[ 13 ]}${\displaystyle \alpha }$

ด้วยการกำหนดแอดเดรสแบบเปิด ค่าตัวประกอบโหลดสูงสุดที่ยอมรับได้ควรอยู่ในช่วงประมาณ 0.6 ถึง 0.75 ^{[ 15 ] [ 16 ] : 110} ${\displaystyle \alpha _{\max }}$

ฟังก์ชันแฮช จะแมปจักรวาลของคีย์ไปยังดัชนีหรือช่องภายในตาราง นั่นคือสำหรับการใช้งานฟังก์ชันแฮชแบบดั้งเดิมนั้นขึ้นอยู่กับสมมติฐานจักรวาลจำนวนเต็มที่ว่าองค์ประกอบทั้งหมดของตารางมาจากจักรวาลโดยที่ความยาวบิตของถูกจำกัดไว้ภายในขนาดคำของสถาปัตยกรรมคอมพิวเตอร์ [ ^{11 ] : 2} ${\displaystyle h:U\rightarrow \{0,...,m-1\}}$${\displaystyle U}$${\displaystyle h(x)\in \{0,...,m-1\}}$${\displaystyle x\in U}$${\displaystyle U=\{0,...,u-1\}}$${\displaystyle u}$

ฟังก์ชันแฮชจะเรียกว่าสมบูรณ์แบบสำหรับเซตที่กำหนดหากเป็นฟังก์ชันหนึ่งต่อหนึ่งบน เซต นั้น กล่าวคือ หากแต่ละองค์ประกอบแมปไปยังค่าที่แตกต่างกันใน เซต นั้น^{[ 17 ] [ 18 ]}สามารถสร้างฟังก์ชันแฮชที่สมบูรณ์แบบได้หากทราบคีย์ทั้งหมดล่วงหน้า^{[ 17 ]}${\displaystyle h}$${\displaystyle S}$${\displaystyle S}$${\displaystyle x\in S}$${\displaystyle {0,...,m-1}}$

รูปแบบการแฮชที่ใช้ในสมมติฐานจักรวาลจำนวนเต็มได้แก่ การแฮชโดยการหาร การแฮชโดยการคูณ การแฮ ชแบบสากลการแฮชสมบูรณ์แบบไดนามิกและการแฮชสมบูรณ์แบบคงที่ [ ^{11 ] : 2} อย่างไรก็ตาม การแฮชโดยการหารเป็นรูปแบบที่ใช้กันทั่วไป^{[ 19 ] : 264 [ 16 ] : 110}

แผนการแฮชโดยการหารมีดังนี้: ^{[ 11 ] : 2} โดยที่คือค่าแฮชของและคือขนาดของตาราง $${\displaystyle h(x)\ =\ x\,{\bmod {\,}}ม,}$$${\displaystyle h(x)}$${\displaystyle x\in S}$${\displaystyle m}$

รูปแบบในการแฮชโดยการคูณมีดังนี้: ^{[ 11 ] : 2–3} โดยที่ เป็น ค่าคงที่ที่ไม่ใช่จำนวนเต็ม และเป็นค่าจริง และเป็นขนาดของตาราง ข้อดีของการแฮชโดยการคูณคือไม่ใช่ค่าวิกฤต^{[ 11 ] : 2–3} แม้ว่าค่าใดๆ ก็สามารถสร้างฟังก์ชันแฮชได้ แต่Donald Knuthแนะนำให้ใช้ค่าอัตราส่วนทองคำ^{[ 11 ] : 3} $${\displaystyle h(x)=\lfloor m{\bigl (}(xA){\bmod {1}}{\bigr )}\rfloor }$$${\displaystyle A}$${\displaystyle m}$${\displaystyle m}$${\displaystyle A}$

โดยทั่วไปจะใช้สตริงเป็นคีย์สำหรับฟังก์ชันแฮชหนังสือ The C++ Programming Language ฉบับที่สาม อธิบายฟังก์ชันแฮชแบบง่ายๆ ซึ่งจำนวนเต็มที่ไม่มีเครื่องหมายซึ่งเริ่มต้นเป็นศูนย์จะถูกเลื่อนไปทางซ้ายทีละบิตซ้ำๆ แล้วทำการ XOR กับค่าจำนวนเต็มของอักขระตัวถัดไป จากนั้นจึงนำค่าแฮชนี้มาหารด้วยขนาดของตาราง^{[ 20 ]}หากการเลื่อนไปทางซ้ายไม่ใช่แบบวงกลม ความยาวของสตริงควรน้อยกว่าขนาดของจำนวนเต็มที่ไม่มีเครื่องหมายอย่างน้อยแปดบิต อีกวิธีหนึ่งที่นิยมใช้ในการแฮชสตริงเป็นจำนวนเต็มคือการใช้ฟังก์ชันแฮชแบบหมุนพหุนาม

การกระจายค่าแฮชอย่างสม่ำเสมอเป็นข้อกำหนดพื้นฐานของฟังก์ชันแฮช การกระจายที่ไม่สม่ำเสมอจะเพิ่มจำนวนการชนกันและต้นทุนในการแก้ไขปัญหา บางครั้งการรับประกันความสม่ำเสมอทำได้ยากโดยการออกแบบ แต่สามารถประเมินได้โดยใช้การทดสอบทางสถิติ เช่นการทดสอบไคกำลังสองของเพียร์สันสำหรับการกระจายแบบสม่ำเสมอแบบไม่ต่อเนื่อง^{[ 21 ] [ 22 ]}

การกระจายจะต้องสม่ำเสมอเฉพาะขนาดตารางที่เกิดขึ้นในแอปพลิเคชันเท่านั้น โดยเฉพาะอย่างยิ่ง หากใช้การปรับขนาดแบบไดนามิกด้วยการเพิ่มเป็นสองเท่าและลดลงครึ่งหนึ่งของขนาดตารางอย่างแม่นยำ ฟังก์ชันแฮชจะต้องสม่ำเสมอเฉพาะเมื่อขนาดเป็นกำลังของสองเท่านั้นในกรณีนี้ ดัชนีสามารถคำนวณได้จากช่วงของบิตบางช่วงของฟังก์ชันแฮช ในทางกลับกัน อัลกอริทึมแฮชบางตัวต้องการให้ขนาดเป็นจำนวนเฉพาะ^{[ 23 ]}

สำหรับ รูปแบบ การกำหนดแอดเดรสแบบเปิดฟังก์ชันแฮชควรหลีกเลี่ยงการรัน ด้วยเช่นกัน ซึ่งก็คือการแมปคีย์สองตัวขึ้นไปไปยังช่องที่ต่อเนื่องกัน การรันดังกล่าวอาจทำให้ต้นทุนการค้นหาพุ่งสูงขึ้น แม้ว่าปัจจัยโหลดจะต่ำและการชนกันจะไม่บ่อยก็ตาม มีการกล่าวอ้างว่าแฮชแบบคูณที่เป็นที่นิยมมีพฤติกรรมรันที่ไม่ดีเป็นพิเศษ^{[ 23 ] [ 4 ]}

การแฮชแบบ K-independentเสนอวิธีการพิสูจน์ว่าฟังก์ชันแฮชบางอย่างไม่มีชุดคีย์ที่ไม่ดีสำหรับตารางแฮชประเภทที่กำหนด ผลลัพธ์ K-independence จำนวนมากเป็นที่รู้จักสำหรับแผนการแก้การชนกัน เช่น การตรวจสอบเชิงเส้นและการแฮชแบบ cuckoo เนื่องจาก K-independence สามารถพิสูจน์ได้ว่าฟังก์ชันแฮชทำงานได้ ดังนั้นจึงสามารถมุ่งเน้นไปที่การค้นหาฟังก์ชันแฮชที่เร็วที่สุดเท่าที่จะเป็นไปได้^{[ 24 ]}

อัลกอริทึมการค้นหาที่ใช้การแฮชประกอบด้วยสองส่วน ส่วนแรกคือการคำนวณฟังก์ชันแฮชซึ่งแปลงคีย์การค้นหาเป็นดัชนีอาร์เรย์กรณีในอุดมคติคือไม่มีคีย์การค้นหาสองคีย์ใดที่แฮชไปยังดัชนีอาร์เรย์เดียวกัน อย่างไรก็ตาม นี่ไม่ใช่กรณีเสมอไปและเป็นไปไม่ได้ที่จะรับประกันสำหรับข้อมูลที่ไม่เคยเห็นมาก่อน^{[ 4 ] : 515} ดังนั้นส่วนที่สองของอัลกอริทึมคือการแก้ไขการชนกัน วิธีการทั่วไปสองวิธีสำหรับการแก้ไขการชนกันคือการเชื่อมโยงแยกและการกำหนดแอดเดรสแบบเปิด^{[ 7 ] : 458}

ในการเชื่อมโยงแบบแยกกัน กระบวนการนี้เกี่ยวข้องกับการสร้างรายการเชื่อมโยงที่มีคู่คีย์-ค่าสำหรับดัชนีอาร์เรย์การค้นหาแต่ละรายการ รายการที่ชนกันจะถูกเชื่อมโยงเข้าด้วยกันผ่านรายการเชื่อมโยงเดียว ซึ่งสามารถสำรวจเพื่อเข้าถึงรายการด้วยคีย์การค้นหาที่ไม่ซ้ำกัน^{[ 7 ] : 464} การแก้ไขการชนกันผ่านการเชื่อมโยงด้วยรายการเชื่อมโยงเป็นวิธีการทั่วไปในการใช้งานตารางแฮช ให้และเป็นตารางแฮชและโหนดตามลำดับ การดำเนินการมีดังต่อไปนี้: ^{[ 19 ] : 258} ${\displaystyle T}$${\displaystyle x}$

Chained-Hash-Insert( T , k ) แทรกx ที่ส่วนหัวของรายการเชื่อมโยงT [ h ( k )] Chained-Hash-Search( T , k ) ค้นหาองค์ประกอบที่มีคีย์k ในรายการเชื่อมโยงT [ h ( k )] Chained-Hash-Delete( T , k ) ลบx จากรายการเชื่อมโยงT [ h ( k )] 

หากองค์ประกอบนั้นสามารถเปรียบเทียบได้ทั้งในเชิงตัวเลขหรือเชิงคำศัพท์และแทรกเข้าไปในรายการโดยรักษาลำดับทั้งหมดไว้ จะส่งผลให้การค้นหาที่ไม่สำเร็จยุติลงเร็วขึ้น^{[ 4 ] : 520–521}

หากคีย์เรียงลำดับ การใช้แนวคิด " การจัดระเบียบตนเอง " เช่น การใช้ต้นไม้ค้นหาไบนารีแบบปรับสมดุลตนเองอาจมีประสิทธิภาพ ซึ่งสามารถลดกรณีที่เลวร้ายที่สุดในเชิงทฤษฎี ลงได้ แม้ว่าจะทำให้เกิดความซับซ้อนเพิ่มเติมก็ตาม^{[ 4 ] : 521} ${\displaystyle O(\log {n})}$

ในการแฮชแบบเพอร์เฟกต์ไดนามิกจะใช้ตารางแฮชสองระดับเพื่อลดความซับซ้อนในการค้นหาให้รับประกันได้ในกรณีที่เลวร้ายที่สุด ในเทคนิคนี้ บัคเก็ตของรายการจะถูกจัดระเบียบเป็นตารางแฮชแบบเพอร์เฟกต์ที่มีช่องซึ่งให้เวลาค้นหาในกรณีที่เลวร้ายที่สุดคงที่ และเวลาเฉลี่ยต่ำสำหรับการแทรก^{[ 25 ]}การศึกษาแสดงให้เห็นว่าการเชื่อมโยงแยกตามอาร์เรย์มีประสิทธิภาพมากกว่า 97% เมื่อเทียบกับวิธีการรายการเชื่อมโยงมาตรฐานภายใต้ภาระหนัก^{[ 26 ] : 99} ${\displaystyle O(1)}$${\displaystyle k}$${\displaystyle k^{2}}$

เทคนิคต่างๆ เช่น การใช้ต้นไม้ฟิวชั่นสำหรับแต่ละถังยังส่งผลให้เวลาคงที่สำหรับการดำเนินการทั้งหมดด้วยความน่าจะเป็นสูง^{[ 27 ]}

รายการเชื่อมโยงของการใช้งานการเชื่อมโยงแบบแยกส่วนอาจไม่คำนึงถึงแคชเนื่องจากความใกล้เคียงเชิงพื้นที่ — ความใกล้เคียงของการอ้างอิง — เมื่อโหนดของรายการเชื่อมโยงกระจายอยู่ทั่วหน่วยความจำ ดังนั้นการท่องรายการระหว่างการแทรกและการค้นหาอาจทำให้เกิดความไม่ eficiente ของแคช CPU ^{[ 26 ] : 91}

ในรูปแบบที่คำนึงถึงแคชของการแก้ไขการชนกันผ่านการเชื่อมโยงแยกกันอาร์เรย์แบบไดนามิกที่พบว่าเป็นมิตรกับแคช มากกว่า จะถูกนำมาใช้ในตำแหน่งที่ปกติแล้วจะใช้รายการเชื่อมโยงหรือต้นไม้ค้นหาไบนารีแบบปรับสมดุลด้วยตนเอง เนื่องจาก รูปแบบ การจัดสรรที่ต่อเนื่องของอาร์เรย์สามารถใช้ประโยชน์ได้โดยตัวดึงข้อมูลแคชฮาร์ดแวร์เช่นบัฟเฟอร์การมองหาการแปลส่งผลให้เวลาในการเข้าถึงและการใช้หน่วยความจำลดลง^{[ 28 ] [ 29 ] [ 30 ]}

การกำหนดแอดเดรสแบบเปิดเป็นเทคนิคการแก้ไขการชนกันอีกวิธีหนึ่ง โดยที่บันทึกรายการแต่ละรายการจะถูกเก็บไว้ในอาร์เรย์บัคเก็ตเอง และการแก้ไขแฮชจะดำเนินการผ่านการตรวจสอบเมื่อต้องแทรกรายการใหม่ บัคเก็ตจะถูกตรวจสอบ โดยเริ่มจากช่องที่แฮชไว้และดำเนินการตามลำดับการตรวจสอบ บางอย่าง จนกว่าจะพบช่องที่ว่างอยู่ เมื่อค้นหารายการ บัคเก็ตจะถูกสแกนตามลำดับเดียวกัน จนกว่าจะพบบันทึกเป้าหมาย หรือพบช่องอาร์เรย์ที่ไม่ได้ใช้ ซึ่งบ่งชี้ว่าการค้นหาไม่สำเร็จ^{[ 31 ]}

ลำดับโพรบที่เป็นที่รู้จักกันดี ได้แก่:

• การตรวจสอบเชิงเส้นซึ่งช่วงเวลาระหว่างการตรวจสอบจะคงที่ (โดยปกติคือ 1) ^{[ 32 ]}
• การตรวจสอบแบบกำลังสองซึ่งช่วงเวลาระหว่างการตรวจสอบจะเพิ่มขึ้นโดยการเพิ่มผลลัพธ์ที่ต่อเนื่องของพหุนามกำลังสองเข้ากับค่าที่กำหนดโดยการคำนวณแฮชดั้งเดิม^{[ 33 ] : 272}
• การแฮชแบบคู่ซึ่งช่วงเวลาระหว่างการตรวจสอบจะถูกคำนวณโดยฟังก์ชันแฮชรอง^{[ 33 ] : 272–273}

ประสิทธิภาพของการกำหนดแอดเดรสแบบเปิดอาจช้ากว่าเมื่อเทียบกับการเชื่อมโยงแบบแยกส่วน เนื่องจากลำดับการตรวจสอบจะเพิ่มขึ้นเมื่อปัจจัยโหลดเข้าใกล้ 1 ^{[ 13 ] [ 26 ] : 93} การตรวจสอบส่งผลให้เกิดลูปอนันต์หากปัจจัยโหลดถึง 1 ในกรณีที่ตารางเต็ม^{[ 7 ] : 471} ต้นทุนเฉลี่ยของการตรวจสอบเชิงเส้นขึ้นอยู่กับความสามารถของฟังก์ชันแฮชในการกระจายองค์ประกอบอย่างสม่ำเสมอทั่วทั้งตารางเพื่อหลีกเลี่ยงการเกิดรันเนื่องจากหากเกิดรันจะทำให้เวลาในการค้นหาเพิ่มขึ้น^{[ 7 ] : 472} ${\displaystyle \alpha }$

เนื่องจากช่องต่างๆ ตั้งอยู่ในตำแหน่งที่ต่อเนื่องกัน การตรวจสอบเชิงเส้นอาจนำไปสู่การใช้แคช CPU ได้ดีขึ้น เนื่องจากความใกล้เคียงของการอ้างอิงส่งผลให้ความหน่วงของหน่วยความจำ ลดลง ^{[ 32 ]}

การแฮชแบบรวม (Coalesced hashing)เป็นการผสมผสานระหว่างการเชื่อมโยงแบบแยกส่วนและการกำหนดแอดเดรสแบบเปิด ซึ่งบัคเก็ตหรือโหนดจะเชื่อมโยงกันภายในตาราง^{[ 34 ] : 6–8} อัลกอริทึมนี้เหมาะอย่างยิ่งสำหรับการจัดสรรหน่วยความจำแบบคงที่ [ ^{34 ] : 4} การชนกันในการแฮชแบบรวมจะได้รับการแก้ไขโดยการระบุช่องว่างที่มีดัชนีสูงสุดในตารางแฮช จากนั้นค่าที่ชนกันจะถูกแทรกเข้าไปในช่องนั้น บัคเก็ตยังเชื่อมโยงกับช่องของโหนดที่แทรกเข้าไปซึ่งมีแอดเดรสแฮชที่ชนกันอยู่^{[ 34 ] : 8}

การแฮชแบบ Cuckooเป็นรูปแบบหนึ่งของเทคนิคการแก้ไขการชนกันของแอดเดรสแบบเปิด ซึ่งรับประกันความซับซ้อนในการค้นหาในกรณีที่เลวร้ายที่สุดและเวลาเฉลี่ยคงที่สำหรับการแทรก การชนกันจะได้รับการแก้ไขโดยการรักษาตารางแฮชสองตาราง โดยแต่ละตารางมีฟังก์ชันแฮชของตัวเอง และช่องที่ชนกันจะถูกแทนที่ด้วยรายการที่กำหนด และองค์ประกอบที่ถูกครอบครองของช่องนั้นจะถูกย้ายไปยังตารางแฮชอีกตารางหนึ่ง กระบวนการนี้จะดำเนินต่อไปจนกว่าคีย์ทุกตัวจะมีที่ของตัวเองในถังว่างของตาราง หากกระบวนการเข้าสู่ลูปอนันต์ซึ่งระบุได้โดยการรักษาตัวนับลูปเกณฑ์ ตารางแฮชทั้งสองจะถูกแฮชใหม่ด้วยฟังก์ชันแฮชที่ใหม่กว่า และกระบวนการจะดำเนินต่อไป^{[ 35 ] : 124–125} ${\displaystyle O(1)}$

การแฮชแบบฮอปสก็อตช์เป็นอัลกอริทึมที่ใช้การกำหนดแอดเดรสแบบเปิด ซึ่งรวมองค์ประกอบของการแฮชแบบคูคูการตรวจสอบเชิงเส้นและการเชื่อมโยงผ่านแนวคิดของบริเวณใกล้เคียงของบัคเก็ต—บัคเก็ตถัดไปรอบๆ บัคเก็ตที่ถูกครอบครองใดๆ ซึ่งเรียกว่าบัคเก็ต "เสมือน" ^{[ 36 ] : 351–352} อัลกอริทึมนี้ได้รับการออกแบบมาเพื่อให้ประสิทธิภาพที่ดีขึ้นเมื่อปัจจัยโหลดของตารางแฮชเพิ่มขึ้นเกิน 90% นอกจากนี้ยังให้ปริมาณงานสูงในการตั้งค่าแบบพร้อมกันจึงเหมาะอย่างยิ่งสำหรับการใช้งานตารางแฮชแบบพร้อมกันที่ ปรับขนาดได้ ^{[ 36 ] : 350} คุณลักษณะของบริเวณใกล้เคียงของการแฮชแบบฮอปสก็อตช์รับประกันคุณสมบัติที่ว่า ต้นทุนในการค้นหารายการที่ต้องการจากบัคเก็ตใดๆ ภายในบริเวณใกล้เคียงนั้นใกล้เคียงกับต้นทุนในการค้นหาในบัคเก็ตนั้นเอง อัลกอริทึมพยายามที่จะนำรายการเข้าไปในบริเวณใกล้เคียง—โดยอาจมีต้นทุนที่เกี่ยวข้องกับการแทนที่รายการอื่นๆ^{[ 36 ] : 352}

แต่ละบัคเก็ตภายในตารางแฮชจะมี "ข้อมูลการกระโดด" เพิ่มเติม ซึ่งเป็นอาร์เรย์บิตHบิตสำหรับระบุระยะทางสัมพัทธ์ของรายการที่ถูกแฮชลงในบัคเก็ตเสมือนปัจจุบันภายในH  − 1 รายการ^{[ 36 ] : 352} ให้และเป็นคีย์ที่จะแทรกและบัคเก็ตที่คีย์ถูกแฮชเข้าไปตามลำดับ มีหลายกรณีที่เกี่ยวข้องในขั้นตอนการแทรกเพื่อให้เป็นไปตามคุณสมบัติของเพื่อนบ้านของอัลกอริทึม: ^{[ 36 ] : 352–353} ถ้าว่างเปล่า จะมีการแทรกองค์ประกอบ และบิตซ้ายสุดของบิตแมปจะถูกตั้งค่าเป็น 1 ถ้าไม่ว่างเปล่า จะใช้การตรวจสอบเชิงเส้นเพื่อค้นหาช่องว่างในตาราง บิตแมปของบัคเก็ตจะได้รับการอัปเดตตามด้วยการแทรก ถ้าช่องว่างไม่อยู่ในช่วงของเพื่อนบ้าน กล่าวคือH − 1 การสลับและการจัดการอาร์เรย์บิตข้อมูล ^การ  กระโดดของแต่ละบัคเก็ตจะดำเนินการตามคุณสมบัติที่ไม่เปลี่ยนแปลง ของเพื่อนบ้าน [ ^{36 ] : 353} ${\displaystyle k}$${\displaystyle Bk}$${\displaystyle Bk}$

การแฮชแบบ Robin Hood เป็นอัลกอริทึมการแก้ไขการชนกันแบบอิงที่อยู่แบบเปิด การชนกันจะได้รับการแก้ไขโดยการให้ความสำคัญกับการเคลื่อนที่ขององค์ประกอบที่อยู่ไกลที่สุด—หรือมีความยาวลำดับการตรวจสอบ (PSL) ที่ยาวที่สุด—จาก "ตำแหน่งบ้าน" ของมัน กล่าวคือ ถังที่รายการนั้นถูกแฮชเข้าไป^{[ 37 ] : 12} มันถูกตั้งชื่อตามRobin Hood โจรผู้กล้าหาญในตำนานที่ขโมยจากคนรวยเพื่อแจกจ่ายให้คนจน

แม้ว่าการแฮชแบบ Robin Hood จะไม่เปลี่ยนแปลงต้นทุนการค้นหาตามทฤษฎีแต่ส่งผลกระทบอย่างมากต่อความแปรปรวนของการกระจายรายการในบัคเก็ต^{[ 38 ] : 2} กล่าวคือ การจัดการกับ การก่อตัว ของรันยาวในตารางแฮช^{[ 39 ]}แต่ละโหนดภายในตารางแฮชที่ใช้การแฮชแบบ Robin Hood ควรได้รับการเสริมเพื่อจัดเก็บค่า PSL เพิ่มเติม^{[ 40 ]}ให้เป็นคีย์ที่จะแทรกเป็นความยาว PSL (เพิ่มขึ้น) ของเป็นตารางแฮช และเป็นดัชนี ขั้นตอนการแทรกมีดังนี้: ^{[ 37 ] : 12–13 [ 41 ] : 5} ${\displaystyle x}$${\displaystyle x{.}{\text{psl}}}$${\displaystyle x}$${\displaystyle T}$${\displaystyle j}$

• ถ้า: การวนซ้ำจะไปยังบัคเก็ตถัดไปโดยไม่พยายามตรวจสอบจากภายนอก${\displaystyle x{.}{\text{psl}}\ \leq \ T[j]{.}{\text{psl}}}$
• ถ้า: ใส่รายการลงในถัง; สลับกับ—ปล่อยไว้แบบนั้น; ดำเนินการตรวจสอบต่อจากถังที่ th เพื่อใส่รายการ; ทำซ้ำขั้นตอนจนกว่าจะใส่ทุกองค์ประกอบเสร็จ${\displaystyle x{.}{\text{psl}}\ >\ T[j]{.}{\text{psl}}}$${\displaystyle x}$${\displaystyle j}$${\displaystyle x}$${\displaystyle T[j]}$${\displaystyle x'}$${\displaystyle (j+1)}$${\displaystyle x'}$

การแทรกซ้ำๆ ทำให้จำนวนรายการในตารางแฮชเพิ่มขึ้น ซึ่งส่งผลให้ปัจจัยการโหลดเพิ่มขึ้นตามไปด้วย เพื่อรักษาประสิทธิภาพโดยเฉลี่ยของการค้นหาและการแทรก ตารางแฮชจะถูกปรับขนาดแบบไดนามิก และรายการของตารางจะถูกแฮชใหม่ลงในบัคเก็ตของตารางแฮชใหม่^{[ 13 ]}เนื่องจากไม่สามารถคัดลอกรายการได้ เนื่องจากขนาดตารางที่แตกต่างกันส่งผลให้ค่าแฮชแตกต่างกันเนื่องจากการดำเนินการโมดูลัส [ ^{42 ] หาก} ตารางแฮช "ว่างเปล่าเกินไป" หลังจากลบองค์ประกอบบางส่วน อาจทำการปรับขนาดเพื่อหลีก เลี่ยงการใช้หน่วยความจำมากเกินไป^{[ 43 ]}${\displaystyle O(1)}$

โดยทั่วไป ตารางแฮชใหม่ที่มีขนาดเป็นสองเท่าของตารางแฮชเดิมจะถูกจัดสรรเป็นการส่วนตัว และทุกรายการในตารางแฮชเดิมจะถูกย้ายไปยังตารางแฮชที่จัดสรรใหม่โดยการคำนวณค่าแฮชของรายการ ตามด้วยการดำเนินการแทรก การรีแฮชนั้นง่าย แต่มีค่าใช้จ่ายในการคำนวณสูง^{[ 44 ] : 478–479}

การใช้งานตารางแฮชบางประเภท โดยเฉพาะในระบบเรียลไทม์ไม่สามารถจ่ายค่าใช้จ่ายในการขยายตารางแฮชทั้งหมดในคราวเดียวได้ เนื่องจากอาจขัดจังหวะการทำงานที่สำคัญต่อเวลา หากไม่สามารถหลีกเลี่ยงการปรับขนาดแบบไดนามิกได้ วิธีแก้ปัญหาคือการปรับขนาดทีละน้อยเพื่อหลีกเลี่ยงการใช้พื้นที่จัดเก็บข้อมูลเพิ่มขึ้นอย่างฉับพลัน—โดยทั่วไปที่ 50% ของขนาดตารางใหม่—ระหว่างการรีแฮช และเพื่อหลีกเลี่ยงการแตกกระจายของหน่วยความจำที่ทำให้เกิดการบีบอัดฮีปเนื่องจากการยกเลิกการจัดสรรบล็อกหน่วยความจำ ขนาดใหญ่ ที่เกิดจากตารางแฮชเก่า^{[ 45 ] : 2–3} ในกรณีดังกล่าว การดำเนินการรีแฮชจะทำทีละน้อยโดยการขยายบล็อกหน่วยความจำก่อนหน้าที่จัดสรรไว้สำหรับตารางแฮชเก่า เพื่อให้บัคเก็ตของตารางแฮชยังคงไม่เปลี่ยนแปลง วิธีการทั่วไปสำหรับการรีแฮชแบบเฉลี่ยเกี่ยวข้องกับการรักษาฟังก์ชันแฮชสองฟังก์ชันและ กระบวนการสร้างแฮช ใหม่ของรายการในบัคเก็ตตามฟังก์ชันแฮชใหม่เรียกว่าการทำความสะอาดซึ่งดำเนินการผ่านรูปแบบคำสั่งโดยการห่อหุ้มการดำเนินการต่างๆ เช่นและผ่านตัวห่อหุ้มเพื่อให้แต่ละองค์ประกอบในบัคเก็ตได้รับการสร้างแฮชใหม่ และขั้นตอนของมันประกอบด้วยดังต่อไปนี้: ^{[ 45 ] : 3} ${\displaystyle h_{\text{old}}}$${\displaystyle h_{\text{new}}}$${\displaystyle \mathrm {Add} (\mathrm {key} )}$${\displaystyle \mathrm {Get} (\mathrm {key} )}$${\displaystyle \mathrm {Delete} (\mathrm {key} )}$${\displaystyle \mathrm {Lookup} (\mathrm {key} ,{\text{command}})}$

• ถังสะอาด${\displaystyle \mathrm {Table} [h_{\text{old}}(\mathrm {key} )]}$
• ถังสะอาด${\displaystyle \mathrm {Table} [h_{\text{new}}(\mathrm {key} )]}$
• คำสั่งนั้นจะถูกดำเนินการ

การแฮชเชิงเส้นเป็นการใช้งานตารางแฮชที่ช่วยให้สามารถขยายหรือย่อขนาดตารางได้แบบไดนามิกทีละบัคเก็ต^{[ 46 ]}

ประสิทธิภาพของตารางแฮชขึ้นอยู่กับความสามารถของฟังก์ชันแฮชในการสร้างตัวเลขกึ่งสุ่ม ( ) สำหรับรายการในตารางแฮช โดยที่และแทนคีย์ จำนวนบัคเก็ต และฟังก์ชันแฮช โดยที่ถ้าฟังก์ชันแฮชสร้างค่าเดียวกันสำหรับคีย์ที่แตกต่างกัน ( ) จะส่งผลให้เกิดการชนกันซึ่งสามารถจัดการได้หลายวิธี ความซับซ้อนของเวลาคงที่ ( ) ของการดำเนินการในตารางแฮชนั้นถือว่ามีเงื่อนไขว่าฟังก์ชันแฮชจะไม่สร้างดัชนีที่ชนกัน ดังนั้นประสิทธิภาพของตารางแฮชจึงเป็นสัดส่วนโดยตรงกับความสามารถของฟังก์ชันแฮชที่เลือกในการกระจายดัชนี^{[ 47 ] : 1} อย่างไรก็ตาม การสร้างฟังก์ชันแฮชดังกล่าวเป็นไปไม่ได้ในทางปฏิบัติดังนั้นการใช้งานจึงขึ้นอยู่กับเทคนิคการแก้ไขการชนกันเฉพาะกรณีเพื่อให้ได้ประสิทธิภาพที่สูงขึ้น^{[ 47 ] : 2} ${\displaystyle \sigma }$${\displaystyle K}$${\displaystyle n}$${\displaystyle h(x)}$${\displaystyle \sigma \ =\ h(K)\ \%\ n}$${\displaystyle \sigma }$${\displaystyle K_{1}\neq K_{2},\ h(K_{1})\ =\ h(K_{2})}$${\displaystyle O(1)}$

ประสิทธิภาพที่ดีที่สุดจะเกิดขึ้นในกรณีที่ฟังก์ชันแฮชกระจายองค์ประกอบของเอกภพอย่างสม่ำเสมอ และองค์ประกอบที่เก็บไว้ในตารางจะถูกสุ่มเลือกจากเอกภพ ในกรณีนี้ ในการแฮชแบบมีการเชื่อมโยง เวลาที่คาดหวังสำหรับการค้นหาที่สำเร็จคือและเวลาที่คาดหวังสำหรับการค้นหาที่ไม่สำเร็จคือ^{[ 48 ]}${\textstyle 1+{\frac {\alpha }{2}}+\Theta \left({\frac {1}{m}}\right)}$${\textstyle e^{-\alpha }+\alpha +\Theta \left({\frac {1}{m}}\right)}$

ตารางแฮชมักใช้ในการสร้างตารางในหน่วยความจำหลายประเภท โดยใช้ในการสร้างอาร์เรย์แบบเชื่อมโยง^{[ 33 ]}

ตารางแฮชอาจใช้เป็น โครงสร้างข้อมูลบน ดิสก์และดัชนีฐานข้อมูล (เช่นในdbm ) แม้ว่าB-treeจะเป็นที่นิยมมากกว่าในแอปพลิเคชันเหล่านี้^{[ 49 ]}

ตารางแฮชสามารถใช้ในการสร้างแคชซึ่งเป็นตารางข้อมูลเสริมที่ใช้เพื่อเร่งความเร็วในการเข้าถึงข้อมูลที่จัดเก็บไว้เป็นหลักในสื่อที่มีความเร็วต่ำกว่า ในแอปพลิเคชันนี้ การชนกันของแฮชสามารถจัดการได้โดยการทิ้งรายการที่ชนกันรายการใดรายการหนึ่งจากสองรายการ—โดยปกติแล้วจะเป็นการลบรายการเก่าที่จัดเก็บอยู่ในตารางและเขียนทับด้วยรายการใหม่ ดังนั้นทุกรายการในตารางจึงมีค่าแฮชที่ไม่ซ้ำกัน^{[ 50 ] [ 51 ]}

ตารางแฮชสามารถใช้ในการใช้งานโครงสร้างข้อมูลเซตซึ่งสามารถจัดเก็บค่าที่ไม่ซ้ำกันโดยไม่ต้องมีลำดับใดๆ เซตมักใช้ในการทดสอบการเป็นสมาชิกของค่าในคอลเลกชัน มากกว่าการดึงองค์ประกอบ^{[ 52 ]}

ตารางการสลับตำแหน่งไปยังตารางแฮชที่ซับซ้อนซึ่งจัดเก็บข้อมูลเกี่ยวกับแต่ละส่วนที่ถูกค้นหา^{[ 53 ]}

ภาษาโปรแกรมหลายภาษาเสนอฟังก์ชันการทำงานของตารางแฮช ไม่ว่าจะเป็นในรูปแบบของอาร์เรย์แบบเชื่อมโยงในตัว หรือในรูปแบบโมดูล ไลบรารีมาตรฐาน

• ในJavaScript "อ็อบเจ็กต์" คือชุดคู่คีย์-ค่าที่เปลี่ยนแปลงได้ (เรียกว่า "คุณสมบัติ") โดยแต่ละคีย์จะเป็นสตริงหรือ "สัญลักษณ์" ที่รับประกันว่าไม่ซ้ำกัน ค่าอื่นๆ เมื่อใช้เป็นคีย์ จะต้องแปลงเป็นสตริงก่อน นอกจากชนิดข้อมูล "พื้นฐาน" ทั้งเจ็ดชนิดแล้ว ทุกค่าใน JavaScript ล้วนเป็นอ็อบเจ็กต์^{[ 54 ]} ECMAScript 2015 ยังเพิ่มMapโครงสร้างข้อมูลซึ่งยอมรับค่าใดๆ ก็ได้เป็นคีย์^{[ 55 ]}
• C++11รวมไว้unordered_mapในไลบรารีมาตรฐานสำหรับการจัดเก็บคีย์และค่าของ^{ประเภท}ต่างๆ [ ^{56 ]}
• Go มีการใช้ งานในตัวmapเป็นประเภทแผนที่ในรูปแบบของประเภทซึ่งมักจะเป็น (แต่ไม่รับประกัน) ตารางแฮช^{[ 57 ]}
• ภาษาการเขียนโปรแกรม Javaประกอบด้วยคอลเลกชันHashSet, HashMap, LinkedHashSet, และคอลเลกชันLinkedHashMapทั่วไป^{[ 58 ]}
• ฟังก์ชัน ในตัวของPythondictใช้ตารางแฮชในรูปแบบ^ของประเภท^[ 59 ^]
• RubyในตัวHashใช้โมเดลการกำหนดแอดเดรสแบบเปิดตั้งแต่ Ruby 2.4 เป็นต้นไป^{[ 60 ]}
• ภาษาการเขียนโปรแกรมRustHashMap ประกอบด้วย ซึ่งHashSetเป็นส่วนหนึ่งของไลบรารีมาตรฐาน Rust ^{[ 61 ]}
• ไลบรารี มาตรฐาน ^. NETประกอบด้วยHashSetและDictionary[ ^{62 ] [ 63 ] ดังนั้นจึงสามารถใช้งาน ได้}จากภาษาต่างๆ เช่นC#และVB.NET [ ^{64 ]}

• Tamassia, Roberto; Goodrich, Michael T. (2006). "บทที่เก้า: แผนที่และพจนานุกรม" โครงสร้างข้อมูลและอัลกอริทึมใน Java: [ปรับปรุงสำหรับ Java 5.0] (ฉบับที่ 4). โฮโบเคน, นิวเจอร์ซีย์: Wiley. หน้า  369–418 . ISBN 978-0-471-73884-8.
• McKenzie, BJ; Harries, R.; Bell, T. (กุมภาพันธ์ 1990). "การเลือกอัลกอริทึมแฮชชิ่ง". ซอฟต์แวร์: การปฏิบัติและประสบการณ์ 20 ( 2): 209– 224. doi : 10.1002/spe.4380200207 . hdl : 10092/9691 . S2CID  12854386 .

วิกิมีเดียคอมมอนส์มีสื่อที่เกี่ยวข้องกับตารางแฮช

เว็บไซต์ Wikibooks มีหนังสือเกี่ยวกับหัวข้อ: โครงสร้างข้อมูล/ตารางแฮช

• บทความของNIST เกี่ยวกับ ตารางแฮช
• โครงสร้างข้อมูลแบบเปิด – บทที่ 5 – ตารางแฮชโดยแพท โมริน
• วิดีโอการบรรยาย MIT OCW เรื่อง "ความรู้เบื้องต้นเกี่ยวกับอัลกอริทึม: การแฮช 1"
• วิดีโอการบรรยาย MIT OCW เรื่อง "ความรู้เบื้องต้นเกี่ยวกับอัลกอริทึม: การแฮช 2"