Hash trie: Difference between revisions
Appearance
Content deleted Content added
m Date maintenance tags and general fixes |
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). |
||
(18 intermediate revisions by 18 users not shown) | |||
Line 1: | Line 1: | ||
⚫ | |||
{{Orphan|date=September 2006}} |
|||
⚫ | |||
* [[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]]<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> |
|||
== See also == |
|||
* [[Hash array mapped trie]] |
|||
* [[Hashed array tree]] |
|||
* [[Merkle tree]] |
|||
⚫ | * A space-efficient implementation of a sparse |
||
* An ordinary [[trie]] used to store [[hash function|hash values]], for example, in an implementation of a [[hash tree]]. |
|||
* A data strcuture which "combines features of hash tables and LC-tries in order to perform efficient lookups and updates" {{ref|Roshan2004}} |
|||
==References== |
==References== |
||
{{reflist}} |
|||
# {{note|Liang}} Frank M. Liang (1983), ''Word hy-phen-a-tion by com-pu-ter'', Ph.D. thesis, Stanford University. |
|||
{{Set index article}} |
|||
# {{note|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 |
|||
}} |
|||
[[Category:Trees ( |
[[Category:Trees (data structures)]] |
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.