[go: nahoru, domu]

Jump to content

Hash trie: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
Tr00st (talk | contribs)
Added check tag, having had a quick peer at the source, acquirable from google.
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).
 
(19 intermediate revisions by 19 users not shown)
Line 1: Line 1:
In [[computer science]], '''hash trie''' can refer to:
{{Orphan|date=September 2006}}

In [[computer science]], '''hash trie''' refers to two kinds of [[data structure]]:
* [[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 [[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|Liang}} {{check|I believe the source doesn't reference a "hash trie", only "packed tries" and "indexed tries"}}
* 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.

[[Category:Trees (structure)]]
{{Set index article}}
# {{note|Roshan2004}} {{citation

|last1=Thomas
[[Category:Trees (data structures)]]
|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
}}

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]
  1. ^ Liang, Frank Mark (June 1983). Word hy-phen-a-tion by com-pu-ter (PDF) (PhD dissertation). Stanford University. Retrieved March 28, 2010.
  2. ^ 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.