Vocabulary structure

Notes:

Vocabulary structure

Dictionary / Hash table
Search tree

Notes:

Suggestions?

Hash table

By Jorge Stolfi - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=6471238

Notes:

What is the complexity of lookup / insert? Does it get slower with more entries?

Hash table

+ Fast lookup: Ο(1): Calculate hash, follow pointer
+ Fast insert: Ο(1)
- Hash collisions: Worst case complexity: Ο(n)

Notes:

Hash table collision

By Jorge Stolfi - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=6472274

Extra lookup necessary when hashes collide. Worst case Ο(n)

Notes:

Search Tree

Max two children per node (binary tree)

<script class="tree" type="application/json"> { "name": "", "children": [ { "name": "A-M", "children": [ { "name": "Austr", "children": [ { "name": "Australia" }, { "name": "Austria" } ] }, { "name": "China" } ] }, { "name": "N-Z", "children": [ { "name": "Norway" }, { "name": "Russia" } ] } ] } </script>

Notes: What is the lookup / insert complexity? Does it get slower with more entries? How much? Ο(log n)

Search Tree

+ Fast lookup: Ο(log n): Average height of the tree
+ Fast insertion: Ο(log n)
+ Supports prefix search

Different types of trees used depending on the use case
E.g., Binary Tree (in-memory), B-Tree (on disk)

Notes: