แถวลำดับจูดี้

จากวิกิพีเดีย สารานุกรมเสรี

แถวลำดับจูดี้ (อังกฤษ: Judy array) คือแถวลำดับแบบจับคู่ ที่ซับซ้อนและรวดเร็วซึ่งใช้ในการเก็บข้อมูล และค้นหาข้อมูลโดยคีย์ที่เป็นจำนวนเต็มหรือข้อความ

ถึงแม้จะเรียกว่าแถวลำดับจูดี้ แต่จริงๆแล้ว แถวลำดับจูดี้จัดเก็บข้อมูลภายในในรูปแบบ digital trees แต่ API ของ แถวลำดับจูดี้จะมีบริการสำหรับผู้ใช้แบบเดียวกับแถวลำดับ

แถวลำดับจูดี้แบ่งเป็น 3 ประเภท โดยมีการmapข้อมูลดังนี้

Judy Array Type key value
Judy1 long bit
JudyL long long
JudySL string bit

แถวลำดับจูดี้ยังถูกเชื่อว่ามีความเสี่ยงต่อการโจมตีให้โครงสร้างข้อมูลใช้งานไม่ได้โดยการให้โครงสร้างข้อมูลทำงานกับข้อมูลที่ทำให้เกิดกรณีที่แย่ที่สุด[1]

Doug Baskins และ Judy น้องสาวของเขา

แถวลำดับจูดี้ถูกคิดขึ้นโดย Doug Baskins และทำให้สำเร็จโดย ฮิวเลตต์-แพคการ์ด (จูดี้คือชื่อของน้องสาวของ Doug Baskins[2])

ประสิทธิภาพเมื่อเทียบกับ ตารางแฮช แบบ SeparateChaining[แก้]

การทดสอบถูกทดสอบบน 2GB HP 9000 J5000 workstation running HP-UX 11i at 440 MHz[3]

การเพิ่มข้อมูล

JudyvsHash1.gif

การค้นข้อมูล

JudyvsHash2.gif

การใช้หนวยความจำ

JudyvsHash3.gif

ดูเพิ่ม[แก้]

อ้างอิง[แก้]