แถวลำดับจูดี้
แถวลำดับจูดี้ (อังกฤษ: Judy array) คือแถวลำดับแบบจับคู่ ที่ซับซ้อนและรวดเร็วซึ่งใช้ในการเก็บข้อมูล และค้นหาข้อมูลโดยคีย์ที่เป็นจำนวนเต็มหรือข้อความ
ถึงแม้จะเรียกว่าแถวลำดับจูดี้ แต่จริงๆแล้ว แถวลำดับจูดี้จัดเก็บข้อมูลภายในในรูปแบบ digital trees แต่ API ของ แถวลำดับจูดี้จะมีบริการสำหรับผู้ใช้แบบเดียวกับแถวลำดับ
แถวลำดับจูดี้แบ่งเป็น 3 ประเภท โดยมีการmapข้อมูลดังนี้
| Judy Array Type | key | value |
|---|---|---|
| Judy1 | long | bit |
| JudyL | long | long |
| JudySL | string | bit |
แถวลำดับจูดี้ยังถูกเชื่อว่ามีความเสี่ยงต่อการโจมตีให้โครงสร้างข้อมูลใช้งานไม่ได้โดยการให้โครงสร้างข้อมูลทำงานกับข้อมูลที่ทำให้เกิดกรณีที่แย่ที่สุด[1]
แถวลำดับจูดี้ถูกคิดขึ้นโดย Doug Baskins และทำให้สำเร็จโดย ฮิวเลตต์-แพคการ์ด (จูดี้คือชื่อของน้องสาวของ Doug Baskins[2])
การทดสอบถูกทดสอบบน 2GB HP 9000 J5000 workstation running HP-UX 11i at 440 MHz[3]
การเพิ่มข้อมูล
การค้นข้อมูล
การใช้หนวยความจำ
ดูเพิ่ม
[แก้]- 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
อ้างอิง
[แก้]- ↑ "Denial of Service via Algorithmic Complexity Attacks". คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2011-02-28. สืบค้นเมื่อ 2011-02-18.
- ↑ http://judy.sourceforge.net/index.html Main Judy arrays web page
- ↑ http://docs.hp.com/en/B6841-90001/ch02s03.html Hashing versus JudyL