CoE KKU

Separate chaining มีข้อเสียเปรียบที่การต้องใช้ลิงค์ลิสต์ ทำให้การทำงานช้าลงไปบ้างเนื่องจากต้องใช้เวลาในการ allocate เซลล์ใหม่, และโดยเฉพาะอย่างยิ่งเราต้องใช้โครงสร้างข้อมูลโครงสร้างที่สอง การใช้ Open addressing เป็นทางเลือกการแก้ปัญหาการชนแทนการใช้ลิงค์ลิสต์ โดยเมื่อเกิดการชนขึ้นก็จะทำการหาตำแหน่งเซลล์ว่างใหม่จนกว่าจะพบเซลล์ว่าง กล่าวคือ จะตรวจสอบเซลล์ $h_0(x), h_1(x), h_2(x), ...$ ตามลำดับ โดยที่ $h_i(x) = (hash(x) + f(i))\ mod\ TableSize$ เมื่อ $f(0) = 0$ ฟังก์ชัน $f$ คือฟังก์ชันที่ใช้เป็นตัวแก้ปัญหาการชน เนื่องจากวิธีนี้จำนวนข้อมูลทั้งหมดต้องบรรจุลงในตาราง ดังนั้นตารางที่ใช้จึงต้องมีขนาดใหญ่กว่าตารางที่ใช้ใน separate chaining hashing โดยทั่วไปแล้วค่า load factor ควรจะต่ำกว่า $\lambda = 0.5$ สำหรับ open addressing hashing วิธีแก้ปัญหาการชน 3 วิธีของ Open addressing คือ Linear Probing, Quadratic Probing, และ Double Hashing

สำหรับ linear probing แล้ว ฟังก์ชัน f เป็น linear function ของ i, ซึ่งปกติแล้วก็จะกำหนดให้ $f(i) = i$ ซึ่งเป็นการตรวจสอบเซลล์เรียงตามลำดับไป (with wraparound) เพื่อหาเซลล์ว่าง รูปที่ 5.11 แสดงผลการบรรจุค่า keys {89, 18, 49, 58, 69} ลงในตารางแฮชโดยใช้ hash function ตัวเดียวกันกับที่ใช้ก่อนหน้านี้ และใช้การแก้ปัญหาการชนด้วย $f(i) = i$

การชนกันเกิดขึ้นครั้งแรกเมื่อมีการบรรจุค่า 49 และได้รับการบรรจุลงในเซลล์ว่างแรกคือตำแหน่ง 0 การบรรจุค่า 58 จะเกิดการชนกับ 18, 89 และ 49 ก่อนที่จะถึงเซลล์ว่าง การบรรจุค่า 69 ก็จะได้รับการจัดการในทำนองเดียวกับที่กล่าวมาแล้วนี้ เราจะเห็นได้ว่า ถ้าตารางมีขนาดใหญ่พอเราก็จะสามารถพบเซลล์ว่างได้เสมอ แต่อาจจะต้องใช้เวลามาก ที่แย่ยิ่งไปกว่านั้นก็คือ ถึงแม้ว่าตารางจะค่อนข้างมีที่ว่างมาก เซลล์ในตารางที่มีข้อมูลบรรจุอยู่ก็จะกระจุกตัวเป็นกลุ่มในบริเวณหนึ่ง ผลดังกล่าวนี้เรียกว่า primary clustering ซึ่งหมายความว่าค่า key ใด ๆ ที่มีค่าแฮชชนกันก็จะถูกจะต้องใช้เวลาในการแก้การชนนี้ด้วยการตรวจเซลล์หลาย ๆ ครั้งและจะบรรจุค่าลงในกลุ่มเซลล์บริเวณเดียวกันต่อเนื่องอีก

รูปที่ 5.11 Open addressing hash table ที่ใช้ linear probing ในการบรรจุค่าลงในตาราง

(ไม่ได้แสดงวิธีการคำนวณเอาไว้ในบทเรียนนี้) ค่าคาดหวังของจำนวนการ probes ที่ใช้ linear probing โดยประมาณ คือ $\frac{1}{2}(1 + \frac{1}{(1 - \lambda)^2})$ ครั้งสำหรับการบรรจุและการค้นหาที่ไม่ประสบความสำเร็จ (unsuccessful searches) และต้องใช้จำนวนการ probe เท่ากับ $\frac{1}{2}(1 + \frac{1}{(1 - \lambda)})$ ครั้งสำหรับการค้นหาที่ประสบความสำเร็จ (successful searches) จากโปรแกรมจะเห็นว่าการบรรจุและการค้นหาที่ไม่ประสบความสำเร็จต้องใช้จำนวนการ probes เท่ากัน และโดยเฉลี่ยการค้นหาที่ประสบความสำเร็จควรจะใช้เวลาน้อยกว่าการค้นหาที่ไม่ประสบความสำเร็จ

ถ้าละเลยเรื่อง clustering (เสมือนไม่มี) และ สมมุติตารางมีขนาดใหญ่มาก และ การ probe แต่ละครั้งเป็นอิสระจากการ probes ก่อนหน้าแล้ว ในกรณีเช่นนี้ก็จะเป็นการแก้ปัญหาการชนที่เรียกว่า random collision resolution strategy ในชั้นแรกจะหาจำนวนการ probe สำหรับกรณีการค้นหาที่ไม่ประสบความสำเร็จ (unsuccessful search) ซึ่งค่าคาดหวังของจำนวนการ probes คือจำนวนการ probe จนกระทั่งพบกับเซลล์ว่าง เนื่องจากสัดส่วนของเซลล์ว่างในตาราง คือ $1 - \lambda$ ดังนั้น จำนวนเซลล์ที่คาดว่าจะต้องทำการ probe คือ $\frac{1}{(1 - \lambda)}$ เซลล์ ส่วนจำนวนการ probe สำหรับกรณีการค้นหาที่ประสบความสำเร็จ (successful search) จะเท่ากับจำนวนการ probes ที่ต้องใช้เมื่อต้องการบรรจุค่านั้น ๆ และเมื่อต้องการบรรจุค่านั้นก็เป็นการบรรจุเมื่อค้นหาค่านั้น ๆ ไม่พบ (unsuccessful search) ดังนั้น เราจึงสามารถใช้ cost ของ unsuccessful search เพื่อคำนวณค่าเฉลี่ยของ cost ของ successful search

สิ่งที่ควรคำนึง คือ ค่า $\lambda$ แปรเปลี่ยนจาก 0 ไปเรื่อย ๆ จนถึงค่าปัจจุบันของมัน ดังนั้นการบรรจุค่าแรก ๆ จะมีค่าใช้จ่ายต่ำและทำให้ค่าเฉลี่ยลดลง เช่น ในตารางข้างบนที่ $\lambda = 0.5$, แต่ cost ในการเข้าถึงค่า 18 คือค่าที่เท่ากับเมื่อบรรจุ 18 ซึ่งขณะนั้นมี $\lambda = 0.2$ เนื่องจากขณะบรรจุ 18 นั้นตารางค่อนข้างว่าง ดังนั้นการเข้าถึงมันจึงง่ายกว่าการเข้าถึงค่าที่บรรจุในตอนหลัง ๆ ดังเช่นค่า 69 เราสามารถประเมินค่าเฉลี่ยได้โดยใช้ integral เพื่อการคำนวณค่า mean ของการบรรจุ โดย $$I(\lambda)=\frac{1}{\lambda}\int_0^λ\frac{1}{(1-x)} dx = \frac{1}{\lambda} ln⁡\frac{1}{(1-\lambda)}$$

รูปที่ 5.12 เปรียบเทียบคุณภาพของ linear probing (เส้นประ) กับค่าที่คาดว่าจะเป็นสำหรับการชนที่ค่อนข้างจะเป็นแบบสุ่ม อักษร S คือ Successful searches และ unsuccessful searches และ insertions แสดงด้วย U และ I ตามลำดับ

รูปที่ 5.12 กราฟแสดงจำนวนการ probe กับค่า load factor สำหรับ linear probe (เส้นประ) และแบบสุ่ม (เส้นทึบ)

ถ้าใช้สูตรข้างบนคำนวณจำนวนครั้งของการ probe ที่ค่า $\lambda = 0.75$ เมื่อมีการบรรจุค่าใหม่ด้วย linear probe ก็จะได้จำนวนครั้งของการ probe คือ 8.5 ครั้ง แต่ถ้า $\lambda = 0.9$ จำนวนครั้งของการ probe คือ 50 ครั้ง ซึ่งดูไม่สมเหตุสมผล ถ้าเทียบกับเมื่อเราไม่นำเงื่อนไขของ clustering มาเป็นปัจจัยในการทำงานก็จะได้จำนวนครั้งของการ probe เป็น 4 และ10 ครั้งสำหรับค่า load factor ที่กล่าวตามลำดับ จากสูตรการคำนวณที่กล่าวมาจะเห็นได้ว่าถ้าใช้ linear probe ก็ไม่ควรให้มีจำนวนข้อมูลในตารางเกินกว่าครึ่งของขนาดตาราง อย่างไรก็ตามที่ $\lambda = 0.5$ นั้นโดยเฉลี่ยแล้วต้องใช้จำนวนครั้งของการ probe 2.5 ครั้งเท่านั้นสำหรับการบรรจุและใช้การ probe จำนวน 1.5 ครั้งโดยเฉลี่ยสำหรับการค้นหาที่ประสบความสำเร็จ

Quadratic probing เป็นการแก้ปัญหาการชนที่สามารถขจัดปัญหาการเกิด primary clustering ใน linear probing ได้ Quadratic probing ใช้ collision function เป็น quadratic และฟังก์ชัน f ที่นิยมใช้คือ $f(i) = i^2$ รูปที่ 5.13 แสดงผลการใช้ open addressing ที่ใช้การแก้ปัญหาการชนด้วย quadratic probe ของข้อมูลชุดเดียวกันกับที่ใช้ในตัวอย่างของ linear probing

เมื่อ 49 เกิดการชนกับค่า 89 ที่อยู่ในตารางอยู่แล้ว ตำแหน่งที่ต้องตรวจสอบต่อไปคือตำแหน่งที่อยู่ถัดไปและพบว่าเป็นตำแหน่งเซลล์ที่ว่างอยู่จึงบรรจุค่า 49 ลงในเซลล์นี้ ต่อไปคือค่า 58 ซึ่งก็จะชนกับค่าที่ยึดครองเซลล์ที่ 8 อยู่แล้วจึงตรวจสอบเซลล์ถัดไปแต่ก็ถูกยึดครองแล้วด้วยค่า 89 เซลล์ถัดไปที่ต้องตรวจสอบคือเซลล์ที่อยู่ห่างออกไปเป็นจำนวน $2^2 = 4$ เซลล์ คือเซลล์หมายเลข 2 ซึ่งเป็นเซลล์ว่าง ดังนั้นจึงบรรจุค่า 58 ลงในตำแหน่งเซลล์นี้ การบรรจุค่า 69 ก็เป็นไปในลักษณะเดียวกัน

รูปที่ 5.13 ผลการใช้ open addressing ที่ใช้การแก้ปัญหาการชนด้วย quadratic probe

สำหรับ quadratic probing แล้วจะไม่ประกันว่าจะสามารถหาเซลล์ว่างได้กรณีที่เซลล์ในตารางมีข้อมูลอยู่แล้วเกินครึ่งหนึ่งของขนาดของตาราง และถึงแม้จะมีเซลล์ว่างอยู่เกินครึ่งหนึ่งก็ตามถ้าขนาดของตารางไม่เป็น prime ความจริงแล้วถ้าตารางมีเซลล์ว่างครึ่งหนึ่งและขนาดของตารางเป็น prime แล้วก็จะประกันได้ว่าจะสามารถบรรจุค่าใหม่ได้เสมอ

THEOREM 5.1 ในการใช้ quadratic probing ที่มีขนาดตารางเป็น prime แล้วเราสามารถบรรจุค่าใหม่ได้เสมอถ้าตารางยังมีเซลล์ว่างอย่างน้อยครึ่งหนึ่งของตาราง PROOF: ให้ตารางมีขนาด TableSize เป็น (odd) prime ที่มีค่ามากกว่า 3 เราจะแสดงให้เห็นว่าตำแหน่งใน $⌈TableSIZE/2⌉$ ที่แรก (รวมทั้งตำแหน่งเริ่มแรก $h_0(x))$ ล้วนเป็นตำแหน่งที่ไม่ซ้ำกัน คือเป็นคนละตำแหน่งกัน และสองตำแหน่งในกลุ่มตำแหน่งเหล่านี้ คือ $h(x) + i^2 (mod\ TableSize)$ และ $h(x) + j^2 (mod\ TableSize)$, เมื่อ $0 < i, j < ⌊TableSize/2⌋$ เพื่อจะใช้ contradiction เราจะสมมุติว่าสองตำแหน่งนี้เป็นตำแหน่งเดียวกัน แต่มี $i \neq j$ ดังนั้น $$ h(x) + i^2 = h(x) + j^2 (mod\ tableSize)$$ $$ i^2 = j^2 (mod\ tableSize)$$ $$ i^2 - j^2 = 0 (mod\ tableSize)$$ $$(i - j)(i + j) = 0 (mod\ tableSize) $$

เนื่องจาก TableSize เป็น prime นั่นหมายความว่าถ้าไม่ (i - j) หรือไม่ก็ (i + j) มีค่าเท่ากับ 0 (mod TableSize) แต่เนื่องจาก i ไม่เท่ากับ j ดังนั้น ข้อสรุปแรก คือ (i - j) มีค่าเท่ากับ 0 (mod TableSize) จึงเป็นไปไม่ได้ และเนื่องจาก 0 < i, j < ëTableSize2û ข้อสรุปที่สองก็เป็นไปไม่ได้เช่นกัน นั่นคือตำแหน่งใน éTableSize2ù แรกจึงเป็นตำแหน่งที่ไม่ซ้ำกัน และดังนั้น ถ้ามีตำแหน่งที่มีข้อมูลอยู่แล้วมากที่สุดเพียง ëTableSize2û ตำแหน่งเราก็จะสามารถหาตำแหน่งว่างได้เสมอ

ถึงแม้ถ้าจำนวนเซลล์ในตารางจะถูกใช้งานไปแล้วมากกว่าครึ่งเพียงเซลล์เดียว การบรรจุค่าใหม่ก็จะล้มเหลวได้ ดังนั้นเราจะต้องระลึกถึงสิ่งนี้เสมอในการใช้งาน สิ่งสำคัญอย่างยิ่งอีกประการก็คือขนาดของตารางจะต้องมีค่าเป็น prime number เพราะถ้าขนาดของตารางไม่เป็น prime ก็จะทำให้จำนวนเซลล์ที่เราสามารถจะเลือกใช้ได้นั้นลดจำนวนลงอย่างมาก เช่น ถ้าขนาดของตาราง คือ 16 ก็จะทำให้เรามีเซลล์ที่จะเลือกต่อ ๆ ไป เมื่อเกิดการชน คือ เซลล์ที่ห่างออกไป 1, 4, และ 9 เท่านั้น

เราไม่สามารถใช้การลบค่าในตารางแฮชด้วยวิธีธรรมดาทั่วไป (คือการลบข้อมูลออกไปจากตาราง) ใน open addressing hash table เนื่องจากอาจจะต้องใช้ข้อมูลในเซลล์นั้นเป็นทางผ่านเพื่อแก้ปัญหาการชน เช่น ในตารางตัวอย่างข้างบน ถ้าลบ 89 ออกไปจากตารางเลย เราก็จะไม่สามารถค้นหาค่าอื่นที่เหลือได้อีก ดังนั้นใน open hash tables จึงต้องใช้การลบข้อมูลในตารางด้วยวิธีที่เรียกว่า lazy deletion

รูปที่ 5.14 แสดงโครงร่างคลาสเพื่อการใช้งาน open addressing hashing เราใช้อะเรย์ของ HashEntry แทนที่จะเป็นอะเรย์ของลิสต์ แต่ละรายการในอะเรย์ของ HashEntry จะอ้างถึงสิ่งหนึ่งสิ่งใด ต่อไปนี้

1. 1. null
2. 2. ไม่เป็น null และเป็นรายการที่ active (คือ ค่า isActive เป็น true)
3. 3. ไม่เป็น null และเป็นรายการที่ถูกทำเครื่องหมายว่าถูกลบไปแล้ว (คือ ค่า isActive เป็น false)

คำสั่งการสร้างตาราง (รูปที่ 5.15) ประกอบด้วยการ allocate เนื้อที่และกำหนดให้แต่ละรายการใน HasEntry มีค่าเป็น (หรืออ้างอิงถึงค่า) null

ฟังก์ชัน find(x) (ดูรูปที่ 5.16) ให้ค่ากลับเป็น reference ที่อ้างอิงถึงออปเจ็กต์ที่มีค่าเท่ากันกับ x ที่อยู่ในตารางแฮช ถ้าไม่มีค่า x ก็จะให้ค่ากลับเป็น null ฟังก์ชัน findPos เป็นฟังก์ชันแบบ private ทำหน้าที่ในการแก้ปัญหาการชน เพื่อความสะดวกเรากำหนดให้ขนาดของตารางแฮชเป็น 2 เท่าของจำนวนสมาชิกในตารางเพื่อประกันว่า quadratic probe ยังคงใช้งานได้เสมอ มิฉะนั้นแล้วเราจะต้องเพิ่มเติมการทดสอบค่า i (คือค่า collisionNum) ก่อนหน้าบรรทัดที่ 4 ในรูปที่ 5.16 นั้นสมาชิกที่ถูกทำเครื่องหมายว่าถูกลบไปแล้วก็จะยังคงถูกนับเป็นค่าที่ยังอยู่ในตารางด้วยซึ่งอาจจะเป็นปัญหาได้เนื่องจากเซลล์ในตารางก็จะถูกยึดครองเต็มเร็วกว่าที่เป็นจริง (จะกล่าวถึงประเด็นนี้อีกครั้ง) บรรทัดที่ 4 ถึง 9 เป็นวิธีการที่รวดเร็วในการคำนวณเพื่อแก้ปัญหาการชน จากนิยามของ quadratic probe เราสามารถคำนวณตำแหน่งตรวจสอบถัดไปได้ด้วยการใช้ $f(i) = f(i – 1) + 2i – 1$ ซึ่งเป็นเพียงการใช้การคูณด้วย 2 และการ decrement การคำนวณนี้ถูกต้องเพราะเหตุว่า ถ้าให้ $f(i)$ เป็นตำแหน่งที่กำลังทำการ probe อยู่ขณะนั้น ๆ และให้ $f(0)$ เป็นตำแหน่งจากการแฮชเริ่มต้น ดังนั้น $f(i – 1)$ ก็จะเป็นการ probe ครั้งล่าสุด และจากนิยามของ quadratic probe จะได้ว่า $$f(i)=f(0)+i^2 (mod\ tableSize) $$ $$f(i-1)=f(0)+(i-1)^2 (mod\ tableSize)$$ นำสมการทั้งสองข้างบนลบกันจะได้ $$f(i)-f(i-1)=i^2-(i-1)^2 (mod\ tableSize)$$ $$f(i)=f(i-1)+2i-1 (mod\ tableSize)$$

ถ้าตำแหน่งใหม่ที่ได้มีค่ามากกว่าขนาดของอะเรย์ก็สามารถปรับค่ากลับมาอยู่ในช่วงได้ด้วยการลบด้วย tableSize การคำนวณนี้ทำงานเร็วกว่าการคำนวณโดยตรง ข้อสังเกตอีกประการของโปรแกรมคือ เงื่อนไขการตรวจสอบ 2 เงื่อนไขหลัง while ในบรรทัดที่ 3 นั้นจะสลับกันไม่ได้

การทำงานการบรรจุค่าลงในตารางแสดงในรูปที่ 5.17 ฟังก์ชันจะไม่ทำสิ่งใดถ้าค่า x ที่จะบรรจุลงในตารางมีอยู่ในตารางแล้วและถ้าไม่มีค่านี้อยู่ x ก็จะถูกบรรจุในตำแหน่งที่ได้กลับจากฟังก์ชัน findPos ถ้าค่า load factor มากกว่า 0.5 ซึ่งคือตารางถูกใช้งานเต็มที่แล้ว เราอาจจะให้โปรแกรมเกิด exception แต่สำหรับโปรแกรมของเราจะให้มีการขยายขนาดตารางซึ่งวิธีนี้เรียกว่า rehashing และจะกล่าวถึงอีกครั้งในหัวข้อที่ 5.5

ถึงแม้ว่า quadratic probe จะสามารถขจัดปัญหาของ primary clustering ไปได้ก็ตามแต่ถ้าสมาชิกที่แฮชลงในตำแหน่งเดียวกันก็จะต้อง probe เพื่อตรวจสอบตำแหน่งเดียวกันไปตลอด ลักษณะที่เกิดการ probe แบบนี้เรียกว่า secondary clustering

class HashEntry 
{       Hashable element;   		// the element
        boolean  isActive;  		// false is deleted
        public HashEntry( Hashable  e )
        {   this( e, true );  }
        public HashEntry( Hashable  e, boolean  i )
        {  element   = e;
            isActive  = i;
        }
} 
 
public class QuadraticProbingHashTable 
{     public QuadraticProbingHashTable( )   {/* Figure 5.15 */}
      public QuadraticProbingHashTable( int size )   {/* Figure 5.15 */}
      public void insert( Hashable x ) {/* Figure 5.17 */}
      private void rehash( ) {/* Figure 5.22 */}
      private int findPos( Hashable x ) {/* Figure 5.16 */}
      public void remove( Hashable x ) {/* Figure 5.17 */}
      public Hashable find( Hashable x ) {/* Figure 5.16 */}
      private boolean isActive( int currentPos ) {/* Figure 5.16 */}
      public void makeEmpty( )  {/* Figure 5.15 */}
      public static int hash( String key, int tableSize ) {/* Figure 5.4 */} 
      private static final int DEFAULT_TABLE_SIZE = 11;
     private HashEntry [ ] array;   	// The array of elements
     private int currentSize;       	// The number of occupied cells
     private void allocateArray( int arraySize ) {/* Figure 5.15 */}

รูปที่ 5.14 โครงร่างคลาสเพื่อการใช้งาน open addressing hashing

     private static int nextPrime( int n )     /* Internal method to find a prime number at least as large as n. */
     {   if( n % 2 == 0 )
                n++;
         for( ; !isPrime( n ); n += 2 )
                ;
            return n;
     } 
 
    private static boolean isPrime( int n )   /* Internal method to test if a number is prime.   */
    {      if( n == 2 || n == 3 )
                return true;
            if( n == 1 || n % 2 == 0 )
                return false;
            for( int i = 3; i * i <= n; i += 2 )
                if( n % i == 0 )
                    return false;
            return true;
        } 
    public static void main( String [ ] args ) 	// Simple main
     { QuadraticProbingHashTable H = new QuadraticProbingHashTable( );
       final int NUMS = 4000;
       final int GAP  =   37;
       System.out.println( "Checking... (no more output means success)" );
       for ( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
            H.insert( new MyInteger( i ) );
       for ( int i = 1; i < NUMS; i+= 2 )
            H.remove( new MyInteger( i ) );
       for ( int i = 2; i < NUMS; i+=2 )
             if( ((MyInteger)(H.find( new MyInteger( i ) ))).intValue( ) != i )
                    System.out.println( "Find fails " + i );
       for ( int i = 1; i < NUMS; i+=2 )
			if ( H.find( new MyInteger( i ) ) != null )
                System.out.println( "OOPS!!! " +  i  );
      }
  }

รูปที่ 5.14 (ต่อ) โครงร่างคลาสเพื่อการใช้งาน open addressing hashing

/* Construct the hash table */
public QuadraticProbingHashTable( )  {  this( DEFAULT_TABLE_SIZE );  }
public QuadraticProbingHashTable( int size )
{    allocateArray( size );
     makeEmpty( );
 }
/* Make the hash table logically empty */
public void makeEmpty( )
{    currentSize = 0;
     for( int i = 0; i < array.length; i++ )
                array[ i ] = null;
 }
/* Method to allocate array */
private void allocateArray( int arraySize )
 {   array = new HashEntry[ arraySize ];    }

รูปที่ 5.15 ฟังก์ชันเพื่อการ initialize ตารางของ open addressing hashing

public Hashable find( Hashable x )
{        int currentPos = findPos( x );
    return isActive( currentPos ) ? array[ currentPos ].element : null;
 }
 private int findPos( Hashable x )
 {
/* 1*/      int collisionNum = 0;
/* 2*/      int currentPos = x.hash( array.length );
/* 3*/      while( array[ currentPos ] != null && !array[ currentPos ].element.equals( x ) )
 	{
/* 4*/          currentPos += 2 * ++collisionNum - 1;  	// Compute ith probe
/* 5*/          if( currentPos >= array.length )      	// Implement the mod
/* 6*/              currentPos -= array.length;
                }
/* 7*/      return currentPos;
 }
 private boolean isActive( int currentPos )
 {  return array[ currentPos ] != null && array[ currentPos ].isActive;   }

รูปที่ 5.16 ฟังก์ชัน find สำหรับ quadratic probing

public void insert( Hashable x )
{   int currentPos = findPos( x ); 	// Insert x as active
    if ( isActive( currentPos ) )
          return;
    array[ currentPos ] = new HashEntry( x, true );
    // Rehash; see Section 5.5
    if ( ++currentSize > array.length / 2 )
          rehash( );
}
 public void remove( Hashable x )
 {  int currentPos = findPos( x );
    if ( isActive( currentPos ) )
    array[ currentPos ].isActive = false;
  }

รูปที่ 5.17 ฟังก์ชันสำหรับการบรรจุค่าที่ใช้ quadratic probing

วิธีการแก้ปัญหาการชนวิธีสุดท้ายที่จะกล่าวถึงคือวิธีที่เรียกว่า double hashing ฟังก์ชันที่นิยมใช้ใน double hashing คือ $f(i) = i • h_2(x)$ กล่าวคือ เราจะใช้ hash function ตัวที่สองกับ x และ probe ไปยังตำแหน่งเซลล์ที่อยู่ที่ระยะห่างเป็นจำนวน $h_2(x), 2h_2(x),...,$ เซลล์ออกไปเรื่อย ๆ การเลือกใช้ $h_2(x)$ ที่ไม่ดีจะเกิดผลเสียอย่างมาก เช่น ถ้าเลือก $h_2(x) = x\ mod\ 9$ จะไม่ช่วยอะไรได้เลยถ้าจะต้องบรรจุค่า 99 ลงในตารางแฮชในตัวอย่างที่แล้ว ดังนั้นฟังก์ชันที่เลือกใช้ต้องไม่ให้ผลเป็น 0 นอกจากนี้ยังต้องมั่นใจด้วยว่าจะสามารถทำการ probe ได้ทุก ๆ เซลล์ด้วย (ซึ่งเป็นไปไม่ได้ในตัวอย่างต่อไปนี้ เนื่องจากขนาดของตารางไม่เป็น prime) ฟังก์ชันที่นิยมใช้ทั่วไป คือ $h_2(x) = R - (x\ mod\ R)$, เมื่อ R เป็นค่า prime ที่น้อยกว่าค่า TableSize

ในกรณีตัวอย่าง ถ้าเราเลือกให้ R = 7, รูปที่ 5.18 ตารางผลการบรรจุค่าข้อมูลชุดเดิมจากตัวอย่างที่แล้ว การชนเกิดขึ้นครั้งแรกเมื่อบรรจุค่า 49 และคำนวณค่า $h_2(49) = 7 - 0 = 7$, ดังนั้นจึงบรรจุค่า 49 ลงในเซลล์ที่ 6 และ $h_2(58) = 7 - 2 = 5$, ดังนั้นจึงบรรจุค่า 58 ลงในเซลล์ที่ 3 สุดท้ายค่า 69 ก็เกิดการชนเช่นกันและใช้ $h_2(69) = 7 - 6 = 1$, และบรรจุลงในเซลล์ถัดไป ถ้าเราต้องการบรรจุค่า 60 ก็จะเกิดการชนที่ตำแหน่งเซลล์ 0 และเนื่องจาก $h_2(60) = 7 - 4 = 3$, ซึ่งจะต้องทำการ probe เซลล์ 3, 6, 9, และ 2 ไปจนกว่าจะพบเซลล์ว่าง

ดังที่ได้กล่าวมาแต่ต้นแล้วว่าขนาดของตารางที่ใช้ในตัวอย่างไม่ได้เป็นค่า prime เพื่อความสะดวกในการคำนวณของ hash function อย่างไรก็ตามการใช้งานจริงนั้นการใช้ตารางที่มีขนาดเป็น prime นั้นมีความสำคัญยิ่งเมื่อใช้ double hashing ดังเช่นถ้าต้องการบรรจุค่า 23 ลงในตารางตัวอย่าง ก็จะเกิดการชนกับค่า 58 และเนื่องจาก $h_2(23) = 7 - 2 = 5$, และขนาดตาราง คือ 10 ดังนั้นเราจึงมีเซลล์ให้เลือกเพียงตำแหน่งเดียว และเป็นตำแหน่งที่มีค่าอื่นอยู่แล้ว นั่นคือถ้าขนาดของตารางที่ใช้ไม่เป็นค่า prime ก็อาจจะทำให้เราไม่มีเซลล์ที่จะบรรจุค่าได้ในเวลาไม่นานนัก ในทางปฏิบัติเนื่องจากการใช้ quadratic probe ไม่ต้องใช้ hash function ตัวที่ 2 ดังนั้นจึงใช้งานง่ายกว่าและทำงานเร็วกว่า double hashing

รูปที่ 5.18 Open addressing hash table