Hash trie: Difference between revisions
Content deleted Content added
SMcCandlish (talk | contribs) link 1st not 2nd occurrence; SIA tag |
SMcCandlish (talk | contribs) parallel construction of list items; MOS:EXPABBR; cite cleanup and correction/completion. Also, there is no reason ever to use WP:LDR in a page this short and simple (it's a style for long and complex articles which reuse sources many times and which are very stable and unlikely to change much; that doesn't apply to a tiny SIA that doesn't yet even provide enough context for anyone but experts). |
||
| Line 2: | Line 2: | ||
* [[Hash tree (persistent data structure)]], a [[trie]] used to map hash values to keys |
* [[Hash tree (persistent data structure)]], a [[trie]] used to map hash values to keys |
||
* A space-efficient implementation of a sparse trie, in which the descendants of each node may be interleaved in memory |
* A space-efficient implementation of a sparse trie, in which the descendants of each node may be interleaved in memory; the name is suggested by a similarity to a closed [[hash table]]<ref>{{cite thesis |last=Liang |first=Frank Mark |title=Word hy-phen-a-tion by com-pu-ter |type=PhD dissertation |date=June 1983 |publisher=[[Stanford University]] |url= http://www.tug.org/docs/liang/liang-thesis.pdf |access-date=March 28, 2010}}</ref>{{Verify source|I believe the source doesn't reference a "hash trie", only "packed tries" and "indexed tries"|date=May 2009}} |
||
* A data structure which "combines features of hash tables and LC-tries (least compression tries) in order to perform efficient lookups and updates"<ref name="Roshan2004">{{cite book |last1=Thomas |first1=Roshan |last2=Mark |first2=Brian |last3=Johnson |first3=Tommy |last4=Croall |first4=James |contribution=High-speed Legitimacy-based DDoS Packet Filtering with Network Processors: A Case Study and Implementation on the Intel IXP1200 |date=2003 |editor1-last=Crowley |editor1-first=Patrick |editor2-last=Franklin |editor2-first=Mark A. |editor3-last=Hadimioglu |editor3-first=Haldun |editor4-last=Onufryk |editor4-first=Peter Z. |title=Network Processor Design: Issues and Practices |volume=2 |series=Series in Computer Architecture and Design |publisher=Morgan Kaufmann Publishers |location=San Francisco |at=Chapter 12, pp. 243–272 |isbn=9780121981570 |contribution-url= http://napl.gmu.edu/pubs/BookContrib/ThomasMarkJC-NPW04.pdf |access-date=May 3, 2009}}</ref> |
|||
* A data structure which "combines features of hash tables and LC-tries (Least Compression tries) in order to perform efficient lookups and updates" <ref name=Roshan2004/> |
|||
== See also == |
== See also == |
||
| Line 11: | Line 11: | ||
==References== |
==References== |
||
{{reflist}} |
|||
<references> |
|||
<ref name=Liang1983>{{Citation |
|||
|last1=Liang |
|||
|first1=Frank Mark |
|||
| date=June 1983 |title=Word hy-phen-a-tion by com-pu-ter |
|||
|format=Ph.D. thesis|publisher= Stanford University |
|||
|url=http://www.tug.org/docs/liang/liang-thesis.pdf |
|||
|accessdate=2010-03-28 |
|||
}}</ref> |
|||
<ref name=Roshan2004>{{citation |
|||
|last1=Thomas |
|||
|first1=Roshan |
|||
|last2=Mark |
|||
|first2=Brian |
|||
|last3=Johnson |
|||
|first3=Tommy |
|||
|last4=Croall |
|||
|first4=James |
|||
|title=High-speed Legitimacy-based DDoS Packet Filtering with Network Processors: A Case Study and Implementation on the Intel IXP1200 |
|||
|url=http://napl.gmu.edu/pubs/BookContrib/ThomasMarkJC-NPW04.pdf |
|||
|accessdate=2009-05-03 |
|||
|year=2004 |
|||
}}</ref> |
|||
</references> |
|||
{{Set index article}} |
{{Set index article}} |
||
Latest revision as of 20:15, 22 June 2024
In computer science, hash trie can refer to:
- Hash tree (persistent data structure), a trie used to map hash values to keys
- A space-efficient implementation of a sparse trie, in which the descendants of each node may be interleaved in memory; the name is suggested by a similarity to a closed hash table[1][verification needed]
- A data structure which "combines features of hash tables and LC-tries (least compression tries) in order to perform efficient lookups and updates"[2]
See also[edit]
References[edit]
- ^ Liang, Frank Mark (June 1983). Word hy-phen-a-tion by com-pu-ter (PDF) (PhD dissertation). Stanford University. Retrieved March 28, 2010.
- ^ Thomas, Roshan; Mark, Brian; Johnson, Tommy; Croall, James (2003). "High-speed Legitimacy-based DDoS Packet Filtering with Network Processors: A Case Study and Implementation on the Intel IXP1200" (PDF). In Crowley, Patrick; Franklin, Mark A.; Hadimioglu, Haldun; Onufryk, Peter Z. (eds.). Network Processor Design: Issues and Practices. Series in Computer Architecture and Design. Vol. 2. San Francisco: Morgan Kaufmann Publishers. Chapter 12, pp. 243–272. ISBN 9780121981570. Retrieved May 3, 2009.
This article includes a list of related items that share the same name (or similar names).
If an internal link incorrectly led you here, you may wish to change the link to point directly to the intended article.
If an internal link incorrectly led you here, you may wish to change the link to point directly to the intended article.