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

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

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

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

Judy Array TypekeyvalueJudy1longbitJudyLlonglongJudySLstringbit

แถวลำดับจูดี้ยังถูกเชื่อว่ามีความเสี่ยงต่อการโจมตีให้โครงสร้างข้อมูลใช้งานไม่ได้โดยการให้โครงสร้างข้อมูลทำงานกับข้อมูลที่ทำให้เกิดกรณีที่แย่ที่สุด
แถวลำดับจูดี้ถูกคิดขึ้นโดย Doug Baskins และทำให้สำเร็จโดย ฮิวเลตต์-แพคการ์ด (จูดี้คือชื่อของน้องสาวของ Doug Baskinshttp://judy.sourceforge.net/index.html Main Judy arrays web page)

ประสิทธิภาพเมื่อเทียบกับ ตารางแฮช แบบ SeparateChaining
การทดสอบถูกทดสอบบน 2GB HP 9000 J5000 workstation running HP-UX 11i at 440 MHzhttp://docs.hp.com/en/B6841-90001/ch02s03.html Hashing versus JudyL

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

ไฟล์:JudyvsHash1.gif

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

ไฟล์:JudyvsHash2.gif

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

ไฟล์:JudyvsHash3.gif

 ดูเพิ่ม 
Main Judy arrays web page 
Programming with Judy: C LanguageJudy 
How Judy arrays work and why they are so fast
A complete technical description of Judy arrays
An independent performance comparison of Judy to Hash Tables
A compact implementation of Judy arrays in 1K lines of C code

อ้างอิง

หมวดหมู่:แถวลำดับ